search_root.cpp

超强国际象棋引擎

    if(best_value == -32767)
        { // no legal move => stalemate
        best_value = 0;
        }

    cut:

    return best_value;
    }

// full_quiescence()

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

    bool in_check;
    int old_alpha;
    int value, best_value;
    int best_move;
    int move;
    int opt_value;
    attack_t attack[1];
    sort_t sort[1];
    undo_t undo[1];
    mv_t new_pv[256];

    // 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(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;
        }

    // more init

    attack_set(attack, board);
    in_check = ATTACK_IN_CHECK(attack);

    if(in_check)
        {
        depth++; // in-check extension
        }

    // height limit

    if(height >= 256 - 1)
        return eval(board, alpha, beta, thread_id);

    // more init

    old_alpha = alpha;
    best_value = -32767;
    best_move = 0;

    opt_value = +30000;

    if(!in_check)
        {

        // lone-king stalemate?

        if(simple_stalemate(board))
            return 0;

        // stand pat

        value = eval(board, alpha, beta, thread_id);

        best_value = value;

        if(value > alpha)
            {
            alpha = value;

            if(value >= beta)
                goto cut;
            }

        opt_value = value + 50;
        }

    // move loop

    sort_init_qs(sort, board, attack, depth >= check_depth);

    while((move = sort_next_qs(sort)) != 0)
        {

        // delta pruning

        if(beta == old_alpha + 1)
            {
            if(!in_check && !move_is_check(move, board) && !capture_is_dangerous(move, board))
                {

                // optimistic evaluation

                value = opt_value;

                int to = MOVE_TO(move);
                int capture = board->square[to];

                if(capture != 0)
                    {
                    value += VALUE_PIECE(capture);
                    }
                else if(MOVE_IS_EN_PASSANT(move))
                    {
                    value += 100;
                    }

                if(MOVE_IS_PROMOTE(move))
                    value += 1000 - 100;

                // pruning

                if(value <= alpha)
                    {
                    if(value > best_value)
                        {
                        best_value = value;
                        PV_CLEAR(pv);
                        }

                    continue;
                    }
                }
            }

        move_do(board, move, undo);
        value = -full_quiescence(board, -beta, -alpha, depth - 1, height + 1, new_pv, thread_id);
        move_undo(board, move, undo);

        if(value > best_value)
            {
            best_value = value;
            pv_cat(pv, new_pv, move);

            if(value > alpha)
                {
                alpha = value;
                best_move = move;

                if(value >= beta)
                    goto cut;
                }
            }
        }

    // ALL node

    if(best_value == -32767)
        { // no legal move
        return VALUE_MATE(height);
        }

    cut:

    return best_value;
    }

// full_new_depth()

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)
    {

    int new_depth;

    new_depth = depth - 1;
    *cap_extended = false;

    if(in_pv && board->square[MOVE_TO(move)] != 0 && !PIECE_IS_PAWN(board->square[MOVE_TO(move)]))
        {
        if((board->piece_size[0] + board->piece_size[1]) == 3)
            {
            return new_depth + 1;
            }

        else if((board->piece_size[0] == 3 && board->piece_size[1] == 2)
            || (board->piece_size[0] == 2 && board->piece_size[1] == 3))
            return new_depth + 1;
        }

    if((single_reply) || move_is_check(move, board) && (in_pv || see_move(move, board) >= -100))
        {
        return new_depth + 1;
        }

    if(in_pv && PIECE_IS_PAWN(MOVE_PIECE(move, board)))
        {
        if(is_passed(board, MOVE_TO(move)))
            return new_depth + 1;
        }

    if(in_pv && board->square[MOVE_TO(move)] != 0 && !extended && see_move(move, board) >= -100)
        {
        *cap_extended = true;
        return new_depth + 1;
        }

    return new_depth;
    }

// pv_fill()

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

    int move;
    int trans_move, trans_depth;
    undo_t undo[1];

    move = *pv;

    if(move != 0 && move != 11)
        {

        move_do(board, move, undo);
        pv_fill(pv + 1, board);
        move_undo(board, move, undo);

        trans_move = move;
        trans_depth = -127;

        trans_store(Trans, board->key, trans_move, trans_depth, 0, -30000);
        }
    }

// move_is_dangerous()

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

    int piece;

    piece = MOVE_PIECE(move, board);

    if(PIECE_IS_PAWN(piece) && is_passed(board, MOVE_TO(move)))
        {
        return true;
        }

    return false;
    }

// capture_is_dangerous()

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

    int piece, capture;

    piece = MOVE_PIECE(move, board);

    if(PIECE_IS_PAWN(piece) && PAWN_RANK(MOVE_TO(move), board->turn) >= (0xA))
        {
        return true;
        }

    capture = move_capture(move, board);

    if(PIECE_IS_QUEEN(capture))
        return true;

    if(PIECE_IS_PAWN(capture) && PAWN_RANK(MOVE_TO(move), board->turn) <= (0x5))
        {
        return true;
        }

    return false;
    }

// simple_stalemate()

static bool simple_stalemate(const board_t *board)
    {

    int me, opp;
    int king;
    int opp_flag;
    int from, to;
    int capture;
    const inc_t *inc_ptr;
    int inc;

    // lone king?

    me = board->turn;

    if(board->piece_size[me] != 1 || board->pawn_size[me] != 0)
        return false; // no

    // king in a corner?

    king = KING_POS(board, me);

    if(king != (0x44) && king != (0x4B) && king != (0xB4) && king != (0xBB))
        return false; // no

    // init

    opp = COLOUR_OPP(me);
    opp_flag = COLOUR_FLAG(opp);

    // king can move?

    from = king;

    for ( inc_ptr = king_inc; (inc = *inc_ptr) != 0; inc_ptr++ )
        {
        to = from + inc;
        capture = board->square[to];

        if(capture == 0 || FLAG_IS(capture, opp_flag))
            {
            if(!is_attacked(board, to, opp))
                return false; // legal king move
            }
        }

    // no legal move

    return true;
    }

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

    int t2;
    int me, opp;
    int file, rank;

    me = board->turn;
    opp = COLOUR_OPP(me);
    file = SQUARE_FILE(to);
    rank = PAWN_RANK(to, me);

    t2 = board->pawn_file[me][file] | bit_rev[board->pawn_file[opp][file]];

    // passed pawns
    if((t2 &bit_gt[rank]) == 0)
        {
        if(((bit_rev[board->pawn_file[opp][file - 1]] | bit_rev[board->pawn_file[opp][file + 1]]) & bit_gt[rank]) == 0)
            {
            return true;
            }
        }

    return false;
    }

// end of search_full.cpp