# 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` implement. The DTS
primitives (HELP/Split/Merge/Share), sequential search, evaluation, iterative
deepening, root splitting, and child worker loop are all implemented and tested.

This plan maps the DTS concepts (Sections 2.3–2.8) onto the codebase and
documents the remaining work: end-to-end UCI integration (H1).

---

## 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 G — Stop / signal / cleanup plumbing
- [x] `threads_all_done()` scans `args[i].finished` atomics — implemented and tested.
- [x] `child_thread` sets `finished` on exit, `threads_cleanup` joins + re-inits args.
- [x] **G2.** `main.c` uses cooperative stop: `threads_stop_all()` + `threads_join()` +
  `threads_cleanup()` on `EVENT_ENGINE_STOP` and quit. Threads clean up gracefully.

### 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`.
- [x] **H2.** Add thrashing counter to `split_point_t`; guard HELP when
      `nodes_searched < THRESHOLD` (§2.1). Re-test.
- [x] **H3.** Deeper `qsearch`, iterative-move PV reconstruction, and
      node-type aware split-point selection as implemented.

---

## 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 for remaining phases:

| Phase | Test name | What it checks |
|---|---|---|
| H | `test_cooperative_stop` | `args->stop = 1` causes all threads to exit cleanly and set `finished` |
| H | `test_thrashing_guard` | HELP is refused when `nodes_searched < THRESHOLD` |

---

## 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 G — Stop / signal / cleanup
- [x] **G2.** In `src/main.c`, replace `pthread_cancel` on `EVENT_ENGINE_STOP`
      with cooperative stop: set `args->stop = 1` on all threads via
      `threads_stop_all()`, then spin on `threads_all_done()` before calling
      `threads_join()` + `threads_cleanup`. Root/child threads exit cleanly.

### 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`.
- [x] **H2.** Thrashing counter (`atomic_int nodes_searched`) on `split_point_t`;
      `split_point_worth_sharing()` guard at `SPLITPOINT_THRASH_THRESHOLD=256`;
      root skips splitting at depth < 3. Tested.
- [x] **H3.** Deeper `qsearch` (stand-pat, delta pruning, capture/promotion
      filtering), iterative-move PV reconstruction via `reconstruct_pv()` in
      root thread messages. Tested.

---

## 7. Files Touched Summary

| File | Action |
|---|---|
| `src/main.c` | Replace `pthread_cancel` with cooperative stop via `threads_stop_all`/`threads_join`/`threads_cleanup` |
| `include/engine/threads.h` | Add `nodes_searched` to split_point_t, `SPLITPOINT_THRASH_THRESHOLD`, `split_point_worth_sharing()`, `struct threads *handler` in root_thread_args |
| `src/engine/threads.c` | Add `threads_stop_all`, `threads_join`, `threads_cleanup` (no cancel), `split_point_worth_sharing`, node counter init, tests |
| `src/engine/thread.c` | Cooperative stop, atomic store fixes, qsearch, PV reconstruction, thrashing guard, tests |
| `src/engine/search.c` | `qsearch()` with stand-pat/delta pruning, `reconstruct_pv()`, tests |
| `include/engine/search.h` | Add `reconstruct_pv` declaration |