diff options
| author | Scott Gasch <[email protected]> | 2026-10-04 08:17:52 -0700 |
|---|---|---|
| committer | Scott Gasch <[email protected]> | 2026-10-04 08:17:52 -0700 |
| commit | bbdf1bda8f410df6aa9be0a38e71b7db04982198 (patch) | |
| tree | e8315247f700ee94875cd6d2eb5dd81aef71395d /src/searchsup.c | |
| parent | 9b28080f8b3dca4588cb2aaaf748451f45e3c626 (diff) | |
Dynamic move-ordering/LMR session: honest FH tracking, decoupled admission/magnitude, bugfixes, tooling
Lands the 2026-09-28..10-03 move-ordering investigation (full history in
lmr_testing/*.md). Summary of what ships:
LMR/move-ordering redesign (searchsup.c, dynamic.c, data.c, chess.h):
- GetLMRReduction's admission decision (do we reduce at all) is now
decoupled from magnitude (how much): LMR_STATIC_ADMIT_THOUSANDTHS=500
gates admission via the 4D joint fail-high table (data.c) plus a
countermove-match veto; magnitude is a flat Crafty/Ethereal-shaped
log(depth)*log(moves) table (g_iLMRQuietReduction), which measured as
good or better than the old per-tier joint-table payout while being
structurally immune to the per-bucket miscalibration that sank the
tiered approach. g_FailHighs honesty fix (real 0/0 init, not a fake
prior) underlies the dynamic-danger signal.
- Retired NumLeftoverMovesToSelect's depth-indexed selection budget --
evidence showed the leftover pool has real findable signal a bailout
was discarding.
- ShouldLatePrune (overt late-move pruning) implemented but disabled at
its call site -- measured net-negative at the tested threshold; kept
for reference and as a base for a future hang-bucket-9-targeted retry.
- PRUNE_VERIFY, PRUNE_LIVE, DISABLE_LMR: opt-in diagnostic build flags
(GNUmakefile), off in the standard profile.
Bug fixes found and fixed while exercising this work:
- JOINT_EXTRA_TIER_COUNT 4->6 (chess.h): fixed an out-of-bounds counter
write reachable at remaining depth >= 14 (unreachable at sd10, routine
in real search/self-play).
- Node-type instrumentation (search.c, root.c, searchsup.c): fixed four
compounding defects that produced impossible percentages (e.g. 106.2%
of PV nodes) -- wrong denominator, qsearch misclassified as main
search, untyped early-exit nodes, and fail-low tests using the
in-place-raised alpha instead of the initial one.
- FH-rate unit unification (search.c, searchsup.c, dynamic.c, chess.h):
GetMoveFailHigh* returned per-mille while g_uJointFHThousandths is
thousandths-of-a-percent, two different units sharing a "_THOUSANDTHS"
suffix. Unified to one scale, renamed to "_PCT_THOUSANDTHS".
RateBucket's band edges fixed to match.
- QSearch option B (search.c): waives the opponent-stand-pat requirement
at NODE_PV only (sound there since the exact score propagates; not
sound at null-window nodes). iExtensionAmount unit fix (was 0/2 into a
ONE_PLY-scaled field). pi->iEval now published when Eval() runs.
- eval_tune/match_play.py local_ebf: was reporting 0.000 in every match
since 2026-09-18 (regex only matched the trailing-stats parser, not
the live move-scan loop; engines were also spawned with "nopost" so
root.c never emitted the lines at all). True per-ply EBF is ~2.0, not
the ~3.9 every prior match report implied.
- eval_tune/test_vs_head.sh: positional-arg shift ordering bug caused
every no-extra-args run to silently rebuild ./typhoon with a
non-standard profile and, separately, could feed a flag's value in as
the candidate binary path.
- PERF_COUNTERS cleanup (eval.c, search.c): moved 3 leaked rdtsc sites to
the existing EVAL_TIME guard, deleted two concluded one-off diagnostics
(u64HeadStyle*, u64FHJointHist/RateBucket/AttemptsBucket) and their
report plumbing, and re-gated a per-move hang-material estimate behind
FH_TABLE_COLLECTION instead of running it unconditionally.
Infrastructure:
- match_play.py time-odds support (--odds/--st-head/--st-candidate),
validated against the engine seat rather than color.
- Wilson-upper-bound re-bake of the joint table (data.c): cells store a
confidence-aware bound instead of a raw point estimate, so a consumer
can threshold on the value alone; monotone, so every consumer became
strictly more conservative. Verified behavior-neutral for LMR.
Known-open items (not resolved here, see lmr_testing/GET_LMR_REDUCTION.md
section 10 and 2026-10-03_UNCOMMITTED_TRIAGE.md): the self-play gate on
this candidate is underpowered (+5 Elo, 95% CI roughly [-6, +17]); the
curated-suite solve-count deltas used earlier in the investigation turned
out to be noise-dominated cancellation when diffed per position, not the
clean signal they first appeared to be.
Co-Authored-By: Claude Sonnet 5 <[email protected]>
Diffstat (limited to 'src/searchsup.c')
| -rw-r--r-- | src/searchsup.c | 871 |
1 files changed, 863 insertions, 8 deletions
diff --git a/src/searchsup.c b/src/searchsup.c index 0201219..58ae61b 100644 --- a/src/searchsup.c +++ b/src/searchsup.c @@ -223,6 +223,413 @@ ThreadUnderTerminatingSplit(IN SEARCHER_THREAD_CONTEXT *ctx) } +// 2026-10-02: moved here from search.c, along with the rest of the +// joint-table-driven graduated-LMR machinery below -- this used to be +// split across two files purely to minimize the original diff against +// HEAD's LMR (GetLMRReduction decided only the baseline -ONE_PLY, +// search.c's move loop did all the bucket/joint-table post-processing +// on top). That split made it easy to reduce FAR less than intended: +// the baseline decision and the "how much more" decision were made +// from two different, inconsistently-strict dynamic signals. Now one +// function makes the whole call. +// +// EstimateHangingMaterialCp/HangCpBucket/GapCpBucket/MoveNumBucket/ +// DepthBucket are no longer file-static -- search.c's own joint-table +// COLLECTION instrumentation (the measurement block gated on +// fPruneReduceEligible alone, independent of whether uDepth>TWO_PLY or +// any reduction is actually applied -- this is what's still generating +// the next round of g_uJointFHThousandths data, a live, in-progress +// collection run as of this writing) still needs them, so they're +// declared in chess.h and shared rather than duplicated. +SCORE +EstimateHangingMaterialCp(IN SEARCHER_THREAD_CONTEXT *ctx, + IN MOVE mv, + IN ULONG uMoveNum, + IN BITBOARD bbMinorAttacksSnapshot[2], + IN BITBOARD bbRookAttacksSnapshot[2]) +/** + +Routine description: + + Does this quiet (or losing-capture) move look like it hangs + material? Used as one axis ("dumb") of the joint fail-high + prediction table. "Strictly cheaper" only (an equal-value trade is + routinely fine, not a blunder) and generalized over every piece + type instead of hand-picking specific attacker/victim pairs. + +Return value: + + SCORE : estimated cp loss (>= 0), or 0 if nothing looks hung. + +**/ +{ + POSITION *pos = &ctx->sPosition; // already reflects the position + // AFTER mv (MakeMove already ran) + ULONG uOpponent = pos->uToMove; // side to move now == opponent of + // whoever just moved + BITBOARD bbTo; + SCORE iMoveScore; + + ASSERT(ctx->uPly >= 1); + + if (IS_CAPTURE_OR_PROMOTION(mv)) + { +#ifdef DEBUG + if (mv.pPromoted) { + ASSERT(pos->rgSquare[mv.cTo].pPiece == mv.pPromoted); + } + else + { + ASSERT(pos->rgSquare[mv.cTo].pPiece == mv.pMoved); + } +#endif + iMoveScore = ComputeMoveScore(ctx, mv, uMoveNum); + ASSERT(iMoveScore < 0); + return -iMoveScore; + } +#ifdef DEBUG + else + { + ASSERT(pos->rgSquare[mv.cTo].pPiece == mv.pMoved); + } +#endif + + // A king can't "hang material" in the sense this function measures + // -- it's never capturable, so PIECE_VALUE(KING) (== INFINITY_SCORE) + // has no business feeding into a cp-loss estimate at all. + if (IS_KING(mv.pMoved)) + { + return 0; + } + + // Any non-pawn moved onto a square an enemy pawn attacks -- + // always unconditionally bad, a pawn is the cheapest possible + // attacker there is. + if ((!IS_PAWN(mv.pMoved)) && + (0 != (g_PawnAttackOriginBB[uOpponent][mv.cTo] & pos->bbPawns[uOpponent]))) + { + return (SCORE)(PIECE_VALUE(mv.pMoved) - VALUE_PAWN); + } + + // Enemy KING adjacency, checked fresh (real board state, no + // scratch-bitboard involved either way). A king can only capture + // on a square its own side doesn't leave it in check on, so king + // "attacking" our destination square means nothing by itself -- + // only flag this when OUR side has zero defenders of the square. + // Pawns excluded, same reasoning as the pawn-attack check above. + bbTo = COOR_TO_BB(mv.cTo); + if ((!IS_PAWN(mv.pMoved)) && + (0 != (g_KingAttacksBB[mv.cTo] & COOR_TO_BB(KingPosition(pos, uOpponent))))) + { + ULONG uMover = FLIP(uOpponent); + BITBOARD bbOurDefenders = + _WhoAttacksSquareBB(pos, mv.cTo, uMover, pos->bbOccupied) | + (g_PawnAttackOriginBB[uMover][mv.cTo] & pos->bbPawns[uMover]); + + if (0 == bbOurDefenders) + { + return (SCORE)PIECE_VALUE(mv.pMoved); + } + // Defended -- the king alone isn't a threat here. Fall through + // to the minor/rook checks below. + } + + // Anything worth more than a minor, moved onto a square an enemy + // minor attacks. Snapshotted locally by the caller -- NOT read + // from pos->bbMinorAttacks directly, which gets clobbered by every + // recursive Eval() call made while searching an earlier sibling + // move and is never restored by UnmakeMove. + if ((PIECE_VALUE(mv.pMoved) > VALUE_KNIGHT) && + (0 != (bbMinorAttacksSnapshot[uOpponent] & bbTo))) + { + return (SCORE)(PIECE_VALUE(mv.pMoved) - VALUE_KNIGHT); + } + + // Anything worth more than a rook, moved onto a square an enemy + // rook attacks. Same snapshot reasoning as the minor check above. + if ((PIECE_VALUE(mv.pMoved) > VALUE_ROOK) && + (0 != (bbRookAttacksSnapshot[uOpponent] & bbTo))) + { + return (SCORE)(PIECE_VALUE(mv.pMoved) - VALUE_ROOK); + } + return 0; +} + +// See chess.h's HANG_CP_BUCKETS comment for the bucket shape. +ULONG +HangCpBucket(SCORE iHangCp) +{ + ULONG u; + + ASSERT(iHangCp >= 0); + if (0 == iHangCp) + { + return 0; + } + u = 1 + (((ULONG)iHangCp - 1) / HANG_CP_BUCKET_WIDTH); + return MINU(u, HANG_CP_BUCKETS - 1); +} + +// See chess.h's GAP_CP_BUCKETS comment for the bucket shape. Unlike +// HangCpBucket, the input can legitimately be negative or zero (this +// node's own eval already meets or beats alpha) -- that whole +// non-positive range collapses into bucket 0, same as HANG's "not +// dumb". +ULONG +GapCpBucket(SCORE iGapCp) +{ + ULONG u; + + if (iGapCp <= 0) + { + return 0; + } + u = 1 + (((ULONG)iGapCp - 1) / GAP_CP_BUCKET_WIDTH); + return MINU(u, GAP_CP_BUCKETS - 1); +} + +// See chess.h's MOVE_NUM_BUCKETS comment. uMoveNum is 1-based (the +// caller passes uLegalMoves, right after MakeMove succeeded) -- index +// 0 is never produced. +ULONG +MoveNumBucket(ULONG uMoveNum) +{ + ASSERT(uMoveNum >= 1); + return MINU(uMoveNum, MOVE_NUM_BUCKETS - 1); +} + +// See chess.h's SEARCH_DEPTH_BUCKETS comment. uCandDepth is uDepth / +// ONE_PLY, whole plies, legitimately 0 or above. +ULONG +DepthBucket(ULONG uCandDepth) +{ + return MINU(uCandDepth, SEARCH_DEPTH_BUCKETS - 1); +} + +// Maps this project's raw, marginal-resolution bucket indices (exactly +// what DepthBucket/MoveNumBucket produce, and what the 2026-09-28 +// collection run counted against) down to the coarser, cache-shaped +// indices g_uJointFHThousandths was actually baked at. dumb and gap +// pass through unchanged (shipped shape kept them at full marginal +// resolution -- see the plan doc's table). Must stay in exact lockstep +// with bake_joint.py's ship_depth()/ship_late() -- these are the same +// mapping, just re-derived in C for the live lookup path. File-private +// -- only the prediction lookup just below needs the shipped shape; +// search.c's own collection instrumentation counts at full raw +// resolution and never calls these. +static ULONG +_ShipDepthBucket(ULONG uRawDepthBucket) +{ + if (uRawDepthBucket <= 9) return uRawDepthBucket; + if (uRawDepthBucket <= 13) return 10; + return 11; +} + +static ULONG +_ShipLateBucket(ULONG uRawLateBucket) +{ + // Raw indices 0 and 1 are never produced: uMoveNum is 1-based (so 0 + // is out), and the collection/live eligibility gate itself + // (fPruneReduceEligible, search.c, requires uLegalMoves > 1) means + // the raw value handed to MoveNumBucket is never less than 2 + // either. Shift the real range (2..) down by two so the shipped + // array wastes no slot -- confirmed against the 2026-09-30 + // collection run, which showed ship_late bucket 0 permanently empty + // under the old (-1) shift. + if ((uRawLateBucket >= 2) && (uRawLateBucket <= 13)) return uRawLateBucket - 2; + if (uRawLateBucket <= 21) return 12; + if (uRawLateBucket <= 31) return 13; + return 14; +} + +#define JOINT_TABLE_SENTINEL (0xFFFF) + +// Looks up this move's predicted FH% (thousandths of a percent) from +// the baked joint table, given the four RAW bucket indices (as +// HangCpBucket/GapCpBucket/MoveNumBucket/DepthBucket produce them). +// Returns JOINT_TABLE_SENTINEL both for a genuine below-sample-floor +// cell AND for dumb bucket 1 (1-100cp "hung") -- traced to ~97% +// SEE-scored losing captures/underpromotions misfiled into the +// quiet-move axis (2026-09-28 plan doc), not a real "this move looks +// safe" signal. Treating it as "no data" rather than trusting its +// literal (low) value means it can never justify extra reduction, nor +// withhold it -- it just falls back to whatever the other checks say. +static USHORT +_JointTablePredictedFHThousandths(IN ULONG uRawDepthBucket, + IN ULONG uRawDumbBucket, + IN ULONG uRawGapBucket, + IN ULONG uRawLateBucket) +{ + if (1 == uRawDumbBucket) + { + return JOINT_TABLE_SENTINEL; + } + return g_uJointFHThousandths[_ShipDepthBucket(uRawDepthBucket)] + [uRawDumbBucket] + [uRawGapBucket] + [_ShipLateBucket(uRawLateBucket)]; +} + +// 2026-10-02: reverted from the DELIBERATE EXTREME EXPERIMENT values +// (9000/8300/1000) back to the original p75/p25/p5-derived calibration +// (72/5/1) -- that experiment was measured while the dynamic gate +// below still had the old fake-100%-decaying-to-10% behavior, itself +// loose and slow to release. Now that the dynamic gate is honest, +// stacking the most aggressive static multiplier on top of it risks +// double-counting the same conservatism twice. Re-measure node +// savings/solve rate with both changes together before drawing any +// conclusion about either one in isolation. +// 2026-10-02: tried loosening to 150/20/5 (cap 4) in the hope that +// Crafty's much larger LMR magnitudes at comparable remaining depth +// (5-10 plies: see lmr_testing discussion) would translate here too. +// Measured sd10 ringers node count instead went UP (23.0M -> 27.7M, +// WORSE than even HEAD's 26.9M) with the tier-1 bucket specifically +// showing a re-search rate (4.13%) HIGHER than tier 0's (2.73%) -- +// exactly the "distribution-shift failure" this file's own research- +// rate-calibration comment warns about (low-predicted-FH tiers should +// show a RISING research rate with tier, never an inversion at tier +// 1). Reverted to the original p75/p25/p5-derived 72/5/1/cap-3 -- +// MAGNITUDE loosening hits a re-search-tax wall fast; the admission +// widening above (LMR_STATIC_ADMIT_PCT_THOUSANDTHS) is the lever that +// actually worked without this failure mode, because it answers "do +// we reduce at all" (base -1 ply, cheap even when wrong) rather than +// "how much" (large cuts, expensive when wrong). +#define JOINT_EXTRA_TIER1_PCT_THOUSANDTHS (72) // ~p75 of the live + // tries-weighted + // distribution: +1 ply +#define JOINT_EXTRA_TIER2_PCT_THOUSANDTHS (5) // ~p25: +2 plies +#define JOINT_EXTRA_TIER3_PCT_THOUSANDTHS (1) // ~p5: below this (the + // rare, best-predicted + // traffic), +3 plies -- + // the max cut +// 2026-10-02: increasing MAGNITUDE again, but narrower than the +// 150/20/5 attempt above -- that one widened TIER1's ADMISSION +// boundary (which moves qualify at all) and broke (tier-1 research +// rate inverted above tier-0's). This time: leave all three admission +// boundaries (72/5/1) untouched, only raise the PAYOUT for tiers 2/3 +// -- the stricter, already-proven-safe buckets (their research rate +// was LOWER than tier 0's even before this change, i.e. headroom, not +// a crack). Tier 1 keeps its original +1 payout unchanged since it's +// the bucket closest to the population that just proved fragile. +#define JOINT_EXTRA_MAX_PLIES (5) + +// 2026-10-02: ADMISSION is a separate question from MAGNITUDE. +// JOINT_EXTRA_TIER1_PCT_THOUSANDTHS above was previously doing double duty +// as both "is the base -ONE_PLY even allowed" AND "does this move +// additionally earn +1 extra ply" -- a threshold calibrated for the +// latter (the top ~25% of traffic) is far too strict a gate for the +// former. The overnight self-play evidence (old dodgy thresholds, +// effectively a no-op admission gate at this layer) shipped even-or- +// better strength at 0.9-1.0 ply deeper than HEAD -- direct evidence +// that broad admission, not a narrow "only the provably safest moves" +// gate, is the right call here. Set this wide open: the static table +// only vetoes the base reduction when it has a real opinion AND that +// opinion is actively bad (worse than the whole-population baseline +// rate), never merely "not in the top tier." +// 2026-10-02: max-admission (1000, a no-op gate) measured a real, +// consistent sn5M solve-count loss on all three curated suites vs. +// HEAD (ringers -2, confident_quick -2, hard_quick -1) despite being +// deeper/lower-EBF than the 500 setting below -- unlike sd10 (where a +// solve dip from less search is expected and uninteresting), a dip at +// FIXED NODE BUDGET means the extra depth bought by over-wide +// admission isn't paying for itself yet. 500 was flat-to-noise on all +// three at sn5M while still gaining +0.1/+0.4/+0.5 ply over HEAD -- +// this is the safer base to build further levers (e.g. LMP) on top of. +// 2026-10-03: LEFT AT 500 across the Wilson-upper-bound re-bake of +// g_uJointFHThousandths (see data.c's header). The re-bake raised +// 19,649 of 21,780 cells, which cut the admitting-CELL count at 500 +// from 21,047 to 15,415 -- so it was briefly raised to 1000 to +// compensate. That was wrong: cell counts are not traffic-weighted. +// Measured against the real eligible population (87.8M tries from the +// 2026-10-03 sd10 collection), admit<500 on the NEW table admits +// 92.57% of LMR traffic versus 92.88% measured on the old one, while +// 1000 admits 95.62% -- i.e. 500 is the value that holds LMR behavior +// constant, and the raised cells turn out to be overwhelmingly +// low-traffic ones. Lesson: size any threshold change against +// tries-weighted traffic, never against cell counts. +#define LMR_STATIC_ADMIT_PCT_THOUSANDTHS (500) // 0.500% +#ifdef DEPTH_ONLY_EXTRA_REDUCTION +// See GNUmakefile's DEPTH_ONLY_EXTRA_REDUCTION comment -- the trigger +// threshold below (6 plies) already guarantees the full R=3 extra plus +// the base -1 ply (4 total cut) leaves at least this much remaining, so +// this floor is smaller than the axis-gated version's -- it's a pure +// safety net here, not doing the real gating work (the depth trigger +// is). +#define JOINT_EXTRA_MIN_REMAINING_DEPTH (TWO_PLY) +#define DEPTH_ONLY_TRIGGER_DEPTH (6 * ONE_PLY) +#else +// 2026-09-29: ONE_PLY -- the most aggressive floor. NEUTRALIZE_NULL_ +// BAILOUT (GNUmakefile) showed the earlier FOUR_PLY floor's +// justification (a measured silent-miss rate) was overwhelmingly +// (80-99.8%) a measurement artifact of shadow-verification +// methodology, not genuine reduction danger -- the true false-negative +// rate at FOUR_PLY, once properly measured, was already near zero. +#define JOINT_EXTRA_MIN_REMAINING_DEPTH (ONE_PLY) +#endif + +// 2026-10-02: g_iLMRQuietReduction (dynamic.c/InitLMRTable) is a +// Crafty/Ethereal-shaped flat log(depth)*log(moves) table, built at +// startup, that NOTHING has ever read -- a prior session built the +// simple mechanism and then went and built the joint-table/dynamic-FH +// system instead without ever wiring this in. It encodes the FULL +// reduction (not an "extra" on top of a base), in ONE_PLY-scaled +// ticks. Checked against Crafty's actual LMR[depth][order] table at +// the remaining-depth range our own suites exercise (5-10 plies): +// d=5,m=8 gives ~2.1 plies here vs Crafty's 2.3; d=10,m=8 gives ~2.7 +// here vs Crafty's 3.0 -- same ballpark, same shape, no per-bucket +// static-table judgment to be selectively wrong about (the failure +// mode that just broke the joint-table magnitude tiers above). Used +// here ONLY for magnitude (how much EXTRA beyond the existing -ONE_PLY +// base) -- admission (whether to reduce at all) stays exactly as +// GetLMRReduction already computes it (static/dynamic agreement, +// killer/countermove vetoes); this only replaces the fragile tier +// payout with Crafty's actual mechanism. +static ULONG +_FlatTableExtraPlies(IN ULONG uRemainingDepth, IN ULONG uMoveNum) +{ + ULONG uDepthIdx = MINU(uRemainingDepth / ONE_PLY, MAX_PLY_PER_SEARCH); + ULONG uMoveIdx = MINU(uMoveNum, LMR_TABLE_MAX_MOVES); + SCORE iTotalTicks = g_iLMRQuietReduction[uDepthIdx][uMoveIdx]; + SCORE iExtraTicks = iTotalTicks - ONE_PLY; + + if (iExtraTicks <= 0) + { + return 0; + } + return (ULONG)(iExtraTicks / ONE_PLY); +} + +// 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 +// universal backstop -- a move identity whose own honest observed +// rate already exceeds what an AVERAGE leftover move does is never +// reduction-safe, regardless of context; (2) folded into the same +// decision below, additionally compared against the joint table's own +// bucket-specific prediction for the exact (depth, hang, gap, late) +// situation this move is in right now -- a strictly tighter, +// context-aware version of the same idea. +// 2026-10-03 unit unification: was (4) in per-mille, which is the SAME +// nominal 0.4% this is now expressed as directly. Not quite a no-op +// though, and the difference is worth knowing: the old comparison was +// `floor(fh*1000/attempts) > 4`, which can only become true once +// fh/attempts >= 0.005 -- i.e. truncation made the old gate behave like +// 0.5%, not the 0.400% it documented. 400 here is faithful to the +// documented intent and is a hair stricter than what actually shipped. +// The affected band is fh/attempts in [0.401%, 0.5%), which requires +// >= 200 observations of one move identity to even express and is +// essentially unpopulated per chess.h's u64FHJointHist (the dynamic +// 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% + +// 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 +// thousandths (0,1,2-4,5-9,10-19,20-49,50-99,100+ -- the last band +// starts exactly at the old HEAD-style 10% ceiling). + + INT GetLMRReduction(IN SCORE iEval, IN SCORE iAlpha, @@ -233,41 +640,489 @@ GetLMRReduction(IN SCORE iEval, IN ULONG uLegalMoves, IN MOVE mv, IN ULONG uMoveNum, - IN INT iExtend) + IN INT iExtend, + IN BITBOARD bbMinorAttacksSnapshot[2], + IN BITBOARD bbRookAttacksSnapshot[2], + OUT ULONG *puExtraTier) /** Routine description: - True pre-LMR/pre-counter-move baseline: original binary history - pruning (fixed -ONE_PLY), no graded table, no PV-parent guard, no - counter-move exemption. Kept under the GetLMRReduction name so - search.c/split.c's call sites need no changes. + 2026-10-02: consolidated here -- this used to be two decisions in + two files (this function decided only a baseline -ONE_PLY; + search.c's move loop separately consulted the joint FH% table and + piled more reduction on top as post-processing), kept split + originally just to minimize the diff against HEAD's LMR. That + split let the baseline decision and the "how much more" decision + run off two different, inconsistently-strict dynamic signals. Now + one function, one combined decision: + + 1. Killer-adjacency exemption (this ply's own killers, ply-2 + back's killers) -- unchanged from the original baseline. + 2. Countermove-table match exemption -- a bare match (any + evidence at all, unlike generate.c's evidence-gated tier + promotion) against the move played immediately before mv + means mv has fail-high'd/been-best here before in this exact + context; withhold reduction. + 3. Dynamic fail-high-rate baseline: GetMoveFailHighPctThousandths + must have real samples (uAttempts > 0) and a rate at or below + the table-wide average leftover move's (data.c's 0.400%). + 4. If all of the above pass, look up the joint table's own + bucket-specific prediction for this move's actual situation + (depth/hang/gap/late) and apply the STRICTER version of check + 3 against it specifically: if this move's own rate already + exceeds what's predicted for moves in this exact situation, + veto the whole reduction, not just the extra plies. No data + for this bucket (JOINT_TABLE_SENTINEL) is treated as no claim + either way, not a veto. + 5. Only once still eligible after (4): convert the bucket + prediction into 0-3 extra whole plies on top of the baseline, + floored so the combined reduction never leaves less than + JOINT_EXTRA_MIN_REMAINING_DEPTH remaining. Note: the move has already been made by the time we get here. +Parameters: + + ... + IN BITBOARD bbMinorAttacksSnapshot[2], + IN BITBOARD bbRookAttacksSnapshot[2] : EstimateHangingMaterialCp's + snapshot inputs -- see that function's own comment for why + they're snapshotted rather than read live. split.c's HelpSearch + call site has no such snapshot available (deliberately never + wired up -- see this file's/search.c's "Main move loop + (search.c) only" history) and passes all-zero arrays instead; + EstimateHangingMaterialCp degrades safely on zeros (every + "attacked by X" check becomes unconditionally false), the same + already-accepted degradation search.c itself uses when its own + snapshot is stale (see search.c's fParentAttackTablesAreFresh). + OUT ULONG *puExtraTier : optional (may be NULL, e.g. split.c, which + has no use for the joint-extra-tier re-search/calibration + instrumentation keyed on this). Receives the extra-ply tier + (0-3) actually applied, 0 whenever this function returns 0 OR + returns only the baseline -ONE_PLY. + Return value: - INT : 0 if no reduction, else -ONE_PLY. + INT : 0 if no reduction, else a negative multiple of ONE_PLY (the + FULL combined baseline+extra reduction). **/ { + ULONG uAttempts; + ULONG uFHPctThousandths; + FLAG fCounterMoveMatch; + ULONG uExtraPlies = 0; + ASSERT(ctx->uPly > 0); ASSERT(mv.uMove); ASSERT((uMoveNum > 0) || (uLegalMoves == 0)); + if (NULL != puExtraTier) + { + *puExtraTier = 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 + // also none of the table/history lookups that feed it. + return(0); +#endif + + // 2026-10-02: countermove-table veto. mv has ALREADY been made by + // the time we get here (this function's own doc comment), so mv's + // own ply is ctx->uPly-1 (same convention the killer checks below + // already use) -- the move the opponent played immediately BEFORE + // mv, which is what the countermove table is keyed on (see + // generate.c's _ScoreAllMoves, which computes this same index at + // ctx->sPlyInfo[uPly-1].mv for a node at ply uPly, i.e. one more + // ply back than mv's own), is therefore ctx->sPlyInfo[ctx->uPly-2].mv. + // Careful: this is TWO plies back from here, not one. + // + // generate.c's own use of a countermove match (COUNTERMOVE_TIER_ + // BONUS) is evidence-gated -- a bare match with no accumulated + // history+continuation evidence gets no promotion there. This is + // a deliberately looser, separate question: a match ALONE, however + // thin its evidence, means mv has fail-high'd (or been the node's + // final best move) at least once immediately after this exact + // previous move somewhere in this search -- a finer-grained, + // context-specific memory than GetMoveFailHighPctThousandths' bare + // per-move-identity rate (which doesn't know what came before mv) + // can offer by itself. Treat a match as sufficient reason to + // withhold reduction even if it wasn't strong enough to promote + // mv's tier in generate.c. + fCounterMoveMatch = FALSE; + if (ctx->uPly >= 2) + { + MOVE mvPrev = ctx->sPlyInfo[ctx->uPly - 2].mv; + if (0 != mvPrev.uMove) + { + ULONG uCounterIdx = MOVE_TO_INDEX(mvPrev); + fCounterMoveMatch = + IS_SAME_MOVE(mv, ctx->mvCounter[uCounterIdx][0]) || + IS_SAME_MOVE(mv, ctx->mvCounter[uCounterIdx][1]); + } + } + + // 2026-10-02: g_FailHighs now starts genuinely empty (0/0) per + // move identity, not seeded to a faked 100% (see + // ClearDynamicMoveOrdering, dynamic.c) -- this is now a real, + // honest observed fail-high rate, not a decaying fake prior. + // 1. uAttempts == 0: we have no dynamic evidence on this exact + // move identity at all (yet) -- play it safe, don't reduce. + // Not a tuned floor; any real observation at all is treated + // as evidence, consistent with the bucket-specific check + // (below) being the thing that actually judges whether that + // evidence is reassuring. + // 2. uFHPctThousandths > LMR_FH_BASELINE_PCT_THOUSANDTHS: this move + // identity's own lifetime rate is already worse than an + // AVERAGE leftover move's -- never reduction-safe on that + // basis alone, independent of context. + uFHPctThousandths = GetMoveFailHighPctThousandths(mv, &uAttempts); + +// 2026-10-03: REMOVED two one-off PERF_COUNTERS diagnostics that lived +// here, both of which did real per-decision WORK rather than just +// incrementing a counter, in the hottest decision point in the search: +// +// 1. The HEAD-style-replay diagnostic (u64HeadStyleEligible / +// u64HeadStyleWouldReduce). It called GetMoveFailHighRawCounts and +// then did an integer division to reconstruct HEAD's old +// fake-1-FH/1-attempt gate, for every LMR decision. Its own comment +// said "Not meant for any other caller; remove once the +// HEAD-vs-candidate reduction-rate comparison this supports is +// done." That comparison is done -- it is what established that the +// candidate admits 92-94% of eligible decisions against HEAD-style's +// 70-75%, recorded in lmr_testing/GET_LMR_REDUCTION.md section 10.2. +// +// 2. The (attempts x rate) joint histogram (u64FHJointHist), also +// marked "one-off". It served its purpose: it is what showed the +// per-move-identity dynamic rate is BIMODAL rather than clustered +// around the 0.400% population average (~71% at exactly 0%, a +// separate well-evidenced population at 1-10%, ~7% pure cold) -- +// see section 4 of that document. +// +// Both were listed for removal in that file's own "next steps" item 5. +// PERF_COUNTERS is supposed to be counter increments; these were +// lookups plus divisions per decision, and PERF_COUNTERS measured at +// ~7.2% nps against a no-counters build. AttemptsBucket/RateBucket +// (the band helpers they used) went with them. + + // 2026-10-02: REDESIGNED (second pass) -- three populations, not + // two. Empirically (chess.h's u64FHJointHist diagnostic) the + // per-move-identity dynamic rate is bimodal, not clustered around + // data.c's 0.400% population average: ~71% of eligible decisions + // sit at a genuine, often well-evidenced 0% own rate; a separate, + // real, often well-evidenced (100+ attempts) chunk sits durably + // at 1-10%; and ~7% are pure cold (zero observations this game). + // Treating "elevated own rate" as a hard veto (old design) throws + // away information for exactly the wrong population -- a move + // with real, well-evidenced personal danger in a static-safe + // situation isn't necessarily UNSAFE to reduce, it's just not + // safe enough to pile extra plies onto. So: + // - cold (uAttempts == 0): no personal history to judge at all + // -- defer entirely to the static table (its job: no game + // warmup needed). Was unconditionally refused before. + // - warm + safe (own rate <= baseline, agrees with a static + // "safe" read): full normal eligibility, base + extra tiers + // -- both signals agree, lean into it. + // - warm + dangerous (own rate > baseline, even though static + // says safe): still reduce, but by the MINIMUM only (base + // -ONE_PLY, extra forced to 0) -- the static table's safe + // read for this general situation doesn't get silently + // overridden to a full veto by one move's specific bad + // personal record, but that record still caps how far we're + // willing to go on its word. + // + // Identity vetoes (killer-adjacency, countermove match) are + // unchanged and still unconditional -- they're a different kind + // of signal (an exact, specific antecedent/ply match) than "this + // move's own aggregate rate looks elevated", and still zero out + // the whole decision regardless of what either FH signal says. if ((!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][0])) && (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][1])) && ((ctx->uPly < 3) || (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][0]) && !IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][1]))) && - (GetMoveFailHighPercentage(mv, NULL) <= 10)) + (FALSE == fCounterMoveMatch)) { + ULONG uRawDepthB, uRawDumbB, uRawGapB, uRawLateB; + USHORT uPredictedFH; + INT iLocalExtend; + FLAG fBaseEligible; + FLAG fDynamicDanger = (uAttempts > 0) && + (uFHPctThousandths > LMR_FH_BASELINE_PCT_THOUSANDTHS); + ASSERT(!InCheck(&ctx->sPosition, ctx->sPosition.uToMove)); - return(-ONE_PLY); + +#ifdef DEPTH_ONLY_EXTRA_REDUCTION + // Bypass the axis-based table entirely -- see GNUmakefile's + // DEPTH_ONLY_EXTRA_REDUCTION comment. No static prediction is + // computed in this branch, so base eligibility is simply + // "survived the identity vetoes above"; a dynamic-danger + // reading still caps the flat extra bonus to 0 even here. + fBaseEligible = TRUE; + uExtraPlies = (!fDynamicDanger && (uRemainingDepth >= DEPTH_ONLY_TRIGGER_DEPTH)) ? + JOINT_EXTRA_MAX_PLIES : 0; +#else + SCORE iHangCp = EstimateHangingMaterialCp( + ctx, mv, uMoveNum, + bbMinorAttacksSnapshot, + bbRookAttacksSnapshot); + uRawDepthB = DepthBucket(uRemainingDepth / ONE_PLY); + uRawDumbB = HangCpBucket(iHangCp); + uRawGapB = GapCpBucket((SCORE)(iAlpha - iEval)); + uRawLateB = MoveNumBucket(uLegalMoves); + uPredictedFH = _JointTablePredictedFHThousandths( + uRawDepthB, uRawDumbB, uRawGapB, uRawLateB); + + if (JOINT_TABLE_SENTINEL == uPredictedFH) + { + // No static data for this exact bucket -- absence of + // data is not evidence of danger. Per the user's + // explicit prescription: moves with no history (static + // OR dynamic) should still get the base reduction unless + // the DYNAMIC signal has actively flagged this exact + // move identity as dangerous. Admit at base-only + // whenever not dynamically dangerous, regardless of + // whether uAttempts is 0 (cold) or warm+safe. + fBaseEligible = (FALSE == fDynamicDanger); + } + 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); + } + uExtraPlies = (fBaseEligible && (FALSE == fDynamicDanger)) ? + _FlatTableExtraPlies(uRemainingDepth, uLegalMoves) : 0; +#endif + + if (FALSE == fBaseEligible) + { + return(0); + } + + // 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- + // wraparound clamp to do this implicitly. + iLocalExtend = iExtend + (-ONE_PLY); + if (uExtraPlies > 0) + { + INT iMaxExtra = + ((INT)uRemainingDepth - (INT)ONE_PLY + iLocalExtend - + (INT)JOINT_EXTRA_MIN_REMAINING_DEPTH) / + (INT)ONE_PLY; + if (iMaxExtra < 0) + { + iMaxExtra = 0; + } + if ((INT)uExtraPlies > iMaxExtra) + { + uExtraPlies = (ULONG)iMaxExtra; + } + if (uExtraPlies > JOINT_EXTRA_MAX_PLIES) + { + uExtraPlies = JOINT_EXTRA_MAX_PLIES; + } + iLocalExtend -= (INT)(uExtraPlies * ONE_PLY); + } + if (NULL != puExtraTier) + { + *puExtraTier = uExtraPlies; + } + return(iLocalExtend); } return(0); } +// 2026-10-02: Crafty-style late move pruning (LMP) -- an overt skip, +// not a reduction. search.c/crafty-25.2's LMP has no static table, no +// dynamic veto, no per-move judgment at all: it hammers everything +// past a per-depth move-count threshold, close to the leaves, and +// relies on iterative deepening (at/near the root) plus the sheer +// branching-factor win to make this pay off in aggregate -- exactly +// the thesis this session's overnight self-play run (0.9-1.0 ply +// deeper, even-or-better strength, from aggressive-even-if-unsound +// reduction) is built on. Unlike LMR, a pruned move has NO re-search +// safety net -- if it was actually good, this search never finds out, +// this iteration, at this node. That irrecoverability is exactly why +// pruning is reserved here for a much narrower population than +// GetLMRReduction's reduction-admission gate: only the tail where +// BOTH static and dynamic signals agree the move is as safe as +// anything in the whole eligible population gets this treatment. +// +// Deliberately does NOT touch GetLMRReduction's own admission gate or +// tiers -- this is a second, independent lever, applied (by the +// caller, search.c) as a check ahead of GetLMRReduction: if this +// returns TRUE, the move is skipped entirely and GetLMRReduction is +// never even called for it. +// 2026-10-02: KNOWN ISSUE, not yet fixed -- flagged during review, +// documented here rather than patched since LMP is disabled at its +// call site (search.c) and not worth further churn right now. This +// function's LMP_MAX_REMAINING_DEPTH ceiling (below) only permits +// pruning near the leaf, mirroring Crafty's FP_depth/LMP_depth +// near-leaf-only restriction -- but our own joint table +// (g_uJointFHThousandths) shows predicted FH% DECLINING as remaining +// depth grows (checked directly, dumb=0/gap=0/late=0: depth-bucket 0 +// predicts 17119 thousandths, bucket 5 predicts 4033, bucket 11 +// predicts 617 -- a ~25x drop). So this ceiling only permits pruning +// in the HIGHEST-FH region and forbids it in the LOWEST-FH region -- +// backwards relative to our own evidence, not a safety margin. +// Crafty's version isn't contradicting itself the same way: it has no +// static table at all, so the near-leaf restriction IS its entire +// risk model (a mistake near the leaf costs little re-exploration). +// We inherited Crafty's structural depth gate without inheriting its +// justification, on top of a mechanism that already has a better, +// contradicting signal. +// +// The real asymmetry (user's framing): the COST of a wrong prune does +// legitimately grow with remaining depth (a missed tactic under a +// 10-ply-remaining subtree is worse than one under a 2-ply one) -- but +// that should tighten the CONFIDENCE BAR required, not forbid the +// decision outright past an arbitrary cutoff. The principled fix, +// per lmr_testing/SPEC.md's "how much statistical confidence is +// actually needed" section: gate on the STATIC table's own per-cell +// sample count via a rule-of-three bound (N ~= 3 * applications_per_game +// / target_misses_per_game), NOT on remaining depth and NOT on a +// per-move-identity dynamic sample count. SPEC.md derives N ~= 14.4M +// for a 1/1000-games miss target (no deep-zone zero-FH cell clears +// this), and a later, explicitly-endorsed loosening to 1/100 games +// gives N ~= 1.44M (largest real cell: 1.34M, close) or 1/20 games +// gives N ~= 288K (16 deep-zone zero-FH cells clear this today). +// **Blocker**: `g_uJointFHThousandths` (data.c) ships only the rate +// per cell, not the sample count behind it (cells need >=500 tries to +// ship at all, per data.c:1208's comment, but a 500-try cell and a +// 1.34M-try cell are indistinguishable once shipped) -- applying this +// bound correctly requires re-baking the table with a companion +// per-cell count array (bake_joint.py + data.c), not yet done. Until +// then, this function's ceiling/dynamic-sample-floor below is a +// placeholder, not a calibrated bound. +#define LMP_MAX_REMAINING_DEPTH (6 * ONE_PLY) // mirrors Crafty's + // FP_depth=7 (prunes + // in the last 6 + // plies before qsearch) +#define LMP_BASE_MOVENUM (12) // never prune before this many + // legal moves already tried +#define LMP_PER_PLY_MOVENUM (4) // + this many moves of extra + // slack per remaining ply +#define LMP_STATIC_MAX_PCT_THOUSANDTHS JOINT_EXTRA_TIER3_PCT_THOUSANDTHS // the + // strictest static tier only + // (~p5 of real traffic) +#define LMP_DYNAMIC_MIN_SAMPLES (10) // well-evidenced, not a guess +// 0.100% -- near-zero observed rate. 2026-10-03 unit unification: was +// (1) in per-mille, i.e. the same nominal 0.1%. Same truncation caveat +// as LMR_FH_BASELINE_PCT_THOUSANDTHS above (the old `> 1` could only +// fire at fh/attempts >= 0.002, so the shipped gate behaved like 0.2%); +// moot in practice since LMP is disabled at its call site +// (search.c:1228). Note this constant and LMP_STATIC_MAX_PCT_THOUSANDTHS +// used to be the two reasons this unit mismatch was dangerous: both +// were literally (1), 100x apart in meaning, four lines apart in this +// same block. +#define LMP_DYNAMIC_MAX_PCT_THOUSANDTHS (100) + +FLAG +ShouldLatePrune(IN SCORE iEval, + IN SCORE iAlpha, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN ULONG uRemainingDepth, + IN ULONG uLegalMoves, + IN MOVE mv, + IN ULONG uMoveNum, + IN BITBOARD bbMinorAttacksSnapshot[2], + IN BITBOARD bbRookAttacksSnapshot[2], + OUT ULONG *puPredictedFH) +{ + ULONG uAttempts, uFHPctThousandths, uMoveNumFloor; + ULONG uRawDepthB, uRawDumbB, uRawGapB, uRawLateB; + USHORT uPredictedFH; + SCORE iHangCp; + + ASSERT(ctx->uPly > 0); + ASSERT(mv.uMove); + + if (uRemainingDepth > LMP_MAX_REMAINING_DEPTH) + { + return FALSE; + } + + uMoveNumFloor = LMP_BASE_MOVENUM + + (LMP_PER_PLY_MOVENUM * (uRemainingDepth / ONE_PLY)); + if (uLegalMoves <= uMoveNumFloor) + { + return FALSE; + } + + // Never prune a move with any killer-adjacency or countermove- + // match history -- same identity vetoes GetLMRReduction uses, + // unconditional here too. + if (IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][0]) || + IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][1]) || + ((ctx->uPly >= 3) && + (IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][0]) || + IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][1])))) + { + return FALSE; + } + if (ctx->uPly >= 2) + { + MOVE mvPrev = ctx->sPlyInfo[ctx->uPly - 2].mv; + if (0 != mvPrev.uMove) + { + ULONG uCounterIdx = MOVE_TO_INDEX(mvPrev); + if (IS_SAME_MOVE(mv, ctx->mvCounter[uCounterIdx][0]) || + IS_SAME_MOVE(mv, ctx->mvCounter[uCounterIdx][1])) + { + return FALSE; + } + } + } + + // Dynamic signal: if there's real, well-evidenced history on this + // exact move identity and it's not essentially zero, don't + // gamble -- this is the ultra-safe tail only, not "probably fine." + uFHPctThousandths = GetMoveFailHighPctThousandths(mv, &uAttempts); + if ((uAttempts >= LMP_DYNAMIC_MIN_SAMPLES) && + (uFHPctThousandths > LMP_DYNAMIC_MAX_PCT_THOUSANDTHS)) + { + return FALSE; + } + + // Static signal: must have real data AND be in the strictest + // (safest) tier -- no data (sentinel) is a reason to NOT gamble + // on overt pruning, unlike GetLMRReduction's more permissive + // treatment of that case for mere reduction. + iHangCp = EstimateHangingMaterialCp(ctx, mv, uMoveNum, + bbMinorAttacksSnapshot, + bbRookAttacksSnapshot); + uRawDepthB = DepthBucket(uRemainingDepth / ONE_PLY); + uRawDumbB = HangCpBucket(iHangCp); + uRawGapB = GapCpBucket((SCORE)(iAlpha - iEval)); + uRawLateB = MoveNumBucket(uLegalMoves); + uPredictedFH = _JointTablePredictedFHThousandths( + uRawDepthB, uRawDumbB, uRawGapB, uRawLateB); + // 2026-10-03: publish the prediction so PRUNE_VERIFY can band-bucket + // this decision by the very number it was made on. Optional -- every + // non-instrumented caller passes NULL. + if (NULL != puPredictedFH) + { + *puPredictedFH = uPredictedFH; + } + if ((JOINT_TABLE_SENTINEL == uPredictedFH) || + (uPredictedFH >= LMP_STATIC_MAX_PCT_THOUSANDTHS)) + { + return FALSE; + } + + return TRUE; +} + SCORE DecodeMoveValueEstimate(IN MOVE mv, |
