path: root/src/docs/DEEPER_PRUNING.md

# Deeper pruning in typhoon: ideas and how to test them

Context: typhoon searches ~800x more nodes than Stockfish to reach a
nominally comparable depth on tactical middlegame positions (see session
notes / `head_reference/`). The gap traces mainly to how conservatively
typhoon's LMR/LMP/null-move gates are calibrated, not to a missing
technique -- see "Why past LMR experiments failed" below before trying
any of this blindly, because that pattern has repeated multiple times in
this codebase already.

## Empirical evidence from TREEDUMP (2026-10-22)

Built a matching diagnostic trace into both engines (`TREEDUMP` build
flag; see `docs/TREEDUMP_FORMAT.md` for the build commands for both
engines, the output format, and a Stockfish-side gotcha worth knowing
before re-running this -- piping commands into Stockfish via a closing
pipe races its input thread against the search actually starting and
silently produces a 0-node "search," observed ~90% of the time on this
box; hold stdin open past the search, e.g. `(printf '...'; sleep 2) |
./stockfish`) that logs every move-level decision
(full search / reduced / pruned-without-searching / null-move probe)
keyed by the move path from root, so the two engines' trees can be
diffed on the same FEN. Ran both on
`2q1r1k1/1ppb4/r2p1Pp1/p4n1p/2P1n3/5NPP/PP3Q1K/2BRRB2 w - -` at the
depth each engine first converges on the correct `f6f7+` tactic (`sd
11` for typhoon, `go depth 11-12` for Stockfish; single-threaded,
--cpus 1 / Threads 1 for both).

**Node counts**: typhoon 96,080 nodes vs. Stockfish 5,666 nodes --
~17x, consistent with the ~20x seen at a shallow `sd 4`/`go depth 4`
comparison and the ~800x seen at `sd 18`/`go depth 18` in the original
session transcript. The ratio grows with depth, as expected from a
per-ply branching-factor difference compounding multiplicatively.

**Per-move-decision (`act=`) breakdown, same run** (counts are move-
decision lines, not nodes):

| typhoon | count | | Stockfish | count |
|---|---|---|---|---|
| LMP (pruned, unsearched) | 212,501 | | FP-QUIET (futility, unsearched) | 4,126 |
| FULL | 81,776 | | LMR | 3,340 |
| NMP (null-move probe) | 24,394 | | FULL | 1,681 |
| LMR | 14,315 | | SEE-QUIET (unsearched) | 895 |
| EXT | 11,788 | | FP-CAP (unsearched) | 408 |
| NULLBAILOUT | 486 | | SEE-CAP (unsearched) | 329 |
| | | | PROBCUT | 164 |
| | | | NMP | 130 |
| | | | LMR-RESEARCH | 73 |
| | | | HIST-PRUNE (unsearched) | 57 |

Three concrete, previously-inferred-from-reading-code points that this
data now confirms directly:

1. **LMR volume gap, confirmed**: Stockfish reduces ~26% of its
   move-decisions (3340/12622); typhoon reduces ~3% (14315/478340).
   Matches idea #1 below -- not a hunch, a measured 9x gap in how often
   the mechanism even fires, before even asking about magnitude.
2. **Stockfish's "cheap unsearched skip" is three separate, narrow
   mechanisms; typhoon's is one wide one.** Stockfish splits shallow-
   depth forward pruning into FP-QUIET/SEE-QUIET/HIST-PRUNE (futility
   margin, SEE margin, continuation-history floor -- each independently
   tunable, each catching a different shape of bad move) totaling
   5,078 decisions. typhoon's `ShouldLatePrune`/LMP is a single
   FH-table lookup doing all of that discrimination through one gate,
   and it accounts for 212,501 decisions on its own -- 44% of
   typhoon's *entire* move-decision volume. This reframes idea #2
   (reinstate EFP) and idea #6 (continuation-history re-sweep): the
   real gap may not be "typhoon lacks these mechanisms" so much as
   "typhoon has fused them into one coarser gate," which is harder to
   calibrate precisely than three narrow ones. Worth considering
   *splitting* LMP back into independently-tunable sub-checks rather
   than only adjusting its one shared threshold.
