From bb07fbd8612dbf2cfb6f257e8cba47b95c83c867 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Fri, 28 Aug 2026 21:13:48 -0700 Subject: Replace EFP (what this file erroneously called EFP for years) with Heinz's actual two-tier schedule, a hardened per-move checklist, and a TT-soundness fix. Proto-LMR (live, unrelated) untouched. The old condition used a single flat VALUE_ROOK margin across uDepth <= TWO_PLY -- that's neither of the two numbers Heinz's book actually specifies for that range. Split into his real two tiers, each gated on the same common conditions (PV-node guard added; HEAD's version had none, unlike GetLMRReduction which has always required non-PV) but different depth bands and margins: - frontier ("selective futility"): VALUE_KNIGHT, one ply above the QSearch jump (bands are relative to THREE_QUARTERS_PLY, the actual cutoff, not ONE_PLY, since the check-extension rework lowered it). - pre-frontier ("extended futility pruning" proper): VALUE_ROOK, the next ply out. Heinz's third tier ("limited razoring", pre-pre-frontier, VALUE_QUEEN) is a per-node depth reduction, not a per-move prune -- a different technique, deliberately not implemented here (spiritual predecessor to LMR, revisit then). Also drops the old ValueOfMaterialInTroubleDespite- Move requirement (an en-prise/trapped-piece safety net) -- intent is to fire on ordinary quiet positions too, not just ones with an already- flagged piece in danger. Per-move checklist, replacing an ASSERT that captures/checks couldn't reach here (untrue in a non-DEBUG build, so no actual protection) with real exemptions: explicit !IS_CAPTURE_OR_PROMOTION / !IS_CHECKING_MOVE, a killer-adjacency exemption (ply-1/ply-3, borrowed from GetLMRReduction), a well-evidenced fail-high-history exemption (GetMoveFailHighPercentage, >=5 samples before trusting it), an en-prise-escape exemption, and suppression at any node where this node's own null-move probe raised fThreat. TT-soundness fix (Heinz's own book, quoted directly): a node whose result depends on alpha/beta via forward pruning can't be stored as an exact score or a sound upper bound -- a skipped move might have been the best one, so the true value could be higher than computed in either case. Tracks fAnyMoveEFPPruned; downgrades an alpha-raise to StoreLowerBound instead of StoreExactScore when set, and skips hash storage entirely on a fail-low with pruning (no sound bound available in either direction). Verified against head_reference (HEAD, commit 7e762b2) at sd10: ecm_ringers: 10/11 -> 9/11 (-1 solve), -8.96% nodes ecm_confident_quick: 87/90 -> 88/90 (+1 solve), -16.49% nodes ecm_hard_quick: 17/90 -> 15/90 (-2 solve), -15.94% nodes Net -2 solves across 269 positions for 9-16% fewer nodes per suite -- similar shape to Heinz's own reported trade-off in the book (8 lost solutions for -16.70% fewer nodes). Old flat-margin candidates built earlier today (kept in git stash, not this commit) only achieved 0.3-1% node reduction vs. a no-EFP baseline; dropping the stale material-in-trouble gate is what actually recovered real pruning power, not the checklist alone. --- src/search.c | 156 ++++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 139 insertions(+), 17 deletions(-) (limited to 'src/search.c') diff --git a/src/search.c b/src/search.c index fbef312..02f4e85 100755 --- a/src/search.c +++ b/src/search.c @@ -75,6 +75,12 @@ extern FLAG g_fCanSplit[MAX_PLY_PER_SEARCH]; #define PREPARE_TO_TRY_MOVES (2) #define TRY_GENERATED_MOVES (3) +// EFP's fail-high-history exemption: below EFP_FH_MIN_SAMPLES +// observations, GetMoveFailHighPercentage'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) + #ifdef DEBUG #define VERIFY_HASH_HIT \ ASSERT(IS_VALID_SCORE(iScore)); \ @@ -155,6 +161,8 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, ULONG uStage = TRY_HASH_MOVE; ULONG u; ULONG uFutilityMargin = 0; + FLAG fAnyMoveEFPPruned = FALSE; + FLAG fThisMoveEFPPruned = FALSE; SCORE iCheckSee; #ifdef DEBUG ASSERT(IS_VALID_SCORE(iAlpha)); @@ -439,22 +447,67 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, } } #endif - // This is very similar to Ernst Heinz's "extended - // futility pruning" except that it uses the added - // dynamic criteria of "ValueOfMaterialInTrouble" - // condition as a safety net. Note: before we actually - // prune away moves we will also make sure there is - // no per-move extension. + // Ernst Heinz's forward-pruning-by-material-margin idea, + // rewritten to match his book's actual two-tier + // schedule (this previously used a single flat + // VALUE_ROOK margin across the whole uDepth <= TWO_PLY + // range, which is neither of the two numbers Heinz + // actually gives for that range): "selective futility" + // at the frontier (VALUE_KNIGHT, his 200-400 + // pawn-equivalent range) and "extended futility + // pruning" proper one ply further back (VALUE_ROOK, his + // 500-600 range). Common conditions (PV-node guard, + // ply floor, no per-position extension here or two + // plies back) are the same for both tiers, so they're + // checked once; only the depth band and margin differ + // per tier. Deliberately drops the old + // ValueOfMaterialInTroubleDespiteMove requirement (an + // en-prise/trapped-piece safety net) -- this is meant + // to fire on ordinary quiet positions too, not just + // ones where a piece is already known to be in danger. + // + // Tier boundaries are relative to THREE_QUARTERS_PLY + // (the actual QSearch cutoff just below, not ONE_PLY -- + // lowered when the check-extension rework made a lone + // check buy exactly one extra full-width ply rather + // than a blanket extra 1/4 ply): "one ply above the + // QSearch jump" is (THREE_QUARTERS_PLY, ONE_PLY + + // THREE_QUARTERS_PLY], "two plies above" is the next + // such band. + // + // "Limited razoring" (Heinz's third tier, pre-pre- + // frontier, VALUE_QUEEN, ~900-1000) is a different + // technique -- a per-node depth reduction, not a + // per-move prune -- and is deliberately not implemented + // here; see lmr_testing/RESULTS.md. + // + // PV-node guard: HEAD's original condition had none + // (unlike GetLMRReduction, which has always required + // FALSE == fPvNode) -- pruning a fail-high inside a PV + // node can silently corrupt the actual principal + // variation, not just tighten a sibling's bound, so + // this closes a real gap rather than relying on it not + // mattering in practice. ASSERT(!uFutilityMargin); - if ((iRoughEval + VALUE_ROOK <= iAlpha) && - (uDepth <= TWO_PLY) && + if ((FALSE == pi->fPvNode) && (ctx->uPly >= 2) && (iOrigExtend == 0) && - (ctx->sPlyInfo[ctx->uPly - 2].iExtensionAmount <= 0) && - (ValueOfMaterialInTroubleDespiteMove(ctx, pos->uToMove))) + (ctx->sPlyInfo[ctx->uPly - 2].iExtensionAmount <= 0)) { - uFutilityMargin = (iAlpha - iRoughEval) / 2; - ASSERT(uFutilityMargin); + if ((uDepth > THREE_QUARTERS_PLY) && + (uDepth <= ONE_PLY + THREE_QUARTERS_PLY) && + (iRoughEval + VALUE_KNIGHT <= iAlpha)) + { + uFutilityMargin = (iAlpha - iRoughEval) / 2; + ASSERT(uFutilityMargin); + } + else if ((uDepth > ONE_PLY + THREE_QUARTERS_PLY) && + (uDepth <= TWO_PLY + THREE_QUARTERS_PLY) && + (iRoughEval + VALUE_ROOK <= iAlpha)) + { + uFutilityMargin = (iAlpha - iRoughEval) / 2; + ASSERT(uFutilityMargin); + } } uStage++; ASSERT(x == ctx->sMoveStack.uBegin[ctx->uPly]); @@ -651,16 +704,49 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, } } - // Maybe even "futility prune" this move away. + // 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. + fThisMoveEFPPruned = FALSE; if ((x != 0) && (uLegalMoves > 1) && (uFutilityMargin) && (ComputeMoveScore(ctx, mv, (x - 1)) < uFutilityMargin) && (iExtend <= 0) && - (!IS_ESCAPING_CHECK(mv))) + (!IS_ESCAPING_CHECK(mv)) && + (!IS_CAPTURE_OR_PROMOTION(mv)) && + (!IS_CHECKING_MOVE(mv)) && + (!fThreat)) + { + ULONG uFHAttempts = 0; + ULONG uFHPct = GetMoveFailHighPercentage(mv, &uFHAttempts); + fThisMoveEFPPruned = + (mv.cFrom != FindEnprisePiece(ctx, pos->uToMove)) && + ((uFHAttempts < EFP_FH_MIN_SAMPLES) || + (uFHPct <= EFP_FH_PRUNE_THRESHOLD)) && + (!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]))); + } + if (TRUE == fThisMoveEFPPruned) { - // TODO: test this more carefully ASSERT(!IS_CHECKING_MOVE(mv)); + fAnyMoveEFPPruned = TRUE; UnmakeMove(ctx, mv); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); } @@ -787,7 +873,22 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // Not checkmate/stalemate; store the result of this search in the // hash table. - if (iAlpha != iInitialAlpha) + // + // Ernst Heinz's warning (the book EFP is from): a node whose search + // depended on alpha/beta via forward pruning (a move skipped + // entirely, not just reduced -- LMR still searches its move, just + // shallower, so it isn't affected) cannot have its result stored as + // an exact score or a sound upper bound. If EFP skipped a move here + // without searching it, that move might have actually been the + // best one -- the true value could be *higher* than what we + // computed, in either case. An "exact" claim needs to know nothing + // better existed; an upper-bound claim needs the true value to be + // <= what we stored, both of which a skipped-but-possibly-better + // move can violate. mvBest/iBestScore (when found) remains a sound + // LOWER bound regardless -- we have a real line proving the + // position is at least this good -- so that's the most this node + // can honestly claim once fAnyMoveEFPPruned is set. + if ((iAlpha != iInitialAlpha) && (FALSE == fAnyMoveEFPPruned)) { ASSERT(mvBest.uMove != 0); if (!IS_CAPTURE_OR_PROMOTION(mvBest)) @@ -800,7 +901,22 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, } StoreExactScore(mvBest, pos, iBestScore, uDepth, fThreat, ctx->uPly); } - else + else if ((iAlpha != iInitialAlpha) && (TRUE == fAnyMoveEFPPruned)) + { + // Downgrade: mvBest proves a real achieving line, so this is a + // sound lower bound, just not provably exact. + ASSERT(mvBest.uMove != 0); + if (!IS_CAPTURE_OR_PROMOTION(mvBest)) + { + UpdateDynamicMoveOrdering(ctx, + uDepth, + mvBest, + iBestScore, + 0); + } + StoreLowerBound(mvBest, pos, iBestScore, uDepth, fThreat); + } + else if (FALSE == fAnyMoveEFPPruned) { // IDEA: "I am very well aware of the fact, that the scores // you get back outside of the window, are not trustable at @@ -820,6 +936,12 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // --Ed Schroder StoreUpperBound(pos, iBestScore, uDepth, fThreat); } + // else: fail-low (iAlpha == iInitialAlpha) AND fAnyMoveEFPPruned -- + // no sound bound in either direction to store (the skipped move + // could have raised the true value above iBestScore, so it's not a + // valid upper bound; there's no mvBest to offer as a lower bound + // either, since nothing beat alpha). Store nothing rather than + // cache an unsound result. end: ASSERT(IS_VALID_SCORE(iBeta)); -- cgit v1.3