path: root/src/docs/TREEDUMP_FORMAT.md

# TREEDUMP: a shared search-tree trace format for typhoon vs. Stockfish

Both engines, when built with a `TREEDUMP` compile-time flag, write a
flat, line-oriented, always-on trace of search decisions to a file
named `treedump.log` in the current directory. There is no runtime
toggle or filtering -- keep a dump small by using a shallow `sd N`
(typhoon) / `go depth N` (Stockfish), not by restricting what gets
written.

The point is to run both engines on the *same FEN* at the *same shallow
depth*, then diff/meld the two `treedump.log` files to see exactly
where their trees diverge -- which move each engine reduces, prunes, or
searches in full, and by how much.

## Building

- typhoon: `gmake release PERF_COUNTERS=1 TREEDUMP=1` (or `debug`).
  Writes `treedump.log` in the working directory from process start to
  exit (`TDOpen`/`TDClose` in `main.c`). Single-threaded runs only
  (`--cpus 1`) -- the file write isn't locked against concurrent
  threads, matching this project's own `--cpus 1` convention for
  diagnostic/comparison runs.
- Stockfish: `gmake build ARCH=x86-64-avx2 COMP=clang EXTRACXXFLAGS=-DTREEDUMP`
  (FreeBSD: use `gmake`, not `make` -- the stock `make` chokes on this
  Makefile's GNU-only syntax; `COMP=clang` because there's no `gcc` on
  this box; `ARCH=x86-64-avx2`, not bare `x86-64` or `ARCH=native` --
  both of the latter either fail FreeBSD's arch-detection outright or
  silently build a popcnt-less binary that reproducibly returns a
  dead/empty search, 0 nodes, on every `go`, with no error -- see the
  gotcha below, this is a different failure mode from it and easy to
  conflate with it). Also writes `treedump.log` in the working
  directory, for the life of the process. Single-threaded only
  (`Threads` UCI option defaults to 1; don't raise it for a comparison
  run). **`EXTRACXXFLAGS` isn't tracked as a `make` dependency** -- if
  you rebuild the same ARCH with/without it back to back, `search.cpp`
  (the only file TREEDUMP touches) won't be recompiled and you'll
  silently get the previous binary; `touch search.cpp` first, or
  `gmake clean` first, whenever toggling the flag.

### A Stockfish-specific gotcha: piping input races the search thread

If you drive Stockfish non-interactively by piping commands in and
letting the pipe close right after (`printf '...\ngo depth N\n' |
./stockfish`), the engine's input-reading thread can see EOF and begin
shutting the engine down *before* the search thread has actually
started producing nodes -- the symptom is `info depth 1 ... nodes 0
... pv ` (empty) immediately followed by a `bestmove`, for every
UCI limit type (`depth`, `nodes`, `movetime` all equally ignored), with
exit code 0 (not a crash). This reproduced on this box on a **clean,
unmodified** Stockfish build too, so it's not a TREEDUMP artifact --
it's inherent to how this fork's shared-memory NNUE bootstrap
(`shm.h`/`shm_unix.h`, "Network replica N: Shared memory" in the
startup banner) races against stdin closing, and it was intermittent
enough (roughly 1 good run in ~15-18 attempts, observed empirically)
that blind retrying is not a reliable workaround.

**Fix: hold stdin open past the point the search should finish**,
e.g.:

```sh
(printf 'position fen <FEN>\ngo depth N\n'; sleep 2) | ./stockfish
```

An interactive terminal session (typing the commands directly, or
redirecting from a real tty) never hits this, which is why it's easy
to not reproduce it while debugging interactively and then hit it
again the next time a script pipes input in.

**Future-work idea, not yet built**: a small purpose-written xboard<->UCI
driver (distinct from `stockfish_xboard`, which hardcodes
`/usr/local/bin/stockfish` via PolyGlot for `match_play.py`'s xboard-only
engine pool, not this instrumented source build) would let this
TREEDUMP-build Stockfish be driven with the same `--batch --command`-style
invocation already used for typhoon and Crafty, sidestepping the
stdin-race gotcha entirely rather than working around it with `sleep`.
Worth doing if this three-engine TREEDUMP comparison becomes a repeated
workflow rather than a one-off batch.

