search_root.cpp

超强国际象棋引擎

                        trans_flags = (1 << 1);
                        }
                    }

                if(trans_depth >= depth)
                    {

                    trans_value = value_from_trans(trans_value, height);

                    if((TRANS_IS_EXACT(trans_flags)) || (TRANS_IS_LOWER(trans_flags) && trans_value >= beta)
                        || (TRANS_IS_UPPER(trans_flags) && trans_value <= alpha))
                        {
                        return trans_value;
                        }
                    }
                }
            }
        }

    // height limit

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

    // more init

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

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

    // null-move pruning

    if(depth >= 2 && node_type != 0)
        {
        if(!in_check && !value_is_mate(beta) && (board->piece_size[board->turn] >= 2)
            && (!false || depth <= R + 1 || eval(board, alpha, beta, thread_id) >= beta))
            {
            if((depth > 7) && (board->piece_size[board->turn] >= 3))
                R = 4;
            else
                R = 3;

            new_depth = depth - R - 1;

            move_do_null(board, undo);
            value =
                -full_search(board, -beta, -beta + 1, new_depth, height + 1, new_pv, NODE_OPP(node_type), false,
                    thread_id);
            move_undo_null(board, undo);

            // verification search

            if(depth > 5)
                {
                if(value >= beta && (!false || (board->piece_size[board->turn] <= 3)))
                    {

                    new_depth = depth - 5;

                    value =
                        full_no_null(board, alpha, beta, new_depth, height, new_pv, 1, trans_move, &move, false,
                            thread_id);

                    if(value >= beta)
                        {
                        played[played_nb++] = move;
                        best_move = move;
                        best_value = value;
                        pv_copy(pv, new_pv);
                        goto cut;
                        }
                    }
                }

            // pruning

            if(value >= beta)
                {
                if(value > +(30000 - 256))
                    value = +(30000 - 256); // do not return unproven mates

                best_move = 0;
                best_value = value;
                goto cut;
                }
            }
        }

    // razoring

    else if(node_type != 0 && depth <= 3 && eval(board, alpha, beta, thread_id) < beta - 300)
        {
        value = full_quiescence(board, alpha, beta, 0, height, pv, thread_id);

        if(value < beta)
            return value;
        }

    // internal iterative deepening

    if(depth >= 3 && node_type == 0 && trans_move == 0)
        {
        new_depth = MIN(depth - 2, depth / 2);

        value = full_search(board, alpha, beta, new_depth, height, new_pv, node_type, false, thread_id);

        if(value <= alpha)
            value = full_search(board, -30000, beta, new_depth, height, new_pv, node_type, false, thread_id);

        trans_move = new_pv[0];
        }

    // move generation

    sort_init(sort, board, attack, depth, height, trans_move, thread_id);

    single_reply = false;

    if(in_check && LIST_SIZE(sort->list) == 1)
        single_reply = true;

    // move loop

    opt_value = +30000;
    good_cap = true;

    while((move = sort_next(sort, thread_id)) != 0)
        {

        // extensions

        new_depth =
            full_new_depth(depth, move, board, single_reply, node_type == 0, height, extended, &cap_extended,
                thread_id);

        // history pruning

        value = sort->value; // history score

        if(!in_check && depth <= 4 && node_type != 0
        && new_depth < depth && value < 2 * 11468 / (depth + depth % 2)
        && played_nb >= 1+/*sort->capture_nb*/+depth && !move_is_check(move,board) && !move_is_dangerous(move,board))
            {
            continue;
            }

        // futility pruning

        if(node_type != 0 && depth <= 5)
            {
            if(!in_check && new_depth < depth && !move_is_tactical(move, board) && !move_is_check(move, board)
                && !move_is_dangerous(move, board))
                {

                // optimistic evaluation as modelled by Chris Formula

                if(opt_value == +30000)
                    {
                    if(depth >= 3)
                        {
                        futility_margin = 300 + (depth % 2) * 100;
                        }
                    else if(depth == 2)
                        {
                        futility_margin = 200;
                        }
                    else
                        {
                        futility_margin = 100;
                        }
                    opt_value = eval(board, alpha, beta, thread_id) + 100;
                    }

                value = opt_value;

                // pruning

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

                    continue;
                    }
                }
            }

        reduced = false;

        if(!in_check && new_depth < depth && played_nb >= 3 && depth >= 3 && !move_is_dangerous(move, board))
            {
            if(good_cap && !move_is_tactical(move, board))
                {
                good_cap = false;
                }

            if(!good_cap)
                {
                if(node_type != 0)
                    {
                    new_depth--;
                    reduced = true;
                    }
                else
                    {
                    if(played_nb >= 3 + 3)
                        {
                        new_depth--;
                        reduced = true;
                        }
                    }
                }
            }

        // recursive search

        move_do(board, move, undo);

        if(node_type != 0 || best_value == -32767)
            { // first move
            value =
                -full_search(board, -beta, -alpha, new_depth, height + 1, new_pv, NODE_OPP(node_type), 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
                value = -full_search(board, -beta, -alpha, new_depth, height + 1, new_pv, 0, cap_extended, thread_id);
                }
            }

        // history-pruning re-search

        if(reduced && value >= beta)
            {
            new_depth++;

            value =
                -full_search(board, -beta, -alpha, new_depth, height + 1, new_pv, NODE_OPP(node_type), cap_extended,
                    thread_id);
            }

        move_undo(board, move, undo);

        played[played_nb++] = move;

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

        if(node_type == 1)
            node_type = -1;
        }

    // ALL node

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

    cut:

    // move ordering

    if(best_move != 0)
        {
        good_move(best_move, board, depth, height, thread_id);

        if(best_value >= beta && !move_is_tactical(best_move, board))
            {
            for ( i = 0; i < played_nb - 1; i++ )
                {
                move = played[i];
                history_bad(move, board, thread_id);
                }

            history_good(best_move, board, thread_id);
            }
        }

    // transposition table

    if(depth >= 1)
        {

        trans_move = best_move;
        trans_depth = depth;
        trans_flags = 0;

        if(best_value > old_alpha)
            trans_flags |= (1 << 1);

        if(best_value < beta)
            trans_flags |= (1 << 0);
        trans_value = value_to_trans(best_value, height);

        trans_store(Trans, board->key, trans_move, trans_depth, trans_flags, trans_value);
        }

    return best_value;
    }

// full_no_null()

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

    int value, best_value;
    int move;
    int new_depth;
    attack_t attack[1];
    sort_t sort[1];
    undo_t undo[1];
    mv_t new_pv[256];
    bool cap_extended;

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

    attack_set(attack, board);

    *best_move = 0;
    best_value = -32767;

    // move loop

    sort_init(sort, board, attack, depth, height, trans_move, thread_id);

    while((move = sort_next(sort, thread_id)) != 0)
        {

        new_depth = full_new_depth(depth, move, board, false, false, height, extended, &cap_extended, thread_id);

        move_do(board, move, undo);
        value =
            -full_search(board, -beta, -alpha, new_depth, height + 1, new_pv, NODE_OPP(node_type), cap_extended,
                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