# 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
- [x] **A1.** In `include/engine/threads.h`, rename the duplicate
      `move_t best_score` on `split_point_t` → `move_t best_move`.
- [x] **A2.** Finish `struct child_thread_args`: add
      `engine_message_handler_t *message;` field; remove or complete the
      dangling `int sp_stack;`.
- [x] **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).
- [x] **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)
- [ ] **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.
- [x] **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`.
- [x] **C2.** Verify a manual `./build uci run` loop prints `info depth ...`
      lines and a `bestmove` before `quit`.

### Phase D — Parallel primitives
- [x] **D1.** Add `split_point_alloc`/`split_point_free` + pool wiring in
      `threads.c` (back `handler->split_point_pool`).
- [x] **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.
- [x] **D3.** Implement `HELP` publish/scan over the pool; `threads_go_loop`
      returns true when all children `finished`. Build green.

### Phase E — Child worker loop
- [x] **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`.
- [x] **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` |