search_root.cpp

超强国际象棋引擎

// search_full.cpp

// includes

#include "board.h"
#include "evaluate.h"
#include "move_list.h"
#include "move.h"
#include "check.h"
#include "make_move.h"
#include "config.h"
#include "pawn.h"
#include "probe.h"
#include "pv.h"
#include "draw.h"
#include "search.h"
#include "see.h"
#include "sort.h"
#include "transposition.h"
#include "values.h"

#define ABS(x) ((x)<0?-(x):(x))
#define MIN(X, Y)  ((X) < (Y) ? (X) : (Y))
#define R_adpt(max_pieces, depth, Reduction) (Reduction + ((depth) > (9 + ((max_pieces<3) ? 2 : 0))))

// constants and variables

// macros

#define NODE_OPP(type)     (-(type))
#define DEPTH_MATCH(d1,d2) ((d1)>=(d2))

static int R = 3;

static int check_depth = 0;

// prototypes

static int full_root(list_t *list, board_t *board, int alpha, int beta, int depth, int height, int search_type,
    int thread_id);

static int full_search(board_t *board, int alpha, int beta, int depth, int height, mv_t pv [], int node_type,
    bool extended, int thread_id);
static int full_no_null(board_t *board, int alpha, int beta, int depth, int height, mv_t pv [], int node_type,
    int trans_move, int *best_move, bool extended, int thread_id);

static int full_quiescence(board_t *board, int alpha, int beta, int depth, int height, mv_t pv [], int thread_id);

static int full_new_depth(int depth, int move, board_t *board, bool single_reply, bool in_pv, int height, bool extended,
    bool *cap_extended, int thread_id);

static void pv_fill(const mv_t pv [], board_t *board);

static bool move_is_dangerous(int move, const board_t *board);
static bool capture_is_dangerous(int move, const board_t *board);

static bool simple_stalemate(const board_t *board);

static bool is_passed(const board_t *board, int to);

// functions

// search_full_init()

void search_full_init(list_t *list, board_t *board, int thread_id)
    {

    int trans_move, trans_depth, trans_flags, trans_value;
    entry_t *found_entry;

    // standard sort

    list_note(list);
    list_sort(list);

    // basic sort

    trans_move = 0;

    trans_retrieve(Trans, &found_entry, board->key, &trans_move, &trans_depth, &trans_flags, &trans_value);
    note_moves(list, board, 0, trans_move, thread_id);
    list_sort(list);
    }

// search_full_root()

int search_full_root(list_t *list, board_t *board, int depth, int search_type, int thread_id)
    {

    int value, a, b;

    a = search_best[thread_id][search_current[thread_id]->multipv].value - 30;
    b = search_best[thread_id][search_current[thread_id]->multipv].value + 30;

    if(search_input->multipv > 0)
        {
        a = -30000;
        b = +30000;
        }

    a = -30000;
    b = +30000;

    value = full_root(list, board, a, b, depth, 0, search_type, thread_id);

    return value;
    }

// full_root()

static int full_root(list_t *list, board_t *board, int alpha, int beta, int depth, int height, int search_type,
    int thread_id)
    {

    int old_alpha;
    int value, best_value[10];
    int i, move, j;
    int new_depth;
    undo_t undo[1];
    mv_t new_pv[256];
    bool found;
    bool cap_extended;

    // init

    search_current[thread_id]->node_nb++;
    search_info[thread_id]->check_nb--;

    if(search_current[thread_id]->multipv == 0)
        for ( i = 0; i < LIST_SIZE(list); i++ )
            list->value[i] = -32767;

    old_alpha = alpha;
    best_value[search_current[thread_id]->multipv] = -32767;

    // move loop

    for ( i = 0; i < LIST_SIZE(list); i++ )
        {

        move = LIST_MOVE(list, i);

        if(search_current[thread_id]->multipv > 0)
            {
            found = false;

            for ( j = 0; j < search_current[thread_id]->multipv; j++ )
                {
                if(search_best[thread_id][j].pv[0] == move)
                    {
                    found = true;
                    break;
                    }
                }

            if(found == true)
                continue;
            }

        search_root[thread_id]->depth = depth;
        search_root[thread_id]->move = move;
        search_root[thread_id]->move_pos = i;
        search_root[thread_id]->move_nb = LIST_SIZE(list);

        search_update_root(thread_id);

        new_depth =
            full_new_depth(depth, move, board, board_is_check(board) && LIST_SIZE(list) == 1, true, height, false,
                &cap_extended, thread_id);

        move_do(board, move, undo);

        if(search_type == 1 || best_value[search_current[thread_id]->multipv] == -32767)
            { // first move
            value = -full_search(board, -beta, -alpha, new_depth, height + 1, new_pv, 0, cap_extended, thread_id);

            if(value <= alpha)
                { // research
                old_alpha = alpha = -30000;
                search_root[thread_id]->change = true;
                search_root[thread_id]->easy = false;
                search_root[thread_id]->flag = false;
                search_update_root(thread_id);
                value = -full_search(board, -beta, 30000, new_depth, height + 1, new_pv, 0, cap_extended, thread_id);
                }
            else if(value >= beta)
                { // research
                search_root[thread_id]->change = true;
                search_root[thread_id]->easy = false;
                search_root[thread_id]->flag = false;
                search_update_root(thread_id);
                value = -full_search(board, -30000, -alpha, new_depth, height + 1, new_pv, 0, cap_extended, thread_id);
                }
            }
        else
            { // other moves
            value = -full_search(board, -alpha - 1, -alpha, new_depth, height + 1, new_pv, 1, cap_extended, thread_id);

            if(value > alpha)
                { // && value < beta
                search_root[thread_id]->change = true;
                search_root[thread_id]->easy = false;
                search_root[thread_id]->flag = false;
                search_update_root(thread_id);
                value = -full_search(board, -30000, -alpha, new_depth, height + 1, new_pv, 0, cap_extended, thread_id);
                }
            }

        move_undo(board, move, undo);

        if(value <= alpha)
            { // upper bound
            list->value[i] = old_alpha;
            }
        else if(value >= beta)
            { // lower bound
            list->value[i] = beta;
            }
        else
            { // alpha < value < beta => exact value
            list->value[i] = value;
            }

        if(value > best_value[search_current[thread_id]->multipv]
            && (best_value[search_current[thread_id]->multipv] == -32767 || value > alpha))
            {

            search_best[thread_id][search_current[thread_id]->multipv].move = move;
            search_best[thread_id][search_current[thread_id]->multipv].value = value;

            if(value <= alpha)
                { // upper bound
                search_best[thread_id][search_current[thread_id]->multipv].flags = 1;
                }
            else if(value >= beta)
                { // lower bound
                search_best[thread_id][search_current[thread_id]->multipv].flags = 2;
                }
            else
                { // alpha < value < beta => exact value
                search_best[thread_id][search_current[thread_id]->multipv].flags = 3;
                }
            search_best[thread_id][search_current[thread_id]->multipv].depth = depth;
            pv_cat(search_best[thread_id][search_current[thread_id]->multipv].pv, new_pv, move);

            search_update_best(thread_id);
            }

        if(value > best_value[search_current[thread_id]->multipv])
            {
            best_value[search_current[thread_id]->multipv] = value;

            if(value > alpha)
                {
                if(search_type == 0)
                    alpha = value;

                if(value >= beta)
                    break;
                }
            }
        }

    list_sort(list);

    if(best_value[search_current[thread_id]->multipv] > old_alpha
        && best_value[search_current[thread_id]->multipv] < beta)
        {
        pv_fill(search_best[thread_id][search_current[thread_id]->multipv].pv, board);
        }

    return best_value[search_current[thread_id]->multipv];
    }