3. **ProbCut (idea #7) is confirmed to matter at non-trivial volume**:
   164 decisions in this one search, each capable of cutting an entire
   node's remaining move list without searching it. Not a rounding
   error.
4. **The Tord Romstad null-move bailout (`searchsup.c:3199`,
   "NULLBAILOUT" above) is real and active** -- 0 fires at `sd 4`, 486
   at `sd 11`, confirming it's a deeper-search phenomenon (it requires
   a parent move that was itself LMR-reduced, which barely happens at
   shallow depth given point 1 above).

See the conversation this came from for the methodology (path-keyed
move-by-move trace, `meld`-able logs) and a worked example of chasing
an apparent score anomaly down to its real (benign) cause -- a
checking-move extension tying alpha, not a bug -- using exactly this
instrumentation.

## Why past LMR experiments failed (read this first)

`lmr_testing/README.md`'s 2026-08-27 sweep record shows a flat pattern:
*every* knob tried moved EBF and solve-count in **opposite directions** --
better branching factor, fewer solves, or vice versa, never both.
Table-only vs `+ONE_PLY` base, fail-high gate at 5/10/20, grandparent-PV
guard, Obsidian's formula vs Ethereal's, adding an "improving" signal --
none was a free win. Two root causes, both still live in the current
codebase and worth internalizing before the next attempt:

1. **Small-suite solve-count deltas are dominated by noise, not signal.**
   The ECM.016 case study in that README: the "stable" baseline PV at
   depth 11 was a shallow, unconvicted pick that flipped to the
   objectively-correct move only past 24.5M nodes. A solve-count delta on
   a position like that measures "which config happened to still be
   wrong at the sample depth," not "which search is better." The fix
   already exists in this repo (the three curated suites +
   `head_reference`'s dual `sd`/`sn` logs) but it has to be used
   correctly: trust `sd` deltas for tree-shape questions, `sn` deltas for
   cost-effectiveness questions, and treat any suite smaller than ~90
   positions as capable of flipping ±2 solves from ordering noise alone
   (see CLAUDE.md's "Dynamic move ordering experiments" section on
   `ecm_ringers`).

2. **Aggregate solve/EBF numbers are a lagging, confounded indicator of
   a *local* decision.** The same CLAUDE.md section (from the later
   move-ordering work, same lesson re-derived independently) is explicit:
   "aggregate solve counts ... are too noisy to tune a single
   move-ordering knob against ... instead, instrument the *local,
   per-move outcome*." Every past LMR sweep in `lmr_testing/` tuned
   purely against the aggregate number. None of them instrumented "of
   the moves this new threshold newly admits for reduction/pruning, what
   fraction actually fail high if searched at full depth" -- which is
   the one measurement that's actually causally close to the knob being
   turned. This is fixable with the existing `FH_TABLE_COLLECTION`/
   `MOVE_ORDERING_EVIDENCE_COLLECTION` infrastructure (see Section 3
   below) and should be done *before* touching an aggregate suite number
   again.

Net: the ideas below are listed with a test plan that leads with the
local/per-move measurement, uses `sd`/`sn` suite diffs as the fast
sanity filter, and reserves self-play/`match_play.py` for final
confirmation only -- specifically to avoid repeating the
aggregate-number-chasing pattern that burned the 2026-08-27 sweep.

## The standing philosophical question

typhoon's LMR/LMP admission is gated on an empirically-measured
"is this bucket almost never a fail-high" threshold
(`LMR_STATIC_ADMIT_PCT_THOUSANDTHS` = 0.5%, `searchsup.c`). Stockfish and
Crafty don't gate this way at all -- Crafty's own comment on its forward
pruning is explicit: *"this is classic forward-pruning and can certainly
introduce errors into the search. However, cluster testing has shown
that this improves play in real games"* (`crafty-25.2/search.c`, around
the FP/LMP block). Both ship it anyway because aggregate Elo over
realistic games is positive even though individual prunes are
provably sometimes wrong.

This means the ideas below fall into two different categories, and they
need *different validation*, not the same one:

- **Category A -- tighten the existing safe-by-construction machinery**
  (bigger tables, more axes, better calibration). These stay validatable
  by the FH-rate/silent-miss harness, because the goal is still "don't
  get it wrong," just "be less overcautious about what counts as safe."
