diff options
| author | Scott Gasch <[email protected]> | 2026-10-24 09:07:03 -0700 |
|---|---|---|
| committer | Scott Gasch <[email protected]> | 2026-10-24 09:07:03 -0700 |
| commit | 5f901d737b17c5f99b6e456d6c0c7d5e3c093dc4 (patch) | |
| tree | 6601dadbd36c8f45991c5dd821a3dbb2059baafe /src/docs | |
| parent | 69525eb2f42ea9cca8255f6cc3b85e6b1312fd05 (diff) | |
More aggressive move reductions; Wilson bound overrides static signal when available
SPRT playtest (2000 games, sd/depth matched): -535 =875 +590, score=0.514,
llr=+1.04 (floated around +1.0 the whole run, never went negative) toward
H1=+2.94. Not a confirmed win, but searches meaningfully deeper (avg depth
14.35 vs 13.50, EBF 3.131 vs 3.305) at no measurable strength cost -- worth
banking and continuing to accumulate games against.
Co-Authored-By: Claude Sonnet 5 <[email protected]>
Diffstat (limited to 'src/docs')
| -rw-r--r-- | src/docs/DEEPER_PRUNING.md | 513 | ||||
| -rw-r--r-- | src/docs/TREEDUMP_FORMAT.md | 95 |
2 files changed, 601 insertions, 7 deletions
diff --git a/src/docs/DEEPER_PRUNING.md b/src/docs/DEEPER_PRUNING.md index b2ff6bc..e71cf21 100644 --- a/src/docs/DEEPER_PRUNING.md +++ b/src/docs/DEEPER_PRUNING.md @@ -86,6 +86,315 @@ an apparent score anomaly down to its real (benign) cause -- a checking-move extension tying alpha, not a bug -- using exactly this instrumentation. +### Adding a third engine: Crafty (2026-10-23) + +Single-position comparisons can't distinguish "this is a real +engine-independent pruning norm" from "this is just how Stockfish +happens to be tuned." Crafty (`~/programming/chess/crafty-25.2`, HCE, +no NNUE) now speaks the same TREEDUMP format (see +`docs/TREEDUMP_FORMAT.md`'s new Crafty section) specifically to add a +second, independently-play-tested reference point with a *much weaker* +eval than typhoon's own NNUE. The logic: if Crafty's LMR/LMP/futility +magnitudes still land near Stockfish's despite a cruder eval backing +the search, that's a better argument for "there's a roughly right +amount of forward pruning, independent of eval strength" than agreement +between two strong-eval engines would be -- agreement there could just +as easily mean "strong eval permits more aggressive pruning," not +"this magnitude is universally right." + +A 20-position batch (7 opening / 7 middlegame / 6 endgame, all >=8 +pieces to stay clear of heavy EGTB-probe territory, drawn from +`tests/cross_sectional_200k.ep_`) at `sd 6` across all three engines is +the first cut at this -- see the conversation/session this came from +for the resulting per-engine LMR-rate and EBF comparison once run. + +**Caveat already known going in, from reading Crafty's `search.c` +directly**: Crafty's FP ("futility") check is raw-material-based +(`MaterialSTM(wtm) + FP_margin[depth] <= alpha`), not a full static-eval +call the way typhoon's and Stockfish's futility-flavored checks are -- +cheaper and cruder. And Crafty's FP/LMP forward-pruning is a `break`, +not a `continue`: once it fires on one move at a node, every remaining +move in that node's move list is abandoned too, not just that one move +(confirmed by reading `search.c` directly, matches the engine's own +comment this investigation started from). Both engines' `act=LMP`/ +`act=FP-QUIET` counts are therefore not directly comparable to +Crafty's -- don't read Crafty's count as "N individually-pruned moves." + +### Correction (2026-10-23, same day): typhoon's own batch runs were also contaminated + +The first full batch run (numbers below were originally drawn from it, +now corrected) had a second bug symmetric to the Crafty one above, this +time in typhoon itself. `go` sets `ePlayMode = I_PLAY_WHITE/BLACK` +(`command.c:1396`, standard xboard semantics: "go" means "you now play +this color"), and the main loop (`main.c:837`) auto-starts a background +`Ponder()` call the instant the real move is delivered -- its own, +separate `SEARCHER_THREAD_CONTEXT` (`root.c:1873`). In batch mode with +no further input queued, that ponder search just kept running and +writing to the same shared `treedump.log` until EOF finally killed the +process, inflating every count by a position-dependent, unpredictable +amount (confirmed by tagging `TDMove`'s `ctx` pointer: one pointer's +LMP count matched the engine's own "Overt move skips" report exactly; +a second pointer -- the ponder context -- contributed another 1-4x on +top, varying per position with no fixed ratio). **Fix: send `easy`** +(`command.c:453`, sets `g_Options.fShouldPonder = FALSE`) as part of +the batch invocation -- confirmed byte-exact match against the engine's +own internal counters afterward. Stockfish and Crafty were checked and +are not affected (UCI's `go depth N` with no `go ponder` doesn't +auto-continue; Crafty's `ponder off` from the earlier fix already +covers it). `run_batch.sh` now includes `easy` in every typhoon +invocation. All numbers in this section are from the corrected rerun; +the original run's typhoon totals were roughly 2x inflated (859k raw +MOVE/RESULT lines dropped to 456k after the fix). + +### 20-position batch results (2026-10-23, corrected) + +Ran all three TREEDUMP-instrumented engines (single-threaded, `sd 6` / +`go depth 6`) across 20 positions from `tests/cross_sectional_200k.ep_` +(7 opening / 7 middlegame / 6 endgame, all >=8 pieces to stay clear of +heavy EGTB territory), parsed into a common schema, and aggregated +`act=` counts, node counts, and LMR admission/magnitude per engine per +phase. Script: `/tmp/typhoon/treedump_crafty_sf/analyze.py` (scratch, +not checked in); raw logs at `/usr/local/tmp/typhoon_treedump/` (not +checked in, 38MB). + +**Build-time trap hit along the way, worth remembering for any future +Crafty TREEDUMP run**: driving Crafty with bare `force`/`go` (no prior +`xboard` or `ponder off`) does NOT behave like typhoon's/Stockfish's +batch invocations. Crafty's `force` command only toggles force-mode +when its internal `xboard` flag is already set (`option.c:727-735`); +without it, bare `force` falls through to a "usage: force <move>" +no-op, and `go` then runs under Crafty's own default-time-control +pondering behavior instead of being capped by `sd`. This produced a +14GB, 110-million-line `treedump.log` for a single opening position +before being killed. **Fix: send `ponder off` as the first command** +(confirmed interactively) -- cleaner than engaging full `xboard` mode +for this single-`go`-per-position use case, and produces an identical +tree to the correctly-xboard-moded version. `run_batch.sh`'s current +version already has this fix plus a 2M-line trip-wire abort and a +`timeout 30` on every engine invocation as defense in depth. + +**EBF (effective branching factor, `mean_nodes^(1/6)`, same depth=6 for +all three -- RESULT-node counts only, qsearch excluded per the Known +Gaps section above):** + +| | typhoon | crafty | stockfish | +|---|---|---|---| +| mean nodes/position | 6,754 | 2,187 | 467 | +| EBF | 4.35 | 3.60 | 2.79 | + +typhoon searches ~3.1x more nodes than Crafty and ~14.5x more than +Stockfish at this depth -- same direction as the original single- +position finding, now confirmed at n=20 across all three phases, though +the magnitude is smaller than the (contaminated) first pass of this +batch suggested -- see the correction above. + +**The standing hypothesis going into this batch -- that Crafty and +Stockfish, as two independently-play-tested engines, would show similar +LMR amounts, pointing at a roughly engine-independent "right" amount -- +did not hold.** typhoon and Crafty cluster together, far below +Stockfish, on both admission rate and magnitude: + +| | typhoon | crafty | stockfish | +|---|---|---|---| +| LMR admission rate (% of MOVE decisions) | 2.11% | 3.36% | 22.36% | +| LMR magnitude, mean plies when reduced | 1.23 | 1.32 | 2.44 | + +This holds per-position, not just in aggregate -- Stockfish is +13-37% in every one of the 20 positions; typhoon and Crafty never +exceed ~5% in any of them (see the per-position table in the session +transcript this came from). Broken out by phase, the same ordering +holds in opening/middlegame/endgame alike, with LMR% roughly flat per +engine across phases (typhoon ~1.9-3.0%, Crafty ~2.7-3.9%, Stockfish +~13-26%) -- not a phase-dependent effect. + +**Why Crafty's tree is still 6x smaller than typhoon's despite having +~similar LMR**, and the resulting reframe: Crafty does almost all of +its forward-pruning via outright skips, not LMR -- `FP-QUIET` (34%) + +`LMP` (22%) = 56% of its move-decisions are unsearched skips, close to +typhoon's 59% LMP-alone figure. But because Crafty's skip is a `break` +(kills the rest of the move list at that node) rather than typhoon's +`continue` (skips just the one move), each Crafty skip event compounds +into a much larger tree-size reduction per occurrence than an +equal-count typhoon LMP figure would suggest. Stockfish's combined +skip categories (FP-QUIET/FP-CAP/SEE-QUIET/SEE-CAP/HIST-PRUNE) land in +a similar 36-52%-of-move-decisions range across phases -- comparable +*skip volume* to both typhoon and Crafty -- but Stockfish *also* layers +aggressive LMR (13-37%) on top of that, which neither of the other two +engines does at meaningful volume. + +**Revised framing for idea #1 (LMR magnitude) and the recommended +order**: the data does not support "typhoon's LMR should converge +toward a shared Crafty/Stockfish amount" as cleanly as hoped going in +-- Crafty's own LMR admission/magnitude is close to typhoon's, not to +Stockfish's. The better-supported, higher-priority lever coming out of +this batch is the **break-vs-continue skip mechanism itself** +(effectively a new idea, call it **#8**): no amount of threshold +tuning on typhoon's current `continue`-based LMP can reproduce the +per-skip tree-size compounding that Crafty's node-abandoning `break` +gets "for free." This is a structural difference, not a calibration +one, and is unambiguously Category B (deliberately accepting that a +late move which *might* have been fine now never gets tried at all, +not just the specific move that triggered the skip) -- needs the full +step-5 validation ladder (self-play, not just suite diff) before +shipping, precisely because it changes the *shape* of what's being +accepted as an error, not just the threshold. + +**Correction (2026-10-23, same day): idea #8 explains Crafty's small +tree, but NOT Stockfish's.** Checked directly against Stockfish's +`search.cpp` move loop (~line 1241-1337): every one of its +forward-pruning skips (`FP-CAP`, `SEE-CAP`, `HIST-PRUNE`, `FP-QUIET`, +`SEE-QUIET`) is a plain `continue`, same per-move-independent semantics +as typhoon's own LMP, not Crafty's `break`. The one thing that looks +break-adjacent, `mp.skip_quiet_moves()` (Stockfish's actual LMP +equivalent -- pure movecount threshold, `moveCount >= (3 + +depth*depth)/(2-improving)`, same shape as Crafty's `LMP[]` table), is +strictly softer than Crafty's: it only stops the move picker from +*yielding further quiet moves*, while captures/checks after that point +still get tried individually through the normal continue-gated path. +So Stockfish's much smaller tree is not explained by any break-like +shortcut at all -- it comes from sheer LMR admission rate and magnitude +(22% of moves at ~2.4 plies mean, both roughly an order of magnitude +above typhoon's/Crafty's own figures above), individually `continue`- +gated the whole way through. + +**Net effect on priority**: idea #8 (break semantics) and idea #1 (LMR +magnitude/volume) are now understood as two *independent*, +non-competing levers rather than one superseding the other -- Crafty +demonstrates break-based skipping works (for Crafty's eval/search +combination), Stockfish demonstrates aggressive continue-gated LMR +works (for Stockfish's), and nothing here shows they're mutually +exclusive for typhoon. Both stay in the queue; #8 is still the newer, +less-explored one and #1 is still worth revisiting on Stockfish's own +terms (not "match Crafty+Stockfish", just "typhoon's LMR volume is an +order of magnitude below a strong continue-gated reference"), so the +recommended order's #8-ahead-of-#1 placement stands, but not because +#1 was invalidated -- only because its original two-engines-agree +rationale was. + +### The leftover-population question (2026-10-23) + +Scott's memory going in: typhoon's `fIsLeftoverMove` gate (base +eligibility requirement in `CanWeReduceOrPruneMove`, `searchsup.c:890- +985`) exempts the hash move, good (non-losing) captures, killers, and +countermove-matches-above-threshold from reduction/pruning consideration +entirely -- unlike Crafty (`order > 1`) and Stockfish (no separate tier +gate, just the reduction formula itself), which apply their +pruning/reduction machinery far more broadly. Measured from the +corrected 20-position batch (typhoon side, excluding `NMP`/ +`NULLBAILOUT` diagnostic lines which aren't moves from the move list): + +| | count | % of real moves tried | +|---|---|---| +| `LMP` (guaranteed leftover, pruned) | 188,465 | 63.4% | +| `LMR` (guaranteed leftover, reduced) | 6,772 | 2.3% | +| **leftover-tier, lower bound** | **195,237** | **65.7%** | +| `FULL` (searched at nominal depth) | 89,010 | 29.9% | +| `EXT` (extended) | 13,134 | 4.4% | +| **non-leftover-tier, upper bound** | **102,144** | **34.3%** | + +So at most ~34% of real moves tried are exempt from reduction/pruning +consideration at all -- this is an upper bound, not a clean number, +since the current `TDMove` tagging can't distinguish "never eligible" +(hash move, good capture, PV-node) from "eligible but exempted" +(killer/countermove match) from "eligible, admission threshold missed." +A real population summary (median/stdev per node, not just an +aggregate percentage) and the by-exemption-reason breakdown would need +a small addition to `CanWeReduceOrPruneMove`'s exemption checks to +surface *which* check excluded a given move into `TDMove`'s otherwise- +unused tagging room -- not yet done, flagged as the natural next step +if this motivates code changes. + +### Ideas added 2026-10-23 (Scott + this session, following the batch) + +- **#9 -- Replace the hard `fIsLeftoverMove` gate with a graduated + eligibility tier.** Scott: "reduce the GOOD_MOVE+ moves, but less + than the leftovers" and "reduce the leftovers more aggressively" -- + two sides of the same structural fix. Rather than binary + (leftover vs. exempt), a move's distance from the `GOOD_MOVE` + boundary could scale a light reduction for near-boundary "good" + moves on top of the existing (and, per idea #1, likely + under-aggressive) treatment for true leftovers -- this is the + mechanism underlying both halves of the idea at once, and is more + surgical than just moving the boundary (which would only reclassify + moves, not let the two curves differ in shape). Directly motivated + by the ~34% exempt-population measurement above: Crafty/Stockfish + don't carve out an exempt tier at all, their reduction formulas just + naturally taper to near-zero for early/good moves. +- **#10 -- Apply the existing FH-rate evidence-calibration methodology + to the *exempted* population, not just the leftover one.** Unknown + whether the ~34% exempt moves are uniformly safe to leave untouched, + or whether a sub-population (killer/countermove-match specifically, + as opposed to hash-move/good-capture) would tolerate #9's light + reduction without a solve-rate cost. Needs the same per-node + exemption-reason tagging #9 depends on before picking a formula. +- **#11 -- Guard against "deterministic re-pruning" / horizon + blindness from repeated reduction across iterative-deepening + iterations (Scott, 2026-10-23).** The concern: if a move is + (mis-)judged bad by the gating signals (late/gap/dumb/etc, all of + which can correlate with each other and with history-table feedback) + and is reduced or pruned at nominal depth 4, then again at 6, 8, 10, + ... with the *absolute residual depth it actually gets searched at* + staying flat or shrinking rather than growing, the engine can miss a + real deep tactic indefinitely, no matter how deep the nominal search + goes -- existing PVS re-search-on-beating-alpha only catches "this + looks promising," not "the residual depth was too shallow to see the + refutation at all," which looks identical to a correctly-judged bad + move from the outside. + + The concrete, checkable property this implies: for any move, residual + depth (nominal depth minus total reduction) must diverge as nominal + depth grows, and grow fast enough to eventually resolve a tactic of + realistic sharpness -- satisfied automatically by a *sublinear* + (e.g. logarithmic, like Stockfish's `log(depth)*log(moveIndex)`) + reduction-magnitude formula, but NOT guaranteed by a formula with a + hard "leave only K plies" clamp. Checked directly: Crafty's own clamp + (`InitializeLMR`, `init.c:1162`: `Min(LMR[d][m], Max(d-1-LMR_rdepth, + 0))`, `LMR_rdepth=1`) caps reduction so residual depth can shrink to + as little as ~1-2 plies at large nominal depth regardless of how deep + the overall search goes -- this wasn't visible in the sd6 batch data + (where that clamp binds at a harmless d-2=4 ceiling) but would matter + at the real game depths (16+) this whole investigation started from. + **Typhoon's current scheme is, by accident rather than design, safer + on this specific axis than Crafty's or Stockfish's**: the tiered + `JOINT_EXTRA_TIER{1,2,3}` scheme caps total reduction at a fixed small + constant (base -1 ply, up to +3 extra = -4 total) regardless of + nominal depth, so residual depth grows 1:1 with nominal depth minus a + constant -- unbounded, never stalls. Idea #1 (increase LMR magnitude + toward Stockfish's/Crafty's own figures) directly trades away this + safety property unless done deliberately: a depth-scaling or + move-count-scaling magnitude increase needs its own explicit residual- + depth floor that *grows* with nominal depth (not just a fixed small + constant floor the way Crafty's `LMR_rdepth` is), or it risks + reintroducing exactly the failure mode being guarded against. + + Not yet designed: what the growing floor should look like, or how to + verify the failure mode isn't already happening somewhere in + typhoon's existing (small-magnitude) reduction scheme. A cheap + diagnostic worth running before any magnitude change ships: across a + deep (16+ ply) iterative-deepening search on sharp tactical + positions, log whether the PV ever flips late (a previously-reduced + move getting picked up only at a much deeper iteration) as a weak + signal that early iterations were systematically missing it -- + absence of late PV flips is consistent with either "no problem" or + "still missing it even at the deepest iteration tried," so this is + suggestive, not conclusive, but cheap to collect alongside whatever + else idea #1/#9's validation ends up measuring. + +**Caveats on this batch, before leaning too hard on it**: (1) n=20 is +still small enough that a handful of positions could be skewing the +per-phase breakdowns -- worth widening if any of the above motivates +real code changes. (2) The EBF formula here (`mean_nodes^(1/6)`) +assumes uniform branching at a fixed depth; it's internally comparable +across the three engines (same depth, same node-counting convention) +but is a simplification, not a reconstructed per-ply fanout. (3) None +of this says anything about whether Stockfish's specific LMR formula +would help typhoon if transplanted wholesale -- only that the +"triangulate via two agreeing reference engines" premise this batch +was designed to test turned out not to apply to LMR specifically (it +might still apply to other mechanisms; this batch's data would need +re-aggregating per-mechanism to check, e.g. null-move R, which wasn't +analyzed in isolation here). + ## Why past LMR experiments failed (read this first) `lmr_testing/README.md`'s 2026-08-27 sweep record shows a flat pattern: @@ -372,11 +681,201 @@ B (ProbCut is explicitly a statistical/unsound cut) and needs step 5. | 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 | +| 8 | Node-abandoning ("break") LMP semantics, à la Crafty (new mechanism, added 2026-10-23) | B | 3, 4 | yes | + +Recommended order (revised 2026-10-23 after the 20-position 3-engine +batch, see above): **3 → 8 → 4a → 5 → 1 → 6 → 2 → 4b → 7** -- #8 moved +up from unlisted to #2 priority because the batch data undercuts #1's +original rationale (Crafty's LMR doesn't actually match Stockfish's, +so "converge toward a shared amount" isn't well-supported) while +directly supporting #8 (Crafty's much smaller tree despite +typhoon-like LMR is best explained by its break-not-continue skip +semantics, not by LMR at all). #1 is still worth doing eventually +(Stockfish's own magnitude is still larger than typhoon's on its own +terms) but no longer has two engines backing it as "the" right amount. +#6 stays down near the bottom since it was already corrected from +"re-sweep an existing threshold" to "build a new mechanism" and nothing +in this batch changes that. + +--- + +## Session status as of 2026-10-23 (end of day): idea #1 implemented, self-play launched + +A single long session turned idea #1 (increase LMR magnitude on +already-admitted moves) from a proposal into actual code, found and +fixed two real bugs along the way (one in Crafty, one in typhoon +itself), and ended with a self-play match in flight. Summary, in +roughly chronological order, for picking this back up tomorrow: + +### What shipped (uncommitted, in the working tree as of session end) + +**The magnitude formula itself** (`searchsup.c`, `_FhBasedExtraPlyTicks` ++ `GetLMRReduction` rewrite): replaces the old flat Crafty-shaped +`(depth, moveNum)` lookup with `extra_plies = k(depth) * +-log10(predictedFH% / 100)`, normalized against the existing 0.400% +baseline so an exactly-average move earns ~0 extra (just the base +`-ONE_PLY`) and only below-baseline (safer-predicted) moves earn +positive extra, continuously, no threshold cliff. `k(depth) = +0.32*ln(depth) + 0.48`, fit by direct regression against Stockfish's +*own* real reduction schedule across a depth 2-13 x move 2-32 grid +(R²=0.965) -- not a guessed shape. `depth` is capped at 13 before +computing `k` AND the table lookup itself independently saturates +there too (`_ShipDepthBucket`), so both halves plateau together past +that point -- this is deliberate, not an oversight: raw collection +data showed tries per cell falling from 56,021 at depth 13 to literal +zero by depth 20 (see the leftover-population section above), so the +formula is designed to stop extrapolating exactly where the evidence +backing it runs out. That, combined with a flat total-reduction +ceiling past depth 13, is this session's concrete answer to the +"deterministic re-pruning across iterations" failure mode discussed +at length early on (idea #11, informal number -- never got a +permanent slot in the numbered list, but is now load-bearing in the +shipped formula): residual depth (nominal minus the now-flat cap) +diverges without bound as nominal search depth grows past 13, so a +heavily-reduced move is guaranteed to eventually get a real look, no +matter how deep the overall iterative-deepening search goes. + +**Works in exact quarter-ply ticks** (`ONE_PLY`/`QUARTER_PLY` fixed- +point), not whole plies -- the regression was fit in continuous plies +and truncating to whole-ply resolution in the engine would have thrown +most of that away for no reason (Scott's own observation, mid-session). + +**The admission-side retirement**: `LMR_STATIC_ADMIT_PCT_THOUSANDTHS` +(the old static-table veto that could refuse the base `-ONE_PLY` +outright) is gone. Admission is now "any move in the leftover tier," +full stop -- magnitude, not admission, is where the FH% signal does its +work now, matching how neither Crafty's nor Stockfish's own formula has +an admission cliff either. + +**The dynamic per-move-identity blend** (Wilson upper confidence bound, +not the raw `FailHighs/Attempts` ratio): `GetMoveFailHighWilsonUpperBoundThousandths` +(`dynamic.c`) looks up a precomputed table (`g_uWilsonUpperBoundThousandths`, +bucketed by `FastLastBit(Attempts|1)` -- branchless bit-length, no +runtime divide/sqrt -- and `MIN(FailHighs,3)`) and the result is +combined into the main formula as `MIN(static_table_FH%, wilson_bound)` +-- a single substitution into the one formula, not a second branch or +veto. This was a long design discussion (see below) that landed on: +dynamic evidence of *safety* (a real, well-evidenced zero-fail-high +streak on this exact move identity) is allowed to win over a more +cautious static reading; dynamic evidence of *danger* (a real fail-high +history) is deliberately **not** allowed to decrease the reduction +below the base `-ONE_PLY` -- Scott's reasoning: the table's own depth +axis already shows shallower remaining depth correlates with *higher* +observed FH%, so "reduce less / search deeper" in response to a danger +signal has no causal footing to stand on, and neither Crafty nor +Stockfish has anything resembling a dedicated exemption rule for this +either (Stockfish's closest analog, the history-heuristic `statScore` +term, is one continuous signal inside one formula, never a separate +branch) -- "let's not invent our own heuristics" was the explicit +governing principle for this whole design pass. + +Measured effect of the Wilson blend alone (`sd 10`, HCE, on top of the +magnitude formula): node counts dropped a further 0.9-25.8% across the +three curated suites (Scott had predicted it would never fire at all, +given his assumption `MIN` always picks the static side -- wrong, +because the dynamic per-move-identity table isn't reset within a +search, and a single deep `sd 10` tree revisits the same coarse +`(from,to,piece)` move identity often enough, across many lines, to +accumulate real evidence within one position's own search). `sn 5M` +(fixed node budget, HCE): 94/191 -> 96/191, net +2 across the three +suites -- a real if modest improvement, not just inert. + +### Two real bugs found and fixed along the way (both already covered above, cross-referenced here for the session-summary view) + +1. Crafty's `ponder off` requirement for TREEDUMP batch runs (background + pondering via a second `SEARCHER_THREAD_CONTEXT` after each `go`, + contaminating the shared `treedump.log`) -- see "Correction + (2026-10-23)" under the Crafty section above. +2. typhoon's own `easy` requirement for the same reason (`go` auto- + enters `I_PLAY_WHITE/BLACK` mode, triggering a background + `Ponder()` call) -- see the matching correction a few paragraphs + later. Both fixed by adding the missing command to + `run_batch.sh`; both were silently inflating every typhoon-side + TREEDUMP number in the first batch run by roughly 2x before being + caught via a `ctx` pointer mismatch in the LMP counters. + +### Measured but NOT yet implemented + +**`IS_CAPTURE(mvHash)`** (was the hash move at this node a capture?): +measured via a new one-off collection macro (`HASHCAP_COLLECTION`, +`GNUmakefile`/`chess.h`/`search.c`/`searchsup.c`/`script.c` -- a new +`PLY_INFO.fHashMoveIsCapture` field set once per node, two small +`[2][2]` counter tables bucketed by `(hash move is capture, node type +is CUT)`, printed by `_PrintSuiteReport`). Real, substantial effect, +roughly halving leftover-move FH% in both node-type slices (500- +position sample, `sd 8`, tries from 40K to 3.1M per cell -- not noise): + +| hash move | node type | tries | FH% | +|---|---|---|---| +| quiet/none | ALL/PV | 3,156,288 | 0.602% | +| quiet/none | CUT | 1,842,368 | 5.450% | +| capture | ALL/PV | 87,457 | 0.362% | +| capture | CUT | 40,826 | 2.467% | + +Not yet wired into the reduction formula -- Scott's instinct (correct, +on reflection) was to measure first rather than assume, specifically +because this signal isn't fully independent of the table's own "dumb" +(hanging-material) axis and he wanted real numbers before trusting it. + +**The CUT-vs-ALL node-type side-finding**: the same table above shows +something that directly bears on the Stockfish-reduction-at-CUT-nodes +discussion earlier in this doc -- among leftover moves that survive +long enough to *be* leftover (i.e. no early cutoff happened at that +node), a **CUT**-labeled node's leftover moves fail high roughly **9x +more often** than an **ALL/PV**-labeled node's (5.450% vs 0.602%, +quiet-hash slice; 2.467% vs 0.362%, capture-hash slice). That's the +opposite direction from Stockfish's own formula, which reduces *harder* +at CUT than at ALL -- consistent with the "sneaky ALL node in CUT +clothing" argument raised earlier in this session (a CUT prediction +that's survived past the early moves without cutting isn't neutral +information, it's evidence the label was probably wrong, and the +survivor population is measurably *more* dangerous than an honestly- +labeled ALL node, not less). Explicitly deferred for now (Scott: "let's +skip it... I can't wrap my head around [Stockfish's own choice]") -- +flagged here because it's a real, substantial, already-measured number +that should inform whichever way this gets revisited, not a hunch. + +### The open table-design tension, for whenever the re-bake happens + +Both of the above are real, low-cardinality, general-purpose signals +-- the kind that "want" to live in the static table rather than bolted +on at runtime. But the shipped table is already `12x11x11x17x11` ≈ +268K cells; a full 4x expansion (2 more binary axes) quadruples that +and thins out cells that are already sparse past depth ~13 (see the +leftover-population section). Scott's own framing at session end: since +both new signals look roughly *multiplicative* on FH% rather than +interacting in some complicated way with the existing five axes (the +capture effect was a consistent ~2x cut across both node-type slices, +not wildly different magnitudes), a *correction factor* learned from +exactly this kind of 2-cell measurement, applied on top of the existing +5D lookup, is worth considering as a cheaper alternative to adding full +new dimensions -- same data, same collection run, folded in as a +multiplier instead of new axes. Not decided; revisit once the self-play +result (below) is in and there's a real "do we even keep this +direction" answer first. + +### What's running right now, and what happens next + +A self-play match is in flight (`eval_tune/test_vs_head.sh`, two +hand-built wrapper scripts since the script's own `NNUE_WEIGHTS=` +handling only NNUE-wraps the candidate side and this match needs NNUE +on both): `typhoon_baseline_nnue` (git HEAD `69525eb`, unmodified, i.e. +today's starting point, NNUE eval) vs. `typhoon_wilson_nnue` (HEAD + +everything in this section, NNUE eval), `--st 4`, `--elo0 0 --elo1 15`, +2000-game cap, label `nnue_pruning_check`. This answers: given the same +NNUE eval (the actual bottleneck motivating this whole investigation -- +NNUE runs at ~400-500K nps vs HCE's ~1.3M+, and "buy a faster CPU" isn't +an option), does today's more-aggressive reduction win or at least +break even against the pre-session baseline? -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. +If it works out: commit, update `head_reference` (including its NNUE +subtree, which doesn't exist yet -- "we just merged the NNUE branch +today and didn't update head reference" per this session), then a +*second* match (NNUE-with-new-pruning vs. the HCE-at-HEAD reference, +same eval-architecture comparison this project already "knows" HCE +currently wins at `--st 4`) to answer the actual motivating question: +is the node-count saving from today's work enough to close any of the +gap against HCE's raw 3x speed advantage (observed ~3 full plies deeper +at `sd 4`), or at least move the needle. Then: revisit `IS_CAPTURE +(mvHash)`, node type, and the table-vs-correction-factor question above +with a real strength signal in hand instead of suite-solve-counts alone. diff --git a/src/docs/TREEDUMP_FORMAT.md b/src/docs/TREEDUMP_FORMAT.md index ecc4325..47d1a82 100644 --- a/src/docs/TREEDUMP_FORMAT.md +++ b/src/docs/TREEDUMP_FORMAT.md @@ -66,6 +66,101 @@ 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 -- |
