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/search.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/search.c')
| -rw-r--r-- | src/search.c | 1052 |
1 files changed, 952 insertions, 100 deletions
diff --git a/src/search.c b/src/search.c index 8f4779e..713d35e 100644 --- a/src/search.c +++ b/src/search.c @@ -76,10 +76,168 @@ extern FLAG g_fCanSplit[MAX_PLY_PER_SEARCH]; #define TRY_GENERATED_MOVES (3) // EFP's fail-high-history exemption: below EFP_FH_MIN_SAMPLES -// observations, GetMoveFailHighPercentage's result isn't trusted +// observations, GetMoveFailHighPctThousandths's result isn't trusted // enough to override the static-eval-based decision either way. -#define EFP_FH_MIN_SAMPLES (5) -#define EFP_FH_PRUNE_THRESHOLD (10) +// THOUSANDTHS, not whole percent, since 2026-10-02's rename -- 100 +// thousandths == 10%, unchanged in effect from the old whole-percent +// EFP_FH_PRUNE_THRESHOLD of 10. +#define EFP_FH_MIN_SAMPLES (5) +#define EFP_FH_PRUNE_THRESHOLD_PCT_THOUSANDTHS (10000) // 10% + +// 2026-10-02: the joint-table-driven graduated-LMR decision itself +// (bucket helpers, _JointTablePredictedFHThousandths/_JointTableExtraPlies, +// JOINT_EXTRA_TIER*_THOUSANDTHS, the floor/cap clamp) moved into +// GetLMRReduction (searchsup.c) -- this file used to make that +// decision as post-processing on top of GetLMRReduction's own +// baseline, split across two files/two inconsistent dynamic checks +// purely to minimize the original diff against HEAD's LMR. The move +// loop below now just calls GetLMRReduction once and uses its result. +// +// EstimateHangingMaterialCp/HangCpBucket/GapCpBucket/MoveNumBucket/ +// DepthBucket moved there too but are no longer file-static -- the +// measurement/collection block further below (gated on +// fPruneReduceEligible alone, independent of the LMR decision -- this +// is what's still generating the next round of g_uJointFHThousandths +// data) still needs them, so they're declared in chess.h and called +// from here unchanged in behavior, just by their new (un-underscored) +// public names. + +#if (defined(PERF_COUNTERS) && defined(PRUNE_VERIFY)) || defined(PRUNE_LIVE) +// Band a deep-prune candidate by the predicted FH% the decision was +// made on (thousandths of a percent; post-Wilson-re-bake that value +// already encodes the cell's own sample confidence -- data.c header). +// Banding by the decision variable is what lets one run answer "is +// 'prune if predicted <= K' sound" for every candidate K at once. +#if defined(PERF_COUNTERS) && defined(PRUNE_VERIFY) +static ULONG +PruneVerifyBand(ULONG uPredicted) +{ + if (uPredicted == 0) return 0; + if (uPredicted == 1) return 1; + if (uPredicted == 2) return 2; + if (uPredicted <= 5) return 3; + if (uPredicted <= 10) return 4; + if (uPredicted <= 50) return 5; + if (uPredicted <= 500) return 6; + return 7; +} +#endif + +// Mirror of searchsup.c's file-static _ShipDepthBucket. Duplicated +// rather than exported because this is calibration-only code that +// should leave no trace in a normal build; if PRUNE_VERIFY ever +// graduates to something permanent, hoist the real one into chess.h +// instead of keeping two copies. +static ULONG +ShipDepthBucketPublic(ULONG uRawDepthBucket) +{ + if (uRawDepthBucket <= 9) return uRawDepthBucket; + if (uRawDepthBucket <= 13) return 10; + return 11; +} +#define JOINT_TABLE_SENTINEL_PUBLIC (0xFFFF) + +static ULONG +ShipLateBucketPublic(ULONG uRawLateBucket) +{ + if ((uRawLateBucket >= 2) && (uRawLateBucket <= 13)) return uRawLateBucket - 2; + if (uRawLateBucket <= 21) return 12; + if (uRawLateBucket <= 31) return 13; + return 14; +} + +// Local mirror of searchsup.c's _JointTablePredictedFHThousandths, +// including its dumb-bucket-1 sentinel rule (that bucket is ~97% +// SEE-scored losing captures/underpromotions misfiled onto the quiet +// axis, so its literal low value is not a real "safe" signal). +// Local mirrors of searchsup.c's file-static AttemptsBucket/RateBucket +// (calibration-only; see ShipDepthBucketPublic's note on duplication). +#if defined(PERF_COUNTERS) && defined(PRUNE_VERIFY) +static ULONG +PvAttBucket(ULONG uAttempts) +{ + if (0 == uAttempts) return 0; + if (1 == uAttempts) return 1; + if (2 == uAttempts) return 2; + if (uAttempts <= 4) return 3; + if (uAttempts <= 9) return 4; + if (uAttempts <= 24) return 5; + if (uAttempts <= 99) return 6; + return 7; +} + +static ULONG +PvRateBucket(ULONG uPct) +{ + if (0 == uPct) return 0; + if (uPct <= 100) return 1; + if (uPct <= 400) return 2; + if (uPct <= 900) return 3; + if (uPct <= 1900) return 4; + if (uPct <= 4900) return 5; + if (uPct <= 9900) return 6; + return 7; +} +#endif + +#define PRUNE_LIVE_SENTINEL JOINT_TABLE_SENTINEL_PUBLIC +#define PruneLivePredict PruneVerifyPredict +static ULONG +PruneVerifyPredict(IN SEARCHER_THREAD_CONTEXT *ctx, IN MOVE mv, + IN ULONG uMoveNum, IN ULONG uLegalMoves, + IN SCORE iAlpha, IN SCORE iEval, IN ULONG uDepth, + IN BITBOARD bbMinor[2], IN BITBOARD bbRook[2], + OUT ULONG *puShipDepth) +{ + SCORE iHangCp = EstimateHangingMaterialCp(ctx, mv, uMoveNum, bbMinor, bbRook); + ULONG uDumb = HangCpBucket(iHangCp); + ULONG uShipD = ShipDepthBucketPublic(DepthBucket(uDepth / ONE_PLY)); + + *puShipDepth = uShipD; + if (1 == uDumb) + { + return JOINT_TABLE_SENTINEL_PUBLIC; + } + return g_uJointFHThousandths[uShipD][uDumb] + [GapCpBucket((SCORE)(iAlpha - iEval))] + [ShipLateBucketPublic(MoveNumBucket(uLegalMoves))]; +} +#endif + +#ifdef JOINT_EXTRA_VERIFY +// 2026-09-28: buckets the FULLY (base + extra) reduced search's actual +// remaining depth by EFP's own two-tier margin-schedule boundaries +// (search.c's "selective futility"/"extended futility" tiers, keyed to +// ONE_PLY+THREE_QUARTERS_PLY and TWO_PLY+THREE_QUARTERS_PLY -- see that +// code's own comment) rather than plain whole-ply buckets. The +// depth-bucketed silent-miss calibration showed a spike specifically +// at whole-ply-bucket "remaining depth 2", which straddles both EFP +// tier boundaries -- this re-buckets on the ACTUAL boundaries to test +// whether the spike is really an EFP-tier-window effect (a different +// pruning mechanism behaving differently in that specific band) rather +// than "shallower is chaotic" in the simple monotonic sense. +static ULONG +_PostReduceDepthBucketEfpAligned(ULONG uNextDepthRaw) +{ + if (uNextDepthRaw < ONE_PLY) + { + return 0; // shouldn't happen given the JOINT_EXTRA_MIN_REMAINING_DEPTH floor -- safety net + } + if (uNextDepthRaw <= (ONE_PLY + THREE_QUARTERS_PLY)) + { + return 1; // EFP "selective futility" tier active + } + if (uNextDepthRaw <= (TWO_PLY + THREE_QUARTERS_PLY)) + { + return 2; // EFP "extended futility" tier active + } + if (uNextDepthRaw <= (TWO_PLY + THREE_QUARTERS_PLY + TWO_PLY)) + { + return 3; // no EFP, but still nearby + } + return 4; // no EFP, comfortably deeper +} +#endif // EXPERIMENT: is history+continuation evidence predictive of a // countermove match's own FH%? See chess.h's CM_EVIDENCE_BUCKETS @@ -301,9 +459,72 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, ULONG uNextDepth; ULONG uLegalMoves = 0; FLAG fIsLeftoverMove = FALSE; + // Stamped once below, right after this node's own Eval() call and + // before any MakeMove in the move loop changes pos's live + // signature out from under it -- see EstimateHangingMaterialCp's + // comment (above _CMEvidenceBucket) for why this matters: bbMinor + // Attacks/bbRookAttacks are only trustworthy when they were + // written by a full, non-lazy Eval() call for THIS exact position. + FLAG fParentAttackTablesAreFresh; + // 2026-09-28: snapshotted into LOCAL (stack) storage at the same + // point fParentAttackTablesAreFresh is captured -- pos->bbMinor + // Attacks/bbRookAttacks themselves are NOT safe to read later in + // the move loop, because every recursive Search() call made while + // trying an earlier sibling move also calls Eval() on ITS OWN + // position, overwriting these same shared pos-> fields, and + // UnmakeMove does not restore them (they're eval scratch space, + // not real position state -- unlike u64NonPawnSig/u64PawnSig, + // which UnmakeMove DOES restore, which is exactly why the + // signature check above kept reporting "fresh" long after the + // underlying bitboards had been clobbered by a completely + // unrelated node deep in an earlier sibling's subtree). Confirmed + // empirically: every single real fail-high sampled in the queen- + // attacked-by-rook bucket turned out to have NO actual rook + // attacking the destination square once checked by hand -- this + // is why. Local copies can't be touched by recursion. + BITBOARD bbMinorAttacksSnapshot[2]; + BITBOARD bbRookAttacksSnapshot[2]; + // 2026-09-30: single shared "would we ever consider pruning or + // reducing this move" eligibility gate -- the unified gate EFP and + // LMR both consult now (formerly two separately-coded, slightly + // different checklists), plus the losing-capture admission rule + // the FH-table work has been testing (the old, separate gates + // excluded ALL captures/promotions unconditionally; this + // deliberately admits losing ones, via the SEE sign generate.c + // already cached on the move, matching the population the joint + // table was actually trained on -- see lmr_testing/SPEC.md's + // "gate-1" section). Computed ONCE per move, unconditionally (not + // just under PERF_COUNTERS -- it now gates live search behavior in + // every build profile), so a move that should never actually be + // pruned or reduced (a check, a check-escape, a PV node, an + // already-extended move, a node-wide threat, a mate-magnitude + // alpha) is excluded up front rather than patched around + // downstream. Note this deliberately does NOT include LMR's old + // uLegalMoves > 5 floor -- that requirement is dropped as part of + // unifying onto this gate, per direct instruction, since it was + // LMR-specific rather than part of the shared "unremarkable move" + // definition gate-1 describes. + FLAG fPruneReduceEligible = FALSE; #ifdef PERF_COUNTERS + // See the node-type counter comment below: guards the surprise + // counters at end: so a node short-circuited by CommonSearchInit + // (and therefore never typed for this visit) cannot be scored + // against a stale eNodeType left by a previous node at this ply. + FLAG fNodeTypedThisVisit = FALSE; FLAG fThisMoveIsCountermoveMatch = FALSE; ULONG uCMEvidenceBucket = 0; + ULONG uThisMoveHangBucket = 0; + ULONG uThisMoveGapBucket = 0; + ULONG uThisMoveNumBucket = 0; + ULONG uThisMoveDepthBucket = 0; + // 2026-09-28: which joint-extra-reduction tier (0 == none, the + // GetLMRReduction baseline only) fired for THIS move, if any -- + // stashed at decision time (LMR call site) and consulted again + // later, at the re-search-on-fail-high check, purely for the + // calibration counters below. Never influences search behavior by + // itself. + ULONG uThisMoveJointExtraTier = 0; + FLAG fThisMoveJointExtraEligible = FALSE; #endif HASH_ENTRY *pHash; FLAG fThreat; @@ -367,14 +588,42 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, { goto end; } + +#ifdef PERF_COUNTERS + // 2026-10-03: denominator for the node-type surprise line, counted + // HERE rather than inside CommonSearchInit, for two reasons that + // were both silently corrupting that metric: + // + // 1. FULL-WIDTH ONLY. CommonSearchInit is the single funnel both + // Search() and QSearch() pass through, so counting there swept + // in qsearch -- ~84% of the tree -- and a qsearch node whose + // stand-pat already beats beta returns iBestScore >= iBeta + // immediately. Typed ALL, that lands in "ALL failed high", + // making the headline number mostly a measure of stand-pat + // frequency. The question the line's name asks is about + // full-width node-type prediction, so qsearch is excluded from + // both numerator (below) and denominator (here). + // 2. NEVER STALE. Every early-exit path in CommonSearchInit (hash + // cutoff, repetition draw, ply/depth limit, EGTB hit) returns + // TRUE *before* pi->eNodeType is assigned, and the caller's + // `goto end` lands squarely on the surprise counters -- which + // then scored the node against whatever type the PREVIOUS node + // at this ply happened to leave behind. That is what produced + // a "PV failed high/low = 106.2% of PV nodes" reading: more + // surprises than nodes of that type, which is impossible + // unless some were attributed to a type the node never had. + // Reaching this line means CommonSearchInit returned FALSE, + // i.e. the type really was assigned for THIS visit. + // + // NOTE: the NODE_TYPE enum and every behavioral consumer of it + // (all of which only ever test against NODE_PV) are untouched. + fNodeTypedThisVisit = TRUE; + ASSERT((ULONG)pi->eNodeType < 3); + INC(ctx->sCounters.tree.u64NodeTypeCount[(ULONG)pi->eNodeType]); +#endif + DTEnterNode(ctx, uDepth, FALSE, iAlpha, iBeta); iInitialAlpha = iAlpha; - // pi->eNodeType is set centrally by CommonSearchInit (see its own - // comment) -- covers both Search() and QSearch() from one place. - // Safe default until the real move-generation/scoring call below - // sets this to whatever scheme actually ran (generate.c's four - // _Score* functions and RescoreMovesViaSearch are the authoritative - // setters -- see MOVE_SCORING_SCHEME's own comment in chess.h). pi->eMoveScoringScheme = MOVE_SCORING_NORMAL; ASSERT((IS_CHECKING_MOVE(mvLast) && (TRUE == pi->fInCheck)) || (!IS_CHECKING_MOVE(mvLast) && (FALSE == pi->fInCheck))); @@ -504,6 +753,28 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, { iImprovement = (iEval - ctx->sPlyInfo[ctx->uPly - 2].iEval); } + // Must be captured HERE, before any MakeMove in the loop below + // changes pos's live signature out from under it. + fParentAttackTablesAreFresh = + (pi->u64FullEvalSig == (pos->u64NonPawnSig ^ pos->u64PawnSig)); + + // Snapshot into local storage RIGHT HERE too, same reasoning -- + // see this array's declaration comment. If not fresh, zero them + // rather than leave garbage; EstimateHangingMaterialCp still + // checks fParentAttackTablesAreFresh first and won't consult + // these when it's FALSE, but zeroing avoids depending on that. + if (TRUE == fParentAttackTablesAreFresh) + { + bbMinorAttacksSnapshot[WHITE] = pos->bbMinorAttacks[WHITE]; + bbMinorAttacksSnapshot[BLACK] = pos->bbMinorAttacks[BLACK]; + bbRookAttacksSnapshot[WHITE] = pos->bbRookAttacks[WHITE]; + bbRookAttacksSnapshot[BLACK] = pos->bbRookAttacks[BLACK]; + } + else + { + bbMinorAttacksSnapshot[WHITE] = bbMinorAttacksSnapshot[BLACK] = 0; + bbRookAttacksSnapshot[WHITE] = bbRookAttacksSnapshot[BLACK] = 0; + } GENERATE_NO_MOVES; @@ -655,6 +926,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, GenerateMoves(ctx, mvHash, GENERATE_ESCAPES); if (MOVE_COUNT(ctx, ctx->uPly)) { + // TODO: Experiment with removing these extensions. if (NUM_CHECKING_PIECES(ctx, ctx->uPly) > 1) { iOrigExtend += QUARTER_PLY; @@ -762,28 +1034,17 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, (ctx->sPlyInfo[ctx->uPly - 2].iExtensionAmount <= 0)) { ASSERT(uDepth >= THREE_QUARTERS_PLY); + ASSERT(iAlpha + 1 == iBeta); if (iEval < iAlpha) { - // 2026-09-17: tried folding + pi->iPositional[ - // pos->uToMove] into both conditions below (same - // role as QSearch's FUTILITY_BASE_MARGIN_BY_ - // SOURCE[tier] + iPositional[side]) -- rolled - // back, untested in isolation, after a bundled - // self-play run (also carrying the margin_a/ - // margin_b percentile switch, the QSearch - // futility margin recalibration, the _EvalKing - // fix, and the drawish-in-both-lazy-tiers change) - // came back flat/slightly negative with no way - // to attribute the result to any one change. See - // TODO (EFP_BASE_MARGIN_BY_SOURCE entry) -- the - // idea itself isn't rejected, just never - // validated on its own. PLY_INFO.iPositional - // (chess.h) and the Eval() call populating it - // (just above, in this function) are left in - // place -- useful per-ply infrastructure - // regardless of whether this exact gate ends up - // using it. + // TODO: EFP is 100% based on the "gap" dimension: i.e., + // the distance between iEval and iAlpha makes a FH under + // this move unlikely. However, there are other good + // signals that we are ignoring here. Such as: does the + // move seem to hang material? If so, we should prune + // more willingly. If not, we should be less eager to + // prune here (maybe). if ((uDepth <= ONE_PLY + THREE_QUARTERS_PLY) && (iEval + VALUE_KNIGHT + iImprovement <= iAlpha)) { @@ -805,6 +1066,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, if (x < ctx->sMoveStack.uEnd[ctx->uPly]) { ASSERT(x >= ctx->sMoveStack.uBegin[ctx->uPly]); + // Always fully select the best remaining move, // regardless of tier -- retired the old // NumLeftoverMovesToSelect budget (a depth-indexed @@ -835,6 +1097,19 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // never classifies an IID-rescored move as a // leftover (matches pre-retirement behavior). fIsLeftoverMove = FALSE; +#ifdef PERF_COUNTERS + // Reset every iteration, BEFORE the LMR decision + // block (below) can set it for this move -- without + // this, a move that skips the extra-reduction + // branch entirely (e.g. GetLMRReduction's own + // baseline didn't fire) would silently inherit and + // re-report a PRIOR move's stale tier at the + // re-search-check site later in this same + // iteration... except stale across ITERATIONS, not + // within one -- this reset must happen before this + // iteration's own LMR decision, not after. + fThisMoveJointExtraEligible = FALSE; +#endif if (MOVE_SCORING_IID_RESCORED == pi->eMoveScoringScheme) { SelectBestNoHistory(ctx, x); @@ -850,12 +1125,12 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, MVF_MOVE_SEARCHED)); ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED; #endif +#ifdef PERF_COUNTERS // Countermove evidence calibration -- ongoing check // that COUNTERMOVE_EVIDENCE_THRESHOLD (chess.h) is // still well-calibrated: log every countermove- // matched move tried, bucketed by its own // accumulated history+continuation evidence. -#ifdef PERF_COUNTERS fThisMoveIsCountermoveMatch = FALSE; if ((!IS_CAPTURE_OR_PROMOTION(mv)) && (ctx->uPly > 0) && @@ -1032,17 +1307,64 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // sole extension-runaway guard now; see root.c's construction // of that table. + // See this flag's declaration comment above. Computed + // unconditionally now -- both EFP and LMR gate live + // pruning/reduction decisions on it, not just the + // PERF_COUNTERS instrumentation that used to be its only + // consumer. + // + // Note: no separate (x != 0) check -- x is only ever 0 + // during the TRY_HASH_MOVE stage's single iteration, which + // is always the very first move tried at this node + // (uLegalMoves == 0 going in, per that stage's own ASSERT), + // so uLegalMoves can be at most 1 while x == 0. The + // (uLegalMoves > 1) test below already rules that out. + ASSERT((uLegalMoves > 1) ? (x != 0) : TRUE); + fPruneReduceEligible = + (uLegalMoves > 1) && + (NODE_PV != pi->eNodeType) && + (TRUE == fIsLeftoverMove) && + (iExtend <= 0) && + (!IS_ESCAPING_CHECK(mv)) && + (!IS_CHECKING_MOVE(mv)) && + (!fThreat) && + (iAlpha < +NMATE) && + ((!IS_CAPTURE_OR_PROMOTION(mv)) || + (!(ctx->sMoveStack.mvf[x - 1].bvFlags & MVF_SEE_NONNEGATIVE))); + + FLAG fThisMoveLMPPruned = FALSE; + if (TRUE == fPruneReduceEligible) + { + fThisMoveLMPPruned = ShouldLatePrune( + iEval, iAlpha, ctx, uDepth, + uLegalMoves, mv, (x - 1), + bbMinorAttacksSnapshot, + bbRookAttacksSnapshot, + NULL); +#ifdef PERF_COUNTERS + if (TRUE == fThisMoveLMPPruned) + { + INC(ctx->sCounters.tree.u64LMPPruned); + } +#endif + } + // Decide how much (if any) to reduce this move's depth -- - // graded LMR. + // graded LMR. Gated on the unified fPruneReduceEligible now + // (2026-09-30) instead of its own separately-coded + // checklist -- note this deliberately drops the old + // uLegalMoves > 5 floor (fPruneReduceEligible only requires + // > 1), and newly admits losing captures (fPruneReduceEligible's + // SEE-sign rule) where the old checklist excluded all + // captures unconditionally. uDepth > TWO_PLY stays as LMR's + // own extra threshold on top -- not part of the shared gate. + // Skipped for an LMP-pruned move -- no point grading a + // reduction for a move that's not being searched at all. if ((uDepth > TWO_PLY) && - (pi->eNodeType != NODE_PV) && - (uLegalMoves > 5) && - (fIsLeftoverMove) && - (0 == iExtend) && - (!IS_ESCAPING_CHECK(mv)) && - (!IS_CAPTURE_OR_PROMOTION(mv)) && - (!IS_CHECKING_MOVE(mv))) + (TRUE == fPruneReduceEligible) && + (FALSE == fThisMoveLMPPruned)) { + ULONG uExtraTier = 0; INT iLMR = GetLMRReduction(iEval, iAlpha, iBeta, @@ -1052,62 +1374,86 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, uLegalMoves, mv, (x - 1), // Note: x==0 if hash - iExtend); + iExtend, + bbMinorAttacksSnapshot, + bbRookAttacksSnapshot, + &uExtraTier); if (iLMR < 0) { ASSERT(iExtend == 0); iExtend = iLMR; +#ifdef PERF_COUNTERS + uThisMoveJointExtraTier = uExtraTier; + fThisMoveJointExtraEligible = TRUE; + INC(ctx->sCounters.tree.u64JointExtraTries[uExtraTier]); +#endif } } // Extended futility pruning -- per-move checklist. EFP // pruning a fail-high is unrecoverable (unlike an LMR - // reduction, which only delays discovery), so this is - // deliberately stricter than GetLMRReduction's own - // checklist, not just a copy of it: explicit capture/ - // promotion/checking-move exemptions (not just an ASSERT - // that they can't reach here, which is all the old code - // had), a killer-adjacency exemption (ply-1 and ply-3, - // borrowed from GetLMRReduction), a well-evidenced - // fail-high-history exemption (GetMoveFailHighPercentage, - // requiring at least EFP_FH_MIN_SAMPLES observations before - // trusting the percentage either way), an en-prise-escape - // exemption, and a node-wide suppression when this node's - // own null-move probe raised fThreat. See - // lmr_testing/RESULTS.md for the individual experiments - // that arrived at this checklist. + // reduction, which only delays discovery), so on top of the + // unified fPruneReduceEligible gate this keeps its own, + // stricter downstream checks: a killer-adjacency exemption + // (ply-1 and ply-3, borrowed from GetLMRReduction), a + // well-evidenced fail-high-history exemption + // (GetMoveFailHighPctThousandths, requiring at least + // EFP_FH_MIN_SAMPLES observations before trusting the + // rate either way). See lmr_testing/RESULTS.md for + // the individual experiments that arrived at this + // checklist. // - // Explicit leftover-only gate (fIsLeftoverMove, this move's - // own iValue < GOOD_MOVE): every high-performer move - // (winning/even capture, killer, killer-mate, sufficiently- - // evidenced countermove match) is excluded from pruning - // consideration by construction, not just as a side effect - // of the capture/check/killer exemptions above happening to - // cover the same ground. Belt-and-suspenders on purpose -- - // this is the one thing that must never be true of a move - // we skip outright. - fThisMoveEFPPruned = FALSE; - if ((x != 0) && - (uLegalMoves > 1) && - (uFutilityMargin) && - (TRUE == fIsLeftoverMove) && - (iExtend <= 0) && - (!IS_ESCAPING_CHECK(mv)) && - (!IS_CAPTURE_OR_PROMOTION(mv)) && - (!IS_CHECKING_MOVE(mv)) && - (!fThreat) && - (ComputeMoveScore(ctx, mv, (x - 1)) < uFutilityMargin)) + // Gated on fPruneReduceEligible now (2026-09-30) instead of + // its own separately-coded checklist -- this newly admits + // losing captures (fPruneReduceEligible's SEE-sign rule) + // where the old checklist excluded all captures + // unconditionally, matching the population the joint table + // was actually trained on (see lmr_testing/SPEC.md's + // "gate-1" section). + // + // No separate ComputeMoveScore(...) < uFutilityMargin test + // -- verified always true given fPruneReduceEligible, not + // just an ASSERT of convenience: fPruneReduceEligible's + // (!IS_ESCAPING_CHECK(mv)) already rules out + // MOVE_SCORING_ESCAPE (generate.c's _ScoreAllEscapes sets + // MOVE_FLAG_ESCAPING_CHECK unconditionally on every move it + // scores, so a node whose own side is in check can never + // reach here), leaving only MOVE_SCORING_NORMAL live at + // this call site. Under that scheme, DecodeMoveValueEstimate + // (searchsup.c) returns MIN0(iRawValue) for every leftover + // move -- an ordinary quiet leftover's iValue (PSQT only, + // 0..1000, generate.c's _ScoreAllMoves) is always < SORT_ + // THESE_FIRST so it clamps to exactly 0, and a losing + // capture's iValue is already negative (SEE's own result, + // never bumped into the winning-capture SORT_THESE_FIRST + // tier) so it passes through unchanged -- either way <= 0. + // uFutilityMargin is always > 0 here (the truthy check just + // above). So (<=0) < (>0) always, for this call site only -- + // this equivalence is NOT claimed for any other caller of + // ComputeMoveScore. + if ((FALSE == fThisMoveEFPPruned) && + (TRUE == fPruneReduceEligible) && + (uFutilityMargin)) { ULONG uFHAttempts = 0; - ULONG uFHPct = GetMoveFailHighPercentage(mv, &uFHAttempts); + ULONG uFHPctThousandths = GetMoveFailHighPctThousandths(mv, &uFHAttempts); fThisMoveEFPPruned = ((uFHAttempts < EFP_FH_MIN_SAMPLES) || - (uFHPct <= EFP_FH_PRUNE_THRESHOLD)) && + (uFHPctThousandths <= EFP_FH_PRUNE_THRESHOLD_PCT_THOUSANDTHS)) && (!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]))); +#ifdef DISABLE_EFP + // Audit-only: everything above still runs (so + // uFutilityMargin, the FH-history lookup, etc. are all + // still exercised/measurable), just never actually + // prunes -- isolates the joint-table LMR's own + // behavior from EFP's single-axis margin pruning. See + // GNUmakefile's DISABLE_EFP comment. + fThisMoveEFPPruned = FALSE; +#endif } if (TRUE == fThisMoveEFPPruned) { @@ -1121,6 +1467,84 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, if (TRUE == fIsLeftoverMove) { INC(ctx->sCounters.tree.u64LeftoverTries); + // 2026-09-28: gated on fPruneReduceEligible now, + // not just fIsLeftoverMove -- excludes checks, + // check-escapes, PV nodes, already-extended moves, + // threat nodes, and mate-magnitude alpha up front, + // matching HEAD's own EFP/LMR eligibility gates + // (see that flag's declaration comment). Captures + // and quiet moves both flow into the SAME buckets + // again -- back to measuring the combined signal, + // now with the contaminating populations removed + // instead of split apart to isolate them. Computed + // here (before UnmakeMove) and reused at the + // FH-side increment below -- calling this again + // after UnmakeMove would evaluate the WRONG + // (restored, side-to-move-flipped-back) position. + // 2026-10-03: this whole 4D-collection block is now + // gated on FH_TABLE_COLLECTION rather than riding + // along with PERF_COUNTERS. It is COLLECTION + // instrumentation -- it exists to build + // g_uJointFHThousandths, not to report on a normal + // search -- and CLAUDE.md already says + // FH_TABLE_COLLECTION is deliberately kept out of + // the standard profile precisely because this + // measurably costs nps. This block escaped that + // gating. + // + // It is not a counter increment: it calls + // EstimateHangingMaterialCp per eligible move, which + // does real attack-bitboard work. It was also being + // computed TWICE per move in any build that also had + // a prune gate enabled, since that gate needs the + // same hang bucket -- which inflated the candidate's + // nps deficit in the PRUNE_LIVE self-play match + // (-6.0% vs head) and made that match mildly unfair + // to the candidate. +#ifdef FH_TABLE_COLLECTION + if (TRUE == fPruneReduceEligible) + { + SCORE iHangCp; + + INC(ctx->sCounters.tree.u64EligibleLeftoverTries); + iHangCp = EstimateHangingMaterialCp( + ctx, mv, x - 1, + bbMinorAttacksSnapshot, + bbRookAttacksSnapshot); + uThisMoveHangBucket = HangCpBucket(iHangCp); + INC(ctx->sCounters.tree.u64HangEstimateTries[uThisMoveHangBucket]); + + // "Down axis": how far below alpha is this + // node's own static eval? Same eligibility + // gate as the dumb axis -- iAlpha/iEval are + // both plain node-local SCOREs (not shared, + // mutable pos-> fields like bbRookAttacks + // was), so no snapshot/staleness concern here. + uThisMoveGapBucket = GapCpBucket( + (SCORE)(iAlpha - iEval)); + INC(ctx->sCounters.tree.u64GapEstimateTries[uThisMoveGapBucket]); + + // "Late axis": this move's own 1-based ordinal + // position among moves actually tried here. + uThisMoveNumBucket = MoveNumBucket(uLegalMoves); + INC(ctx->sCounters.tree.u64MoveNumEstimateTries[uThisMoveNumBucket]); + + // "Depth axis": remaining search depth at + // this node, before this move's own + // extension/reduction. + uThisMoveDepthBucket = DepthBucket(uDepth / ONE_PLY); + INC(ctx->sCounters.tree.u64DepthEstimateTries[uThisMoveDepthBucket]); + + // Joint 4D cell, same four bucket indices, in + // addition to (not instead of) the marginals + // above -- keeps the marginals live this run as + // a cheap cross-check that the joint reduces to + // what we already understand. + INC(ctx->sCounters.tree.u64JointTries + [uThisMoveDepthBucket][uThisMoveHangBucket] + [uThisMoveGapBucket][uThisMoveNumBucket]); + } +#endif } if (TRUE == fThisMoveIsCountermoveMatch) { @@ -1179,10 +1603,252 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // Research deeper if history pruning failed if ((iExtend < 0) && (iScore >= iBeta)) { +#ifdef PERF_COUNTERS + // Calibration for the joint-extra-reduction tiers + // above: did the tier this move was assigned (0 == + // GetLMRReduction's baseline only, 1-3 == extra + // plies the table added) actually predict a + // re-search here? If low-predicted-FH tiers show an + // ELEVATED research rate rather than a lower one, + // that's the distribution-shift failure this + // project's history keeps producing, caught here + // (a suite run) instead of in a self-play match. + if (TRUE == fThisMoveJointExtraEligible) + { + INC(ctx->sCounters.tree.u64JointExtraResearch[uThisMoveJointExtraTier]); + } +#endif uNextDepth -= iExtend; // undo the full reduction, whatever its magnitude pi->iExtensionAmount = 0; iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth); } +#if defined(PERF_COUNTERS) && defined(JOINT_EXTRA_VERIFY) + // "Silent miss" shadow verification -- only reachable + // when the branch above did NOT fire, i.e. this move's + // extra-reduced score was < beta and so triggered no + // real re-search. Would removing just the EXTRA plies + // (restoring the depth HEAD's own baseline -ONE_PLY + // reduction alone would have used) have found a + // fail-high we're about to silently miss? Full + // coverage, every extra-reduced move that reaches here + // -- see GNUmakefile's JOINT_EXTRA_VERIFY comment for + // why this is calibration-only, never a normal build. + else if ((TRUE == fThisMoveJointExtraEligible) && + (uThisMoveJointExtraTier > 0)) + { + ULONG uShadowDepth = + uNextDepth + (uThisMoveJointExtraTier * ONE_PLY); + SCORE iShadowScore; +#ifdef NEUTRALIZE_NULL_BAILOUT + // 2026-09-29: searchsup.c's null-move "history- + // reduced bailout" branch (Tord Romstad idea) reads + // (pi-1)->iExtensionAmount -- OUR OWN reduction on + // mv -- to decide whether to fabricate a "please + // re-search me" placeholder score instead of a + // real one. In a real move-loop search that's + // correct: the fabricated score negates up to + // exactly iBeta+1 one level up, which search.c's + // own re-search-on-fail-high machinery correctly + // interprets and acts on. Our shadow verification + // is a bespoke one-off Search() call with no such + // wrapper, so we'd misread that signal as a + // genuinely-computed fail-high. Temporarily zero + // OUR OWN pi->iExtensionAmount so this one specific + // check can't fire for mv -- everything deeper in + // the shadow subtree still goes through the normal + // move loop (with its wrapper intact) if the same + // mechanism legitimately fires there for some + // other, unrelated reduced move. + INT iSavedExtensionAmount = pi->iExtensionAmount; + pi->iExtensionAmount = 0; +#endif + iShadowScore = + -Search(ctx, -iBeta, -iAlpha, uShadowDepth); +#ifdef NEUTRALIZE_NULL_BAILOUT + pi->iExtensionAmount = iSavedExtensionAmount; +#endif +#ifdef SILENT_MISS_TRACE + // UpdatePV is only ever called on the iScore > + // iAlpha branch that does NOT also fail high + // (search.c's main move loop) -- a beta cutoff + // jumps straight to "end" without touching the PV + // array at all, since a fail-high score is only a + // lower bound, not a real line. Since our whole + // diagnostic signal IS a fail-high (iShadowScore >= + // iBeta), WalkPV would always come back empty here + // -- not useful. What DOES get written on a cutoff + // is the hash table (StoreLowerBound, just before + // that same "end" jump), so walk a short hash + // chain instead, the same side-effect-free idiom + // FinishPVTailFromHash (util.c) already uses for + // exactly this purpose. + CHAR szShadowPV[SMALL_STRING_LEN_CHAR] = ""; + { + MOVE mvChain[8]; + ULONG uChainLen = 0; + MOVE mvNext; + + while ((uChainLen < 8) && + (0 != (mvNext = GetPonderMove(pos)).uMove)) + { + strncat(szShadowPV, MoveToSan(mvNext, pos), + ARRAY_LENGTH(szShadowPV) - strlen(szShadowPV) - 1); + strncat(szShadowPV, " ", + ARRAY_LENGTH(szShadowPV) - strlen(szShadowPV) - 1); + mvChain[uChainLen++] = mvNext; + if (FALSE == MakeMove(ctx, mvNext)) + { + uChainLen--; + break; + } + } + while (uChainLen > 0) + { + UnmakeMove(ctx, mvChain[--uChainLen]); + } + } +#endif + // EFP-tier-aligned bucket for the FULLY (base + + // extra) reduced search's actual remaining depth -- + // see _PostReduceDepthBucketEfpAligned's comment. + ULONG uPostReduceDepthBucket = + _PostReduceDepthBucketEfpAligned(uNextDepth); + + INC(ctx->sCounters.tree.u64JointExtraVerifyTries + [uThisMoveJointExtraTier][uPostReduceDepthBucket]); + if (iShadowScore >= iBeta) + { + INC(ctx->sCounters.tree.u64JointExtraVerifySilentMiss + [uThisMoveJointExtraTier][uPostReduceDepthBucket]); + if (iShadowScore == (iBeta + 1)) + { + INC(ctx->sCounters.tree.u64JointExtraVerifyNullBailoutSignature + [uThisMoveJointExtraTier]); + } +#ifdef SILENT_MISS_TRACE + // pos currently reflects the position AFTER mv + // (MakeMove already ran earlier this + // iteration, UnmakeMove hasn't run yet) -- + // pi->sPosition (the pre-move parent) is + // DEBUG-only, not available in a release + // build, so print the POST-move FEN plus the + // move in coordinate notation (MoveToIcs takes + // just the move, no pre-move disambiguation + // context needed) rather than SAN. + Trace("SILENT_MISS_TRACE tier=%u bucket=%u " + "uNextDepth=%lu uShadowDepth=%lu " + "alpha=%d beta=%d " + "realScore=%d shadowScore=%d " + "move=%s postMoveFen=\"%s\" " + "shadowRefutation=\"%s\"\n", + uThisMoveJointExtraTier, + uPostReduceDepthBucket, + uNextDepth, uShadowDepth, + iAlpha, iBeta, + iScore, iShadowScore, + MoveToIcs(mv), + PositionToFen(pos), + szShadowPV); +#endif + } + } +#endif +#if defined(PERF_COUNTERS) && defined(PRUNE_VERIFY) + // The audited move has now had its ordinary search. If + // it failed high, the deep-prune gate would have thrown + // away a move that actually raised beta -- a silent + // miss, attributed to the band/depth the decision was + // made in. The margin is accumulated so that + // boundary-noise clears (a score that only just beats a + // tight inherited PVS window, JOINT_EXTRA_VERIFY's + // documented false-positive class) can be separated + // from real misses afterwards rather than hand-traced. + if (TRUE == fVerifyFlagged) + { + if (iScore >= iBeta) + { + INC(ctx->sCounters.tree.u64PruneVerifyFailHigh + [uVerifyBand][uVerifyDepthB]); + if (uVerifyBand <= 4) + { + INC(ctx->sCounters.tree.u64PruneVerifyDynMiss + [uVerifyAttB][uVerifyRateB]); + } + ctx->sCounters.tree.u64PruneVerifyMarginSum + [uVerifyBand][uVerifyDepthB] += + (UINT64)(iScore - iBeta); +#ifdef SILENT_MISS_TRACE + // pos is the POST-move position here (UnmakeMove + // has not run yet) -- same convention as the + // JOINT_EXTRA_VERIFY trace above. + // 2026-10-03: log the DYNAMIC signals alongside + // the static prediction, so a real miss can be + // interrogated for "what would have saved us, and + // at what threshold". Motivated by the band-0 + // miss at + // 6k1/p4p1p/3p2q1/2p1rP2/2P3p1/P7/1P1Qn1PK/3R1R2, + // Qg6 -- a move whose queen only LOOKS hung + // (White is losing too badly to take it; best + // line grabs the e2 knight and White is -14 at + // depth 19), i.e. a genuine structural + // mispredict of the dumbness axis, which no + // amount of sampling conservatism in the static + // table can catch. + // + // fhpct/fhatt: this exact move identity's own + // observed rate and sample count + // (GetMoveFailHighPctThousandths) -- answers + // "what GetMoveFailHigh threshold would have + // vetoed this". + // cm: countermove-table level -- 0 none, 1 slot + // 0 match, 2 slot 1 match, against the move + // played two plies back (the index + // generate.c's _ScoreAllMoves uses). + // hist/cont: accumulated history and + // continuation-history evidence for this + // [piece][to]. + // killer: 1 if this ply's killer, 2 if ply-3's. + { + ULONG uDynAtt = 0; + ULONG uDynPct = GetMoveFailHighPctThousandths(mv, &uDynAtt); + ULONG uCmLevel = 0; + ULONG uHist = g_HistoryCounters[mv.pMoved][mv.cTo]; + ULONG uKiller = 0; + + if (ctx->uPly >= 2) + { + MOVE mvPrev = ctx->sPlyInfo[ctx->uPly - 2].mv; + if (0 != mvPrev.uMove) + { + ULONG uCi = MOVE_TO_INDEX(mvPrev); + if (IS_SAME_MOVE(mv, ctx->mvCounter[uCi][0])) uCmLevel = 1; + else if (IS_SAME_MOVE(mv, ctx->mvCounter[uCi][1])) uCmLevel = 2; + } + } + if (IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][0]) || + IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][1])) + { + uKiller = 1; + } + else if ((ctx->uPly >= 3) && + (IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][0]) || + IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][1]))) + { + uKiller = 2; + } + Trace("PRUNEMISS pred=%u band=%u depthb=%u " + "alpha=%d beta=%d score=%d margin=%d " + "fhpct=%u fhatt=%u cm=%u hist=%u killer=%u " + "mv=%s postfen=%s\n", + uVerifyPred, uVerifyBand, uVerifyDepthB, + iAlpha, iBeta, iScore, (iScore - iBeta), + uDynPct, uDynAtt, uCmLevel, uHist, uKiller, + MoveToIcs(mv), PositionToFen(pos)); + } +#endif + } + } +#endif UnmakeMove(ctx, mv); pf->iCumulativeExtend -= iExtend; ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); @@ -1209,6 +1875,24 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, if (TRUE == fIsLeftoverMove) { INC(ctx->sCounters.tree.u64LeftoverFH); + // Gated on fPruneReduceEligible now, + // matching the tries side -- must + // match exactly, or this would reuse a + // stale bucket left over from a + // different (eligible) move for one + // that never got a bucket computed + // this iteration. + if (TRUE == fPruneReduceEligible) + { + INC(ctx->sCounters.tree.u64EligibleLeftoverFH); + INC(ctx->sCounters.tree.u64HangEstimateFH[uThisMoveHangBucket]); + INC(ctx->sCounters.tree.u64GapEstimateFH[uThisMoveGapBucket]); + INC(ctx->sCounters.tree.u64MoveNumEstimateFH[uThisMoveNumBucket]); + INC(ctx->sCounters.tree.u64DepthEstimateFH[uThisMoveDepthBucket]); + INC(ctx->sCounters.tree.u64JointFH + [uThisMoveDepthBucket][uThisMoveHangBucket] + [uThisMoveGapBucket][uThisMoveNumBucket]); + } } if (TRUE == fThisMoveIsCountermoveMatch) { @@ -1374,9 +2058,29 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); #ifdef PERF_COUNTERS - if ((!WE_SHOULD_STOP_SEARCHING) && IS_VALID_SCORE(iBestScore)) + // fNodeTypedThisVisit: a node short-circuited by CommonSearchInit + // (hash cutoff, repetition draw, ply/depth limit, EGTB hit) returns + // here via `goto end` WITHOUT pi->eNodeType having been assigned for + // this visit, so scoring it would attribute the outcome to whatever + // type the previous node at this ply left behind. That is what made + // this line report "PV failed high/low = 106.2% of PV nodes" -- + // more surprises than nodes of that type. + if ((!WE_SHOULD_STOP_SEARCHING) && IS_VALID_SCORE(iBestScore) && + (TRUE == fNodeTypedThisVisit)) { - FLAG fFailedLow = (iBestScore <= iAlpha); + // 2026-10-03: compare against iInitialAlpha, NOT iAlpha. + // search.c:2048 raises iAlpha IN PLACE as moves improve the + // score, so by the time we reach end: a node that SUCCESSFULLY + // raised alpha has iAlpha == iBestScore -- and the old + // (iBestScore <= iAlpha) test then read TRUE, scoring the + // ordinary success case as a "fail low". That is why the PV row + // reported 99.1% surprised: it was measuring "alpha was raised" + // rather than "the node-type prediction was wrong". + // iInitialAlpha is the node's alpha on entry (stashed at + // search.c:626 and already used for exactly this distinction at + // search.c:2105), which is what a fail-low must be judged + // against. + FLAG fFailedLow = (iBestScore <= iInitialAlpha); FLAG fFailedHigh = (iBestScore >= iBeta); switch (pi->eNodeType) { @@ -2080,7 +2784,27 @@ QSearchFromCheckNoStandPat(IN SEARCHER_THREAD_CONTEXT *ctx, uQsearchCheckExtension = 2; INC(ctx->sCounters.extension.uQExtend); } - ctx->sPlyInfo[ctx->uPly].iExtensionAmount = uQsearchCheckExtension; + // 2026-10-03: was `= uQsearchCheckExtension` (0 or 2), a + // UNIT MISMATCH. uQsearchCheckExtension counts qsearch + // CHECK PLIES (it is added to pf->uQsearchCheckDepth), but + // iExtensionAmount is ONE_PLY-scaled everywhere else in the + // codebase -- root.c writes HALF_PLY (32), split.c writes + // iLMR (a negative multiple of 64), search.c writes + // iExtend. Writing 2 here meant 2/64 of a ply in this + // field's own units. + // + // Benign as it stood, because both readers only test sign + // (searchsup.c's Tord Romstad null-move bailout tests + // `< 0`; search.c's EFP gate tests `<= 0`) and 2 behaves + // like any positive extension. But this field is already a + // documented stale-state hazard (see the "Record the + // extension/reduction actually applied to THIS move" + // comment in the main move loop), so a latent 32x error + // sitting in it is not worth keeping. Scaled to the field's + // real units; the sign, and therefore every current + // reader's behavior, is unchanged. + ctx->sPlyInfo[ctx->uPly].iExtensionAmount = + (INT)(uQsearchCheckExtension * ONE_PLY); } } @@ -2128,6 +2852,24 @@ QSearchFromCheckNoStandPat(IN SEARCHER_THREAD_CONTEXT *ctx, iEval = Eval(ctx, iAlpha, iBeta, &rgiPositional); ASSERT(ctx->sPlyInfo[ctx->uPly].uLastPositionalSource < EVAL_POSITIONAL_SOURCE_COUNT); + // 2026-10-03: publish it. This function used to keep the + // score purely local, so pi->iEval retained whatever a + // PREVIOUS visit to this ply slot left behind for every + // in-check qsearch node. The one reader + // (iImprovement, from sPlyInfo[uPly-2].iEval in Search) + // should never see a qsearch ply given that Search sits + // strictly above qsearch -- but that invariant is held + // by layering alone, and iImprovement feeds null-move + // and EFP decisions, so a stale value here is not worth + // leaving around once we have paid for the Eval anyway. + // + // NOTE this is still only set when Eval actually RAN. + // The common in-check path never calls Eval at all (no + // stand-pat is offered, so there is nothing to compute + // it for), and those nodes still leave pi->iEval stale. + // Making that safe properly means invalidating it on + // entry, which is a separate change. + ctx->sPlyInfo[ctx->uPly].iEval = iEval; fEvalComputed = TRUE; } @@ -2259,6 +3001,15 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx, #endif FLAG fIncludeChecks; FLAG fOrigStandPat = ctx->sSearchFlags.fCouldStandPat[pos->uToMove]; +#ifdef PERF_COUNTERS + // Entry alpha, for the qsearch node-type accounting at end:. QSearch + // raises iAlpha IN PLACE (the stand-pat branch and the move loop + // both do), so a fail-low test against the live iAlpha would score + // every successful alpha-raise as a fail-low -- the same defect that + // made Search()'s PV row read 99.1%. + SCORE iQEntryAlpha = iAlpha; + FLAG fQNodeTyped = FALSE; +#endif static ULONG _WhatToGen[] = { GENERATE_CAPTURES_PROMS, @@ -2283,6 +3034,13 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx, { goto end; } +#ifdef PERF_COUNTERS + // Reaching here means CommonSearchInit returned FALSE, i.e. it + // really assigned pi->eNodeType for THIS visit. + fQNodeTyped = TRUE; + ASSERT((ULONG)pi->eNodeType < 3); + INC(ctx->sCounters.tree.u64QNodeTypeCount[(ULONG)pi->eNodeType]); +#endif DTEnterNode(ctx, 0, TRUE, iAlpha, iBeta); // Probe interior node recognizers. Qsearch runs at the deepest, @@ -2354,21 +3112,54 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx, // its other uses: deciding whether a *whole line* looks forcing // enough to justify extra qsearch depth/breadth), not gating // per-node stand-pat correctness. - if (0 != ValueOfMaterialInTroubleDespiteMove(ctx, pos->uToMove)) { - iBestScore = iAlpha; - } - else - { - ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE; - if (iBestScore > iAlpha) + SCORE iInTrouble = ValueOfMaterialInTroubleDespiteMove(ctx, pos->uToMove); + + if (0 != iInTrouble) { - iAlpha = iBestScore; - ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove == 0); - ASSERT(pi->mvBest.uMove == 0); - if (iBestScore >= iBeta) + // REVERTED 2026-10-03, same day it was tried. The change was + // `iBestScore = MAX(iAlpha, iEval - iInTrouble)`, motivated by + // a real observation: the beta test below lives only in the + // else-branch, so a node with iEval far ABOVE beta and hanging + // material returns a fail-low instead of cutting off. + // + // But the fix was unsound AND expensive, for the same reason. + // Work the signs: a parent searching this node passed window + // (-iBeta_p, -iAlpha_p), so iAlpha here == -iBeta_p. The parent + // fails high iff -V >= iBeta_p, i.e. iff V <= iAlpha. So + // returning exactly iAlpha is not a crude placeholder -- it is + // precisely the value that HANDS THE PARENT ITS CUTOFF. That is + // the standard fail-low idiom: refuse the stand-pat, start at + // alpha, and if nothing beats it report a fail-low. + // + // Returning MAX(iAlpha, iEval - iInTrouble) instead reports a + // better-than-alpha value, denying the parent that cutoff -- + // measured as ~0.45 ply of lost search depth in self-play + // (candidate 13.10 vs 13.55 for the same tree without this + // change, against a comparable head). And it asserts the node + // is worth at least iEval - iInTrouble WITHOUT SEARCHING + // ANYTHING, i.e. a stand-pat credit at a discount -- exactly + // what this branch exists to refuse. If every move from here is + // terrible, the true value can be far below that. + // + // The original observation is still valid and still unfixed: a + // sound fix needs a lower bound the node has actually EARNED, + // which iEval - iInTrouble is not. A beta test on a + // search-established bound would be the way, not a static one. + iBestScore = iAlpha; + } + else + { + ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE; + if (iBestScore > iAlpha) { - goto end; + iAlpha = iBestScore; + ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove == 0); + ASSERT(pi->mvBest.uMove == 0); + if (iBestScore >= iBeta) + { + goto end; + } } } } @@ -2418,11 +3209,46 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx, // and the other side has not yet been able to stand pat yet, and // we have material OR we have hanging pieces, generate checks // here too. Checks are a "good way" to escape from "trouble". + // 2026-10-03: the opponent-stand-pat half of the first clause is + // waived at a PV node. + // + // The suppression exists because of a sound argument: if the + // opponent was able to stand pat at an ancestor, then once their + // stand-pat score has raised alpha there, no line below worth less + // than that score can change what they return -- so resolving + // whether this subtree is mate-in-10 or merely loses a queen is + // wasted work. That reasoning covers every case in a NULL-WINDOW + // search: even where their stand-pat did NOT raise alpha, the node + // is heading for a fail-low, and a fail-low here is precisely the + // parent's beta cutoff -- any score at or below alpha answers the + // question identically, so extra precision buys nothing. + // + // It does not cover a WIDE-WINDOW node. There the exact score + // propagates toward the root, so "mate-in-10" and "drops a queen" + // are a different PV and a different reported score -- and finding + // forced mates from the early plies of qsearch is the whole reason + // this check-generation machinery exists. Neither this gate nor + // QSearchFromCheckNoStandPat's escape-futility gate consulted node + // type, so that case was suppressed along with the rest. + // + // Hence: at NODE_PV, drop the fCouldStandPat[opponent] requirement + // but KEEP the material requirement (an independent sanity check on + // whether checks are worth generating at all, not a suppression). + // pi->eNodeType is read, never written -- CommonSearchInit remains + // the only assigner, and it has already run for this visit (an + // early exit there would have jumped to end: long before here), so + // the value cannot be stale. Using eNodeType rather than recomputing + // (iBeta != iAlpha + 1) matters: iAlpha may have been RAISED by the + // stand-pat above, which would make a recomputed test read narrow + // for a node that is still genuinely PV. fIncludeChecks = ( (pf->uQsearchDepth < pf->uQsearchCheckDepth) && ( ( - (pf->fCouldStandPat[FLIP(pos->uToMove)] == FALSE) && + ( + (pf->fCouldStandPat[FLIP(pos->uToMove)] == FALSE) || + (NODE_PV == pi->eNodeType) + ) && (pos->uNonPawnMaterial[pos->uToMove] > (VALUE_KING + VALUE_BISHOP)) ) || @@ -2566,34 +3392,60 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx, ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING); DTLeaveNode(ctx, TRUE, iBestScore, pi->mvBest); #ifdef PERF_COUNTERS - // See Search()'s own "end:" label for the full rationale. - if ((!WE_SHOULD_STOP_SEARCHING) && IS_VALID_SCORE(iBestScore)) + // Qsearch half of the node-type accounting -- see chess.h's + // u64QNodeTypeCount comment for why this is counted separately + // rather than folded into the full-width counters (it used to be + // folded in, which made those rates mostly a measure of stand-pat + // frequency) and why dropping it entirely broke the CUT-FL/ALL-FH + // identity. + if ((!WE_SHOULD_STOP_SEARCHING) && IS_VALID_SCORE(iBestScore) && + (TRUE == fQNodeTyped)) { - FLAG fFailedLow = (iBestScore <= iAlpha); - FLAG fFailedHigh = (iBestScore >= iBeta); + FLAG fQLow = (iBestScore <= iQEntryAlpha); + FLAG fQHigh = (iBestScore >= iBeta); + switch (pi->eNodeType) { case NODE_PV: - if (fFailedLow || fFailedHigh) + if (fQLow || fQHigh) { - INC(ctx->sCounters.tree.u64PVNodeSurprised); + INC(ctx->sCounters.tree.u64QNodeSurprise[NODE_PV]); } break; case NODE_ALL: - if (fFailedHigh) + if (fQHigh) { - INC(ctx->sCounters.tree.u64AllNodeFailedHigh); + INC(ctx->sCounters.tree.u64QNodeSurprise[NODE_ALL]); } break; case NODE_CUT: - if (fFailedLow) + if (fQLow) { - INC(ctx->sCounters.tree.u64CutNodeFailedLow); + INC(ctx->sCounters.tree.u64QNodeSurprise[NODE_CUT]); } break; } } #endif +// 2026-10-03: QSearch's copy of the node-type surprise counters was +// MOVED to its own slots (above), not deleted. CommonSearchInit types qsearch nodes too (it is the one +// funnel both Search() and QSearch() pass through), and qsearch is ~84% +// of the tree -- so these counters were dominated by it. Specifically: a +// qsearch node whose stand-pat score already beats beta returns +// iBestScore >= iBeta immediately, and if that node happened to be typed +// ALL it was scored as "ALL failed high". A stand-pat cutoff is the most +// ordinary event in qsearch, not a node-type misprediction, which is why +// the line reported ~47% of all nodes as ALL-failed-high and looked +// absurd. The question the line's name asks is about FULL-WIDTH +// node-type prediction, so qsearch is now excluded from both the +// numerator (here) and the denominator (u64NodeTypeCount, incremented in +// Search() only). +// +// The NODE_TYPE enum itself is deliberately unchanged -- adding a +// NODE_QNODE value was considered and rejected, because eNodeType feeds +// eParentType chaining in CommonSearchInit and every behavioral consumer +// tests against NODE_PV; excluding qsearch from the instrumentation gets +// the same signal with zero risk to any of that. // Note: iBestScore can be +INFINITY_SCORE or -INFINITY_SCORE here even in the // absence of a legitimate mate detected if we disallowed stand |