- **Category B -- deliberately accept a nonzero, known error rate**
  because the aggregate payoff is worth it (Crafty/Stockfish's actual
  model). For these, the FH-rate harness tells you *where* the errors
  are, but **only self-play / `match_play.py` can tell you whether
  shipping them is a net win** -- see the earlier conversation for why
  that's not reducible to a suite diff. Don't skip straight to self-play
  though; use the suite-diff step first to confirm the knob is doing
  what you think before spending match-play budget on it (see the
  Validation Ladder below).

## Validation ladder (use for every idea below)

1. **Wiring sanity**: `gmake DEBUG=1 TEST=1` + `debug_smoke_test.sh` --
   confirms no crashes/assert failures before anything else.
2. **Local/per-move instrumentation** (the step every past LMR attempt
   skipped): for the exact population a new threshold newly admits,
   measure "if NOT pruned/reduced, would this move have failed high at
   full depth" via `FH_TABLE_COLLECTION`/`MOVE_ORDERING_EVIDENCE_COLLECTION`-
   style collection builds. This is the only step that tells you *why* a
   suite number moved, and it's what distinguishes "this threshold is
   fine, the suite noise is unrelated" from "this threshold is genuinely
   more dangerous."
3. **`sd 10` suite diff** against `head_reference` on all three curated
   suites (`ecm_ringers`, `ecm_confident_quick`, `ecm_hard_quick`) --
   fast (minutes), tells you whether the tree actually shrank the way you
   expect. Node count is the metric here, not solve count (too noisy at
   this size, see above).
4. **`sn 5000000` suite diff**, same three suites -- tells you whether the
   shrunk tree is cost-effective (same node budget, solved more or
   fewer). This is where Category A ideas should land flat-or-better; a
   regression here (not at `sd`) is the "shrank the tree but made it
   worse" pattern that killed most of the 2026-08-27 sweep attempts.
5. **Only if 1-4 pass**: `match_play.py` gated match
   (`LOWER95 >= 0.5`) against the current baseline DNA/eval, enough games
   for the lower-confidence-bound to actually clear break-even (small-N
   matches are noisy even with identical code, per existing notes). This
   is mandatory for any Category B idea, and a nice-to-have confirmation
   for Category A ideas before baking in.

Never skip straight to step 5. Every idea below should die at step 2 or
3 if it's bad; step 5 is expensive and, on its own, doesn't tell you
*why* something failed, which is exactly the information you need to
iterate.

---

## Ideas

### 1. Increase LMR *magnitude* on already-admitted moves (not admission rate)

Current: admitted moves get `-ONE_PLY` base, with +1/+2/+3 extra plies
reserved for the top 72%/5%/1% most-confident buckets
(`JOINT_EXTRA_TIER{1,2,3}_PCT_THOUSANDTHS`, `searchsup.c:685-692`).
Stockfish's reduction is continuous and unconditional:
`2872/128 * log(moveIndex)`, routinely 3-6 plies for ordinary late quiet
moves at depth 10+ -- more than an order of magnitude bigger than
typhoon's typical cut.

This is the single highest-leverage lever given the ~800x node gap, and
also the one every past attempt already poked at (see `GetLMRReduction`
rewrite history in `lmr_testing/`). The past failures were on the
*admission* side (which moves get reduced), not magnitude alone, and
were tuned against aggregate solve-count, which is exactly what Section
"Why past experiments failed" says not to do. Worth retrying with the
corrected methodology:

- Leave admission (`LMR_STATIC_ADMIT_PCT_THOUSANDTHS`) untouched.
- Replace the flat `_FlatTableExtraPlies` tier payout with something
  continuous in depth and move-number, shaped like Stockfish's/Crafty's
  log-product formula, for the *already-admitted* population only.
- Test: step 2 (does the newly-bigger-cut population's measured FH rate
  stay near the existing ~0.4% baseline, or does it jump specifically in
  the newly-added magnitude band?), then step 3/4.

### 2. Reinstate a cheap, unconditional move-level futility skip (EFP)

