From 54afeb6dd89fffae92274cb6fe2e9a86fd57c6e3 Mon Sep 17 00:00:00 2001 From: Aargh Rai Date: Sat, 15 Aug 2026 15:15:21 +0530 Subject: phase B --- src/engine/search.c | 206 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 206 insertions(+) create mode 100644 src/engine/search.c (limited to 'src/engine/search.c') diff --git a/src/engine/search.c b/src/engine/search.c new file mode 100644 index 0000000..41e004c --- /dev/null +++ b/src/engine/search.c @@ -0,0 +1,206 @@ +#include "engine/search.h" + +#include + +#include "engine/evaluate.h" +#include "bitboard.h" + +// stop the search early? (time limit reached, node budget exhausted by the UCI +// thread, or an external stop signal). +static bool search_should_stop(search_ctx_t *ctx) { + if (ctx == NULL) return false; + if (ctx->stop != NULL && atomic_load(ctx->stop)) return true; + if (ctx->go_args != NULL && ctx->go_args->nodes != 0 && + ctx->nodes != NULL && *ctx->nodes >= (u64)ctx->go_args->nodes) { + return true; + } + return false; +} + +search_result_t search( + position_t position, + int depth, + int alpha, + int beta, + search_ctx_t *ctx +) { + if (ctx != NULL && ctx->nodes != NULL) (*ctx->nodes)++; + if (search_should_stop(ctx)) { + // TODO: this might be a problem, if all the paths are losing, + // and it reaches this condition. then it will suddenly think + // WOW, this move will equialise the position!! + // Which, obviously it didn't, maybe returning a score of relative negative + // infinite will help + return (search_result_t) { .score = 0, .best_move = (move_t){0} }; + } + + if (depth <= 0) { + return (search_result_t) { .score = evaluate(position) }; + } + + moves_t moves; + moves_init(&moves); + get_legal_moves(&moves, position); + + // terminal node: no legal moves -> checkmate or stalemate. + if (moves.length == 0) { + moves_deinit(moves); + u8 king = position.turn == WHITE_TURN ? WHITE_KING : BLACK_KING; + int king_sq = __builtin_ctzll(position.bitboards[king]); + u8 opponent = position.turn == WHITE_TURN ? BLACK_TURN : WHITE_TURN; + if (square_attacked(position, king_sq, opponent)) { + return (search_result_t) { + .score = -SEARCH_MATE, + .best_move = (move_t){0}, + }; + } + return (search_result_t) { .score = 0, .best_move = (move_t){0} }; + } + + // transposition-table probe. + u64 key = 0; + tentry_t *tt_entry = NULL; + bool have_tt = ctx != NULL && ctx->ttable != NULL; + if (have_tt) { + key = zobrist_hash(position); + tt_entry = ttable_find(*ctx->ttable, key); + } + + search_result_t result = { .score = -SEARCH_INF, .best_move = moves.moves[0] }; + int orig_alpha = alpha; + + if (tt_entry != NULL && tt_entry->depth >= (u16)depth) { + i16 tt_score = tt_entry->score; + if (tt_entry->flag == TT_EXACT) { + result.score = tt_score; + result.best_move = tt_entry->best_move; + moves_deinit(moves); + return result; + } + if (tt_entry->flag == TT_LOWERBOUND && tt_score > alpha) alpha = tt_score; + else if (tt_entry->flag == TT_UPPERBOUND && tt_score < beta) beta = tt_score; + if (alpha >= beta) { + result.score = tt_score; + result.best_move = tt_entry->best_move; + moves_deinit(moves); + return result; + } + } + + for (u32 i = 0; i < moves.length; i++) { + position_t child = position; + position_make_move(&child, moves.moves[i]); + + search_result_t child_res = search(child, depth - 1, -beta, -alpha, ctx); + i32 score = -child_res.score; + + if (score > result.score) { + result.score = score; + result.best_move = moves.moves[i]; + } + if (score > alpha) alpha = score; + if (alpha >= beta) break; + } + + // transposition-table store. + if (have_tt) { + u8 flag = (result.score >= beta) ? TT_LOWERBOUND + : (result.score <= orig_alpha) ? TT_UPPERBOUND + : TT_EXACT; + ttable_insert(*ctx->ttable, + .key = key, + .move = result.best_move, + .score = (i16)result.score, + .eval = 0, + .depth = (u16)depth, + .flag = flag, + .generation = 0 + ); + } + + moves_deinit(moves); + return result; +} + +#ifdef TEST_MOD +#include +#include + +#include "fen.h" + +bool test_search_finds_mate_in_one() { + // Ka6, Qb6 vs Ka8 -> Qa7# or Qb7# + struct fen_load r = load_fen("k7/8/KQ6/8/8/8/8/8 w - - 0 1"); + if (r.failed) return false; + + ttable_t tt; + ttable_init(&tt, 2); + + _Atomic bool stop = false; + go_args_t go = {0}; + u64 nodes = 0; + search_ctx_t ctx = { .ttable = &tt, .go_args = &go, .stop = &stop, .nodes = &nodes }; + + search_result_t res = search(r.position, 2, -SEARCH_INF, SEARCH_INF, &ctx); + ttable_deinit(tt); + + // the queen delivers mate, so the value at the root must be a (positive) mate. + return res.score == SEARCH_MATE; +} + +bool test_search_handles_no_moves() { + // "7k/5Q2/6K1/8/8/8/8/8 b - - 0 1" — black to move, stalemated, not in check. + struct fen_load r = load_fen("7k/5Q2/6K1/8/8/8/8/8 b - - 0 1"); + if (r.failed) return false; + + ttable_t tt; + ttable_init(&tt, 2); + + _Atomic bool stop = false; + go_args_t go = {0}; + u64 nodes = 0; + search_ctx_t ctx = { .ttable = &tt, .go_args = &go, .stop = &stop, .nodes = &nodes }; + + search_result_t res = search(r.position, 2, -SEARCH_INF, SEARCH_INF, &ctx); + ttable_deinit(tt); + + // no legal moves + not in check -> stalemate, value 0 (not a mate). + return res.score == 0; +} + +bool test_search_respects_depth() { + position_t pos = position_starting(); + ttable_t tt; + ttable_init(&tt, 2); + + _Atomic bool stop = false; + go_args_t go = {0}; + u64 nodes = 0; + search_ctx_t ctx = { .ttable = &tt, .go_args = &go, .stop = &stop, .nodes = &nodes }; + + search_result_t res = search(pos, 3, -SEARCH_INF, SEARCH_INF, &ctx); + ttable_deinit(tt); + + // must return a legal on-board move and a finite (non-sentinel) score. + bool on_board = res.best_move.from < 64 && res.best_move.to < 64; + return on_board && res.score > -SEARCH_INF && res.score < SEARCH_INF; +} + +bool test_search_stop_signal_halts() { + position_t pos = position_starting(); + ttable_t tt; + ttable_init(&tt, 2); + + _Atomic bool stop = false; + go_args_t go = {0}; + go.nodes = 1; // node budget of 1 -> should stop almost immediately + u64 nodes = 0; + search_ctx_t ctx = { .ttable = &tt, .go_args = &go, .stop = &stop, .nodes = &nodes }; + + search_result_t res = search(pos, 6, -SEARCH_INF, SEARCH_INF, &ctx); + ttable_deinit(tt); + + // with a 1-node budget the search must bail early, not run to depth 6. + return nodes <= 2 && res.score == 0; +} +#endif -- cgit v1.2.3