## Building a third engine: Crafty

Crafty (`~/programming/chess/crafty-25.2`) also speaks this format now
(added 2026-10-23), giving a third data point alongside typhoon and
Stockfish -- useful specifically because Crafty's HCE is much "dumber"
than typhoon's NNUE, so if Crafty's pruning/reduction magnitudes still
line up with Stockfish's despite the weaker eval, that's a stronger
signal that the magnitude is calibration-driven (an engine-independent
"right amount") rather than an artifact of how strong the eval backing
the search happens to be.

Crafty compiles everything into one translation unit (`crafty.c`
`#include`s every other `.c` file), so the `TREEDUMP` instrumentation
lives directly in `search.c` (new `TDOpen`/`TDClose`/`TDMove`/`TDResult`
functions, prototyped in `chess.h` behind `#if defined(TREEDUMP)`) rather
than needing a new source file. `main.c` opens `treedump.log` at process
start and registers `TDClose` via `atexit()` so it's closed on every exit
path, not just a clean `quit`.

Build (single-threaded, matching typhoon's and Stockfish's TREEDUMP
convention -- `search.c`'s path-reconstruction helper assumes Crafty's
single-TREE-struct-per-thread model, where `tree->curmv[1..ply]` holds
every move played so far in *this* recursion; that invariant only holds
cleanly with one thread):

```sh
cd ~/programming/chess/crafty-25.2
rm -f *.o crafty
gmake target=UNIX CC=clang opt='-DSYZYGY -DCPUS=1 -DTREEDUMP' \
    CFLAGS='-Wall -Wno-array-bounds -pipe -O3 -mpopcnt' \
    LDFLAGS='-lstdc++ -lm' crafty-make
```