`searchsup.c:1094` documents that EFP ("extended futility pruning," a
near-free `eval + margin <= alpha` → skip the move outright, no search)
was removed and folded into the same FH-table-gated LMR/LMP path.
Stockfish still runs this as an *independent*, much cheaper layer
(`search.cpp:1185`, `:1221`) ahead of LMR, on almost every non-improving
quiet move near the leaves, with no empirical-safety gate.

Reintroducing this as a separate, deliberately Category-B (unsound,
margin-based, no FH-table gate) layer -- rather than re-folding it into
the evidence-gated system -- restores a pruning mechanism typhoon
currently lacks entirely. Test: step 2 to characterize the error rate
this specific population would have had (useful data even though you're
accepting it), then step 3/4, then step 5 since this is unambiguously
Category B.

### 3. Loosen null-move pruning's R factor / depth floor

`SelectNullmoveRFactor` and the `NULLMOVE_SKIP_FH_CEILING_THOUSANDTHS`
gate (search.c:82-108) were already recalibrated once this session
(300 → 36000) after discovering the old value was tuned against the
wrong proxy quantity and was "essentially never firing." Worth checking
whether R itself (the reduction applied to the null-move verification
search) is still conservative relative to Stockfish's dynamic R
(`search.cpp` Step 10, scales more aggressively with depth and eval
margin). Given the recalibration just happened and already moved a real
number, this is a good candidate for the *same* sweep methodology
(`nullskip_sweep.sh` already exists) applied to R itself rather than
just the skip ceiling.

Test: step 3/4 directly (R doesn't have a clean "admitted population" to
instrument the way LMR/LMP do -- the null-move verification search
itself is the ground-truth check), using the same sd8/sd11/sd12
cross-sectional sweep methodology as the existing
`NULLMOVE_SKIP_FH_CEILING_THOUSANDTHS` calibration.

### 4. Late Move Pruning: compare against Crafty's move-count-only shape

typhoon's `ShouldLatePrune` (`searchsup.c:1188-1205`) gates on a static
per-remaining-depth max-FH% table (`325, 300, 250, 200, 150, 100, 80, 25,
6, 1, 0` thousandths) *and* a dynamic per-move-identity check, both
empirically calibrated. Crafty's LMP is pure move-count × depth, no
empirical gate at all: `order > LMP[depth]` where `LMP[i] = LMP_base +
pow(i + .5, LMP_scale)`, active through `LMP_depth = 16` plies (own
`data.c`). Crafty prunes **unconditionally** on move count/depth, far
deeper into the tree (16 plies vs. typhoon's effectively much shallower
reach given how fast `uLMPStaticMaxPctThousandths[]` tightens to
near-zero by remaining depth 10).

Two sub-experiments, both worth separating:
- **4a (Category A)**: extend the existing FH-table-gated LMP's reach
  (loosen the tail of `uLMPStaticMaxPctThousandths[]`) -- stays
  validatable via step 2.
- **4b (Category B)**: add an unconditional move-count/depth LMP layer
  on top (or instead of) the gated one, à la Crafty, deliberately
  accepting the error rate. Needs step 5.

`searchsup.c:1138-1149`'s own comment flags that there's currently *no
explicit floor or ceiling* on how deep LMP can fire or how early at the
root it can trigger -- that's worth hardening (an explicit depth floor,
the way Crafty's `LMP_depth` is an explicit, tunable cutoff) regardless
of which sub-experiment you pursue, so a future bad interaction with
some other mechanism doesn't silently prune at the root.

### 5. SEE-based pruning of bad captures earlier/more aggressively

Stockfish's move-loop futility (`search.cpp:1232`,
`!pos.see_ge(move, -23*lmrDepth*lmrDepth)`) prunes losing captures with
a margin that scales quadratically with the already-reduced depth --
i.e. the deeper a losing capture already got reduced, the more freely it
also gets SEE-pruned outright. typhoon's eligibility check
(`CanWeReduceOrPruneMove`, `searchsup.c`) already restricts
captures/promotions to SEE-negative ones before they're even eligible,
but doesn't appear to apply a depth-scaled SEE *margin* the way SF does
-- worth checking whether a losing capture that clears the existing
SEE-negative bar by a wide margin (badly losing, not marginally losing)
could be pruned more aggressively than one that's only slightly losing.

Test: step 2 (bucket by SEE-loss magnitude, not just negative/
non-negative, and check FH rate per bucket -- likely to show the same
kind of monotonic signal the countermove-evidence calibration did), then
3/4.

