Dynamic move ordering overhaul: continuation-history, evidence-gated

countermove promotion, retired hung-piece-escape and NumLeftoverMovesToSelect.

Full session was built on a "measure the pick, not the game" methodology:
aggregate solve counts on curated suites are too noisy to tune move-ordering
knobs against, so most decisions here came from per-move fail-high/alpha-raise
rates at much larger sample sizes (leftover FH% instrumentation, a zero-
selection-budget diagnostic that isolates a single best-of-remaining pick,
and evidence-bucket calibration), not solve-count deltas alone. See
CLAUDE.md's "Dynamic move ordering experiments" section for the reusable
methodology and generate.c's _ScoreAllMoves comment for the resulting
ordering hierarchy.

Changes:
- Added g_ContinuationHistory: same growth/decay math as the existing
  g_HistoryCounters butterfly table, additionally keyed by the previous
  move, so its magnitude is self-calibrated rather than a hand-picked
  constant. Flat, sufficient response across a 256x scale sweep.
- Countermove-table matches now get a real GOOD_MOVE-tier promotion
  (previously the table was write-only, tracked for stats but never read
  for ordering), but only when the match's own accumulated
  history+continuation evidence clears COUNTERMOVE_EVIDENCE_THRESHOLD
  (10,000) -- a raw match with no track record was shown to perform
  identically to an ordinary leftover (~0.6-0.85% FH), so promoting on
  match alone would have repeated hung-piece-escape's mistake below.
