diff options
| author | Scott Gasch <[email protected]> | 2026-10-23 13:19:17 -0700 |
|---|---|---|
| committer | Scott Gasch <[email protected]> | 2026-10-23 13:19:17 -0700 |
| commit | 69525eb2f42ea9cca8255f6cc3b85e6b1312fd05 (patch) | |
| tree | d78420b6c45d584a3f09b4dcbaf4f1edb36e8d5d /src/docs | |
| parent | 6b883e83935f5e8110788565cfcb77cd6fbf8950 (diff) | |
NNUE search integration: FH% tables, NODE_TYPE refinement, TREEDUMP rewrite
- data.c/chess.h: widen the joint FH% table's late axis 16->17, dedicating
the new bucket 0 to a whole-node ("will something here fail high at
all") sample rather than sharing it with the first-leftover-move curve.
Add an NNUE-eval counterpart table (g_uJointFHThousandths_NNUE) and an
NNUE counterpart of the beta-side table, selected at runtime based on
whether NNUE eval is active.
- search.c/searchsup.c: add _RefineNodeTypeGuess, which uses the FH%
tables (via g_NodeTypeGuessTable) to refine a node's NODE_TYPE guess
instead of the old heuristic; thread uParentMoveFHEstimate through
PLY_INFO so a node can see its parent's prediction for the move that
led to it.
- generate.c: initialize sKillers[2]/[3].uBonus unconditionally (an
uninitialized-stack read caught by valgrind under LTO; harmless today
but a real bug).
- dumptree.c/chess.h/GNUmakefile: replace the long-dead DUMP_TREE XML
tree dump (written for a GUI this project no longer has) with TREEDUMP,
a flat, path-keyed move/result trace meant to diff against an
identically-instrumented Stockfish build -- see docs/TREEDUMP_FORMAT.md.
- docs/DEEPER_PRUNING.md: notes on closing the search-efficiency gap vs
Stockfish.
- crafty_egtb/stockfish_xboard/typhoon_nnue: wrapper scripts so
match_play.py's Engine class can drive Crafty, Stockfish (via
PolyGlot), and an NNUE-enabled typhoon the same way it drives HCE
typhoon.
- tests/lop: rename lop.txt -> lop.ep_; update compare_lop.cpp.
- annotate_pgns: add aggregate_marginsafety.py, dedup_pgn.py,
fit_lazy_probe.py; update annotate.py/run_nnue_pipeline.py for the NNUE
training pipeline.
- .gitignore: ignore compile_commands.json (clangd build DB) and
eval.nnue (a symlink into the untracked head_reference/ comparison
baseline), neither of which belongs in the repo.
Co-Authored-By: Claude Sonnet 5 <[email protected]>
Diffstat (limited to 'src/docs')
| -rw-r--r-- | src/docs/DEEPER_PRUNING.md | 382 | ||||
| -rw-r--r-- | src/docs/TREEDUMP_FORMAT.md | 191 |
2 files changed, 573 insertions, 0 deletions
diff --git a/src/docs/DEEPER_PRUNING.md b/src/docs/DEEPER_PRUNING.md new file mode 100644 index 0000000..b2ff6bc --- /dev/null +++ b/src/docs/DEEPER_PRUNING.md @@ -0,0 +1,382 @@ +# Deeper pruning in typhoon: ideas and how to test them + +Context: typhoon searches ~800x more nodes than Stockfish to reach a +nominally comparable depth on tactical middlegame positions (see session +notes / `head_reference/`). The gap traces mainly to how conservatively +typhoon's LMR/LMP/null-move gates are calibrated, not to a missing +technique -- see "Why past LMR experiments failed" below before trying +any of this blindly, because that pattern has repeated multiple times in +this codebase already. + +## Empirical evidence from TREEDUMP (2026-10-22) + +Built a matching diagnostic trace into both engines (`TREEDUMP` build +flag; see `docs/TREEDUMP_FORMAT.md` for the build commands for both +engines, the output format, and a Stockfish-side gotcha worth knowing +before re-running this -- piping commands into Stockfish via a closing +pipe races its input thread against the search actually starting and +silently produces a 0-node "search," observed ~90% of the time on this +box; hold stdin open past the search, e.g. `(printf '...'; sleep 2) | +./stockfish`) that logs every move-level decision +(full search / reduced / pruned-without-searching / null-move probe) +keyed by the move path from root, so the two engines' trees can be +diffed on the same FEN. Ran both on +`2q1r1k1/1ppb4/r2p1Pp1/p4n1p/2P1n3/5NPP/PP3Q1K/2BRRB2 w - -` at the +depth each engine first converges on the correct `f6f7+` tactic (`sd +11` for typhoon, `go depth 11-12` for Stockfish; single-threaded, +--cpus 1 / Threads 1 for both). + +**Node counts**: typhoon 96,080 nodes vs. Stockfish 5,666 nodes -- +~17x, consistent with the ~20x seen at a shallow `sd 4`/`go depth 4` +comparison and the ~800x seen at `sd 18`/`go depth 18` in the original +session transcript. The ratio grows with depth, as expected from a +per-ply branching-factor difference compounding multiplicatively. + +**Per-move-decision (`act=`) breakdown, same run** (counts are move- +decision lines, not nodes): + +| typhoon | count | | Stockfish | count | +|---|---|---|---|---| +| LMP (pruned, unsearched) | 212,501 | | FP-QUIET (futility, unsearched) | 4,126 | +| FULL | 81,776 | | LMR | 3,340 | +| NMP (null-move probe) | 24,394 | | FULL | 1,681 | +| LMR | 14,315 | | SEE-QUIET (unsearched) | 895 | +| EXT | 11,788 | | FP-CAP (unsearched) | 408 | +| NULLBAILOUT | 486 | | SEE-CAP (unsearched) | 329 | +| | | | PROBCUT | 164 | +| | | | NMP | 130 | +| | | | LMR-RESEARCH | 73 | +| | | | HIST-PRUNE (unsearched) | 57 | + +Three concrete, previously-inferred-from-reading-code points that this +data now confirms directly: + +1. **LMR volume gap, confirmed**: Stockfish reduces ~26% of its + move-decisions (3340/12622); typhoon reduces ~3% (14315/478340). + Matches idea #1 below -- not a hunch, a measured 9x gap in how often + the mechanism even fires, before even asking about magnitude. +2. **Stockfish's "cheap unsearched skip" is three separate, narrow + mechanisms; typhoon's is one wide one.** Stockfish splits shallow- + depth forward pruning into FP-QUIET/SEE-QUIET/HIST-PRUNE (futility + margin, SEE margin, continuation-history floor -- each independently + tunable, each catching a different shape of bad move) totaling + 5,078 decisions. typhoon's `ShouldLatePrune`/LMP is a single + FH-table lookup doing all of that discrimination through one gate, + and it accounts for 212,501 decisions on its own -- 44% of + typhoon's *entire* move-decision volume. This reframes idea #2 + (reinstate EFP) and idea #6 (continuation-history re-sweep): the + real gap may not be "typhoon lacks these mechanisms" so much as + "typhoon has fused them into one coarser gate," which is harder to + calibrate precisely than three narrow ones. Worth considering + *splitting* LMP back into independently-tunable sub-checks rather + than only adjusting its one shared threshold. +3. **ProbCut (idea #7) is confirmed to matter at non-trivial volume**: + 164 decisions in this one search, each capable of cutting an entire + node's remaining move list without searching it. Not a rounding + error. +4. **The Tord Romstad null-move bailout (`searchsup.c:3199`, + "NULLBAILOUT" above) is real and active** -- 0 fires at `sd 4`, 486 + at `sd 11`, confirming it's a deeper-search phenomenon (it requires + a parent move that was itself LMR-reduced, which barely happens at + shallow depth given point 1 above). + +See the conversation this came from for the methodology (path-keyed +move-by-move trace, `meld`-able logs) and a worked example of chasing +an apparent score anomaly down to its real (benign) cause -- a +checking-move extension tying alpha, not a bug -- using exactly this +instrumentation. + +## Why past LMR experiments failed (read this first) + +`lmr_testing/README.md`'s 2026-08-27 sweep record shows a flat pattern: +*every* knob tried moved EBF and solve-count in **opposite directions** -- +better branching factor, fewer solves, or vice versa, never both. +Table-only vs `+ONE_PLY` base, fail-high gate at 5/10/20, grandparent-PV +guard, Obsidian's formula vs Ethereal's, adding an "improving" signal -- +none was a free win. Two root causes, both still live in the current +codebase and worth internalizing before the next attempt: + +1. **Small-suite solve-count deltas are dominated by noise, not signal.** + The ECM.016 case study in that README: the "stable" baseline PV at + depth 11 was a shallow, unconvicted pick that flipped to the + objectively-correct move only past 24.5M nodes. A solve-count delta on + a position like that measures "which config happened to still be + wrong at the sample depth," not "which search is better." The fix + already exists in this repo (the three curated suites + + `head_reference`'s dual `sd`/`sn` logs) but it has to be used + correctly: trust `sd` deltas for tree-shape questions, `sn` deltas for + cost-effectiveness questions, and treat any suite smaller than ~90 + positions as capable of flipping ±2 solves from ordering noise alone + (see CLAUDE.md's "Dynamic move ordering experiments" section on + `ecm_ringers`). + +2. **Aggregate solve/EBF numbers are a lagging, confounded indicator of + a *local* decision.** The same CLAUDE.md section (from the later + move-ordering work, same lesson re-derived independently) is explicit: + "aggregate solve counts ... are too noisy to tune a single + move-ordering knob against ... instead, instrument the *local, + per-move outcome*." Every past LMR sweep in `lmr_testing/` tuned + purely against the aggregate number. None of them instrumented "of + the moves this new threshold newly admits for reduction/pruning, what + fraction actually fail high if searched at full depth" -- which is + the one measurement that's actually causally close to the knob being + turned. This is fixable with the existing `FH_TABLE_COLLECTION`/ + `MOVE_ORDERING_EVIDENCE_COLLECTION` infrastructure (see Section 3 + below) and should be done *before* touching an aggregate suite number + again. + +Net: the ideas below are listed with a test plan that leads with the +local/per-move measurement, uses `sd`/`sn` suite diffs as the fast +sanity filter, and reserves self-play/`match_play.py` for final +confirmation only -- specifically to avoid repeating the +aggregate-number-chasing pattern that burned the 2026-08-27 sweep. + +## The standing philosophical question + +typhoon's LMR/LMP admission is gated on an empirically-measured +"is this bucket almost never a fail-high" threshold +(`LMR_STATIC_ADMIT_PCT_THOUSANDTHS` = 0.5%, `searchsup.c`). Stockfish and +Crafty don't gate this way at all -- Crafty's own comment on its forward +pruning is explicit: *"this is classic forward-pruning and can certainly +introduce errors into the search. However, cluster testing has shown +that this improves play in real games"* (`crafty-25.2/search.c`, around +the FP/LMP block). Both ship it anyway because aggregate Elo over +realistic games is positive even though individual prunes are +provably sometimes wrong. + +This means the ideas below fall into two different categories, and they +need *different validation*, not the same one: + +- **Category A -- tighten the existing safe-by-construction machinery** + (bigger tables, more axes, better calibration). These stay validatable + by the FH-rate/silent-miss harness, because the goal is still "don't + get it wrong," just "be less overcautious about what counts as safe." +- **Category B -- deliberately accept a nonzero, known error rate** + because the aggregate payoff is worth it (Crafty/Stockfish's actual + model). For these, the FH-rate harness tells you *where* the errors + are, but **only self-play / `match_play.py` can tell you whether + shipping them is a net win** -- see the earlier conversation for why + that's not reducible to a suite diff. Don't skip straight to self-play + though; use the suite-diff step first to confirm the knob is doing + what you think before spending match-play budget on it (see the + Validation Ladder below). + +## Validation ladder (use for every idea below) + +1. **Wiring sanity**: `gmake DEBUG=1 TEST=1` + `debug_smoke_test.sh` -- + confirms no crashes/assert failures before anything else. +2. **Local/per-move instrumentation** (the step every past LMR attempt + skipped): for the exact population a new threshold newly admits, + measure "if NOT pruned/reduced, would this move have failed high at + full depth" via `FH_TABLE_COLLECTION`/`MOVE_ORDERING_EVIDENCE_COLLECTION`- + style collection builds. This is the only step that tells you *why* a + suite number moved, and it's what distinguishes "this threshold is + fine, the suite noise is unrelated" from "this threshold is genuinely + more dangerous." +3. **`sd 10` suite diff** against `head_reference` on all three curated + suites (`ecm_ringers`, `ecm_confident_quick`, `ecm_hard_quick`) -- + fast (minutes), tells you whether the tree actually shrank the way you + expect. Node count is the metric here, not solve count (too noisy at + this size, see above). +4. **`sn 5000000` suite diff**, same three suites -- tells you whether the + shrunk tree is cost-effective (same node budget, solved more or + fewer). This is where Category A ideas should land flat-or-better; a + regression here (not at `sd`) is the "shrank the tree but made it + worse" pattern that killed most of the 2026-08-27 sweep attempts. +5. **Only if 1-4 pass**: `match_play.py` gated match + (`LOWER95 >= 0.5`) against the current baseline DNA/eval, enough games + for the lower-confidence-bound to actually clear break-even (small-N + matches are noisy even with identical code, per existing notes). This + is mandatory for any Category B idea, and a nice-to-have confirmation + for Category A ideas before baking in. + +Never skip straight to step 5. Every idea below should die at step 2 or +3 if it's bad; step 5 is expensive and, on its own, doesn't tell you +*why* something failed, which is exactly the information you need to +iterate. + +--- + +## Ideas + +### 1. Increase LMR *magnitude* on already-admitted moves (not admission rate) + +Current: admitted moves get `-ONE_PLY` base, with +1/+2/+3 extra plies +reserved for the top 72%/5%/1% most-confident buckets +(`JOINT_EXTRA_TIER{1,2,3}_PCT_THOUSANDTHS`, `searchsup.c:685-692`). +Stockfish's reduction is continuous and unconditional: +`2872/128 * log(moveIndex)`, routinely 3-6 plies for ordinary late quiet +moves at depth 10+ -- more than an order of magnitude bigger than +typhoon's typical cut. + +This is the single highest-leverage lever given the ~800x node gap, and +also the one every past attempt already poked at (see `GetLMRReduction` +rewrite history in `lmr_testing/`). The past failures were on the +*admission* side (which moves get reduced), not magnitude alone, and +were tuned against aggregate solve-count, which is exactly what Section +"Why past experiments failed" says not to do. Worth retrying with the +corrected methodology: + +- Leave admission (`LMR_STATIC_ADMIT_PCT_THOUSANDTHS`) untouched. +- Replace the flat `_FlatTableExtraPlies` tier payout with something + continuous in depth and move-number, shaped like Stockfish's/Crafty's + log-product formula, for the *already-admitted* population only. +- Test: step 2 (does the newly-bigger-cut population's measured FH rate + stay near the existing ~0.4% baseline, or does it jump specifically in + the newly-added magnitude band?), then step 3/4. + +### 2. Reinstate a cheap, unconditional move-level futility skip (EFP) + +`searchsup.c:1094` documents that EFP ("extended futility pruning," a +near-free `eval + margin <= alpha` → skip the move outright, no search) +was removed and folded into the same FH-table-gated LMR/LMP path. +Stockfish still runs this as an *independent*, much cheaper layer +(`search.cpp:1185`, `:1221`) ahead of LMR, on almost every non-improving +quiet move near the leaves, with no empirical-safety gate. + +Reintroducing this as a separate, deliberately Category-B (unsound, +margin-based, no FH-table gate) layer -- rather than re-folding it into +the evidence-gated system -- restores a pruning mechanism typhoon +currently lacks entirely. Test: step 2 to characterize the error rate +this specific population would have had (useful data even though you're +accepting it), then step 3/4, then step 5 since this is unambiguously +Category B. + +### 3. Loosen null-move pruning's R factor / depth floor + +`SelectNullmoveRFactor` and the `NULLMOVE_SKIP_FH_CEILING_THOUSANDTHS` +gate (search.c:82-108) were already recalibrated once this session +(300 → 36000) after discovering the old value was tuned against the +wrong proxy quantity and was "essentially never firing." Worth checking +whether R itself (the reduction applied to the null-move verification +search) is still conservative relative to Stockfish's dynamic R +(`search.cpp` Step 10, scales more aggressively with depth and eval +margin). Given the recalibration just happened and already moved a real +number, this is a good candidate for the *same* sweep methodology +(`nullskip_sweep.sh` already exists) applied to R itself rather than +just the skip ceiling. + +Test: step 3/4 directly (R doesn't have a clean "admitted population" to +instrument the way LMR/LMP do -- the null-move verification search +itself is the ground-truth check), using the same sd8/sd11/sd12 +cross-sectional sweep methodology as the existing +`NULLMOVE_SKIP_FH_CEILING_THOUSANDTHS` calibration. + +### 4. Late Move Pruning: compare against Crafty's move-count-only shape + +typhoon's `ShouldLatePrune` (`searchsup.c:1188-1205`) gates on a static +per-remaining-depth max-FH% table (`325, 300, 250, 200, 150, 100, 80, 25, +6, 1, 0` thousandths) *and* a dynamic per-move-identity check, both +empirically calibrated. Crafty's LMP is pure move-count × depth, no +empirical gate at all: `order > LMP[depth]` where `LMP[i] = LMP_base + +pow(i + .5, LMP_scale)`, active through `LMP_depth = 16` plies (own +`data.c`). Crafty prunes **unconditionally** on move count/depth, far +deeper into the tree (16 plies vs. typhoon's effectively much shallower +reach given how fast `uLMPStaticMaxPctThousandths[]` tightens to +near-zero by remaining depth 10). + +Two sub-experiments, both worth separating: +- **4a (Category A)**: extend the existing FH-table-gated LMP's reach + (loosen the tail of `uLMPStaticMaxPctThousandths[]`) -- stays + validatable via step 2. +- **4b (Category B)**: add an unconditional move-count/depth LMP layer + on top (or instead of) the gated one, à la Crafty, deliberately + accepting the error rate. Needs step 5. + +`searchsup.c:1138-1149`'s own comment flags that there's currently *no +explicit floor or ceiling* on how deep LMP can fire or how early at the +root it can trigger -- that's worth hardening (an explicit depth floor, +the way Crafty's `LMP_depth` is an explicit, tunable cutoff) regardless +of which sub-experiment you pursue, so a future bad interaction with +some other mechanism doesn't silently prune at the root. + +### 5. SEE-based pruning of bad captures earlier/more aggressively + +Stockfish's move-loop futility (`search.cpp:1232`, +`!pos.see_ge(move, -23*lmrDepth*lmrDepth)`) prunes losing captures with +a margin that scales quadratically with the already-reduced depth -- +i.e. the deeper a losing capture already got reduced, the more freely it +also gets SEE-pruned outright. typhoon's eligibility check +(`CanWeReduceOrPruneMove`, `searchsup.c`) already restricts +captures/promotions to SEE-negative ones before they're even eligible, +but doesn't appear to apply a depth-scaled SEE *margin* the way SF does +-- worth checking whether a losing capture that clears the existing +SEE-negative bar by a wide margin (badly losing, not marginally losing) +could be pruned more aggressively than one that's only slightly losing. + +Test: step 2 (bucket by SEE-loss magnitude, not just negative/ +non-negative, and check FH rate per bucket -- likely to show the same +kind of monotonic signal the countermove-evidence calibration did), then +3/4. + +### 6. Continuation-history-based pruning (new mechanism -- corrected) + +**Correction (2026-10-22): this item previously claimed typhoon already +had a `history < -4136*depth`-style skip "mentioned in the 2026-08-29 +move-ordering writeup."** That's wrong -- `-4136` is Stockfish's own +constant (`search.cpp`'s continuation-history pruning `continue`, +confirmed present only in `search.cpp`, grepped and absent everywhere +in typhoon's own sources). The 2026-08-29 work added a continuation- +history *table* (`g_ContinuationHistory`) for move-*ordering* +comparisons (`SelectBestWithHistory`) -- it has never been used to +*prune* (skip a move without searching it) at all. The TREEDUMP +empirical data above confirms this independently: Stockfish's +HIST-PRUNE bucket (57 decisions) has no typhoon counterpart in the +`act=` breakdown because there is no code path to tag. + +So this is actually **idea #7's sibling**: a structurally absent +mechanism, not an existing one needing a re-sweep. Given typhoon +already tracks the evidence this would need (`g_HistoryCounters` + +`g_ContinuationHistory`, same tables the countermove-evidence +calibration already validated for ordering), adding a pruning check on +top is comparatively cheap to wire up -- the hard part (evidence +infrastructure) already exists; what's missing is the `continue`-style +skip itself plus a threshold, calibrated the same way as everything +else here. + +Test: step 2 first and foremost here, since there's no existing +behavior to compare against -- bucket candidate moves by their +existing combined history+continuation evidence (log-ish bands, same +shape as the countermove-evidence calibration) and measure FH rate per +bucket before picking a threshold, rather than guessing one and +sweeping blind. Then 3/4, and 5 if the chosen threshold is deliberately +loose enough to be Category B. + +### 7. Multi-cut / ProbCut-style forward pruning at CUT nodes (new mechanism) + +Stockfish's "Step 11 internal iterative reductions" and ProbCut +(`search.cpp`, around line 1046-1090) are forward-pruning mechanisms +typhoon doesn't appear to have an equivalent of at all: try a handful of +moves at reduced depth with a raised beta, and if enough of them fail +high, cut the whole node without searching the rest -- a different shape +of pruning than LMR/LMP (both of which operate move-by-move) because it +operates on an aggregate signal across a small sample of moves at the +node. This is a bigger lift than tuning an existing threshold (new code, +not a constant change), so it belongs later in the queue, but it's worth +flagging as a structurally different -- not just more aggressive -- +pruning technique that's currently entirely absent, rather than +something typhoon has a weaker version of. It's unambiguously Category +B (ProbCut is explicitly a statistical/unsound cut) and needs step 5. + +--- + +## Summary table + +| # | Idea | Category | Fast test (step) | Needs self-play? | +|---|------|----------|-------------------|-------------------| +| 1 | LMR magnitude on admitted moves | A (if gated) / B (if unconditional) | 2, 3, 4 | only if B | +| 2 | Reinstate cheap unconditional EFP | B | 2 (diagnostic only), 3, 4 | yes | +| 3 | Null-move R factor sweep | A (self-verifying) | 3, 4 (sweep script exists) | confirm only | +| 4a | Extend gated LMP's tail | A | 2, 3, 4 | confirm only | +| 4b | Add unconditional LMP layer | B | 3, 4 | yes | +| 5 | Depth-scaled SEE pruning margin | A | 2, 3, 4 | confirm only | +| 6 | Continuation-history pruning (new mechanism, corrected 10-22) | A (if gated) / B (if loose) | 2, 3, 4 | only if loose | +| 7 | Multi-cut / ProbCut (new mechanism) | B | 3, 4 (after implementing) | yes | + +Recommended order: **3 → 1 → 4a → 5 → 6 → 2 → 4b → 7** -- cheapest/ +lowest-risk (re-sweeping an existing, already-partially-recalibrated +knob) first, brand-new mechanisms (6, 2, 4b, 7) later since those need +new code plus the most expensive validation (step 5 for the Category B +ones). #6 moved down from its original #2 slot in this ordering once +it was corrected from "re-sweep an existing threshold" to "build a new +one" -- it's no longer the cheap win it looked like. diff --git a/src/docs/TREEDUMP_FORMAT.md b/src/docs/TREEDUMP_FORMAT.md new file mode 100644 index 0000000..ecc4325 --- /dev/null +++ b/src/docs/TREEDUMP_FORMAT.md @@ -0,0 +1,191 @@ +# 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. + +## 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). |
