diff options
| -rwxr-xr-x | src/search.c | 156 |
1 files changed, 139 insertions, 17 deletions
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)); |