- Retired hung-piece-escape's unconditional GOOD_MOVE-tier promotion.
  Evidence-calibration showed the overwhelming majority of triggers (a
  zero-evidence population 250-1000x larger than countermove's) performed
  at the plain-leftover baseline -- the promotion was mostly free tier-
  escape treatment for moves that hadn't earned it. Replaced with
  FLEE_BONUS, a flat same-tier nudge inside SelectBestWithHistory (never
  escapes GOOD_MOVE/leftover classification, unlike a generation-time
  promotion) at the magnitude found to plateau a same-tier-nudge sweep.
- Retired NumLeftoverMovesToSelect (the depth-indexed budget on how many
  leftover moves got a full selection scan before falling back to
  unsorted order). search.c's main move loop now always fully selects --
  the leftover pool was shown to contain real, findable signal a bailout
  budget was discarding for a node-count savings that didn't hold up net-
  net once measured by solve counts and fail-high rates rather than raw
  node counts (noisy on small suites independent of this change).
- Collapsed leftover-move instrumentation from sorted/raw pairs down to a
  single set now that "raw" (unsorted fallback) is structurally
  impossible; kept the countermove evidence-bucket calibration counters
  (ongoing check that COUNTERMOVE_EVIDENCE_THRESHOLD stays well-
  calibrated); removed the contested-node A/B harness and hung-piece
  evidence calibration now that the decisions they were built to inform
  are made.

Net effect on the three curated suites (sd 10): solve counts wash (tied,
+1, -1 across ringers/confident/hard), leftover fail-high rate improved
consistently on all three (the intended, directly-measured target of this
work). Not yet validated beyond sd 10 -- an sn-based run or
eval_tune/match_play.py head-to-head gate is the natural next check before
leaning on this as a proven strength gain rather than a directionally-
sound, sd-10-clean change.

Co-Authored-By: Claude Sonnet 5 <[email protected]>
Claude-Session: https://claude.ai/code/session_014XePz6Sk4qQsTaP2jVJWJu

1 files changed, 106 insertions, 55 deletions

diff --git a/src/search.c b/src/search.c
index 33cd09d..61fa428 100755
--- a/src/search.c
+++ b/src/search.c
@@ -81,6 +81,27 @@ extern FLAG g_fCanSplit[MAX_PLY_PER_SEARCH];
 #define EFP_FH_MIN_SAMPLES     (5)
 #define EFP_FH_PRUNE_THRESHOLD (10)
 
+// EXPERIMENT: is history+continuation evidence predictive of a
+// countermove match's own FH%? See chess.h's CM_EVIDENCE_BUCKETS
+// comment. Buckets by log-ish bands rather than linear, since evidence
+// values span 0 to ~STRIP_OFF_FLAGS*2 (~16.7M).
+static ULONG
+_CMEvidenceBucket(ULONG uEvidence)
+{
+    static const ULONG uFloors[CM_EVIDENCE_BUCKETS] =
+        { 0, 1, 100, 1000, 10000, 100000, 1000000 };
+    ULONG i;
+
+    for (i = CM_EVIDENCE_BUCKETS; i > 0; i--)
+    {
+        if (uEvidence >= uFloors[i - 1])
+        {
+            return(i - 1);
+        }
+    }
+    return(0);
+}
+
 #ifdef DEBUG
 #define VERIFY_HASH_HIT                                \
     ASSERT(IS_VALID_SCORE(iScore));                    \
@@ -152,8 +173,9 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
     INT iExtend;
     ULONG uNextDepth;
     ULONG uLegalMoves = 0;
-    FLAG fInLeftovers = FALSE;
-    ULONG uLeftoverPicks = 0;
+    FLAG fIsLeftoverMove = FALSE;
+    FLAG fThisMoveIsCountermoveMatch = FALSE;
+    ULONG uCMEvidenceBucket = 0;
     HASH_ENTRY *pHash;
     FLAG fThreat;
     FLAG fSkipNull;
@@ -517,60 +539,44 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
                 if (x < ctx->sMoveStack.uEnd[ctx->uPly])
                 {
                     ASSERT(x >= ctx->sMoveStack.uBegin[ctx->uPly]);
-                    // EXPERIMENT (replaces the old pure move-count
-                    // SEARCH_SORT_LIMIT gate -- see lmr_testing/RESULTS.md):
-                    // a fixed count is blind to whether this move list is a
-                    // "strong team" (lots of winning captures/killers) or a
-                    // "weak team" (nothing but ordinary quiet moves) --
-                    // stopping at count N throws away real signal when N
-                    // good moves is an arbitrary cutoff partway through a
-                    // list full of good moves, modeled on Crafty (hash,
-                    // then MVV/LVA captures, then killers -- all always
-                    // fully ordered -- only *then* does its cheap fallback
-                    // kick in) and Stockfish (a value threshold, not a
-                    // position threshold, decides what's worth sorting).
+                    // Always fully select the best remaining move,
+                    // regardless of tier -- retired the old
+                    // NumLeftoverMovesToSelect budget (a depth-indexed
+                    // cutoff on how many "leftover", i.e. sub-GOOD_MOVE,
+                    // moves were worth a full SelectBestWithHistory scan
+                    // before taking the remainder in whatever order it
+                    // sat in) once this session's evidence-calibration
+                    // work (see chess.h's COUNTERMOVE_EVIDENCE_THRESHOLD/
+                    // FLEE_BONUS) showed the leftover pool has real,
+                    // findable signal -- countermove matches and
+                    // continuation-history-backed quiet moves both fail
+                    // high at rates well above the pool's average -- so
+                    // a bailout budget was discarding real information
+                    // for a node-count savings that didn't hold up
+                    // net-net once measured properly (solve counts and
+                    // leftover fail-high rates, not raw node counts,
+                    // which are too noisy on small suites to trust
+                    // alone). GOOD_MOVE itself is still meaningful here:
+                    // it's generate.c's own quality floor (below every
+                    // killer tier and SORT_THESE_FIRST's winning/even-
+                    // capture range), used below only to classify a
+                    // move as "leftover" for EFP eligibility and
+                    // instrumentation, not to gate how it's searched.
                     //
                     // On an IID-rescored ply, iValue is a real eval-axis
-                    // score (see RescoreMovesViaSearch/ComputeMoveScore) --
-                    // GOOD_MOVE is a generate.c ordering-encoding constant,
-                    // meaningless on that axis, so always fully select
-                    // there with no bailout point at all (unchanged from
-                    // before this experiment).
-                    //
-                    // Otherwise: keep fully selecting for as long as every
-                    // move found so far is >= GOOD_MOVE (a "high performer"
-                    // -- this constant already sits, by construction, below
-                    // every killer tier and SORT_THESE_FIRST's
-                    // winning/even-capture range, and above ordinary quiet
-                    // moves and losing captures, so it's a real quality
-                    // floor already baked into generate.c's own encoding,
-                    // not a new one). The first time a selection reveals a
-                    // move below that floor, we've hit "the rest of the
-                    // team" -- from then on, apply a budget
-                    // (NumLeftoverMovesToSelect, indexed by remaining
-                    // depth, not distance from root -- see searchsup.c)
-                    // on how many more full selections are worth the
-                    // cost before just taking the remainder in place.
+                    // score (see RescoreMovesViaSearch/ComputeMoveScore)
+                    // -- GOOD_MOVE is meaningless on that axis, so this
+                    // never classifies an IID-rescored move as a
+                    // leftover (matches pre-retirement behavior).
+                    fIsLeftoverMove = FALSE;
                     if (TRUE == pi->fMovesRescoredByIID)
                     {
                         SelectBestNoHistory(ctx, x);
                     }
-                    else if ((FALSE == fInLeftovers) ||
-                             (uLeftoverPicks <
-                              NumLeftoverMovesToSelect(ctx, uDepth)))
+                    else
                     {
                         SelectBestWithHistory(ctx, x);
-                        if (FALSE == fInLeftovers)
-                        {
-                            if (ctx->sMoveStack.mvf[x].iValue < GOOD_MOVE)
-                            {
-                                fInLeftovers = TRUE;
-                            }
-                        }
-                        else
-                        {
-                            uLeftoverPicks++;
-                        }
+                        fIsLeftoverMove = (ctx->sMoveStack.mvf[x].iValue < GOOD_MOVE);
                     }
                     mv = ctx->sMoveStack.mvf[x].mv;
 #ifdef DEBUG
@@ -578,6 +584,25 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
                                  MVF_MOVE_SEARCHED));
                     ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED;
 #endif
