search.cpp

template<bool PV>
int search_t::searchAB(int alpha, int beta, int ply, int depth) {
    nodes++;
    pv_table_len[ply] = ply;

    if (depth < 1) return searchQS(alpha, beta, ply + 1);
    bool pv = PV;
    int score, best_score = -INF;
    const int old_alpha = alpha;
    move_t best_move{};

    // Probe transposition table
    tt::entry_t h = {0};
    if(tt->probe(board.record[board.now].hash, h)) {
        score = fromHash(h.value, ply);
        hashhit++;

        if((h.depth >= depth || score <= ply - MATE(0) || score > MATE(0) - ply - 1)) {
            hashcut++;
            if(h.bound == tt::LOWER && score >= beta) return score;
            if(h.bound == tt::UPPER && score <= alpha) return score;
            if(h.bound == tt::EXACT) return score;
            hashcut--;
        }
    }

    // Info
    bool in_check = board.is_incheck();

    movegen_t gen(board);
    int n_moves = gen.gen_normal(), n_legal = 0;
    for (int move_idx = 0; move_idx < n_moves; move_idx++) {
        board.move(&gen.buf[move_idx]);
        if (board.is_illegal()) {
            board.unmove();
            continue;
        } else {
            n_legal++; // Legal move

            if (pv) {
                score = -searchAB<true>(-beta, -alpha, ply + 1, depth - 1);
            } else {
                score = -searchAB<false>(-alpha-1, -alpha, ply + 1, depth - 1);
                if (score > alpha) {
                    pv = true;
                    // We'd rather not need to search again, but :/
                    score = -searchAB<true>(-beta, -alpha, ply + 1, depth - 1);
                }
            }

            board.unmove();

            if (score > best_score) {
                best_score = score;
                best_move = gen.buf[move_idx];

                if (score >= beta) {
                    tt->save(tt::LOWER, board.record[board.now].hash, depth, toHash(best_score, ply), best_move);

                    return beta; // Fail hard
                }

                if (score > alpha) {
                    alpha = score;
                    pv = false;

                    if(PV) {
                        pv_table[ply][ply] = gen.buf[move_idx];
                        for (int i = ply + 1; i < pv_table_len[ply + 1]; i++) {
                            pv_table[ply][i] = pv_table[ply + 1][i];
                        }
                        pv_table_len[ply] = pv_table_len[ply + 1];
                    }
                }
            }
        }
    }

    if (board.record[board.now].halfmove_clock >= 100) return 0;

    if (n_legal == 0) {
        if (in_check) {
            return -MATE(ply);
        } else {
            return 0;
        }
    }

    if (best_move.move_bytes) {
        if(alpha > old_alpha) {
            tt->save(tt::EXACT, board.record[board.now].hash, depth, toHash(best_score, ply), best_move);
        } else {
            tt->save(tt::UPPER, board.record[board.now].hash, depth, toHash(best_score, ply), best_move);
        }
    }

    return alpha;
}