(`-j` can be dropped or kept; `crafty.o` depends on `*.c *.h` as one
glob so there's no partial-rebuild hazard the way Stockfish's
`EXTRACXXFLAGS` has -- no `touch` trick needed here. Rebuild the normal
multi-threaded profile afterward the same way the other two engines'
TREEDUMP builds get reverted: `rm -f *.o crafty && gmake target=UNIX
CC=clang opt='-DSYZYGY -DTEST -DCPUS=4' CFLAGS='-Wall -Wno-array-bounds
-pipe -O3 -mpopcnt -pthread' LDFLAGS='-pthread -lstdc++ -lm'
crafty-make` -- note the `-pthread` CFLAGS/LDFLAGS are required once
`CPUS` > 1, the TREEDUMP/`CPUS=1` build doesn't need them.)

Crafty speaks xboard natively (no PolyGlot/UCI adapter needed, unlike
driving it through `stockfish_xboard`-style tooling), so it can be
driven the same way as typhoon's own `--batch --command` invocations:

```sh
(printf 'force\nsetboard <FEN>\nsd 6\ngo\nquit\n'; sleep 2) | ./crafty
```

Hold stdin open past the search the same way Stockfish needs (see the
gotcha below) -- not yet confirmed whether Crafty has the identical
race, but cheap to guard against unconditionally rather than
re-discover it.

**Mapped `act=` values**: `FP-QUIET` (Crafty's `FP_margin[]` futility
check -- note this is a **raw-material** check,
`MaterialSTM(wtm) + FP_margin[depth] <= alpha`, not a full static-eval
call the way typhoon's/Stockfish's futility-flavored checks are, so
don't read "FP-QUIET volume" as directly comparable cost between
engines even where the tag matches), `LMP` (pure move-count/depth
threshold, no evidence gate at all -- matches the `search.c` comment
block this investigation started from), `NMP` (null-move probe, `r`
left `0.00` same convention as typhoon), `FULL`/`LMR`/`EXT` (the main
move loop, after Crafty's own `reduce`/`extend` locals are resolved).
Crafty has no ProbCut and no IID-as-a-traced-decision (IID's recursive
call reuses the *same* ply rather than descending one, so it doesn't fit
the path model and isn't traced).

**A Crafty-specific wrinkle worth remembering when reading a diff**:
Crafty's own `search.c` comment on this block (the one this
investigation started from) says forward pruning here "simply avoid[s]
searching this move at all, and skip[s] to the next move" -- but
functionally this is a `break`, not a `continue`: once FP or LMP fires on
one move, every *remaining* move at that node is abandoned too, not just
the one move. typhoon's and Stockfish's LMP-equivalents are evaluated
move-by-move (a `continue`, not a `break`) -- a given late move being
pruned doesn't prevent trying a later move that might not be. Don't read
Crafty's `act=LMP`/`act=FP-QUIET` *count* at a node as "N moves pruned
out of the move list" the way you might for the other two engines; it
usually means "the move list ended early starting here," which has a
different effect on tree shape (and EBF) than an equal count of
individually-pruned moves scattered across a wider move list.

## Why path-keyed, not node-numbered

Internal node counters are meaningless across two different engines --
their recursion order, node numbering, and even which positions get
revisited (transposition table hits) differ completely. The only thing
that identifies "the same position" in both engines is the sequence of
moves played from the root, since both start from the same FEN. Every
line is therefore keyed by `path="<uci moves from root, space-separated>"`
-- sort or `grep` on that field to line up corresponding decisions from
the two logs regardless of visit order.

A null move is spelled `0000` in a path (both engines already use this
UCI convention for `Move::null()`/`NULLMOVE` internally -- it's not an
invented token).

## Record types

Two kinds of line, both single-line, both flushed immediately (so a
killed/crashed process still leaves a readable partial log):

```
MOVE path="<path, ending in the move this line is about>" depth=<float> alpha=<int> beta=<int> kind=<str> act=<str> r=<float> ext=<float> score=<int|SKIPPED>

RESULT path="<path, NOT including any move at this node>" depth=<float> alpha=<int> beta=<int> eval=<int> bound=<EXACT|LOWER|UPPER> score=<int>
```

- `depth`: remaining search depth in whole plies (float, since
  typhoon's internal depth is fixed-point in `ONE_PLY`-sized ticks and
  extensions/reductions can be fractional ply amounts; Stockfish's is
  already integer plies and just prints with no fractional part).
- `alpha`/`beta`: the window at the node the move/result belongs to.
  For a `RESULT` line, this is the node's *original* (pre-aspiration-
  widening) window, so the `bound` field's classification is
  consistent.
- `kind` (MOVE only): rough move classification -- `FIRST`, `HASH`,
  `CAP`, `QUIET`, `NULL`, `PROBCUT`, freeform otherwise. Not identical
  granularity between the two engines (see Known Gaps below) --
  treat it as a hint, not a guaranteed-matching taxonomy.
- `act` (MOVE only): what happened to this move --
  `FULL` (searched at full/nominal depth), `LMR` (late-move-reduced),
  `LMR-RESEARCH` (Stockfish only: a reduced search failed high and got
  a full-depth re-search), `EXT` (extended), `LMP` (pruned without
  being searched, "late move pruning"), `FP-CAP`/`SEE-CAP`/
  `HIST-PRUNE`/`FP-QUIET`/`SEE-QUIET` (Stockfish's shallow-depth move
  pruning variants -- typhoon currently has no direct equivalent to
  several of these, which is itself one of the interesting things to
  look for in a diff), `NMP` (null-move probe), `PROBCUT` (Stockfish
  only -- typhoon has no ProbCut at all).
- `r`/`ext` (MOVE only): magnitude, in whole plies, of any reduction
  (`r`) or extension (`ext`) applied. Exactly one is normally nonzero.
- `score`: the score this move/node returned, or the literal `SKIPPED`
  on a `MOVE` line for a move that was pruned without ever being
  searched.
- `eval` (RESULT only): the node's static eval. May be stale/0 on a
  typhoon node that returned before `Eval()` ran (e.g. an immediate
  hash/recognizer cutoff) -- diagnostic only, don't trust it blindly.

## Known gaps / asymmetries (read before drawing conclusions from a diff)

- **Neither engine traces into qsearch.** Qsearch nodes vastly
  outnumber full-width nodes even at `sd 4`/`go depth 4` and would
  swamp a diff of the full-width move-ordering/pruning decisions that
  are actually of interest. This means a TREEDUMP diff only shows the
  full-width tree shape, not what happens once captures start
  resolving near the horizon -- keep comparisons shallow enough that
  qsearch isn't where most of the interesting divergence lives, or
  treat this as future work if it turns out qsearch matters too.
- **`kind` is not a matched taxonomy.** typhoon's `TDMove` call sites
  classify moves coarsely (`FIRST`/`CAP`/`QUIET`/`NULL`); Stockfish's
  do the same but the two engines' internal move-ordering concepts
  (killers, countermoves, TT move, etc.) don't line up 1:1. Don't
  diff on `kind` expecting an exact match -- diff on `act`, `r`/`ext`,
  and `score` for a given `path`, and use `kind` only as a sanity
  check.
- **typhoon has no ProbCut.** Any `act=PROBCUT` line will only ever
  appear in Stockfish's log. This is itself a structural difference
  worth noting, not a bug in the instrumentation.
- **Stockfish's null-move `depth` field is the full pre-reduction
  parent depth minus R; typhoon's null-move `MOVE` line's `depth`
  field is the already-reduced probe depth** (`TryNullmovePruning`
  never receives the pre-reduction parent depth) -- compare the
  *absolute* depth value in context, don't assume the two `r` fields
  for null moves are computed the same way (typhoon's is left `0.00`
  for null moves rather than faked).
- **typhoon's `RESULT.eval` can be stale (0 or a leftover value)** on
  any node that returned before `Eval()` ran. Stockfish's `eval` field
  comes from `ss->staticEval`, which has its own, different set of
  early-return paths that skip a real eval. Don't diff raw eval
  numbers across engines expecting them to be comparable at all (they
  use different evaluation functions) -- only use `eval` to sanity-
  check a single engine's own `RESULT` line against its own earlier
  `MOVE` lines.

## Suggested workflow

```sh
# typhoon side
cd /usr/home/scott/typhoon/src
gmake release PERF_COUNTERS=1 TREEDUMP=1
rm -f treedump.log
./typhoon --cpus 1 --hash 8m --logfile - --batch --command \
    "force; book name /nonexistent.book.bin; setboard <FEN>; sd 4; go"
cp treedump.log /tmp/typhoon/td_typhoon.log

# stockfish side
cd ~/programming/chess/stockfish/src
touch search.cpp  # EXTRACXXFLAGS isn't a tracked dependency -- force the recompile
gmake build ARCH=x86-64-avx2 COMP=clang EXTRACXXFLAGS=-DTREEDUMP
rm -f treedump.log
(printf 'position fen <FEN>\ngo depth 4\n'; sleep 2) | ./stockfish
cp treedump.log /tmp/typhoon/td_sf.log

# compare (sort by path first so corresponding positions line up
# regardless of each engine's own visit order)
sort -t'"' -k2 /tmp/typhoon/td_typhoon.log > /tmp/typhoon/td_typhoon.sorted
sort -t'"' -k2 /tmp/typhoon/td_sf.log > /tmp/typhoon/td_sf.sorted
meld /tmp/typhoon/td_typhoon.sorted /tmp/typhoon/td_sf.sorted
```

Rebuild each engine back to its normal release profile afterward
(`TREEDUMP` should never be the profile left in place for a real run --
it's diagnostic-only, same spirit as this project's other collection-
build flags).