// full_search()

static int full_search(board_t *board, int alpha, int beta, int depth, int height, mv_t pv [], int node_type,
    bool extended, int thread_id)
    {

    bool in_check;
    bool single_reply;
    bool good_cap;
    int trans_move, trans_depth, trans_flags, trans_value;
    int old_alpha;
    int value, best_value;
    int move, best_move;
    int new_depth;
    int played_nb;
    int i;
    int opt_value;
    bool reduced, cap_extended;
    attack_t attack[1];
    sort_t sort[1];
    undo_t undo[1];
    mv_t new_pv[256];
    mv_t played[256];
    int futility_margin;
    int probe_score, probe_depth;
    entry_t *found_entry;

    // horizon?

    if(depth <= 0)
        {
        if(node_type == 0)
            check_depth = 1 - 1 - 1;
        else
            check_depth = 1 - 1;
        return full_quiescence(board, alpha, beta, 0, height, pv, thread_id);
        }

    // init

    search_current[thread_id]->node_nb++;
    search_info[thread_id]->check_nb--;
    PV_CLEAR(pv);

    if(height > search_current[thread_id]->max_depth)
        search_current[thread_id]->max_depth = height;

    if(search_info[thread_id]->check_nb <= 0)
        {
        search_info[thread_id]->check_nb += search_info[thread_id]->check_inc;
        search_check(thread_id);
        }

    // draw?

    if(board_is_repetition(board))
        return 0;

    if(egbb_is_loaded && board->piece_nb <= 5)
        {
        probe_depth = (2 * search_current[thread_id]->act_iteration) / 3;

        if((board->piece_nb <= 4 || height <= probe_depth)
            && (height >= probe_depth || board->cap_sq != 0 || PIECE_IS_PAWN(board->moving_piece)))
            {
            if(probe_bitbases(board, probe_score))
                {
                probe_score = value_from_trans(probe_score, height);

                return probe_score;
                }
            }
        }

    if(recog_draw(board, thread_id))
        return 0;

    // mate-distance pruning

    // lower bound

    value = VALUE_MATE(height + 2); // does not work if the current position is mate

    if(value > alpha && board_is_mate(board))
        value = VALUE_MATE(height);

    if(value > alpha)
        {
        alpha = value;

        if(value >= beta)
            return value;
        }

    // upper bound

    value = -VALUE_MATE(height + 1);

    if(value < beta)
        {
        beta = value;

        if(value <= alpha)
            return value;
        }

    // transposition table

    trans_move = 0;

    if(depth >= 1)
        {
        if(trans_retrieve(Trans, &found_entry, board->key, &trans_move, &trans_depth, &trans_flags, &trans_value))
            {
            if(node_type != 0)
                {
                if(trans_depth < depth)
                    {
                    if(trans_value < -(30000 - 256) && TRANS_IS_UPPER(trans_flags))
                        {
                        trans_depth = depth;
                        trans_flags = (1 << 0);
                        }
                    else if(trans_value > +(30000 - 256) && TRANS_IS_LOWER(trans_flags))
                        {
                        trans_depth = depth;