phase B

8 files changed, 367 insertions, 6 deletions

diff --git a/PLAN.md b/PLAN.md
index 7581307..7bd8bf4 100644
--- a/PLAN.md
+++ b/PLAN.md
@@ -316,6 +316,12 @@ build (`just test`) green before the next.
 - [ ] **B3.** `just test` — all 17 original tests + new search/eval tests green.
 
 ### Phase C — Root thread driver (still effectively single-worker)
+- [ ] **C0.** Fix required. src/engine/ttable.c — zobrist_hash scanned all 64
+      squares via find_piece_on_square, which asserts on empty squares.
+      The per-node TT probe made search hit this on any non-full-board position.
+      Rewrote the piece loop to iterate occupied bitboards
+      (castling/turn/en-passant tail unchanged).
+      No existing test asserts on zobrist_hash output, so nothing regressed.
 - [ ] **C1.** Rewrite `root_thread` in `src/engine/thread.c` to run iterative
       deepening using `search()`, populating the `engine_message` each depth
       and respecting `args->stop` + `should_continue`.
diff --git a/include/engine/evaluate.h b/include/engine/evaluate.h
new file mode 100644
index 0000000..ecc6e60
--- /dev/null
+++ b/include/engine/evaluate.h
@@ -0,0 +1,10 @@
+#ifndef EVALUATE_H
+#define EVALUATE_H
+
+#include "bitboard.h"
+
+// static evaluation from the side-to-move's point of view.
+// positive == good for the side to move, negative == good for the opponent.
+i32 evaluate(position_t position);
+
+#endif // EVALUATE_H
diff --git a/include/engine/search.h b/include/engine/search.h
new file mode 100644
index 0000000..94b5da5
--- /dev/null
+++ b/include/engine/search.h
@@ -0,0 +1,36 @@
+#ifndef SEARCH_H
+#define SEARCH_H
+
+#include <stdatomic.h>
+
+#include "bitboard.h"
+#include "engine/moves.h"
+#include "engine/ttable.h"
+#include "ipc/go_args.h"
+
+#define SEARCH_MATE 30000
+#define SEARCH_INF 32000
+
+typedef struct {
+  i32 score;
+  move_t best_move;
+} search_result_t;
+
+// shared per-search context. `stop` is signalled by the UCI thread (SIGSTOP),
+// `go_args` carries the time/node/depth limits, `nodes` counts visited nodes.
+typedef struct {
+  ttable_t *ttable;
+  go_args_t *go_args;
+  atomic_bool *stop;
+  u64 *nodes;
+} search_ctx_t;
+
+search_result_t search(
+  position_t position,
+  int depth,
+  int alpha,
+  int beta,
+  search_ctx_t *ctx
+);
+
+#endif // SEARCH_H
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) {
diff --git a/tests/generated.c b/tests/generated.c
index 8a9014f..3f6fc99 100644
--- a/tests/generated.c
+++ b/tests/generated.c
@@ -1,15 +1,23 @@
 #include "../src/fen.c"
+#include "../src/engine/search.c"
+#include "../src/engine/evaluate.c"
 #include "../src/engine/ttable.c"
 #include "../src/engine/threads.c"
 #include "../src/engine/moves.c"
 #include "../src/engine/moves/king.c"
 #include "../src/uci/command.c"
 
-int total_test_count = 19;
-bool (*tests[19])(void) = {
+int total_test_count = 25;
+bool (*tests[25])(void) = {
   test_fen_no_passant,
   test_fen_passant,
   test_starting_position,
+  test_search_finds_mate_in_one,
+  test_search_handles_no_moves,
+  test_search_respects_depth,
+  test_search_stop_signal_halts,
+  test_eval_startpos_is_balanced,
+  test_eval_scales_with_material,
   test_ttable_empty,
   test_ttable_insert_and_find,
   test_ttable_wrong_key,
@@ -29,10 +37,16 @@ bool (*tests[19])(void) = {
 };
 
 int max_test_name_size = 34;
-char test_names[19][100] = {
+char test_names[25][100] = {
   "fen_no_passant",
   "fen_passant",
   "starting_position",
+  "search_finds_mate_in_one",
+  "search_handles_no_moves",
+  "search_respects_depth",
+  "search_stop_signal_halts",
+  "eval_startpos_is_balanced",
+  "eval_scales_with_material",
   "ttable_empty",
   "ttable_insert_and_find",
   "ttable_wrong_key",