plan

1 files changed, 378 insertions, 0 deletions

diff --git a/PLAN.md b/PLAN.md
new file mode 100644
index 0000000..2b3a05d
--- /dev/null
+++ b/PLAN.md
@@ -0,0 +1,378 @@
+# Gacrux — Distributed (DTS) Search Implementation Plan
+
+## 0. Context
+
+`resources/search.html` is the DTS ("Dynamic Tree Splitting") paper by Robert
+Hyatt et al. (Cray Blitz). It is the blueprint for the multi-threaded search
+that `src/engine/threads.c` + `src/engine/thread.c` are meant to implement. The
+current thread code is a **stubbed-out refactor**: `child_thread()` busy-waits
+and emits a hardcoded best move; `root_thread()` is empty; the search, eval,
+and parallel primitives do not exist yet.
+
+This plan maps the DTS concepts (Sections 2.3–2.8) onto the **actual data
+structures already declared** in `include/engine/threads.h`, fixes the bugs in
+that header, and lays out a phased implementation.
+
+---
+
+## 1. Current State of the Thread/Search Code
+
+### Declared in `include/engine/threads.h` (but incomplete or buggy)
+
+| Item | State |
+|---|---|
+| `split_point_t` | Declared, **two fields both named `best_score`** (`atomic_int` + `move_t` — one must be `best_move`). |
+| `struct child_thread_args` | **Truncated** — ends with a dangling `int` (no member name); `child_thread()` in `thread.c` references `args->message` which isn't in the struct. |
+| `struct root_thread_args` | Complete (has `engine_message_handler_t *message`). |
+| `struct threads` | Has `split_point_pool`, `ttable`, `engine_messages`, `go_args`, `position` placeholders but nothing is wired up in `threads.c`. |
+| `threads_go()` | Spawns root (id 0) + children; `__threads_args_init` only sets a few fields. |
+
+### What's missing
+
+- `src/engine/search.c` — the alpha–beta negamax search.
+- `src/engine/evaluate.c` — static evaluation.
+- Any node type classification (PV / CUT / ALL from DTS §3.1).
+- The HELP / Split / Merge / Share (§2.3–2.8) primitives.
+- Time/iteration control via `go_args_t`.
+- Connection of search results to `engine_message_handler_t` for UCI `info`/`bestmove` output.
+
+### What already exists (and is reliable)
+
+- Move generation: `src/engine/moves.c` + `src/engine/moves/*.c` (pawn, knight,
+  king w/ castling, rook/bishop/queen via **magic bitboards**, attacks).
+- Legal-move filtering & `position_make_move()` (castling, en-passant, promotion,
+  castling-right updates).
+- Undo is done by **copying the whole `position_t`** then mutating — perft tests
+  in `src/engine/moves.c` use `position_t copy = position; position_make_move(&copy, m);`.
+- Transposition table: `ttable_init/find/insert` + Zobrist hashing
+  (`zobrist_init`, `zobrist_hash`), tested.
+- UCI plumbing: stdin readline loop, `uci_cmd_t` parsing, option handling,
+  `handle_ipc` emitting `info ... pv ... bestmove`.
+- `go_args_t` has all time control fields + `should_continue()`.
+
+---
+
+## 2. Design Constraints From the Codebase
+
+1. **Position is copied, not undone.** `position_make_move()` mutates its argument
+   and there is no `undo_move`. Every caller (perft, future search) does
+   `position_t child = position; position_make_move(&child, m);` and recurses on
+   the copy. **The search must use this same copy-on-recurse style** — this is
+   actually *easier* for DTS than save/move/undo because a split point can hand
+   its entire `position_snapshot` to a worker without stack-frame concerns.
+
+2. **`position_t` is ~100 bytes**, so copying per node is acceptable.
+
+3. **Threads communicate via atomics + shared split points** (`atomic_int`
+   already used in `split_point_t`). No new synchronization primitives needed.
+
+4. **`go_args_t`** already carries everything the search needs: `wtime/btime`,
+   `winc/binc`, `movestogo`, `depth`, `nodes`, `mate`, `movetime`, `infinite`,
+   `perft`, `ponder`. `should_continue(message, go_args)` is the stop predicate.
+
+5. **Single translation unit**: `engine.c` `#include`s `threads.c`,
+   `thread.c`, `moves.c`, `ttable.c` together. New `.c` files just need to be
+   added to `engine.c` and to `tests/generated.c`'s include list (auto-generated
+   by `tests/find_tests.c`).
+
+---
+
+## 3. DTS Algorithm Mapping (§2.3–2.8) to This Codebase
+
+| DTS concept | Code mapping |
+|---|---|
+| **HELP** (§2.3) — idle proc broadcasts; busy procs publish tree state | Idle `child_thread` spins on shared `split_point_t` list; `root_thread` and busy children expose their `split_point_t`s for pickup. |
+| **Split()** (§2.4) — copy full tree state to a shared SPLIT BLOCK; hand address to idle procs; they copy to private memory & resume at split ply | `split_point_t` already carries `position_snapshot`, `moves` (move list), `alpha`, `beta`, `best_score`/`best_move`, `next_move_idx`. A `create_split_point()` copies the search stack up to the split ply into it. Workers `atomic_fetch_add(&sp->next_move_idx, 1)` to **claim** moves (the DTS `Select()`/`Selget`/`Selput` pattern). |
+| **Select()** (§2.5) — lock shared move list, copy to local, pick one, write back | `next_move_idx` (atomic counter) *is* the lock-free version of the semaphore-protected `Selget`/`Selput`. Each worker does `int idx = atomic_fetch_add(&sp->next_move_idx, 1); if (idx >= len) → done at this split point.` |
+| **Merge()** (§2.6) — runs out of moves at a split point; compare score; `workers--`; if 1 remains, send UNSPLIT | `atomic_fetch_sub(&sp->workers, 1)`; when 2, the last worker "owns" the node and must return the final value. |
+| **Unsplit()** (§2.7) — drop the split block, keep best partial | `sp->state = SPLITPOINT_STATE_FREE`; free back to `split_point_pool`. |
+| **Share()** (§2.8) — back up a new best at a split point; notify other workers | `atomic_store(&sp->best_score, newbest)`; bound updates propagate on next `Select()`. |
+| **Node typing** (§3.1–3.2) — PV/CUT/ALL + confidence override | New field on `split_point_t` (or derived from `alpha`/`beta == INFs`). `confidence` already exists. |
+| **Thrashing counter** (§2.1 end) — refuse HELP when < N nodes searched at end of iteration | `split_point_t.confidence` or a dedicated `thrashing` counter in `struct threads`. |
+
+The existing `enum { NODE_PV, NODE_CUT, NODE_ALL }` and `confidence`/`ply` fields on
+`split_point_t` were placed there precisely for §3.x.
+
+---
+
+## 4. Phased Implementation
+
+### Phase A — Fix up the data structures (header + struct wiring)
+**Files:** `include/engine/threads.h`, `include/engine/ttable.h` (minor)
+
+- **Fix `split_point_t`**: rename the duplicate `move_t best_score` →
+  `move_t best_move`. Keep `atomic_int best_score`.
+- **Finish `struct child_thread_args`**: add the missing
+  `engine_message_handler_t *message;` field it's missing (matches
+  `root_thread_args`), and give the dangling `int sp_stack;` a real purpose or
+  remove it. Add `go_args_t *go_args;` is already there.
+- **Add `ttable_t` population**: `__threads_args_init` already has access to
+  `handler->ttable`; ensure `threads_go` / `threads_reserve` propagate it to
+  each `thread_args_t`. (Ttable is created in `struct threads` but never
+  `ttable_init`'d — wire that into the engine startup.)
+- **Add a `struct search_stack`** (lightweight): not strictly needed since we
+  copy `position_t`, but a per-worker `int ply; int depth;` helper is useful for
+  node typing. Keep it minimal.
+
+### Phase B — Sequential search foundation (single-threaded, testable)
+**New files:** `src/engine/evaluate.c`, `src/engine/search.c`,
+`include/engine/evaluate.h`, `include/engine/search.h`
+
+- **`evaluate.c` → `i32 evaluate(position_t)`**
+  - Material + PST (piece-square tables). Start simple:
+    material weights (P=100, N=B=320, R=500, Q=900, K=20000) + basic PST.
+  - Wire into `engine.c` aggregation + tests.
+
+- **`search.c`**:
+  - `search_result_t search(position_t pos, int depth, int alpha, int beta,
+    struct search_ctx *)`.
+    - `struct search_ctx` bundles `*ttable`, `*go_args`, a `*stop` atomic, and a
+      `nodes` counter.
+  - At `depth == 0`: quiescence or just `return evaluate(pos)`.
+    - **Quiescence** (`qsearch`): only captures/promotions, until stand-pat or
+      no capture improves. Keep it simple first.
+  - Probe TT (`zobrist_hash` → `ttable_find`); if hit & depth sufficient &
+    compatible flag, return stored score (DTS relies on TT "a lot").
+  - `get_legal_moves` → iterate; for each move:
+    - `position_t child = pos; position_make_move(&child, m);`
+    - recurse `search(child, depth-1, -beta, -alpha, ctx)`.
+    - alpha/beta window update + best-move tracking.
+    - Check `*stop` / `should_continue` each node.
+  - Store into TT (`ttable_insert`).
+  - Return `{score, best_move}` (negamax: negate score).
+
+- **`search_test_*`** embedded in `search.c` under `#ifdef TEST_MOD`:
+  - `test_search_handles_no_moves`, `test_search_respects_depth`, etc.
+  - A `test_qsearch_does_not_explode` for stability.
+
+### Phase C — Root thread: iterative deepening + perft-style driver
+**File:** `src/engine/thread.c` (rewrite `root_thread`)
+
+- `root_thread(void *_args)`:
+  1. `magic_init()` already done in main; `zobrist_init()` too.
+  2. Set up `search_ctx` pointing at `handler->ttable`, `args->go_args`, a
+     `*stop` atomic tied to `args->stop`.
+  3. **Iterative deepening**: for `depth = 1; depth <= max; depth++`
+     (max from `go_args->depth` or a default like 100):
+     - call `search()` at this depth from the root position.
+     - Populate the root's `engine_message` with `depth`, `nodes`, `score_cp`,
+       `pv` (best move line), `best_move`.
+     - `engine_message_mark_ready()` so the UCI thread can emit `info`.
+     - Check `*stop` (from `args->stop`) and `should_continue` each iteration;
+       break out if time/limit exhausted.
+  4. On stop or completion: push the final best-move into the message, mark
+     ready, set `args->stop` so children also leave their busy loops.
+
+- The engine_message lifecycle already exists (`engine_message_handler_push`
+  creates a fresh zeroed message; UCI pops + emits + `deinit`s it). The search
+  fills fields on the message handed to it via `args->message`.
+
+### Phase D — Parallel DTS primitives (HELP / Split / Merge / Share)
+**File:** `src/engine/threads.c` (add parallel primitives; `include/engine/threads.h` declares them)
+
+- **Split-point pool**: `threads_init` allocates
+  `capacity * sizeof(split_point_t)` into `handler->split_point_pool`; add
+  `split_point_t *split_point_alloc(struct threads *)`,
+  `split_point_free(struct threads *, split_point_t *)`.
+- **`HELP`**: idle child sets a flag / publishes availability. Concrete:
+  a worker that finds its split-point `moves` exhausted calls
+  `publish_split_point(sp)` (sets `sp->state = SPLITPOINT_STATE_ACTIVE` with
+  remaining work) so other idle workers can `claim_work(sp)`.
+  - Keep it lock-free: `atomic` state + `atomic` `next_move_idx`.
+- **`Split()`**: `create_split_point(handler, parent_sp, ply, position,
+  alpha, beta, moves)` — snapshot current position + move list + bounds.
+  - Used by root at depth boundaries, or by any worker when distributing its
+    move list.
+- **`Select()`**: `claim_next_move(sp, &move)` → `int i = atomic_fetch_add(
+    &sp->next_move_idx,1); if (i >= sp->moves.length) return false; move = ...;`.
+- **`Merge()`**: after a worker is out of moves at `sp`,
+  `atomic_fetch_sub(&sp->workers, 1)`; if it was the last, finalize the node
+  and `Unsplit` (free the block, propagate best score to parent).
+- **`Share()`**: when a worker finds a better `best_score` at a shared `sp`,
+  `atomic_store(&sp->best_score, val)`; other workers refresh alpha/beta bound
+  on their next `Select()`.
+- **Thrashing guard** (§2.1): a per-split-point `nodes_searched` counter; before
+  answering a HELP (i.e. before creating another split point) require
+  `nodes_searched >= THRESHOLD` (tune, e.g. 1000), else spin-search locally a
+  bit more. Prevents the end-of-iteration "15 idle procs bug 1 proc" collapse.
+
+### Phase E — Child thread worker loop (DTS worker)
+**File:** `src/engine/thread.c` (rewrite `child_thread`)
+
+```
+child_thread:
+  for (;;) {
+    claim a move (idx) from the highest-work split_point on the shared pool
+      (idle: scan pool for SP_ACTIVE with next_move_idx < length;
+       if none, publish own work or spin briefly)
+    if no move available:
+      if own split point exhausted -> Merge (workers--, maybe Unsplit)
+      else: HELP (publish self, loop)
+    search the move (recursive alpha/beta on the copied position)
+    Share() if improved best
+    if *stop / should_continue false: bail
+  }
+```
+
+Concretely the idle case is: scan `split_point_pool` for an `ACTIVE` split
+point with `next_move_idx < moves.length`; `atomic_fetch_add` to claim; search;
+back up. This is the lock-free equivalent of DTS's shared-memory move-queue.
+
+### Phase F — Root splitting (search the root move list in parallel)
+- `root_thread` at each ID iteration creates one split point spanning **all root
+  moves** (DTS §3.4: splitting at the root). Children claim root moves via
+  `Select()`. Each child runs a full iterative-deepening-less `search()` on its
+  slice and reports back its local best; the root merges (picks max).
+- This is where most real parallelism comes from for Gacrux's 2–5 thread config.
+
+### Phase G — Stop / signal / cleanup plumbing
+- Tie `args->stop` to `UCI_SIGNAL_STOP` / `UCI_SIGNAL_GO_LOOP` (already handled
+  in `src/uci.c:handle_ipc`).
+- `threads_all_done()` (exists) becomes the "all children finished" predicate
+  used by the main loop in `src/main.c` (currently
+  `threads_go_loop` is a stub). Implement it to scan
+  `args[i].finished`.
+- `threads_cleanup()` already cancels + re-inits args; extend the arg init to
+  also point `message`/`ttable`/`go_args` at the right shared objects.
+
+### Phase H — Integration & end-to-end
+- `src/main.c`: after `magic_init()`/`zobrist_init()`, also
+  `ttable_init(&ipc_state.threads.ttable, log2(hash_mb))` using the `Hash`
+  option (default 256 here maps to `256MB → log2`; `1<<18` entries ≈ 256 MiB of
+  256-byte buckets — clamp the log appropriately).
+- Wire the final best move + PV into `engine_message_handler_push` so the UCI
+  thread's `handle_ipc` emits `info depth ... pv ...` / `bestmove`.
+- Run `just test` (17 existing tests must still pass) + manual `uci` loop.
+
+---
+
+## 4.1 Node-Type Classification (DTS §3.x)
+
+A `split_point_t` (or derived) gets a `node_type`:
+
+```
+PV  = (alpha == -INF && beta == +INF)           // full window
+CUT = odd-ply && alpha == orig_alpha  (or even-ply && beta == orig_beta)
+ALL = otherwise
+```
+
+`confidence` = number of moves already searched at that ply (more searched →
+higher confidence in the type). Used by the idle-side `Split()` to pick a good
+ply to split (prefer ALL > PV-after-first-mover > CUT-avoid).
+
+For a first working version, split at the **root only** (always PV, always safe)
+and at interior plies only on ALL nodes — this avoids the bad split-point class
+of bugs from §3.2.
+
+---
+
+## 5. Testing Strategy (match existing test harness)
+
+The existing harness auto-discovers `bool test_*()` functions from `src/` via
+`tests/find_tests.c` → regenerates `tests/generated.c`. New tests just need to
+be named `test_*` and compiled under `TEST_MOD`.
+
+Recommended tests per phase:
+
+| Phase | Test name | What it checks |
+|---|---|---|
+| B | `test_eval_startpos` | evaluate() returns near 0 for startpos |
+| B | `test_search_findmate` | search(2 ply on a known mate-in-2) returns the mate |
+| B | `test_search_respects_depth` | depth-limited search picks a sensible move |
+| B | `test_qsearch_does_not_explode` | qsearch on a quiet position is fast & sane |
+| D | `test_split_claim_moves` | atomic `next_move_idx` claims exactly N moves across T threads |
+| D | `test_merge_decrements_workers` | Merge decrements `workers`, last one owns |
+| E | `test_help_publishes_splitpoint` | idle thread finds a published split point |
+| F | `test_root_split_all_moves_claimed` | root split point's moves all claimed exactly once |
+
+---
+
+## 6. TODO (Step-by-step)
+
+These are concrete, ordered steps. Each should be a single commit/patch and
+build (`just test`) green before the next.
+
+### Phase A — Data-structure fixes
+- [ ] **A1.** In `include/engine/threads.h`, rename the duplicate
+      `move_t best_score` on `split_point_t` → `move_t best_move`.
+- [ ] **A2.** Finish `struct child_thread_args`: add
+      `engine_message_handler_t *message;` field; remove or complete the
+      dangling `int sp_stack;`.
+- [ ] **A3.** In `src/main.c`, add `ttable_init(&ipc_state.threads.ttable,
+      <log2 of Hash option>)` before `threads_link` (use the `hash` spin option,
+      default 256 → pick a sensible log2, e.g. 18 for ~256 MiB buckets, clamped).
+- [ ] **A4.** In `src/engine/threads.c`, make `__threads_args_init` copy
+      `handler->ttable` and `handler->go_args` into each `thread_args_t`
+      (currently `go_args`/`ttable` are set on `handler` but never propagated to
+      per-thread args). Build + existing tests still pass.
+
+### Phase B — Sequential search + eval (no threads yet)
+- [ ] **B1.** Create `include/engine/evaluate.h` + `src/engine/evaluate.c`
+      with `i32 evaluate(position_t)` (material + simple PST). `#include` in
+      `engine.c`. Add `test_eval_startpos` under `TEST_MOD`.
+- [ ] **B2.** Create `include/engine/search.h` + `src/engine/search.c` with
+      `search_result_t` and `search(...)`. Probe/emit TT. Add `TEST_MOD`
+      tests: `test_search_findmate`, `test_search_respects_depth`.
+- [ ] **B3.** `just test` — all 17 original tests + new search/eval tests green.
+
+### Phase C — Root thread driver (still effectively single-worker)
+- [ ] **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`.
+- [ ] **C2.** Verify a manual `./build uci run` loop prints `info depth ...`
+      lines and a `bestmove` before `quit`.
+
+### Phase D — Parallel primitives
+- [ ] **D1.** Add `split_point_alloc`/`split_point_free` + pool wiring in
+      `threads.c` (back `handler->split_point_pool`).
+- [ ] **D2.** Implement `split_point_claim_move` (atomic `next_move_idx`),
+      `split_point_merge` (atomic `workers--`, last-owns),
+      `split_point_share` (atomic `best_score`/`alpha`/`beta` store). Add tests.
+- [ ] **D3.** Implement `HELP` publish/scan over the pool; `threads_go_loop`
+      returns true when all children `finished`. Build green.
+
+### Phase E — Child worker loop
+- [ ] **E1.** Rewrite `child_thread` as a DTS worker: scan pool for an
+      `ACTIVE` split point; claim via `split_point_claim_move`; run `search()`;
+      `split_point_share`; on exhaustion `split_point_merge`; bail on `*stop`.
+- [ ] **E2.** `just test` green (threaded search shouldn't break perft/ttable
+      unit tests since they don't use threads).
+
+### Phase F — Root move-list splitting
+- [ ] **F1.** In `root_thread`, create a root split point spanning all root
+      moves (after root move gen); let children claim root moves and report
+      partials; root merges and picks the best. This is where real speedup from
+      2–5 threads arrives.
+- [ ] **F2.** Manual `perft`-style verification: node counts at depth 3–4 match
+      the non-parallel perft (sanity check correctness under splitting).
+
+### Phase G — Stop / cleanup
+- [ ] **G1.** Confirm `threads_cleanup` / `threads_all_done` correctly observe
+      `finished` atomics; `child_thread` must set `finished` on exit.
+- [ ] **G2.** `stop` from UCI (`handle_ipc` → `EVENT_ENGINE_STOP`) propagates
+      into `args->stop` so search returns promptly.
+
+### Phase H — End-to-end + polish
+- [ ] **H1.** `./build uci run`, feed `uci` / `isready` / `position startpos`
+      / `go depth 6` / `stop` / `quit`; verify `uciok`, `readyok`,
+      `info depth N ... pv`, `bestmove`.
+- [ ] **H2.** Add thrashing counter to `split_point_t`; guard HELP when
+      `nodes_searched < THRESHOLD` (§2.1). Re-test.
+- [ ] **H3.** Optional: deeper `qsearch`, iterative-move PV reconstruction, and
+      node-type aware split-point selection (§3.2) as time allows.
+
+---
+
+## 7. Files Touched Summary
+
+| File | Action |
+|---|---|
+| `include/engine/threads.h` | Fix `split_point_t`, finish `child_thread_args` |
+| `src/engine/threads.c` | Pool + parallel primitives + `__threads_args_init` fix |
+| `src/engine/thread.c` | Rewrite `root_thread` (CD), `child_thread` (E) |
+| `src/engine/search.c` | **new** — alpha-beta search |
+| `include/engine/search.h` | **new** — search API |
+| `src/engine/evaluate.c` | **new** — static evaluation |
+| `include/engine/evaluate.h` | **new** — eval API |
+| `src/engine.c` | Add `search.c`/`evaluate.c` to aggregation |
+| `src/main.c` | Add `ttable_init` |