+                    // Countermove evidence calibration -- ongoing check
+                    // that COUNTERMOVE_EVIDENCE_THRESHOLD (chess.h) is
+                    // still well-calibrated: log every countermove-
+                    // matched move tried, bucketed by its own
+                    // accumulated history+continuation evidence.
+                    fThisMoveIsCountermoveMatch = FALSE;
+                    if ((!IS_CAPTURE_OR_PROMOTION(mv)) &&
+                        (ctx->uPly > 0) &&
+                        (0 != (pi - 1)->mv.uMove) &&
+                        (IS_SAME_MOVE(mv, ctx->mvCounter[MOVE_TO_INDEX((pi - 1)->mv)][0]) ||
+                         IS_SAME_MOVE(mv, ctx->mvCounter[MOVE_TO_INDEX((pi - 1)->mv)][1])))
+                    {
+                        ULONG uEvidence = g_HistoryCounters[mv.pMoved][mv.cTo] +
+                            g_ContinuationHistory[(MOVE_TO_CONT_KEY((pi - 1)->mv) *
+                                                   CONT_KEY_RANGE) +
+                                                  MOVE_TO_CONT_KEY(mv)];
+                        fThisMoveIsCountermoveMatch = TRUE;
+                        uCMEvidenceBucket = _CMEvidenceBucket(uEvidence);
+                    }
                     mv.bvFlags |= WouldGiveCheck(ctx, mv);
 
                     // Note: x is the index of the NEXT move to be
@@ -722,20 +747,20 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
             // lmr_testing/RESULTS.md for the individual experiments
             // that arrived at this checklist.
             //
-            // Explicit leftover-only gate (fInLeftovers, set above once
-            // the first sub-GOOD_MOVE move is selected, true for every
-            // move after): every high-performer move (winning/even
-            // capture, killer, killer-mate) is excluded from pruning
+            // Explicit leftover-only gate (fIsLeftoverMove, this move's
+            // own iValue < GOOD_MOVE): every high-performer move
+            // (winning/even capture, killer, killer-mate, sufficiently-
+            // evidenced countermove match) is excluded from pruning
             // consideration by construction, not just as a side effect
             // of the capture/check/killer exemptions above happening to
             // cover the same ground. Belt-and-suspenders on purpose --
             // this is the one thing that must never be true of a move
             // we skip outright.
             fThisMoveEFPPruned = FALSE;
-            if ((x != 0) && 
-                (uLegalMoves > 1) && 
+            if ((x != 0) &&
+                (uLegalMoves > 1) &&
                 (uFutilityMargin) &&
-                (TRUE == fInLeftovers) &&
+                (TRUE == fIsLeftoverMove) &&
                 (iExtend <= 0) &&
                 (!IS_ESCAPING_CHECK(mv)) && 
                 (!IS_CAPTURE_OR_PROMOTION(mv)) &&
@@ -763,6 +788,16 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
             }
             else
             {
+#ifdef PERF_COUNTERS
+                if (TRUE == fIsLeftoverMove)
+                {
+                    INC(ctx->sCounters.tree.u64LeftoverTries);
+                }
+                if (TRUE == fThisMoveIsCountermoveMatch)
+                {
+                    INC(ctx->sCounters.tree.u64CMEvidenceTries[uCMEvidenceBucket]);
+                }
+#endif
                 // Compute the next search depth for this move/subtree.
                 uNextDepth = uDepth - ONE_PLY + iExtend;
                 if (uNextDepth >= MAX_DEPTH_PER_SEARCH) uNextDepth = 0;
@@ -813,6 +848,16 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
                     {
                         if (iScore >= iBeta)
                         {
+#ifdef PERF_COUNTERS
+                            if (TRUE == fIsLeftoverMove)
+                            {
+                                INC(ctx->sCounters.tree.u64LeftoverFH);
+                            }
+                            if (TRUE == fThisMoveIsCountermoveMatch)
+                            {
+                                INC(ctx->sCounters.tree.u64CMEvidenceFH[uCMEvidenceBucket]);
+                            }
+#endif
                             // Update history and killers list and store in
                             // the transposition table.
                             UpdateDynamicMoveOrdering(ctx,
@@ -846,6 +891,12 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
                         }
                         else
                         {
+#ifdef PERF_COUNTERS
+                            if (TRUE == fIsLeftoverMove)
+                            {
+                                INC(ctx->sCounters.tree.u64LeftoverAlpha);
+                            }
+#endif
                             // PV move...
                             UpdatePV(ctx, mv);
                             iAlpha = iScore;