diff options
| author | Scott Gasch <[email protected]> | 2026-10-05 09:01:25 -0700 |
|---|---|---|
| committer | Scott Gasch <[email protected]> | 2026-10-05 09:01:25 -0700 |
| commit | 64b5d3307a7a95975f7f8c0248f3f1febedd8617 (patch) | |
| tree | 993fffd62a68bec962261caf033a8f05c6370ea9 /src/searchsup.c | |
| parent | bbdf1bda8f410df6aa9be0a38e71b7db04982198 (diff) | |
Continue dynamic move-ordering/LMR session: SPRT-validated at 1770+ games
Gate match vs head (st4.0) shows LLR=+2.89 approaching the H1=+2.94
bound, candidate score 0.5324 (LOWER95=0.5092, ELO=+22.6+/-16.2),
candidate depth/ebf both improved (13.98 vs 13.61 avg depth, ebf 3.324
vs 3.464) with comparable nps -- consistent with real search-efficiency
gains rather than noise. match_play.py gets additional instrumentation
to report these stats; search.c/searchsup.c/generate.c/chess.h/eval.c
carry the underlying move-ordering/LMR changes from this session's
line of work.
Co-Authored-By: Claude Sonnet 5 <[email protected]>
Diffstat (limited to 'src/searchsup.c')
| -rw-r--r-- | src/searchsup.c | 717 |
1 files changed, 317 insertions, 400 deletions
diff --git a/src/searchsup.c b/src/searchsup.c index 58ae61b..2bbf1ef 100644 --- a/src/searchsup.c +++ b/src/searchsup.c @@ -259,14 +259,40 @@ Routine description: Return value: - SCORE : estimated cp loss (>= 0), or 0 if nothing looks hung. + SCORE : estimated cp loss (>= 0), or 0 if nothing looks hung -- EXCEPT + for a capture/promotion scored under MOVE_SCORING_IID_RESCORED + (ctx->sPlyInfo[ctx->uPly - 1].eMoveScoringScheme), where the + result can be negative. fPruneReduceEligible only ever admits a + capture/promotion here when generate.c's own SEE sign flagged it + as a LOSING one, so ordinarily ComputeMoveScore's decoded value + is guaranteed negative and this just flips its sign into a + positive loss. But IID rescoring (searchsup.c's + RescoreMovesViaSearch, unconditionally live -- see chess.h's + unconditional `#define DO_IID`) overwrites iValue with a real, + searched eval-axis score for every move at that ply, which can + legitimately disagree with the cheap SEE-sign classification + that got mv into this eligible population in the first place -- + a capture that LOOKS like a material-losing trade can still be + the actual best move in the position (a real tactic SEE can't + see), in which case the honest searched score is positive, not + negative, and this function will return a NEGATIVE number here. + 2026-10-04: deliberately trust the searched score over the SEE + sign in that case rather than clamping it away -- IID's shallow + search genuinely knows more than a static material exchange + does, and a caller folding this value directly into a margin + calculation (EFP, search.c) WANTS "this move turned out to + actually be good" to look like the opposite of "hung", not like + "hung = 0" -- see search.c's EFP comment. Callers that need a + true cp-loss-or-zero reading instead (the "dumb" axis feeding + the joint FH table) must go through HangCpBucket, which clamps + exactly this case to bucket 0 rather than asserting it away. **/ { POSITION *pos = &ctx->sPosition; // already reflects the position - // AFTER mv (MakeMove already ran) + // AFTER mv (MakeMove already ran) ULONG uOpponent = pos->uToMove; // side to move now == opponent of - // whoever just moved + // whoever just moved BITBOARD bbTo; SCORE iMoveScore; @@ -283,8 +309,12 @@ Return value: ASSERT(pos->rgSquare[mv.cTo].pPiece == mv.pMoved); } #endif + // No ASSERT(iMoveScore < 0) here -- see this function's own + // return-value comment above. It was true under every + // generate.c tier-encoded scoring scheme (the only ones in + // play when this ASSERT was written), but IID rescoring can + // legitimately make it false. iMoveScore = ComputeMoveScore(ctx, mv, uMoveNum); - ASSERT(iMoveScore < 0); return -iMoveScore; } #ifdef DEBUG @@ -356,13 +386,22 @@ Return value: } // See chess.h's HANG_CP_BUCKETS comment for the bucket shape. +// +// 2026-10-04: was ASSERT(iHangCp >= 0), on the belief that +// EstimateHangingMaterialCp (its only real producer) could never +// return a negative value. That ASSERT is wrong, not just stale -- see +// EstimateHangingMaterialCp's own return-value comment: IID rescoring +// can legitimately make it negative (a capture SEE-sign flagged as +// losing, but which a real shallow search found is actually the best +// move in the position). A negative input just means "even more +// definitely not hung" than 0 already does, so it belongs in the same +// bucket 0 -- clamp rather than assert. ULONG HangCpBucket(SCORE iHangCp) { ULONG u; - ASSERT(iHangCp >= 0); - if (0 == iHangCp) + if (iHangCp <= 0) { return 0; } @@ -454,7 +493,7 @@ _ShipLateBucket(ULONG uRawLateBucket) // 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 +USHORT _JointTablePredictedFHThousandths(IN ULONG uRawDepthBucket, IN ULONG uRawDumbBucket, IN ULONG uRawGapBucket, @@ -629,73 +668,173 @@ _FlatTableExtraPlies(IN ULONG uRemainingDepth, IN ULONG uMoveNum) // 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). +FLAG +CanWeReduceOrPruneMove(IN SEARCHER_THREAD_CONTEXT *ctx, + IN MOVE mv, + IN ULONG x, + IN ULONG uLegalMoves, + IN SCORE iExtend, + IN SCORE iAlpha, + IN FLAG fThreat, + IN FLAG fIsLeftoverMove) +/** + +Routine description: + + 2026-10-04: hoisted out of Search()'s move loop (search.c), where + this had grown into an inline block setting fPruneReduceEligible + plus two more exemption checks (killer-adjacency, countermove + match) immediately below it -- EFP, LMP and LMR all gate on the + combined result. Pulled into one function so the "is this move + even a candidate for pruning/reduction" question has a single, + named answer instead of three co-located but separately-maintained + checks. + + Base eligibility (see search.c's original comment, preserved in + spirit): a move is a candidate only if (1) it isn't the first move + tried at this node (uLegalMoves > 1 -- there must be something to + compare it against), (2) this isn't a PV node (a PV node must + resolve every move exactly, not approximately), (3) it's already + in the leftover/late tier (fIsLeftoverMove), (4) it wasn't + independently extended (iExtend <= 0), (5) it isn't escaping check + or (6) giving check, (7) there's no node-wide threat in play + (fThreat), (8) alpha isn't already mate-magnitude, and (9) it's + either a non-capture/non-promotion or a losing one (SEE-negative; + a non-losing capture/promotion is excluded outright, matching the + population the joint fail-high table was actually trained on -- + see lmr_testing/SPEC.md's "gate-1" section). + + On top of that, two move-identity-specific exemptions withdraw + eligibility even if the base checks above all pass: a killer at + this ply or two plies back (killers already proved themselves + elsewhere in the tree and the table can change between visits, so + this is re-checked every call, not cached), and a bare countermove + match against the move played two plies ago (ctx->sPlyInfo[uPly-2] + -- mv has already been made by the time this runs, so the "move + immediately before mv" is two plies back from here, not one). + + FOUND WHILE HOISTING, FIXED HERE: the countermove check in + search.c's inline version was `return FALSE;` -- inside Search(), + which returns SCORE, not FLAG. That silently returned a score of + 0 for the entire node (abandoning the rest of the move loop, and + doing so without the matching UnmakeMove) the instant the current + move matched a countermove-table entry, rather than merely + excluding that one move from pruning/reduction eligibility the way + the killer check two lines above it does. Expressed here as an + ordinary `return FALSE;` from this FLAG-returning helper, which is + the behavior that was actually intended. + +Parameters: + + ctx : current searcher thread context. Reads uPly, + sPlyInfo (for eNodeType and the countermove key), + mvKiller, mvCounter, and the already-made move's + cached flags out of sMoveStack. + mv : the move just made (MakeMove has already returned + TRUE for it by the time this is called). + x : this move's 1-based index into ctx->sMoveStack, + i.e. the move loop's own loop variable -- used to + read sMoveStack.mvf[x - 1].bvFlags for the cached + MVF_SEE_NONNEGATIVE bit. x == 0 never reaches here + in practice (TRY_HASH_MOVE's single iteration is + always the first move, so uLegalMoves > 1 already + rules it out). + uLegalMoves : legal moves found at this node so far, including mv. + iExtend : this move's own per-move extension amount. + iAlpha : this node's current alpha. + fThreat : whether a node-wide threat extension is in play. + fIsLeftoverMove : whether mv already sorted into the leftover/late + move-ordering tier. + +Return value: + + FLAG : TRUE iff mv is eligible to be considered for pruning or + reduction (EFP/LMP/LMR still each apply their own further checks + on top of this). + +**/ +{ + PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; + FLAG fPruneReduceEligible = + (NODE_PV != pi->eNodeType) && + (uLegalMoves > 1) && + (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))); + if (FALSE == fPruneReduceEligible) + { + return FALSE; + } + + ULONG uPly = ctx->uPly; + if (uPly >= 2) + { + // We have to check this every time too because the killers can + // change any time we search recursively. + if (IS_SAME_MOVE(mv, ctx->mvKiller[uPly - 1][0]) || + IS_SAME_MOVE(mv, ctx->mvKiller[uPly - 1][1])) + { + return FALSE; + } + + MOVE mvPrev = ctx->sPlyInfo[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; + } + } + + if (uPly >= 3) + { + if (IS_SAME_MOVE(mv, ctx->mvKiller[uPly - 3][0]) || + IS_SAME_MOVE(mv, ctx->mvKiller[uPly - 3][1])) + { + return FALSE; + } + } + } + return TRUE; +} INT -GetLMRReduction(IN SCORE iEval, - IN SCORE iAlpha, - IN SCORE iBeta, - IN SCORE iImprovement, - IN SEARCHER_THREAD_CONTEXT *ctx, +GetLMRReduction(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uRemainingDepth, IN ULONG uLegalMoves, IN MOVE mv, - IN ULONG uMoveNum, IN INT iExtend, - IN BITBOARD bbMinorAttacksSnapshot[2], - IN BITBOARD bbRookAttacksSnapshot[2], + IN ULONG uAttempts, + IN ULONG uFHPctThousandths, + IN ULONG uPredictedFH, OUT ULONG *puExtraTier) /** Routine description: - 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. + Decide how much (if any) to reduce the depth of the search below + this move. 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). + ctx : current searcher thread context. + uRemainingDepth : remaining depth below this move. + uLegalMoves : legal moves tried at this node so far. + mv : the move just made. + iExtend : this move's own per-move extension amount so far + (ASSERTed to be 0 when a reduction is applied). + uAttempts : this move identity's dynamic sample count. + uFHPctThousandths : this move identity's dynamic fail-high rate. + uPredictedFH : the joint table's static prediction for this + move's (depth, hang, gap, late) situation, or + JOINT_TABLE_SENTINEL if no data. 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 @@ -709,15 +848,11 @@ Return value: **/ { - ULONG uAttempts; - ULONG uFHPctThousandths; - FLAG fCounterMoveMatch; - ULONG uExtraPlies = 0; - ASSERT(ctx->uPly > 0); ASSERT(mv.uMove); - ASSERT((uMoveNum > 0) || (uLegalMoves == 0)); + ASSERT(!InCheck(&ctx->sPosition, ctx->sPosition.uToMove)); + ULONG uExtraPlies = 0; if (NULL != puExtraTier) { *puExtraTier = 0; @@ -729,285 +864,70 @@ Return value: 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) + INT iLocalExtend; + FLAG fBaseEligible; + FLAG fDynamicDanger = (uAttempts > 0) && + (uFHPctThousandths > LMR_FH_BASELINE_PCT_THOUSANDTHS); + + if (JOINT_TABLE_SENTINEL == uPredictedFH) { - 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]); - } + // No static data for this exact bucket, fall back on dynamic. + fBaseEligible = (FALSE == fDynamicDanger); } - - // 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]))) && - (FALSE == fCounterMoveMatch)) + else { - 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)); - -#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); + // Static table has an opinion: admission is now a wide- + // open, separate threshold from the extra-tier magnitude + // grading below (LMR_STATIC_ADMIT_PCT_THOUSANDTHS, not + // JOINT_EXTRA_TIER1_PCT_THOUSANDTHS) -- only veto the base + // reduction when the static table itself thinks this + // bucket is actively bad. A dynamic-danger reading does + // NOT veto this either -- it only caps uExtraPlies to 0 + // below. + fBaseEligible = (uPredictedFH < LMR_STATIC_ADMIT_PCT_THOUSANDTHS); + } + if (FALSE == fBaseEligible) + { + return(0); + } - 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 + // We are going to reduce it; let's see if we want to pile on extra + // reduction because we're pretty sure it's "safe". + uExtraPlies = (fBaseEligible && (FALSE == fDynamicDanger)) ? + _FlatTableExtraPlies(uRemainingDepth, uLegalMoves) : 0; - if (FALSE == fBaseEligible) + // Clamp. Combine with the baseline -ONE_PLY and floor the total + // so it never leaves less than JOINT_EXTRA_MIN_REMAINING_DEPTH + // remaining -- never rely on the move loop's own unsigned- + // 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) { - return(0); + iMaxExtra = 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) + if ((INT)uExtraPlies > iMaxExtra) { - 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); + uExtraPlies = (ULONG)iMaxExtra; } - if (NULL != puExtraTier) + if (uExtraPlies > JOINT_EXTRA_MAX_PLIES) { - *puExtraTier = uExtraPlies; + uExtraPlies = JOINT_EXTRA_MAX_PLIES; } - return(iLocalExtend); + iLocalExtend -= (INT)(uExtraPlies * ONE_PLY); } - return(0); + if (NULL != puExtraTier) + { + *puExtraTier = uExtraPlies; + } + return(iLocalExtend); } -// 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 @@ -1015,7 +935,7 @@ Return value: #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 +#define LMP_DYNAMIC_MIN_SAMPLES (1) // 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 @@ -1025,33 +945,70 @@ Return value: // 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) +#define LMP_DYNAMIC_MAX_PCT_THOUSANDTHS (1) + FLAG -ShouldLatePrune(IN SCORE iEval, - IN SCORE iAlpha, - IN SEARCHER_THREAD_CONTEXT *ctx, +ShouldLatePrune(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) + IN ULONG uFHAttempts, + IN ULONG uFHPctThousandths, + IN ULONG uPredictedFH) +/** + +Routine description: + + 2026-10-04: second gate, applied by the caller (search.c) only + after CanWeReduceOrPruneStatic has already passed -- so the + killer-adjacency and countermove-match exemptions that used to be + duplicated here are gone; the caller never reaches this function + for a move either of those would have exempted. Takes the FH-table + lookups (uFHAttempts, uFHPctThousandths, uPredictedFH) as inputs + rather than recomputing them -- search.c's move loop already looks + them up once per move for LMP/LMR/EFP to share. + + Four remaining checks, any one of which refuses to prune: + 1. Depth ceiling (LMP_MAX_REMAINING_DEPTH) -- see the KNOWN ISSUE + comment above this function: backwards relative to our own + joint-table evidence, kept as a placeholder pending a per-cell + sample-count re-bake, not a validated bound. + 2. Move-number floor (LMP_BASE_MOVENUM + per-ply slack) -- don't + gamble this early in the move list regardless of what either + FH signal says. + 3. Dynamic signal: any real, nonzero observed fail-high history + on this exact move identity. + 4. Static signal: the joint table's own prediction for this + move's situation, outside the strictest (safest) tier, or no + data at all (sentinel) -- unlike GetLMRReduction's more + permissive treatment of a sentinel for mere reduction, overt + pruning requires real, favorable data. + +Parameters: + + ctx : current searcher thread context (uPly only, + for the sanity ASSERT). + uRemainingDepth : remaining depth below this move. + uLegalMoves : legal moves tried at this node so far. + uFHAttempts : this move identity's dynamic sample count. + uFHPctThousandths : this move identity's dynamic fail-high rate. + uPredictedFH : the joint table's static prediction for this + move's (depth, hang, gap, late) situation, or + JOINT_TABLE_SENTINEL if no data. + +Return value: + + FLAG : TRUE iff mv should be pruned outright (skipped, not merely + reduced) -- see search.c's call site comment for why that's + currently audit-only, not wired to actually skip the move. + +**/ { - ULONG uAttempts, uFHPctThousandths, uMoveNumFloor; - ULONG uRawDepthB, uRawDumbB, uRawGapB, uRawLateB; - USHORT uPredictedFH; - SCORE iHangCp; + ULONG uMoveNumFloor; ASSERT(ctx->uPly > 0); - ASSERT(mv.uMove); - - if (uRemainingDepth > LMP_MAX_REMAINING_DEPTH) - { - return FALSE; - } + // Only consider very late moves. uMoveNumFloor = LMP_BASE_MOVENUM + (LMP_PER_PLY_MOVENUM * (uRemainingDepth / ONE_PLY)); if (uLegalMoves <= uMoveNumFloor) @@ -1059,36 +1016,10 @@ ShouldLatePrune(IN SCORE iEval, 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) && + if ((uFHAttempts >= LMP_DYNAMIC_MIN_SAMPLES) && (uFHPctThousandths > LMP_DYNAMIC_MAX_PCT_THOUSANDTHS)) { return FALSE; @@ -1098,28 +1029,11 @@ ShouldLatePrune(IN SCORE iEval, // (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; } @@ -1176,6 +1090,7 @@ Return value: iRawValue -= MOVE_SCORE_ORDERING_BIAS(mv); return(iRawValue); } + // All quiet moves (including killer/killer-mate quiet // moves, which can reach SORT_THESE_FIRST or the killer- // tier bits via generate.c's ordering bonuses with no @@ -1274,6 +1189,7 @@ ComputeMoveScore(IN SEARCHER_THREAD_CONTEXT *ctx, ASSERT(uMoveNum < MAX_MOVE_STACK); ASSERT(IS_SAME_MOVE(mv, ctx->sMoveStack.mvf[uMoveNum].mv)); ASSERT(ctx->uPly > 0); + // Every current caller (search.c's EFP check, and // ComputeMoveExtension's two ComputeMoveScore() call sites) only // reaches here after MakeMove(ctx, mv) has already succeeded, so @@ -1499,7 +1415,8 @@ Return value: } } - // Responses to check extensions: +#if 0 + // Responses to check extensions --- moved to search.c @ positional bonus if (IS_CHECKING_MOVE(mvLast)) { ASSERT(IS_ESCAPING_CHECK(mv)); @@ -1511,14 +1428,13 @@ Return value: { FLAG fBigBonus = (iMoveScore + VALUE_KNIGHT > iAlpha); *piExtend += (QUARTER_PLY + HALF_PLY * fBigBonus); - INC(ctx->sCounters.extension.uOneLegalMove); INC(ctx->sCounters.extension.uOneLegalMoveByQuarterPly[ fBigBonus ? (THREE_QUARTERS_PLY / QUARTER_PLY) : (QUARTER_PLY / QUARTER_PLY)]); } - // One "good" way to response to check? Kinda dodgy but "works". + // One "good" way to response to check --- dead code, kill it? if (!fIsLeftoverMove && mv.pCaptured && (iRoughEval + 300 < iAlpha) && @@ -1528,13 +1444,14 @@ Return value: INC(ctx->sCounters.extension.uSingularReplyToCheck); } } +#endif // These last ones only happen if we are close to the root score. ASSERT(_window[ctx->uPly] > 0); if ((iRoughEval >= (g_iRootScore[uColor] - _window[ctx->uPly] * 2)) && (iRoughEval <= (g_iRootScore[uColor] + _window[ctx->uPly] * 2))) { - // Endgame extension + // Entering the endgame extension if ((ctx->sPlyInfo[1].uTotalNonPawns > 2) && ((TotalNonPawnCount(pos, BLACK) + TotalNonPawnCount(pos, WHITE)) == 2)) |
