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.

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));