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.c | 2 + src/engine/evaluate.c | 83 ++++++++++++++++++++ src/engine/search.c | 206 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/engine/ttable.c | 10 ++- 4 files changed, 298 insertions(+), 3 deletions(-) create mode 100644 src/engine/evaluate.c create mode 100644 src/engine/search.c (limited to 'src') diff --git a/src/engine.c b/src/engine.c index 9f0a2d2..8ddffef 100644 --- a/src/engine.c +++ b/src/engine.c @@ -2,3 +2,5 @@ #include "engine/thread.c" #include "engine/moves.c" #include "engine/ttable.c" +#include "engine/evaluate.c" +#include "engine/search.c" diff --git a/src/engine/evaluate.c b/src/engine/evaluate.c new file mode 100644 index 0000000..1722da2 --- /dev/null +++ b/src/engine/evaluate.c @@ -0,0 +1,83 @@ +#include "engine/evaluate.h" + +#include + +enum { + EVAL_PAWN = 100, + EVAL_KNIGHT = 320, + EVAL_BISHOP = 320, + EVAL_ROOK = 500, + EVAL_QUEEN = 900, +}; + +static const i32 MATERIAL[PIECE_TYPE_COUNT] = { + [WHITE_KING] = 0, + [WHITE_QUEEN] = EVAL_QUEEN, + [WHITE_ROOK] = EVAL_ROOK, + [WHITE_BISHOP] = EVAL_BISHOP, + [WHITE_KNIGHT] = EVAL_KNIGHT, + [WHITE_PAWN] = EVAL_PAWN, + [BLACK_KING] = 0, + [BLACK_QUEEN] = EVAL_QUEEN, + [BLACK_ROOK] = EVAL_ROOK, + [BLACK_BISHOP] = EVAL_BISHOP, + [BLACK_KNIGHT] = EVAL_KNIGHT, + [BLACK_PAWN] = EVAL_PAWN, +}; + +// simple positional bonus (a light "pst"): pawns like to advance, knights like +// the centre. everything else is just material. +static i32 pst_bonus(int piece_type, int square) { + int rank = square / 8; + int file = square % 8; + if (piece_type == WHITE_PAWN) return (rank - 1) * 6; + if (piece_type == BLACK_PAWN) return (6 - rank) * 6; + if (piece_type == WHITE_KNIGHT || piece_type == BLACK_KNIGHT) { + bool central = (file == 3 || file == 4) && (rank == 3 || rank == 4); + bool nearcentre = (file >= 2 && file <= 5) && (rank >= 2 && rank <= 5); + return central ? 16 : (nearcentre ? 4 : -4); + } + return 0; +} + +i32 evaluate(position_t position) { + i32 white = 0; + i32 black = 0; + for (int piece = 0; piece < PIECE_TYPE_COUNT; piece++) { + bitboard_t bb = position.bitboards[piece]; + while (bb) { + int sq = __builtin_ctzll(bb); + bb &= bb - 1; + if (piece < BLACK_KING) { + white += MATERIAL[piece] + pst_bonus(piece, sq); + } else { + black += MATERIAL[piece] + pst_bonus(piece, sq); + } + } + } + i32 score = white - black; + return (position.turn == WHITE_TURN) ? score : -score; +} + +#ifdef TEST_MOD +#include + +bool test_eval_startpos_is_balanced() { + position_t start = position_starting(); + // symmetric starting position -> static eval should be ~0. + return abs(evaluate(start)) < 100; +} + +bool test_eval_scales_with_material() { + position_t pos = {0}; + pos.turn = WHITE_TURN; + // give white a queen on a1, black only a king on h8 + pos.bitboards[WHITE_QUEEN] = 1ULL; + pos.bitboards[BLACK_KING] = (1ULL << 63); + pos.bitboards[WHITE_KING] = (1ULL << 4); // a5, far from the action + pos.bitboards[BLACK_PAWN] = 0; + i32 score = evaluate(pos); + // white is up a queen (~900) plus a little; should be comfortably positive. + return score > 800; +} +#endif 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 diff --git a/src/engine/ttable.c b/src/engine/ttable.c index fc1b6f0..c98bf62 100644 --- a/src/engine/ttable.c +++ b/src/engine/ttable.c @@ -23,9 +23,13 @@ void zobrist_init() { u64 zobrist_hash(position_t position) { u64 output = 0; - for (int i = 0; i < 64; i++) { - int piece_type = find_piece_on_square(&position, i); - output ^= zobrist_keys.piece[piece_type][i]; + for (int piece = 0; piece < PIECE_TYPE_COUNT; piece++) { + bitboard_t bb = position.bitboards[piece]; + while (bb) { + int sq = __builtin_ctzll(bb); + bb &= bb - 1; + output ^= zobrist_keys.piece[piece][sq]; + } } if (position.castling & WHITE_SHORT_CASTLE) { -- cgit v1.2.3