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