summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorScott Gasch <[email protected]>2026-08-28 21:31:52 -0700
committerScott Gasch <[email protected]>2026-08-28 21:31:52 -0700
commitbc8a3fddb01a3708be54e1b5453cbd13c7afaaeb (patch)
tree654a568490f19ebf0f3c14bb272ef374f2197d3f
parentbb07fbd8612dbf2cfb6f257e8cba47b95c83c867 (diff)
Replace SEARCH_SORT_LIMIT's ply-indexed leftover-selection budget with
NumLeftoverMovesToSelect, indexed by remaining depth; make EFP's leftover-only scope explicit. SEARCH_SORT_LIMIT[ply] was a poor proxy for what actually matters here -- how large the remaining subtree below this node is. Distance from root only correlates with that when total search depth is roughly fixed; it says nothing once extensions/reductions/iterative-deepening are in play. NumLeftoverMovesToSelect(ctx, uDepth) uses remaining depth instead, only ever consulted once every high-performer move (winning/ even capture, killer, killer-mate -- anything >= GOOD_MOVE) has already been exhausted; this never limits how many of *those* get selected, only how much further care to spend on the ordinary/leftover tail. Table values carried over verbatim from the old one as an untuned starting point, just reindexed. Also adds an explicit (TRUE == fInLeftovers) gate to EFP's per-move checklist (landed last commit) -- every high-performer move was already excluded as a side effect of the capture/check/killer exemptions, but this makes "EFP only ever touches leftovers" a real, direct condition rather than an emergent property of unrelated checks. Verified against HEAD (commit bb07fbd) at sd10: ecm_ringers: 9/11 -> 10/11 (+1 solve), ~flat nodes (-0.04%) ecm_confident_quick: 88/90 -> 88/90 (even), +0.43% nodes ecm_hard_quick: 15/90 -> 18/90 (+3 solves), +4.4% nodes Net +4 solves across 269 positions for a negligible node-count cost.
-rwxr-xr-xsrc/chess.h12
-rwxr-xr-xsrc/data.c33
-rwxr-xr-xsrc/main.c1
-rwxr-xr-xsrc/search.c24
-rw-r--r--src/searchsup.c53
5 files changed, 72 insertions, 51 deletions
diff --git a/src/chess.h b/src/chess.h
index 9722414..6cd2d7a 100755
--- a/src/chess.h
+++ b/src/chess.h
@@ -1900,7 +1900,6 @@ extern VECTOR_DELTA g_VectorDelta[256];
extern VECTOR_DELTA *g_pVectorDelta;
extern CHAR g_SwapTable[14][32][32];
extern SCORE _PSQT[14][128];
-extern ULONG g_uSearchSortLimits[];
extern MOVE NULLMOVE;
extern MOVE HASHMOVE;
extern MOVE RECOGNMOVE;
@@ -1931,17 +1930,8 @@ InitializeSwapTable(void);
void
InitializeDistanceTable(void);
-void
-InitializeSearchDepthArray(void);
-
ULONG
-GetSearchSortLimit(ULONG);
-
-#ifdef DEBUG
-#define SEARCH_SORT_LIMIT(x) (GetSearchSortLimit((x)))
-#else
-#define SEARCH_SORT_LIMIT(x) (g_uSearchSortLimits[(x)])
-#endif
+NumLeftoverMovesToSelect(SEARCHER_THREAD_CONTEXT *ctx, ULONG uDepth);
#ifdef DEBUG
ULONG CheckVectorWithIndex(int i, ULONG uColor);
diff --git a/src/data.c b/src/data.c
index 2631d3a..b8f631d 100755
--- a/src/data.c
+++ b/src/data.c
@@ -34,9 +34,6 @@ CHAR g_SwapTable[14][32][32];
VECTOR_DELTA g_VectorDelta[256];
VECTOR_DELTA *g_pVectorDelta = &(g_VectorDelta[128]);
-// How many generated moves should we bother to sort
-ULONG g_uSearchSortLimits[MAX_PLY_PER_SEARCH];
-
// Hardcoded move patterns to terminate PVs with
MOVE NULLMOVE = {0};
MOVE HASHMOVE = {0x11118888};
@@ -183,36 +180,6 @@ VerifyVectorDelta(void)
}
void
-InitializeSearchDepthArray(void)
-{
- ULONG x;
-
- for (x = 0;
- x < ARRAY_LENGTH(g_uSearchSortLimits);
- x++)
- {
- g_uSearchSortLimits[x] = 5;
- }
- g_uSearchSortLimits[0] = 0;
- g_uSearchSortLimits[1] = 17;
- g_uSearchSortLimits[2] = 12;
- g_uSearchSortLimits[3] = 9;
- g_uSearchSortLimits[4] = 7;
- g_uSearchSortLimits[5] = 6;
-}
-
-#ifdef DEBUG
-ULONG
-GetSearchSortLimit(ULONG uPly)
-{
- ASSERT(uPly > 0);
- ASSERT(uPly < MAX_PLY_PER_SEARCH);
- ASSERT(g_uSearchSortLimits[uPly] != 0);
- return(g_uSearchSortLimits[uPly]);
-}
-#endif
-
-void
InitializeWhiteSquaresTable(void)
{
COOR c;
diff --git a/src/main.c b/src/main.c
index 3267da6..b09c8f0 100755
--- a/src/main.c
+++ b/src/main.c
@@ -457,7 +457,6 @@ Return value:
InitializeEGTB();
InitializeSigSystem();
InitializeInteriorNodeRecognizers();
- InitializeSearchDepthArray();
InitializeWhiteSquaresTable();
InitializeVectorDeltaTable();
InitializeSwapTable();
diff --git a/src/search.c b/src/search.c
index 02f4e85..b0bcafd 100755
--- a/src/search.c
+++ b/src/search.c
@@ -546,17 +546,18 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
// 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 (borrowing
- // SEARCH_SORT_LIMIT's existing table as an untuned
- // starting point for this new meaning) on how many more
- // full selections are worth the cost before just taking
- // the remainder in place.
+ // 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.
if (TRUE == pi->fMovesRescoredByIID)
{
SelectBestNoHistory(ctx, x);
}
else if ((FALSE == fInLeftovers) ||
- (uLeftoverPicks < SEARCH_SORT_LIMIT(ctx->uPly)))
+ (uLeftoverPicks <
+ NumLeftoverMovesToSelect(ctx, uDepth)))
{
SelectBestWithHistory(ctx, x);
if (FALSE == fInLeftovers)
@@ -720,10 +721,21 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
// own null-move probe raised fThreat. See
// 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
+ // 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) &&
(uFutilityMargin) &&
+ (TRUE == fInLeftovers) &&
(ComputeMoveScore(ctx, mv, (x - 1)) < uFutilityMargin) &&
(iExtend <= 0) &&
(!IS_ESCAPING_CHECK(mv)) &&
diff --git a/src/searchsup.c b/src/searchsup.c
index 5673bbe..e0d8251 100644
--- a/src/searchsup.c
+++ b/src/searchsup.c
@@ -24,6 +24,59 @@ extern SCORE g_iRootScore[2];
extern ULONG g_uHardExtendLimit;
extern ULONG g_uIterateDepth;
+ULONG
+NumLeftoverMovesToSelect(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uDepth)
+/**
+
+Routine description:
+
+ How many "leftover" (below GOOD_MOVE -- see search.c's
+ TRY_GENERATED_MOVES gate) moves are worth a full SelectBestWithHistory
+ scan before we give up and just take the remainder in whatever order
+ they're sitting in. Only ever consulted once every high-performer
+ move (winning/even capture, killer, killer-mate) has already been
+ exhausted -- this never limits how many of *those* get selected,
+ only how much further care to spend on the ordinary/leftover tail.
+
+ Replaces the old g_uSearchSortLimits[ply], indexed by distance from
+ the root -- a poor proxy for what actually matters here, which is
+ how large the remaining subtree below this node is (distance from
+ root only correlates with that when total search depth is roughly
+ fixed; it says nothing once extensions/reductions/iterative-deepening
+ are in play). uDepth (remaining depth, in ONE_PLY units, possibly
+ fractional) is the more principled signal: a bigger remaining
+ subtree makes the cost of a few extra O(n) selection scans more
+ worth paying to avoid a bad early choice cascading into extra
+ full-width re-searches.
+
+ STARTING POINT, NOT YET VALIDATED under this new meaning: this
+ reuses the previous table's six numbers verbatim, just reindexed by
+ plies of *remaining* depth instead of *distance from root* -- same
+ overall shape (more care with more depth left), same specific
+ values, carried over only because they're a known, testable
+ starting point, not because they were ever confirmed correct here.
+
+Parameters:
+
+ IN SEARCHER_THREAD_CONTEXT *ctx,
+ IN ULONG uDepth
+
+Return value:
+
+ ULONG
+
+**/
+{
+ static const ULONG _uLimits[] = { 8, 9, 11, 13, 15, 17 };
+ ULONG uPlies = uDepth / ONE_PLY;
+
+ if (uPlies >= ARRAY_LENGTH(_uLimits))
+ {
+ uPlies = ARRAY_LENGTH(_uLimits) - 1;
+ }
+ return(_uLimits[uPlies]);
+}
+
void
UpdatePV(SEARCHER_THREAD_CONTEXT *ctx, MOVE mv)
/**