summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/engine.c2
-rw-r--r--src/engine/evaluate.c83
-rw-r--r--src/engine/search.c206
-rw-r--r--src/engine/ttable.c10
4 files changed, 298 insertions, 3 deletions
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 <stdlib.h>
+
+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 <stdbool.h>
+
+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 <assert.h>
+
+#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 <stdbool.h>
+#include <stdlib.h>
+
+#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) {
generated by cgit v1.2.3 (git 2.39.1) at 2026-10-23 00:46:27 +0000