### 6. Continuation-history-based pruning (new mechanism -- corrected)

**Correction (2026-10-22): this item previously claimed typhoon already
had a `history < -4136*depth`-style skip "mentioned in the 2026-08-29
move-ordering writeup."** That's wrong -- `-4136` is Stockfish's own
constant (`search.cpp`'s continuation-history pruning `continue`,
confirmed present only in `search.cpp`, grepped and absent everywhere
in typhoon's own sources). The 2026-08-29 work added a continuation-
history *table* (`g_ContinuationHistory`) for move-*ordering*
comparisons (`SelectBestWithHistory`) -- it has never been used to
*prune* (skip a move without searching it) at all. The TREEDUMP
empirical data above confirms this independently: Stockfish's
HIST-PRUNE bucket (57 decisions) has no typhoon counterpart in the
`act=` breakdown because there is no code path to tag.

So this is actually **idea #7's sibling**: a structurally absent
mechanism, not an existing one needing a re-sweep. Given typhoon
already tracks the evidence this would need (`g_HistoryCounters` +
`g_ContinuationHistory`, same tables the countermove-evidence
calibration already validated for ordering), adding a pruning check on
top is comparatively cheap to wire up -- the hard part (evidence
infrastructure) already exists; what's missing is the `continue`-style
skip itself plus a threshold, calibrated the same way as everything
else here.

Test: step 2 first and foremost here, since there's no existing
behavior to compare against -- bucket candidate moves by their
existing combined history+continuation evidence (log-ish bands, same
shape as the countermove-evidence calibration) and measure FH rate per
bucket before picking a threshold, rather than guessing one and
sweeping blind. Then 3/4, and 5 if the chosen threshold is deliberately
loose enough to be Category B.

### 7. Multi-cut / ProbCut-style forward pruning at CUT nodes (new mechanism)

Stockfish's "Step 11 internal iterative reductions" and ProbCut
(`search.cpp`, around line 1046-1090) are forward-pruning mechanisms
typhoon doesn't appear to have an equivalent of at all: try a handful of
moves at reduced depth with a raised beta, and if enough of them fail
high, cut the whole node without searching the rest -- a different shape
of pruning than LMR/LMP (both of which operate move-by-move) because it
operates on an aggregate signal across a small sample of moves at the
node. This is a bigger lift than tuning an existing threshold (new code,
not a constant change), so it belongs later in the queue, but it's worth
flagging as a structurally different -- not just more aggressive --
pruning technique that's currently entirely absent, rather than
something typhoon has a weaker version of. It's unambiguously Category
B (ProbCut is explicitly a statistical/unsound cut) and needs step 5.

---

## Summary table

| # | Idea | Category | Fast test (step) | Needs self-play? |
|---|------|----------|-------------------|-------------------|
| 1 | LMR magnitude on admitted moves | A (if gated) / B (if unconditional) | 2, 3, 4 | only if B |
| 2 | Reinstate cheap unconditional EFP | B | 2 (diagnostic only), 3, 4 | yes |
| 3 | Null-move R factor sweep | A (self-verifying) | 3, 4 (sweep script exists) | confirm only |
| 4a | Extend gated LMP's tail | A | 2, 3, 4 | confirm only |
| 4b | Add unconditional LMP layer | B | 3, 4 | yes |
| 5 | Depth-scaled SEE pruning margin | A | 2, 3, 4 | confirm only |
| 6 | Continuation-history pruning (new mechanism, corrected 10-22) | A (if gated) / B (if loose) | 2, 3, 4 | only if loose |
| 7 | Multi-cut / ProbCut (new mechanism) | B | 3, 4 (after implementing) | yes |

Recommended order: **3 → 1 → 4a → 5 → 6 → 2 → 4b → 7** -- cheapest/
lowest-risk (re-sweeping an existing, already-partially-recalibrated
knob) first, brand-new mechanisms (6, 2, 4b, 7) later since those need
new code plus the most expensive validation (step 5 for the Category B
ones). #6 moved down from its original #2 slot in this ordering once
it was corrected from "re-sweep an existing threshold" to "build a new
one" -- it's no longer the cheap win it looked like.