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 | |
| 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]>
| -rw-r--r-- | src/GNUmakefile | 13 | ||||
| -rwxr-xr-x | src/chess.h | 32 | ||||
| -rw-r--r-- | src/docs/DEEPER_PRUNING.md | 513 | ||||
| -rw-r--r-- | src/docs/TREEDUMP_FORMAT.md | 95 | ||||
| -rw-r--r-- | src/dynamic.c | 172 | ||||
| -rw-r--r-- | src/main.c | 1 | ||||
| -rw-r--r-- | src/root.c | 11 | ||||
| -rw-r--r-- | src/script.c | 46 | ||||
| -rw-r--r-- | src/search.c | 9 | ||||
| -rw-r--r-- | src/searchsup.c | 221 |
10 files changed, 1062 insertions, 51 deletions
diff --git a/src/GNUmakefile b/src/GNUmakefile index e710834..041ffbd 100644 --- a/src/GNUmakefile +++ b/src/GNUmakefile @@ -195,6 +195,19 @@ endif ifdef MOVE_ORDERING_EVIDENCE_COLLECTION PROFILE += -DMOVE_ORDERING_EVIDENCE_COLLECTION endif +# 2026-10-23, one-off measurement: does IS_CAPTURE(mvHash) (optionally +# && pi->eNodeType==NODE_CUT) meaningfully predict a leftover move's +# fail-high rate, beyond what the existing joint FH table's five axes +# already capture? Neither signal is currently baked into the table at +# all. Bucketed counters only (chess.h's u64HashCapTries/FH, [2][2] -- +# [hash move is a capture][node type guess is CUT]), printed by +# script.c's _PrintSuiteReport -- cheap enough to leave compiled in for +# a --cpus 1 collection run; not wired into split.c's MP merge, same +# convention as the other single-threaded-only calibration counters +# (u64TotalCMEvidenceTries et al) in that same report. +ifdef HASHCAP_COLLECTION +PROFILE += -DHASHCAP_COLLECTION +endif ifdef BOUNDS_CHECKING PROFILE += -fbounds-checking endif diff --git a/src/chess.h b/src/chess.h index 189e0a4..05052c6 100755 --- a/src/chess.h +++ b/src/chess.h @@ -1187,6 +1187,18 @@ typedef struct _COUNTERS UINT64 u64LeftoverTries; // leftover (sub-GOOD_MOVE) move tried UINT64 u64LeftoverAlpha; // ...raised alpha (didn't fail high) UINT64 u64LeftoverFH; // ...failed high +#ifdef HASHCAP_COLLECTION + // 2026-10-23, one-off measurement: P(leftover move fails high | + // hash move at this node was a capture, node type guess). See + // GNUmakefile's HASHCAP_COLLECTION comment for what's being + // measured and why -- not a permanent production signal, this + // is purely to find out whether IS_CAPTURE(mvHash) (optionally + // && eNodeType==NODE_CUT) is worth baking into the joint table + // as a real axis before building anything around it. + // Indexed [fHashMoveIsCapture][eNodeType==NODE_CUT]. + UINT64 u64HashCapTries[2][2]; + UINT64 u64HashCapFH[2][2]; +#endif UINT64 u64CMEvidenceTries[CM_EVIDENCE_BUCKETS]; UINT64 u64CMEvidenceFH[CM_EVIDENCE_BUCKETS]; UINT64 u64HangEstimateTries[HANG_CP_BUCKETS]; @@ -1759,6 +1771,16 @@ typedef struct _PLY_INFO MOVE mvBest; MOVE PV[MAX_PLY_PER_SEARCH]; + // 2026-10-23, one-off diagnostic support: was the hash move at + // THIS node a capture/promotion? Set once per node, right after + // mvHash is established (search.c), read back by SearchOneMove + // (searchsup.c) to bucket the HASHCAP_COLLECTION measurement -- + // see that macro's own comment (GNUmakefile) for what it's + // measuring and why. FALSE (not just unset) whenever there was no + // hash move at all, same as IS_CAPTURE_OR_PROMOTION on a null move + // would read. + FLAG fHashMoveIsCapture; + // Stamped with (pos->u64NonPawnSig ^ pos->u64PawnSig) the instant a // full (not lazy/super-lazy) Eval() call finishes for the position // currently sitting at this ply -- see Eval()'s own comment near @@ -2229,6 +2251,10 @@ typedef struct _GAME_OPTIONS UINT64 u64LeftoverTries; UINT64 u64LeftoverAlpha; UINT64 u64LeftoverFH; +#ifdef HASHCAP_COLLECTION + UINT64 u64HashCapTries[2][2]; + UINT64 u64HashCapFH[2][2]; +#endif UINT64 u64CMEvidenceTries[CM_EVIDENCE_BUCKETS]; UINT64 u64CMEvidenceFH[CM_EVIDENCE_BUCKETS]; UINT64 u64HangEstimateTries[HANG_CP_BUCKETS]; @@ -4338,6 +4364,12 @@ extern SCORE g_iLMRQuietReduction[MAX_PLY_PER_SEARCH + 1][LMR_TABLE_MAX_MOVES + void InitializeLMRTable(void); +void +InitializeWilsonBoundTable(void); + +ULONG +GetMoveFailHighWilsonUpperBoundThousandths(MOVE mv); + FLAG CanWeReduceOrPruneMove(IN SEARCHER_THREAD_CONTEXT *ctx, IN MOVE mv, 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 -- diff --git a/src/dynamic.c b/src/dynamic.c index 07fc02e..50bc36a 100644 --- a/src/dynamic.c +++ b/src/dynamic.c @@ -37,10 +37,11 @@ Revision History: #include "chess.h" -// Declared directly instead of #include <math.h> -- that header -// #defines its own INFINITY_SCORE, which collides with ours (chess.h:198, -// MAX_SHORT). Only needed once, at startup, to build g_iLMRQuietReduction. -extern double log(double); +// Only needed once, at startup, to build g_iLMRQuietReduction and +// g_uWilsonUpperBoundThousandths below -- math.h's own INFINITY macro +// used to collide with ours before chess.h's was renamed to +// INFINITY_SCORE (2026-10-23). +#include <math.h> ULONG g_HistoryCounters[14][128]; ULONG g_ContinuationHistory[CONTINUATION_TABLE_SIZE]; @@ -69,6 +70,53 @@ typedef struct _FH_STATS FH_STATS g_FailHighs[FH_STATS_TABLE_SIZE]; +// Precomputed Wilson-score upper-confidence-bound table for the dynamic +// per-move-identity fail-high rate, in the same "thousandths of a +// percent" unit g_uJointFHThousandths uses -- so a caller can feed this +// straight into the same reduction-magnitude formula without any unit +// conversion. See GetLMRReduction's 2026-10-23 dynamic-blend comment for +// why an upper CONFIDENCE BOUND (not the raw FailHighs/Attempts ratio) +// is the right thing to feed that formula: a bound widens automatically +// for a thin sample (0 fail-highs in 2 tries proves almost nothing) and +// narrows toward the true rate as real evidence accumulates (0 fail- +// highs in 65,000 tries is real evidence of safety), which is exactly +// the asymmetric trust a raw point estimate can't express on its own. +// +// Computing the real Wilson formula (one divide for p-hat, several more +// for the z^2/n terms, one sqrt) per move at Search's call frequency is +// a non-starter -- this is the hottest function in the engine. Instead: +// bucket both inputs onto small, branchless-indexable ranges and pay +// the real formula's cost exactly once per cell, at startup, in +// InitializeWilsonBoundTable below. At the one call site that matters +// (GetLMRReduction's hot path), the whole lookup is two bit-length/min +// ops and one array index -- no FP divide, no sqrt, nothing branchy +// keyed on "essentially random move metadata" the way a comparison +// chain would be. +// +// Bucket shape, chosen to be cheap to compute rather than retrofitted +// onto one (contrast with _ShipDepthBucket/_ShipLateBucket's comparison +// chains elsewhere in this file's sibling searchsup.c, which can't be +// changed this way without also re-baking the static table they index -- +// not a problem here, this table has no offline-baked counterpart to +// stay in lockstep with): +// - Attempts bucket = FastLastBit(Attempts | 1) (chess.h) -- a single +// bsr/clz instruction, 1-based bit-length, so bucket b covers the +// power-of-two range [2^(b-1), 2^b - 1]. u16Attempts is at most +// 65535, so b runs 1..16; index 0 is unused (kept so the raw +// FastLastBit result can be used directly with no decrement). +// - FailHigh bucket = MIN(FailHighs, 3) -- a single branchless min +// (MINU already compiles to cmov elsewhere in this codebase), 0/1/2 +// exact, 3 meaning "3 or more". Finer resolution buys little here: +// by the time a move identity has a handful of real fail-highs on +// record, the formula this feeds already treats it as maximally +// dangerous regardless of the exact count (see the 10%/50%/90% +// finding from the same day's design discussion -- all three +// already clamp to zero extra reduction against the 0.4% baseline, +// so distinguishing "3 fail-highs" from "30" buys nothing further). +#define WILSON_ATTEMPTS_BUCKETS (17) +#define WILSON_FH_BUCKETS (4) +USHORT g_uWilsonUpperBoundThousandths[WILSON_ATTEMPTS_BUCKETS][WILSON_FH_BUCKETS]; + #ifdef MP volatile static ULONG g_uDynamicLock; #define DYN_IS_LOCKED (g_uDynamicLock != 0) @@ -86,6 +134,122 @@ volatile static ULONG g_uDynamicLock; void +InitializeWilsonBoundTable(void) +/** + +Routine description: + + Build g_uWilsonUpperBoundThousandths once at startup -- see that + table's own comment for why (cost: real Wilson-score math, paid + once per bucket cell here, never at Search's call frequency). + + z=2.0 (~95.4% one-sided confidence) chosen as a simple round + constant, same spirit as InitializeLMRTable's own Ethereal-derived + starting constants a few lines down: a reasonable starting shape, + not load-bearing, expect to retune once this is actually wired into + a reduction decision and measured. + + Representative (n, k) per cell: n = the bucket's own lower power- + of-two bound (2^(bucket-1) for bucket >= 1) -- deliberately the + SMALLER end of the bucket's range, so the bound computed is the + more cautious (wider) one a real Attempts value anywhere in that + bucket could justify, never an optimistic extrapolation past what + the smallest member of the bucket actually earns. k = the FH + bucket's own index (0, 1, 2, or 3), capped to n (k can't exceed + attempts) -- using 3 as the representative for the "3+" bucket + rather than something larger only makes that cell's bound MORE + cautious than reality, which is the safe direction to be wrong in. + +Parameters: + + void + +Return value: + + void + +**/ +{ + ULONG uAttemptsBucket, uFhBucket; + double z = 2.0; + double z2 = z * z; + + for (uAttemptsBucket = 0; uAttemptsBucket < WILSON_ATTEMPTS_BUCKETS; uAttemptsBucket++) + { + double n = (uAttemptsBucket == 0) ? + 1.0 : (double)(1UL << (uAttemptsBucket - 1)); + + for (uFhBucket = 0; uFhBucket < WILSON_FH_BUCKETS; uFhBucket++) + { + double k = (double)uFhBucket; + double phat, center, spread, denom, upper; + ULONG uThousandths; + + if (k > n) + { + k = n; + } + phat = k / n; + denom = 1.0 + z2 / n; + center = phat + z2 / (2.0 * n); + spread = z * sqrt((phat * (1.0 - phat) / n) + (z2 / (4.0 * n * n))); + upper = (center + spread) / denom; + if (upper > 1.0) + { + upper = 1.0; + } + uThousandths = (ULONG)((upper * 100000.0) + 0.5); + if (uThousandths > 100000) + { + uThousandths = 100000; + } + g_uWilsonUpperBoundThousandths[uAttemptsBucket][uFhBucket] = + (USHORT)uThousandths; + } + } +} + + +// Branchless lookup into g_uWilsonUpperBoundThousandths -- see that +// table's own comment for the design rationale. FastLastBit (chess.h) +// is a single bsr/clz instruction; MINU is this codebase's existing +// branchless-min macro (compiles to cmov). No divide, no sqrt, no +// comparison chain, at this call site -- all of that cost was paid +// once, at startup, in InitializeWilsonBoundTable above. +ULONG +GetMoveFailHighWilsonUpperBoundThousandths(IN MOVE mv) +/** + +Routine description: + + Look up a move identity's dynamic fail-high rate as a Wilson-score + upper confidence bound (thousandths of a percent, same unit + g_uJointFHThousandths uses) rather than the raw FailHighs/Attempts + ratio GetMoveFailHighPctThousandths returns -- see + g_uWilsonUpperBoundThousandths's comment for why that distinction + matters for feeding a reduction-magnitude formula specifically. + +Parameters: + + MOVE mv + +Return value: + + ULONG : Wilson upper bound, thousandths of a percent (0-100000) + +**/ +{ + ULONG u = MOVE_TO_FH_INDEX(mv); + ULONG uAttempts = g_FailHighs[u].u16Attempts; + ULONG uFailHighs = g_FailHighs[u].u16FailHighs; + ULONG uAttemptsBucket = FastLastBit((BITBOARD)(uAttempts | 1)); + ULONG uFhBucket = MINU(uFailHighs, (ULONG)(WILSON_FH_BUCKETS - 1)); + + return(g_uWilsonUpperBoundThousandths[uAttemptsBucket][uFhBucket]); +} + + +void InitializeLMRTable(void) /** @@ -592,6 +592,7 @@ Return value: InitializeOpeningBook(); InitializeDynamicMoveOrdering(); InitializeLMRTable(); + InitializeWilsonBoundTable(); InitializeHashSystem(); InitializeEval(); #ifdef MP @@ -1674,6 +1674,17 @@ Return value: g_Options.u64LeftoverTries = ctx->sCounters.tree.u64LeftoverTries; g_Options.u64LeftoverAlpha = ctx->sCounters.tree.u64LeftoverAlpha; g_Options.u64LeftoverFH = ctx->sCounters.tree.u64LeftoverFH; +#ifdef HASHCAP_COLLECTION + for (u = 0; u < 2; u++) + { + ULONG v; + for (v = 0; v < 2; v++) + { + g_Options.u64HashCapTries[u][v] = ctx->sCounters.tree.u64HashCapTries[u][v]; + g_Options.u64HashCapFH[u][v] = ctx->sCounters.tree.u64HashCapFH[u][v]; + } + } +#endif for (u = 0; u < CM_EVIDENCE_BUCKETS; u++) { g_Options.u64CMEvidenceTries[u] = ctx->sCounters.tree.u64CMEvidenceTries[u]; diff --git a/src/script.c b/src/script.c index 7de170c..848546b 100644 --- a/src/script.c +++ b/src/script.c @@ -97,6 +97,10 @@ typedef struct _SUITE_COUNTERS UINT64 u64TotalJointExtraTries[JOINT_EXTRA_TIER_COUNT]; UINT64 u64TotalJointExtraResearch[JOINT_EXTRA_TIER_COUNT]; UINT64 u64TotalLMPPruned; +#ifdef HASHCAP_COLLECTION + UINT64 u64TotalHashCapTries[2][2]; + UINT64 u64TotalHashCapFH[2][2]; +#endif #ifdef FH_TABLE_COLLECTION // Full dual-table (5D alpha + 4D beta) collection -- see chess.h's // SEARCHER_THREAD_CONTEXT.sCounters.tree comment for the full @@ -460,6 +464,21 @@ _ProcessSuiteLine(char *szLine, POSITION *pos) g_Options.u64LeftoverAlpha; g_SuiteCounters.u64TotalLeftoverFH += g_Options.u64LeftoverFH; +#ifdef HASHCAP_COLLECTION + { + ULONG u2, v2; + for (u2 = 0; u2 < 2; u2++) + { + for (v2 = 0; v2 < 2; v2++) + { + g_SuiteCounters.u64TotalHashCapTries[u2][v2] += + g_Options.u64HashCapTries[u2][v2]; + g_SuiteCounters.u64TotalHashCapFH[u2][v2] += + g_Options.u64HashCapFH[u2][v2]; + } + } + } +#endif { ULONG v; for (v = 0; v < CM_EVIDENCE_BUCKETS; v++) @@ -892,6 +911,33 @@ _PrintSuiteReport(double dSuiteStart) } +#ifdef HASHCAP_COLLECTION + // 2026-10-23, one-off measurement: P(leftover move fails high | + // hash move at this node was a capture, node type guess). See + // GNUmakefile's HASHCAP_COLLECTION comment. + { + static const char *_pszLabel[2][2] = { + { "hashMove=quiet/none, type=ALL/PV", "hashMove=quiet/none, type=CUT" }, + { "hashMove=capture, type=ALL/PV", "hashMove=capture, type=CUT" }, + }; + ULONG u2, v2; + Trace("\nhash-move-is-capture fail-high calibration " + "(leftover moves only):\n"); + for (u2 = 0; u2 < 2; u2++) + { + for (v2 = 0; v2 < 2; v2++) + { + Trace(" %s : %6.3f%% FH (%" + COMPILER_LONGLONG_UNSIGNED_FORMAT " tries)\n", + _pszLabel[u2][v2], + (100.0 * (double)g_SuiteCounters.u64TotalHashCapFH[u2][v2] / + ((double)g_SuiteCounters.u64TotalHashCapTries[u2][v2] + 1.0)), + g_SuiteCounters.u64TotalHashCapTries[u2][v2]); + } + } + } +#endif + #ifdef JOINT_EXTRA_VERIFY // "Silent miss" shadow-verification calibration: of the extra- // reduced moves whose real score never triggered a re-search (the diff --git a/src/search.c b/src/search.c index c054333..a347e12 100644 --- a/src/search.c +++ b/src/search.c @@ -511,6 +511,10 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, &mvHash, &iScore, &sHash); + // 2026-10-23, one-off diagnostic support -- see PLY_INFO's + // fHashMoveIsCapture comment (chess.h). mvHash is never reassigned + // below this point, so it's final the instant HashLookup returns. + pi->fHashMoveIsCapture = (0 != mvHash.uMove) && IS_CAPTURE_OR_PROMOTION(mvHash); if (TRUE == fHashHit) { VERIFY_HASH_HIT; @@ -1220,6 +1224,11 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, if (TRUE == fIsLeftoverMove) { INC(ctx->sCounters.tree.u64LeftoverFH); +#ifdef HASHCAP_COLLECTION + INC(ctx->sCounters.tree.u64HashCapFH + [pi->fHashMoveIsCapture ? 1 : 0] + [(NODE_CUT == pi->eNodeType) ? 1 : 0]); +#endif // Gated on fMoveIsPruneReduceEligible now, // matching the tries side -- must // match exactly, or this would reuse a diff --git a/src/searchsup.c b/src/searchsup.c index d43d387..397d57e 100644 --- a/src/searchsup.c +++ b/src/searchsup.c @@ -19,6 +19,7 @@ Revision History: **/ #include "chess.h" +#include <math.h> // log(), log10() -- _FhBasedExtraPliesF extern SCORE g_iRootScore[2]; extern ULONG g_uHardExtendLimit; @@ -856,6 +857,110 @@ _FlatTableExtraPlies(IN ULONG uRemainingDepth, IN ULONG uMoveNum) return (ULONG)(iExtraTicks / ONE_PLY); } +// 2026-10-23: replaces _FlatTableExtraPlies as GetLMRReduction's primary +// magnitude source (that function is kept as the JOINT_TABLE_SENTINEL +// fallback below, for buckets the joint table has no opinion on at all). +// +// Derived from a direct regression against Crafty's and Stockfish's own +// (independently play-tested) reduction schedules: at fixed remaining +// depth, both engines' actual reduction in plies is extremely well +// predicted (R^2=0.96 against Stockfish's own formula, checked across a +// depth 2-13 x move 2-32 grid) by a single term proportional to +// -log10(predictedFH%/100) -- i.e. both engines are implicitly already +// reducing in proportion to how unlikely a move is to fail high, using +// depth and move-number as cheap proxies for that probability. We have +// a materially richer, directly-measured estimate of the same quantity +// (uPredictedFH, 5 axes vs. their 2), so this leans on it directly +// rather than re-deriving the same signal through depth/move-number +// proxies -- the same way the existing admission gate already does. +// +// The proportionality constant itself (k) is NOT fixed -- it was also +// measured, in the same regression, to climb with remaining depth +// (k =~ 0.32*ln(depth) + 0.48 against Stockfish's schedule): both +// engines reduce more per unit of -log10(FH%) the deeper the search +// is. This isn't re-deriving something the FH% estimate already +// contains -- FH% itself already depends on depth, but evidently not +// with the magnitude a calibrated reduction schedule needs, so depth +// earns a second, explicit role here beyond whatever it contributed to +// uPredictedFH upstream. +// +// uRemainingDepth is deliberately capped at 13 plies before computing +// k -- not an arbitrary safety margin, but the exact point where the +// joint table's own raw collection data runs out (see the DEEPER_ +// PRUNING.md "leftover-population question" discussion: tries per +// cell fall from 56,021 at depth 13 to low hundreds by depth 16-19 and +// to zero past depth 19). Freezing k's depth input here means k stops +// growing exactly where the data backing it stops being trustworthy -- +// and since _ShipDepthBucket() independently freezes uPredictedFH's +// own depth axis at the same raw-13 boundary, both halves of this +// formula plateau together, automatically capping total reduction to +// a flat ceiling past this depth. That's the direct fix for the +// "deterministic re-pruning across iterations" failure mode discussed +// the same day: residual depth (nominal depth minus this flat cap) +// diverges without bound as nominal search depth grows past 13, so a +// move reduced this heavily is guaranteed to eventually receive a +// residual look deep enough to find whatever it was missing, no +// matter how deep the overall iterative-deepening search goes -- it +// is never reduced by a *growing* amount indefinitely. +// +// Normalized against LMR_FH_BASELINE_PCT_THOUSANDTHS (the same 0.400% +// whole-population baseline the dynamic-danger check already uses) so +// an exactly-average leftover move earns ~0 extra plies (just the +// existing flat -ONE_PLY base), and only moves predicted safer than +// that baseline earn positive extra, scaling up continuously with how +// much safer -- no threshold cliff, matching how neither reference +// engine's own formula has an admission cliff either. +// Relocated here (was originally right before CanWeReduceOrPruneMove) +// so _FhBasedExtraPliesF below can use it -- same single definition, +// just earlier in the file now. See its original comment, still in +// place further down, for the full "0.400%" provenance story. +#define LMR_FH_BASELINE_PCT_THOUSANDTHS (400) // 0.400% + +// Returns the EXTRA reduction (beyond the base -ONE_PLY) in raw depth +// ticks, rounded to the nearest QUARTER_PLY -- the engine's actual +// reduction/extension resolution (chess.h: ONE_PLY=64, QUARTER_PLY=16, +// i.e. depth is fixed-point in quarter-ply units throughout the +// search, not whole plies). The regression this formula is built from +// was fit in continuous plies; truncating to whole plies here would +// throw away most of its resolution for no reason, so this returns +// ticks directly instead of letting the caller round first. +static ULONG +_FhBasedExtraPlyTicks(IN ULONG uRemainingDepth, IN ULONG uPredictedFHThousandths) +{ + double dDepth = (double)(MINU(uRemainingDepth / ONE_PLY, 13)); + double dK; + double dFhThousandths; + double dNegLogFh; + double dNegLogBaseline; + double dExtraPlies; + ULONG uTicks; + + if (dDepth < 2.0) + { + dDepth = 2.0; + } + dK = 0.32 * log(dDepth) + 0.48; + + dFhThousandths = (double)uPredictedFHThousandths; + if (dFhThousandths < 1.0) + { + dFhThousandths = 1.0; // avoid log(0); table has no real 0 cells anyway + } + dNegLogFh = -log10(dFhThousandths / 100000.0); + dNegLogBaseline = + -log10((double)LMR_FH_BASELINE_PCT_THOUSANDTHS / 100000.0); + + dExtraPlies = dK * (dNegLogFh - dNegLogBaseline); + if (dExtraPlies <= 0.0) + { + return 0; + } + // Round to nearest quarter-ply tick (ONE_PLY=64, QUARTER_PLY=16). + uTicks = (ULONG)((dExtraPlies * (double)ONE_PLY / (double)QUARTER_PLY) + 0.5) + * QUARTER_PLY; + return uTicks; +} + // data.c:1209's "Overall eligible FH%: 0.400%" -- the tries-weighted // fail-high rate of the WHOLE fPruneReduceEligible population across // the 500B-node joint-table collection run. Used two ways: (1) as the @@ -879,7 +984,7 @@ _FlatTableExtraPlies(IN ULONG uRemainingDepth, IN ULONG uMoveNum) // rate is bimodal -- ~71% at exactly 0, with the next real mass not // starting until ~1%). So: intended behavior preserved, shipped // behavior changed by an immeasurably small amount. -#define LMR_FH_BASELINE_PCT_THOUSANDTHS (400) // 0.400% +// (Defined earlier in this file now -- see _FhBasedExtraPliesF's use.) // 2026-10-02, one-off diagnostic support for chess.h's u64FHJointHist: // 8 attempts bands (0,1,2,3-4,5-9,10-24,25-99,100+) and 8 rate bands in @@ -1070,7 +1175,7 @@ Return value: ASSERT(mv.uMove); ASSERT(!InCheck(&ctx->sPosition, ctx->sPosition.uToMove)); - ULONG uExtraPlies = 0; + ULONG uExtraTicks = 0; #ifdef DISABLE_LMR // See GNUmakefile's DISABLE_LMR comment. Bail before any signal is // consulted so the no-LMR arm is a clean control: no reduction, and @@ -1079,41 +1184,68 @@ Return value: #endif INT iLocalExtend; - FLAG fBaseEligible; - FLAG fDynamicDanger = (uAttempts > 0) && - (uFHPctThousandths > LMR_FH_BASELINE_PCT_THOUSANDTHS); + ULONG uExtraTierForCounters; + // 2026-10-23: admission is no longer gated on the static table's + // opinion (LMR_STATIC_ADMIT_PCT_THOUSANDTHS retired from this + // function -- CanWeReduceOrPruneMove's base eligibility, i.e. "is + // this move even in the leftover tier," is still the only gate). + // Every eligible leftover move gets at least the base -ONE_PLY; + // uPredictedFH drives MAGNITUDE continuously via + // _FhBasedExtraPlyTicks below instead of gating whether to reduce + // at all -- matching how neither Crafty's nor Stockfish's own + // formula has an admission cliff either. + // + // 2026-10-23: the dynamic per-move-identity signal (this move's + // own observed fail-high history) no longer gets a separate + // veto-to-zero branch (the old fDynamicDanger check, removed). + // Deliberate, not an oversight -- discussed at length the same + // day: neither Crafty nor Stockfish exempts a move from reduction + // because of its own track record (Crafty has no dynamic signal + // in its reduction formula at all; Stockfish's analogous history- + // based term only ever feeds one continuous formula, never a + // separate exemption branch). A move's own real fail-high history + // is folded into the SAME formula's input instead, as a Wilson- + // score upper confidence bound (GetMoveFailHighWilsonUpperBoundThousandths, + // dynamic.c) on that move's true fail-high rate -- a tighter + // (lower) bound than the static table's prediction is real, + // sample-size-earned evidence of safety and is allowed to win; + // a looser (higher) bound -- including the "real history of + // failing high" case -- never overrides the static table's own + // reading, by construction: taking the minimum of two FH% + // estimates can only ever pick the smaller (safer) one, never + // push the effective rate up. (Deliberately NOT using this to + // justify reducing a dangerous-looking move LESS, either -- see + // the same discussion: the data argues searching a flagged- + // dangerous move deeper doesn't straightforwardly buy a safer + // read, since the table's own depth axis already shows shallower + // remaining depth correlates with HIGHER fail-high rates, not + // lower, so "reduce less" has no causal footing to stand on here.) + // + // Also 2026-10-23: works in raw depth ticks (QUARTER_PLY-rounded), + // not whole plies -- the engine's actual reduction/extension + // resolution is quarter-ply fixed-point throughout (chess.h: + // ONE_PLY=64, QUARTER_PLY=16), and the regression this formula + // comes from was fit in continuous plies, so truncating to whole + // plies here would throw away most of that precision for no + // reason. The old flat-table fallback (JOINT_TABLE_SENTINEL case) + // still only has whole-ply resolution, hence the *ONE_PLY there. if (JOINT_TABLE_SENTINEL == uPredictedFH) { - // No static data for this exact bucket, fall back on dynamic. - fBaseEligible = (FALSE == fDynamicDanger); + // No static data for this exact bucket -- fall back to the + // old flat Crafty-shaped (depth, moveNum) table rather than + // feeding a sentinel into the log formula. (Not blended with + // the Wilson bound either -- there's no static reading here + // to take a minimum against.) + uExtraTicks = _FlatTableExtraPlies(uRemainingDepth, uLegalMoves) * ONE_PLY; } else { - // Static table has an opinion: admission is now a wide- - // open, separate threshold from the extra-tier magnitude - // grading below (LMR_STATIC_ADMIT_PCT_THOUSANDTHS, not - // JOINT_EXTRA_TIER1_PCT_THOUSANDTHS) -- only veto the base - // reduction when the static table itself thinks this - // bucket is actively bad. A dynamic-danger reading does - // NOT veto this either -- it only caps uExtraPlies to 0 - // below. - fBaseEligible = (uPredictedFH < LMR_STATIC_ADMIT_PCT_THOUSANDTHS); - } - if (FALSE == fBaseEligible) - { - if (NULL != puExtraTier) - { - *puExtraTier = 0; - } - return(0); + ULONG uWilsonBound = GetMoveFailHighWilsonUpperBoundThousandths(mv); + ULONG uEffectiveFH = MINU(uPredictedFH, uWilsonBound); + uExtraTicks = _FhBasedExtraPlyTicks(uRemainingDepth, uEffectiveFH); } - // We are going to reduce it; let's see if we want to pile on extra - // reduction because we're pretty sure it's "safe". - uExtraPlies = ((FALSE == fDynamicDanger)) ? - _FlatTableExtraPlies(uRemainingDepth, uLegalMoves) : 0; - // Clamp. Combine with the baseline -ONE_PLY and floor the total // so it never leaves less than JOINT_EXTRA_MIN_REMAINING_DEPTH // remaining -- never rely on the move loop's own unsigned- @@ -1125,25 +1257,28 @@ Return value: // -ONE_PLY -- no need to fold a variable iExtend into it. ASSERT(0 == iExtend); iLocalExtend = -ONE_PLY; - if (uExtraPlies > 0) + uExtraTierForCounters = 0; + if (uExtraTicks > 0) { // MAX0 branchlessly floors the numerator at 0 before the - // divide (it can go negative when uRemainingDepth is small), - // so uMaxExtra is safely non-negative going into MINU -- both - // macros need their inputs' high-order bit clear, true here - // since none of uRemainingDepth/ONE_PLY/JOINT_EXTRA_MAX_PLIES - // come anywhere near 2^31. + // divide (it can go negative when uRemainingDepth is small). INT iExtraNumerator = (INT)uRemainingDepth - 2 * (INT)ONE_PLY - (INT)JOINT_EXTRA_MIN_REMAINING_DEPTH; - ULONG uMaxExtra = (ULONG)MAX0(iExtraNumerator) / (ULONG)ONE_PLY; - uExtraPlies = MINU(uExtraPlies, uMaxExtra); - uExtraPlies = MINU(uExtraPlies, (ULONG)JOINT_EXTRA_MAX_PLIES); - iLocalExtend -= (INT)(uExtraPlies * ONE_PLY); + ULONG uMaxExtraTicks = (ULONG)MAX0(iExtraNumerator); + uExtraTicks = MINU(uExtraTicks, uMaxExtraTicks); + uExtraTicks = MINU(uExtraTicks, (ULONG)(JOINT_EXTRA_MAX_PLIES * ONE_PLY)); + iLocalExtend -= (INT)uExtraTicks; + // The joint-extra-tier instrumentation (u64JointExtraTries[] + // etc, JOINT_EXTRA_TIER_COUNT=6 slots, see chess.h) predates + // fractional extra plies and indexes by whole extra plies -- + // floor to that resolution for counter purposes only; the + // actual applied reduction above keeps full tick precision. + uExtraTierForCounters = uExtraTicks / ONE_PLY; } if (NULL != puExtraTier) { - *puExtraTier = uExtraPlies; + *puExtraTier = uExtraTierForCounters; } return(iLocalExtend); } @@ -2034,6 +2169,12 @@ Return value: { INC(ctx->sCounters.tree.u64LeftoverTries); +#ifdef HASHCAP_COLLECTION + INC(ctx->sCounters.tree.u64HashCapTries + [pi->fHashMoveIsCapture ? 1 : 0] + [(NODE_CUT == pi->eNodeType) ? 1 : 0]); +#endif + #ifdef FH_TABLE_COLLECTION if (TRUE == fMoveIsPruneReduceEligible) { |
