summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rwxr-xr-xsrc/search.c156
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));
generated by cgit v1.3 (git 2.53.0) at 2026-09-09 16:06:54 +0000