# Extended pruning depth: closing the ebf gap to Crafty/Stockfish ## Background Typhoon's effective branching factor is worse than Crafty's and Stockfish's despite having the same core forward-pruning toolkit (EFP, LMP, LMR, nullmove, same R factor). An experiment that forced the main search loop to abandon all remaining moves the instant one looked prune-worthy (`continue` -> `goto end`) cut node counts at low depth but made deep searches *worse* -- the single most informative result driving this plan, since it shows the gap isn't about move ordering (already measured as competitive, see the 2026-08-29 dynamic-move-ordering session) and isn't fixed by recklessness alone. It's about margin size and depth-extent of existing mechanisms, and possibly a mechanism we don't have at all. Reading both reference engines' actual source settled several questions that would otherwise have been guesswork: - `~/programming/chess/crafty-25.2/search.c` + `data.c`: Crafty's `FP_margin[16] = {0,100,150,200,250,300,400,500,...}` with `FP_depth = 7` prunes with a flat, hand-picked margin schedule out to **6 plies of remaining depth**, and on a prune it executes `break` -- abandons every remaining move at that node, not just the one under consideration. No reverse/static-null mechanism exists in Crafty; what looked like it might be one is actually "razoring" (Kent et al.), which drops to qsearch when *eval is far below alpha*, the opposite side of the board from what's relevant here. Margins are tuned by whole-game cluster testing, not per-node surprise-rate measurement. - `~/programming/chess/stockfish/src/search.cpp`: Stockfish has **both** mechanisms, cleanly separated, and both use `continue`/return-based pruning rather than Crafty's `break`: - "Step 9. Futility pruning: child node" (`eval - futilityMargin >= beta`, no nullmove verification, depth < 19) -- a true reverse-futility/ static-null check, evaluated once per node before the move loop even starts. - "Futility pruning: parent node" (`futilityValue <= alpha`, gated on `lmrDepth < 12` where `lmrDepth` is itself adjusted by that move's own history score) -- the same idea as Typhoon's EFP, but extended much deeper and with a per-move, history-sensitive margin instead of a flat depth-indexed one. Typhoon's own EFP (`search.c` ~line 1310) is exactly 2 tiers (remaining depth <= 1.75 ply: margin `VALUE_KNIGHT`; <= 2.75 ply: margin `VALUE_ROOK`), sourced from Ernst Heinz's "Scalable Search in Computer Chess" and calibrated against measured surprise rates via `CALIBRATE_QSEARCH_FUTILITY` (QSearch only -- this calibration harness does not currently cover main search's EFP). It already uses `continue`, matching Stockfish's safer choice, not Crafty's `break`. ## Alpha-side vs. beta-side pruning: two mechanisms, not one Despite feeling like the same idea, EFP and reverse futility pruning (RFP) differ enough mechanically to warrant separate experiments, even though they are related by a satisfying piece of algebra. **The algebra.** In negamax, a parent's alpha is the negation of the child's beta (`alpha_parent = -beta_child`). EFP's test at the parent -- skip move `m` if `iEstimatedMoveValue + margin <= iAlpha_parent` -- uses `iEstimatedMoveValue` as an approximation of `-StaticEval(child)` (the mover's-eye view of the position after `m`, without actually making it). Substituting: ``` -StaticEval(child) + margin <= iAlpha_parent StaticEval(child) - margin >= -iAlpha_parent StaticEval(child) - margin >= beta_child ``` ...which is exactly Stockfish's RFP test, evaluated one ply later with a real number in place of an estimate. So EFP-at-the-parent-with-an-estimate and RFP-at-the-child-with-ground-truth are the same inequality, viewed from opposite sides of one ply. That's a useful mental model, but not a reason to implement only one of them: | | EFP (alpha-side) | RFP (beta-side) | |---|---|---| | Granularity | Per move, inside the move loop | Per node, before move generation | | Input | Estimated child eval (`iEval + iImprovement - iHangCp`) -- approximate, no Make() | Current node's own already-computed static eval -- exact, no estimation error | | Cost when it fires | Skips one move; loop continues | Skips the entire node, including move generation | | What it's betting on | "Even optimistically, this specific move can't reach alpha" | "This position is already so good that no single reply drags it back below beta" | | Typhoon status | 2 tiers, Heinz margins, `continue` | Does not exist | | Crafty | 6 tiers, flat small margins, `break` | Does not exist (razoring is alpha-side, not this) | | Stockfish | ~12-ply-equivalent (history-adjusted), `continue` | Exists, depth < 19, dynamic margin | Both are in scope. They prune different populations and at different points in the per-node sequence (RFP can save move-generation cost entirely; EFP cannot, since it needs the move to estimate against). ## Why this is dangerous and needs a safety net Both mechanisms are forward pruning: skipping real search based on a static/approximate signal. Typhoon's EFP margins were chosen from Heinz's paper and calibrated after the fact against measured surprise rates (`CALIBRATE_QSEARCH_FUTILITY`, QSearch-side only). Crafty's much more aggressive schedule was validated only by whole-game cluster testing, which answers "does this help in aggregate" but not "how often, and at what cost, is a specific prune wrong." Any extension of EFP's tiers, and any new RFP mechanism, should ship with the same evidence-calibration discipline already used elsewhere in this codebase (QSearch futility calibration, the 2026-08-29 move-ordering fail-high-rate-by-evidence-bucket methodology): measure the surprise rate at the proposed margin/tier/depth *before* trusting it live, not just end-to-end solve counts on a 90-position suite (too noisy for a single knob, per that session's own finding). ## Eval variance and the shape of the tree Does the variance/distribution of `Eval()`'s output materially shape the tree built above it, independent of whether `Eval()` is accurate on average? Yes, and the mechanism is stronger than "noisy input, noisy output" -- minimax search doesn't just pass leaf noise through, it amplifies it. **Why.** If `Eval()` returns the true value plus independent noise at each leaf, backing that up through alternating min/max nodes doesn't average the noise away -- at each max node the search picks the most favorably-noisy branch, at each min node the most unfavorably-noisy one. The backed-up value is systematically biased relative to the true value, and the distortion grows with branching factor and with noise variance (the "minimax pathology" result -- Beal, Pearl, Nau). Searching deeper helps for two separable reasons that are usually bundled together as one: it resolves real tactics (moves bias toward truth), *and* it averages over more terminal positions (shrinks the noise-driven distortion). The second effect is exactly the mechanistic version of "a more accurate eval shapes a smaller, more correct tree" floated earlier about NNUE -- not just closer to the true value on average (bias), but plausibly smoother across similar positions too (variance), and the two have different consequences for search quality. **Where this bites every mechanism in this plan, concretely.** EFP's margin test, LMP's gap axis, the proposed RFP test, and `iImprovement` are all built directly on `iEval`. `iImprovement` specifically (`iEval - eval_two_plies_ago`) is a *difference* of two noisy reads -- if the per-call noise is roughly independent, the difference is noisier than either input, which argues for some skepticism before trusting it as a calibration axis (as proposed above for the new beta-side table) without checking its own signal-to-noise ratio first. More importantly, the joint FH% table's own "gap" axis is computed from `iEval` -- if `iEval` is noisy, a move's measured gap bucket is partly noise, not signal. That's a textbook attenuation-bias setup: a noisy covariate systematically shrinks the measured strength of a true relationship toward zero. Which reframes a question from earlier in this plan -- **Typhoon's margins may need to be wider than Stockfish's/ Crafty's not because of a different risk-tolerance philosophy, but because the thing the margin is being compared against is measured less precisely.** That's a mechanistic, testable claim, not an editorial one. It also touches an assumption the "approximate the beta-side table from the existing one" idea leaned on and that got ruled out on bucketing grounds (see above) -- "move 1, by move ordering, is probably the best move." Move ordering itself depends partly on eval-derived heuristics; a noisier eval weakens that assumption independent of the bucketing problem that already killed the shortcut. **What to actually measure, using instrumentation that mostly already exists:** - **Eval-tier disagreement, position held fixed.** `eval.c`'s margin- safety-swing tracking (`g_uSuperLazyMarginSwing*`, built for the lazy/ super-lazy calibration) already measures how much the eval disagrees with itself across tiers, bucketed by army -- a clean noise measurement since only the eval *tier* varies, not the position. Re-read this data with the variance question in mind rather than building new collection. - **Sibling-eval spread at a node.** A full-move-list population analysis (evaluate every legal move's resulting position, look at the spread) is messier -- it conflates genuine positional differences between moves with eval noise -- but it's informative in its own right: a node where every move evals similarly is exactly the "tactics can equalize anything" case flagged as the real risk in pruning deep, independent of noise. Worth collecting, but don't conflate it with the tier- disagreement measurement above when interpreting results. - **Correlate either signal against measured EFP/LMP/RFP surprise rate.** If noisier positions (by either measure) show higher surprise rates at a fixed margin, margins should be a function of (depth, gap, noise/ variance bucket), not just depth and gap -- a genuinely new axis candidate for the tables in this plan, pending that correlation holding up. **A genuinely new idea this surfaces, not yet anywhere in the tuning pipeline:** `eval_tune/`'s DNA tuner fits constants to minimize squared error against game outcomes -- a pure bias-reduction objective. Nothing in that objective rewards a parameterization with *lower score variance across similar positions* at equal average error, and two settings of the same constants could plausibly achieve the same training loss with very different volatility. If eval variance is costing tree quality the way this reasoning suggests, the fix isn't "tune harder" on the current objective, it's checking whether the tuner is unknowingly indifferent between a low-variance and a high-variance solution, and adding an explicit variance penalty to the objective if so. Lower priority than the RFP/EFP work above -- a tuning-pipeline change, not a search change -- but worth tracking as a follow-on, since it would improve every downstream mechanism in this plan rather than just one of them. ## Plan 1. **Baseline audit.** Confirm current EFP tier count/margins and absence of RFP in the working tree; snapshot `head_reference/` at the pre-change commit if not already current, both `sd 10` and `sn 5000000` logs for all three curated suites. 2. **Map the beta-side (inverted-gap) half of the 4D joint table.** `g_uJointFHThousandths` has only ever been populated/queried for the alpha-side case (gap-to-alpha positive, used by EFP/LMP pruning decisions). The beta-side case (`iEval` already above `iBeta`) is unmapped. See "The 4D FH% table and static nullmove" below for the dimensional analysis -- the existing table's `lateness` and `hung material` axes are not meaningful for this question, so this is a new, smaller table, not a re-slice of the existing one. 3. **Reverse futility pruning (RFP) experiment.** Add a Stockfish-style static cutoff (`iEval - margin >= iBeta`, no nullmove verification, evaluated once per node before move generation) at shallow-to-moderate remaining depth. Margin sourced from the new 2D table where sample confidence supports it, a Heinz/Stockfish-style formula as fallback elsewhere. Add a `CALIBRATE_`-style diagnostic (search anyway, log whether the cutoff would have held) before trusting it live, matching the existing QSearch-futility calibration pattern. 4. **EFP-vs-LMP substitution experiment** (supersedes a plain "extend EFP's tiers" plan -- see "EFP vs LMP: same actuary, fewer dimensions" below for the full reasoning). Rather than hand-extending EFP's own Heinz-derived margin schedule deeper, test whether LMP's existing, already-4D-informed schedule can be given equivalent license at the depths EFP currently owns (1-2 ply) and simply carried further out, retiring EFP once that's confirmed. If it can't hold strength even with matched permissiveness, that's real evidence EFP's margin/value test sees something the table's current axes don't, and extending EFP's own tiers (calibrated against measured surprise rate, not hand-picked) becomes the right fallback. 5. **Eval-variance side study.** See "Eval variance and the shape of the tree" below for the full reasoning -- short version: minimax doesn't just pass eval noise through, it amplifies it, and every mechanism in this plan (EFP, LMP, RFP, `iImprovement`) reads `iEval` directly, so this isn't a side curiosity, it's a shared input-quality question for the whole plan. 6. **Validation protocol.** One variable at a time against the `head_reference/` baseline, fixed `sd` depth (not `st`, per existing ECM-comparison guidance), all three curated suites per change (not just the fastest one), fail-high/surprise rate as the primary signal on individual knobs and curated-suite solve counts as the final gate. Rebuild `head_reference/` when a change is kept. ## EFP vs LMP: same actuary, fewer dimensions Working through this live surfaced a cleaner way to see the relationship, and it changes what "extend EFP" should even mean. **EFP is LMP running on 2 of its 4 axes, with a hand-picked margin standing in for what the table would otherwise estimate directly.** Both start from the same base eligibility gate (`CanWeReduceOrPruneMove`) and both end up consulting `g_uJointFHThousandths` for the same move. Where they differ: | | EFP | LMP (`ShouldLatePrune`) | |---|---|---| | Gap to alpha | Explicit, via a margin test (`iEstimatedMoveValue + margin <= iAlpha`) | Implicit, as one of the table's own 4 trained axes | | Hung material | Explicit, via `iHangCp` folded into the same margin test | Same `iHangCp`, same table axis -- identical input | | Remaining depth | Coarse 2-tier switch (`<=1.75 ply` / `<=2.75 ply`), margin hand-picked per tier from Heinz's paper | Smooth, trained schedule (`{200,200,150,75,50,25,12,6,3,1,0}` thousandths, indexed by remaining ply) | | Move lateness | Not consulted at all | One of the table's 4 trained axes | | Verdict source | A margin/value threshold, independently derived, then AND-ed with the table's strictest veto tier (`uPredictedFH < 300`) | The table's own calibrated prediction against a depth-indexed threshold, plus this move-identity's dynamic history | So EFP doesn't disagree with LMP's calibration -- on gap and hung material it uses the *identical* inputs, and both schedules get more conservative (prune less readily) as remaining depth grows, which matches the uncontroversial "more depth remaining = more chance of recovering" logic both Crafty and Heinz build on. Measured by hand (gdb breakpoints on real positions): EFP's working threshold (~0.3%, with 0.1% found to "kill" it) sits right next to LMP's own shallow-depth allowance (200/1000 = 0.2%) -- not a coincidence, the same calibrated reality reached two different ways. The one thing EFP has that LMP doesn't is lateness-blindness: it prunes a move regardless of how early or late it was tried, something LMP's table lookup already accounts for. **Why the earlier "remove EFP, it backfired" result doesn't settle anything on its own.** That experiment removed a pruning mechanism without compensating the other one -- if LMP's shallow-depth threshold was left exactly as it was (tuned to co-exist alongside EFP owning the 1-2 ply window), removing EFP just leaves a gap neither mechanism covers, which is a different, less informative test than "margin-based pruning vs. table-based pruning, given equal license." It demonstrates removing a safety net without replacing it is bad, which isn't surprising, not that EFP's specific mechanism is what's load-bearing. **The fair test:** disable EFP, but first widen LMP's allowed-FH% threshold at remaining depth 1-2 ply to be at least as permissive as EFP was there, and let that same (already depth-and-lateness-aware) schedule extend outward toward the depths Crafty/Stockfish prune at, tightening further out the way the existing array already does. If strength holds, LMP genuinely subsumes EFP, and "go deeper" becomes "keep widening LMP's schedule outward," not "invent new EFP tiers." If it doesn't hold even with matched permissiveness, that's real evidence EFP's margin/value test catches something the table's current 4 axes can't see on their own -- worth identifying what, specifically, before extending EFP's own tiers as the fallback plan (calibrated against measured surprise rate the way `CALIBRATE_QSEARCH_FUTILITY` already does, not hand-picked the way Heinz's original schedule was). The real, unresolved risk either way -- independent of which mechanism wins this test -- is the one check-evade-capture/tactical-volatility point raises: a full-ply search below a "hopeless-looking" move genuinely can even out the score the deeper it's allowed to run, and that volatility is exactly what's being traded away for node count the further from the horizon pruning reaches. Crafty's results say that trade pays off in aggregate even with real misses; whether Typhoon's calibration machinery (the table, or LMP's dynamic per-move history) lets the same trade be made more selectively -- pruning deep only where confidence is actually high, rather than uniformly the way Crafty's flat schedule does -- is the thing this whole plan is trying to find out. ## The 4D FH% table and static nullmove ### What the existing table answers, and why it doesn't directly apply `g_uJointFHThousandths[uShipD][uDumb][uGap][uLate]` (`data.c`) currently answers: *given remaining depth, hung-material estimate, gap-to-alpha, and move lateness, what's the (Wilson-bound, pessimistic) percent chance this specific move raises alpha?* It's built and consumed entirely on the alpha side (`search.c`'s `uRawGapB = GapCpBucket(iAlpha - iEval)`, used by `ShouldLatePrune` and to veto EFP). A static-nullmove/RFP decision is a different question: *given remaining depth and how far `iEval` already clears `iBeta`, what's the chance that a full search of this node would still come in at or above beta?* Two of the four existing axes don't transfer: - **Lateness is meaningless.** RFP is evaluated once per node, before any move is even selected -- there is no "move number" to bucket by. - **Hung material (the `uDumb`/`iHangCp` axis) is move-specific** (it's an estimate of what a *particular* move gives away). RFP has no candidate move in hand yet when it fires, so this axis doesn't apply either. (It may still be useful as a *node*-level signal -- see below -- but it would need to be redefined as "is anything hanging in the current position," not "what does this move give away," which is a different computation.) So this needs a new, smaller table: **FH% predicted by (gap above beta, remaining depth)** -- the direct beta-side analogue of the existing alpha-side table, not a re-slice of it. ### What `return` value RFP should use Three choices, in order of how much they trust the margin: - **`iBeta`** -- the conservative choice, and what Stockfish effectively approximates (`(661 * beta + 363 * eval) / 1024`, a weighted blend biased toward `beta` rather than the raw `eval`). Safe: never returns a score less plausible than the bound being tested. Stockfish's blend is worth copying outright rather than re-deriving -- it's already tuned. - **`iEval - margin`** (the actual tested quantity) -- more information- preserving for any caller that inspects the returned score (e.g. a parent's own improving/stand-pat logic), but injects the raw margin's uncertainty into the score, not just the boolean pass/fail. - **A genuine average/expected value**, if the new table's confidence is high enough to support one (i.e., calibrate not just "prune or don't" but "what score should this cell predict" directly from the sampled distribution). This is the most ambitious option and should only be attempted after the simpler two have been validated -- it's a significantly larger calibration effort (predicting a continuous score, not a prune/don't-prune boolean) and shouldn't gate the first working version of RFP. Start with Stockfish's blended-toward-beta return value; revisit once the new table has enough sample volume to ask whether a sharper value is justified. ### Other signals worth considering for the new table - **`iImprovement`** (already computed and used by EFP's own estimate) -- whether static eval has been trending up across recent plies at this node. Stockfish's own RFP explicitly folds in an `improving`/ `opponentWorsening` correction to the margin; this is likely the single highest-value addition beyond the two base axes, and it's already computed elsewhere in the search, so it's cheap to add as a bucket dimension. - **Side-to-move's own king safety / piece activity**, as a coarse proxy for "how much tactical headroom does the opponent have to claw back the gap" -- more speculative, more expensive, lower priority than `iImprovement`. - **Whether the position is a capture-heavy/tactical node** (recent-ply volatility) vs. quiet -- RFP is riskiest exactly where the position is about to get sharp; a coarse "was the last move a capture/check" bucket may be cheap evidence for that without needing a full tactical-detector. - **Explicitly not** `iHangCp`/lateness, per above -- they don't have a node-level equivalent that means the same thing they mean on the alpha side. Recommended starting axis set for the new table: **(gap-above-beta bucket, remaining-depth bucket, improving bucket)** -- a 3D table, one dimension richer than the bare 2D minimum, reusing `iImprovement` since it's already on hand at every relevant call site. Hold the capture/check-volatility signal and king-safety proxy as "measure once collection infra exists, add only if the bucket shows a real split" rather than building them in up front. ### Two more axes, found by re-examining what's already in the codebase **Opponent trend, not just own trend.** `iImprovement` (`search.c:728`, `iEval - ctx->sPlyInfo[ctx->uPly-2].iEval`) is the *mover's own* eval trend over the last full move, and it's already folded into EFP's per-move estimate as one scalar (`iEstimatedMoveValue = iEval + iImprovement - iHangCp`) -- which means the existing alpha-side joint table never sees it as an independent axis; a big gap with a flat trend and a smaller gap with a strongly-improving trend currently bucket identically. Worth adding `iImprovement` as a genuine 5th axis to the *existing* alpha-side table, not just the new one -- same collection machinery, one more dimension. Stockfish's RFP keeps this as **two** separate signals, not one: `improving` (mover's own trend, what Typhoon already computes) and `opponentWorsening` (the opponent's own trend, computed from the opponent's eval history, not a sign-flip of the mover's). Both are candidates for the new table's axis list -- don't conflate them into one "negate and reuse" axis. **Hung material can transfer, but needs a new consumer of a signal that already exists live -- correcting an earlier wrong turn in this discussion.** `_EvalLookForDanger` (`eval.c:6194`) really is `#if 0`'d out and dead, but it is *not* the only hung-piece detector in `Eval()`. `_EvalTrappedPieces` (`eval.c`, live, runs every full eval for both colors) already detects exactly "nowhere safe to move to, and currently attacked" -- the `bbStillSafe == 0` branch combined with `_WhoControlsSquareFast(pos, c) == xColor`. When it fires for the side *not* currently on move, it calls `RecordEnprisePieceAtPly(ctx, ctx->uPly - 1, c)`. Tracing where that's actually consumed today: `generate.c:5342` -- `s += (mv.cFrom == cEnprise) * (PIECE_VALUE(mv.pMoved) / 4)`, read via `FindEnprisePiece`. That's a **flee bonus**: it rewards moving a piece *away from* the square where this check found it endangered. So the live detector is wired in the same direction as the disabled routine's docstring (self-protective -- "the mover is about to lose something"), not the "the opponent left me a free capture" direction RFP would want. It's a real, already-computed fact (both colors, every full eval) with only one consumer today (move-ordering's flee nudge) -- using it for RFP means adding a *second* consumer that reads the same recorded fact in the other direction (does the opponent, who just moved, have a trapped+ attacked piece sitting there for the side now on move to take), not writing new detection code and not re-enabling anything disabled. This still matters for RFP the way originally argued: `Eval()` is purely static/positional and never searches captures, so a free piece sitting on the board isn't reflected in `iEval` at all. If the existing detector already flagged one for the side about to move, the true value of the position is higher than `iEval` says, and RFP should fire more confidently (accept a smaller gap), not less. The cost question from the original (disabled) routine -- full-eval-only, judged not worth paying unconditionally -- doesn't block this, since the detection is already being paid for and computed; the only new cost is reading it. Updated axis set to collect for the new table, reflecting both additions: **(gap-above-beta, remaining-depth, improving, opponent-has-hung-piece)** -- four axes. The last one reads `_EvalTrappedPieces`'s already-recorded `cEnprise`/`cTrapped` data from a new angle (see above) rather than computing anything new, but it's still only populated when a full eval actually ran at that node -- gate collection on eval tier, don't force a full eval just to populate the table during data collection. ### Checked and ruled out: approximating the beta-side table from the existing one Tempting shortcut considered: skip collecting new data entirely and approximate the beta-side FH% by querying the *existing* alpha-side table at `(depth, hung=0, gap = iBeta - iEval, lateness=1)` -- i.e. treat the first (best-ordered) move's own "does it raise alpha" cell, with the sign of the gap flipped, as a proxy for "does the node's best move clear beta." The algebra behind it is sound (it's the same mirror-image relationship discussed above, evaluated at the same node instead of one ply over). It doesn't work, though, and the reason is checkable rather than a matter of judgment: `searchsup.c`'s `GapCpBucket` collapses every non-positive gap into a single bucket 0 -- ```c ULONG GapCpBucket(SCORE iGapCp) { if (iGapCp <= 0) { return 0; } ... } ``` -- by design, since from the alpha side, once a move already clears alpha there's nothing left to decide, so the table was never built to distinguish "cleared by 10cp" from "cleared by 900cp" in that regime. A beta-side lookup via `iBeta - iEval` (always <= 0 whenever RFP would even be considered) always lands in that same bucket regardless of magnitude -- exactly the graded information an RFP margin needs, lost before it was ever shipped. It's not recoverable from the raw collection logs either: `search.c`'s own instrumentation (`uRawGapB = GapCpBucket(iAlpha - iEval)`, `search.c:1275`) applies the identical collapse at collection time, not just at baking/shipping time, so the magnitude was discarded at the source. Conclusion: a genuinely new collection run on the positive side of this boundary is required; it can't be shortcut from data already on hand. The one thing worth keeping from this idea: once the new table exists, check that it roughly agrees with the old table's bucket-0 values near the gap-is-zero boundary, as a cheap cross-validation between the two tables.