diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/CLAUDE.md | 101 | ||||
| -rwxr-xr-x | src/chess.h | 76 | ||||
| -rwxr-xr-x | src/dynamic.c | 118 | ||||
| -rwxr-xr-x | src/generate.c | 113 | ||||
| -rwxr-xr-x | src/movesup.c | 44 | ||||
| -rwxr-xr-x | src/root.c | 8 | ||||
| -rwxr-xr-x | src/script.c | 45 | ||||
| -rwxr-xr-x | src/search.c | 161 | ||||
| -rw-r--r-- | src/searchsup.c | 53 | ||||
| -rwxr-xr-x | src/split.c | 24 |
10 files changed, 623 insertions, 120 deletions
diff --git a/src/CLAUDE.md b/src/CLAUDE.md index c7c7e4a..52a6877 100644 --- a/src/CLAUDE.md +++ b/src/CLAUDE.md @@ -317,6 +317,107 @@ bake-in-if-better, repeatable indefinitely against a growing game pool. large improvement it first looked like. Always diff ECM numbers taken at the same `sd` depth. +## Dynamic move ordering experiments (2026-08-29) + +A single long session that redesigned how quiet ("leftover", i.e. +sub-`GOOD_MOVE`) moves get ordered, replacing several hand-picked-and-never- +revisited heuristics with evidence-driven ones. Landed changes: retired +`NumLeftoverMovesToSelect` (see below), added a continuation-history table, +retired hung-piece-escape's unconditional tier promotion in favor of a +same-tier `FLEE_BONUS` nudge, and made the countermove table's tier +promotion evidence-gated instead of automatic. See `generate.c`'s +`_ScoreAllMoves` routine-description comment for the resulting move-ordering +hierarchy. The methodology below is the more durable takeaway -- reusable +for any future move-ordering question, not just the ones it already +answered. + +**Core technique: measure the *pick*, not the *game*.** Aggregate solve +counts on a 90-position suite are too noisy to tune a single move-ordering +knob against (a handful of positions flipping either way swamps the +signal) -- confirmed independently twice now, once by a prior session (see +`lmr_testing/RESULTS.md`'s "given-up leftover"/"would-prune surprise rate" +methodology) and once by this one. Instead, instrument the *local, per-move +outcome* (did trying this move raise alpha or fail high?) at a much larger +sample size, and read percentages off that instead of solve/pass counts. + +- **The "select nothing" / zero-selection-budget trick**: temporarily force + the leftover-selection budget to 0 (a compile-time constant swap + + rebuild, not a runtime flag -- keep this diagnostic-only, never commit + it) so that only the single "discovered we're in leftover territory" + transition move gets a full `SelectBestWithHistory` scan per node. That + scan still runs over the *entire* remaining pool regardless of budget, so + its result is genuinely "the best-of-remaining leftover, if we could only + afford to pick one" -- a clean, isolated read on whether the move-ordering + heuristic itself is any good, uncontaminated by how many picks the budget + allows. This is what first revealed that the countermove table's exact- + match signal was real (a forced-dominant version of it lifted the + best-leftover fail-high rate by about +1 percentage point, consistently, + across three curated suites) after a *scaled* continuation-history + version of the same signal showed a flat, uninformative response curve + across a 256x range -- the two experiments together showed scale wasn't + the missing variable, key resolution was (exact-move match vs. a coarser + [piece][to]-keyed proxy). +- **The contested-node A/B harness**, for "should class A rank above or + below class B" questions (e.g. countermove match vs. ply-2 killer): + aggregate per-class fail-high rates are confounded by *censoring* -- + whichever class is ranked higher gets tried first, so a lower-ranked + class's measured rate only ever reflects the subset of nodes where + nothing higher-ranked already resolved the position. Fix: at each node, + cheaply detect (piggybacked on the *first* `SelectBestWithHistory` call's + already-full-pool scan, no separate pass needed) whether *both* classes' + candidates are present as genuinely different moves; only log an outcome + on nodes where that's true, and only for the first candidate tried that + belongs to either class. **Caveat discovered by running this twice** (once + for countermove-vs-killer, once for hung-escape-vs-killer): whichever + class is *structurally disadvantaged* in a given test setting only wins + its rare contests via unusually strong self-reinforcing history/ + continuation evidence -- a self-selection effect that inflates the + disadvantaged class's apparent quality and deflates the favored class's, + independent of which is actually the better signal. Don't read a single + A/B setting's numbers at face value; compare each class's *least-filtered* + sample (the setting where it's favored) against the other's, not the + "loser" numbers from either individual run. +- **Evidence calibration**: once a structural pattern-match (countermove + table hit, en-prise escape) is identified, bucket every occurrence by its + own accumulated `g_HistoryCounters`+`g_ContinuationHistory` evidence + (log-ish bands: 0, 1-99, 100-999, ...) and plot fail-high rate per bucket. + This is the test for "is this pattern-match alone trustworthy, or does it + need a track record?" -- countermove matches with zero evidence scored + statistically identically to an ordinary unprivileged leftover (~0.6- + 0.85% FH) while evidence >=10,000 cleared 53-64%; hung-piece-escape's + zero-evidence population was 250-1000x larger than countermove's *and* + scored at the plain-leftover baseline too, revealing that the then- + shipping unconditional promotion was handing free tier-escape treatment + to a huge population that had done nothing to earn it. + +**Load-bearing gotcha, easy to reintroduce by accident**: a bonus added +inside `SelectBestWithHistory` (a selection-time-only nudge to the local +comparison value) never touches a move's persisted `iValue`, so it cannot +change `fIsLeftoverMove`/EFP eligibility no matter how large it is -- +useful for a same-tier nudge like `FLEE_BONUS`, useless if the goal is an +actual tier promotion. A real promotion (like the evidence-gated +countermove bonus) has to be written into `iValue` at *generation* time +(`generate.c`), not selection time. Confirmed by testing: an earlier +"dominant countermove" diagnostic added its huge bonus at selection time +and, despite clearly winning every internal comparison, never once actually +exempted a move from EFP or leftover classification -- the data it produced +was still valid (still genuinely measuring leftover-pool behavior) but the +mechanism didn't do what it looked like it should. + +**`NumLeftoverMovesToSelect` retirement**: the depth-indexed budget that +decided how many leftover moves got a full `SelectBestWithHistory` scan +before falling back to unsorted order was removed entirely once the +evidence above showed the leftover pool has real, findable signal a bailout +was discarding -- `search.c`'s main move loop now always fully selects. +Aggregate node-count deltas from this and related changes bounced around +by double-digit percentages on the smallest curated suite (`ecm_ringers`, +11 positions) with no corresponding solve change -- **on a suite this +small, a..b search's chaotic sensitivity to move order (a few more +depth-N-to-N+1 re-searches, a root fail-high or two) can move node counts +a lot for reasons unrelated to the change being tested. Fail-high +percentages and solve counts are the signal; raw node counts on small +suites mostly aren't.** + ## Environment notes - Shared, multi-user FreeBSD box with genuinely variable load (other Claude diff --git a/src/chess.h b/src/chess.h index b6175f7..137344f 100755 --- a/src/chess.h +++ b/src/chess.h @@ -783,6 +783,11 @@ MOVE_STACK; ((ctx)->sMoveStack.sGenFlags[(x)].uCheckingPieces) +// EXPERIMENT: see the fuller comment near COUNTERMOVE_TIER_BONUS below. +// Needs to be visible before COUNTERS/GAME_OPTIONS, which use it to +// size the evidence-bucket counter arrays. +#define CM_EVIDENCE_BUCKETS (7) + // ---------------------------------------------------------------------- // // Accumulators @@ -817,6 +822,11 @@ typedef struct _COUNTERS UINT64 u64BetaCutoffsOnFirstMove; UINT64 u64CounterMoveTries; // valid counter-move slot existed UINT64 u64CounterMoveHits; // ...and it was the move that won + UINT64 u64LeftoverTries; // leftover (sub-GOOD_MOVE) move tried + UINT64 u64LeftoverAlpha; // ...raised alpha (didn't fail high) + UINT64 u64LeftoverFH; // ...failed high + UINT64 u64CMEvidenceTries[CM_EVIDENCE_BUCKETS]; + UINT64 u64CMEvidenceFH[CM_EVIDENCE_BUCKETS]; UINT64 u64NullMoves; UINT64 u64NullMoveSuccess; #ifdef TEST_NULL @@ -1072,6 +1082,11 @@ typedef struct _GAME_OPTIONS UINT64 u64BetaCutoffsOnFirstMove; UINT64 u64CounterMoveTries; UINT64 u64CounterMoveHits; + UINT64 u64LeftoverTries; + UINT64 u64LeftoverAlpha; + UINT64 u64LeftoverFH; + UINT64 u64CMEvidenceTries[CM_EVIDENCE_BUCKETS]; + UINT64 u64CMEvidenceFH[CM_EVIDENCE_BUCKETS]; CHAR szLogfile[SMALL_STRING_LEN_CHAR]; CHAR szEGTBPath[SMALL_STRING_LEN_CHAR]; CHAR szBookName[SMALL_STRING_LEN_CHAR]; @@ -1830,6 +1845,46 @@ TestMakeUnmakeMove(void); #define SECOND_COUNTER_MOVE (0x00800000) #define STRIP_OFF_FLAGS (0x007FFFFF) +// Countermove-match tier bonus, placed above GOOD_MOVE (see +// generate.c's _ScoreAllMoves quiet-move branch) so a *sufficiently +// evidenced* match (see COUNTERMOVE_EVIDENCE_THRESHOLD) escapes +// "leftover" classification -- and the fIsLeftoverMove-gated EFP check -- +// entirely, becoming its own tier alongside killers. Conservatively +// placed below both ply-2 killer slots (FOURTH_KILLER/THIRD_KILLER): +// the contested-node A/B harness never found clean evidence a +// qualifying match should outrank killers, only that it beats them on +// average when forced to compete -- revisit with real data before +// moving it, don't just nudge it up. +#define COUNTERMOVE_TIER_BONUS (0x03000000) + +// Evidence threshold gating the promotion above -- the same +// history+continuation sum already used to score ordinary leftovers, +// evaluated for the specific countermove-matched move. Calibration +// (search.c's CM_EVIDENCE_BUCKETS harness) showed a match with zero +// evidence performs identically to an unprivileged leftover (~0.6- +// 0.85% FH); 10,000 is where the curve first clearly exceeds killer- +// ply2's own filtered/elite FH% (53.92-64.07% vs. 34.85-51.38%) on all +// three curated suites, the strongest defensible bar found. +#define COUNTERMOVE_EVIDENCE_THRESHOLD (10000) + +// EXPERIMENT: flee-to-safety same-tier nudge -- a flat bonus added at +// selection time (movesup.c's SelectBestWithHistory) for a quiet +// leftover move whose origin square is currently en prise, alongside +// history/continuation. Unlike the retired GOOD_MOVE-tier promotion, +// this never changes a move's classification -- it only nudges its +// rank among other leftovers. Swept empirically via the zero-selection- +// budget diagnostic, same methodology as CONTINUATION_SCALE. +#define FLEE_BONUS (100000) + +// EXPERIMENT: is history+continuation evidence actually predictive of +// a countermove match's FH%? Bucket every tried countermove-matched +// move by its accumulated evidence (g_HistoryCounters[piece][to] + +// g_ContinuationHistory[prev,cur], the same sum already used to score +// ordinary leftovers) and track tries/FH per bucket -- see search.c. +// Independent of tier placement; COUNTERMOVE_TIER_BONUS should be 0 +// while this runs so the calibration reflects unmodified behavior. +// (CM_EVIDENCE_BUCKETS itself is defined earlier, before COUNTERS.) + extern const int g_iQKDeltas[9]; extern const int g_iNDeltas[9]; extern const int g_iBDeltas[5]; @@ -1938,9 +1993,6 @@ InitializeSwapTable(void); void InitializeDistanceTable(void); -ULONG -NumLeftoverMovesToSelect(SEARCHER_THREAD_CONTEXT *ctx, ULONG uDepth); - #ifdef DEBUG ULONG CheckVectorWithIndex(int i, ULONG uColor); #define CHECK_VECTOR_WITH_INDEX(i, color) \ @@ -2779,6 +2831,24 @@ TestBitboards(void); // extern ULONG g_HistoryCounters[14][128]; +// Continuation history: same growth/decay math as g_HistoryCounters +// (see dynamic.c), but keyed additionally by the previous move, at the +// same [piece][to] coarseness -- not full from/to -- to keep the table +// a manageable size (14*128 * 14*128 = ~3.2M ULONGs, ~12MB). "Did a +// move of this piece-type to this square tend to fail high right after +// a move like that?" +// EXPERIMENT: read-time-only multiplier on the continuation-history +// contribution to a leftover move's selection score. Write-side growth/ +// decay math is untouched (still self-calibrating by evidence), this +// just scales how much weight that accumulated evidence carries +// relative to PSQT+history. Swept empirically via the zero-selection- +// budget diagnostic binary to trace best-leftover FH% vs. scale. +#define CONTINUATION_SCALE (1) +#define CONT_KEY_RANGE (14 * 128) +#define MOVE_TO_CONT_KEY(mv) (((mv).pMoved * 128) + (mv).cTo) +#define CONTINUATION_TABLE_SIZE (CONT_KEY_RANGE * CONT_KEY_RANGE) +extern ULONG g_ContinuationHistory[CONTINUATION_TABLE_SIZE]; + ULONG GetMoveFailHighPercentage(MOVE mv, ULONG *puAttempts); diff --git a/src/dynamic.c b/src/dynamic.c index 694fe50..5915721 100755 --- a/src/dynamic.c +++ b/src/dynamic.c @@ -43,6 +43,7 @@ Revision History: extern double log(double); ULONG g_HistoryCounters[14][128]; +ULONG g_ContinuationHistory[CONTINUATION_TABLE_SIZE]; SCORE g_iLMRQuietReduction[MAX_PLY_PER_SEARCH + 1][LMR_TABLE_MAX_MOVES + 1]; // Keyed by (cFrom, cTo, pMoved) -- the low 20 bits of mv.uMove -- rather @@ -178,6 +179,7 @@ Return value: ULONG u; memset(g_HistoryCounters, 0, sizeof(g_HistoryCounters)); + memset(g_ContinuationHistory, 0, sizeof(g_ContinuationHistory)); for (u = 0; u < FH_STATS_TABLE_SIZE; u++) { g_FailHighs[u].uWholeThing = 0x00010001; @@ -780,6 +782,111 @@ Return value: } +static void +_IncrementContinuationCounter(MOVE mvPrev, MOVE mv, ULONG uRemainingDepth) +/** + +Routine description: + + Continuation-history counterpart to _IncrementMoveHistoryCounter -- + same (depth+1)^2 growth, same overflow-driven rescale, but keyed by + (mvPrev, mv) instead of mv alone. No-op if there was no previous + move (root). + +Parameters: + + MOVE mvPrev, + MOVE mv, + ULONG uRemainingDepth + +Return value: + + void + +**/ +{ + ULONG uVal; + ULONG *pu; + ULONG x; + + ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); + if (0 == mvPrev.uMove) + { + return; + } + uVal = uRemainingDepth / ONE_PLY; + ASSERT(uVal >= 0); + ASSERT(uVal <= MAX_PLY_PER_SEARCH); + uVal += 1; + uVal *= uVal; + ASSERT(uVal > 0); + + pu = &(g_ContinuationHistory[(MOVE_TO_CONT_KEY(mvPrev) * CONT_KEY_RANGE) + + MOVE_TO_CONT_KEY(mv)]); + LOCK_DYN; + *pu += uVal; + while (*pu & ~STRIP_OFF_FLAGS) + { + for (x = 0; x < CONTINUATION_TABLE_SIZE; x++) + { + g_ContinuationHistory[x] >>= 4; + } + } + UNLOCK_DYN; +} + + +static void +_DecrementContinuationCounter(MOVE mvPrev, MOVE mv, ULONG uRemainingDepth) +/** + +Routine description: + + Continuation-history counterpart to _DecrementMoveHistoryCounter. + No-op if there was no previous move (root). + +Parameters: + + MOVE mvPrev, + MOVE mv, + ULONG uRemainingDepth + +Return value: + + void + +**/ +{ + ULONG uVal; + ULONG *pu; + + ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); + if (0 == mvPrev.uMove) + { + return; + } + uVal = uRemainingDepth / ONE_PLY; + ASSERT(uVal >= 0); + ASSERT(uVal <= MAX_PLY_PER_SEARCH); + uVal /= 4; + uVal += 1; + ASSERT(uVal > 0); + + pu = &(g_ContinuationHistory[(MOVE_TO_CONT_KEY(mvPrev) * CONT_KEY_RANGE) + + MOVE_TO_CONT_KEY(mv)]); + LOCK_DYN; + if (*pu >= uVal) + { + *pu -= uVal; + } + else + { + *pu = 0; + } + UNLOCK_DYN; +} + + void UpdateDynamicMoveOrdering(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uRemainingDepth, @@ -811,6 +918,9 @@ Return value: { ULONG u; MOVE mv; + MOVE mvPrev; + + mvPrev.uMove = (ctx->uPly > 0) ? (ctx->sPlyInfo[ctx->uPly - 1]).mv.uMove : 0; // // Add this move to the killer list and increment its history count @@ -820,6 +930,7 @@ Return value: _NewKillerMove(ctx, mvBest, iScore); _NewCounterMove(ctx, mvBest, uRemainingDepth); _IncrementMoveHistoryCounter(mvBest, uRemainingDepth); + _IncrementContinuationCounter(mvPrev, mvBest, uRemainingDepth); } // @@ -838,6 +949,7 @@ Return value: if (!IS_CAPTURE_OR_PROMOTION(mv)) { _DecrementMoveHistoryCounter(mv, uRemainingDepth); + _DecrementContinuationCounter(mvPrev, mv, uRemainingDepth); } } } @@ -923,7 +1035,7 @@ Return value: **/ { ULONG x, y; - + LOCK_DYN; for (x = 0; x <= WHITE_KING; x++) { @@ -932,5 +1044,9 @@ Return value: g_HistoryCounters[x][y] >>= 1; } } + for (x = 0; x < CONTINUATION_TABLE_SIZE; x++) + { + g_ContinuationHistory[x] >>= 1; + } UNLOCK_DYN; } diff --git a/src/generate.c b/src/generate.c index 3e3c3a5..765c082 100755 --- a/src/generate.c +++ b/src/generate.c @@ -2433,6 +2433,56 @@ Routine description: We have just generated all the moves, now score them. See comments inline below about order. + Full move-ordering hierarchy for a normal (not-in-check) node, from + highest-scored to lowest -- "vNext", the dynamic-move-ordering + overhaul from the 2026-08-29 session (see CLAUDE.md's "Dynamic move + ordering experiments" section for the methodology behind it): + + 1. Hash move -- already handled by Search(), never (re)generated + here; excluded from this list entirely. + 2. Killer that also threatens/delivers mate -- FIRST_KILLER (or + whichever killer slot matched) OR'd with SORT_THESE_FIRST. + 3. Winning/even captures & promotions -- SORT_THESE_FIRST, MVV/LVA + tiebreak; strictly-winning-by-raw-material trades skip SEE, an + even or ambiguous trade (or any promotion) gets the full + exchange walk. + 4. Killers, this ply's slot 0/1, then ply-2's slot 0/1 (Crafty-style + ordering, this ply's own pair before either ply-2-back one) -- + FIRST_KILLER/SECOND_KILLER/THIRD_KILLER/FOURTH_KILLER. + 5. A countermove-table match (exact move, keyed by whatever the + opponent just played) *whose own accumulated history+ + continuation-history evidence clears COUNTERMOVE_EVIDENCE_ + THRESHOLD* -- COUNTERMOVE_TIER_BONUS, placed below both ply-2 + killer slots (conservative default; never validated as + deserving to outrank them). An *unevidenced* match gets no + special treatment at all and falls through to tier 6 -- see + chess.h's COUNTERMOVE_TIER_BONUS/COUNTERMOVE_EVIDENCE_THRESHOLD + comments for why the promotion is evidence-gated rather than + automatic on a bare match. + 6. GOOD_MOVE boundary. Below this, "leftover" (see search.c's + fIsLeftoverMove) -- eligible for EFP pruning, but every leftover + is still fully ranked via SelectBestWithHistory (movesup.c); the + old NumLeftoverMovesToSelect depth-indexed selection budget was + retired once evidence showed the leftover pool has real, + findable signal a bailout was discarding. An ordinary leftover + quiet move's score is: + PSQT (g_iPSQT[piece][to], 0..1000) + + g_HistoryCounters[piece][to] (classic butterfly history, + (depth+1)^2 growth on fail-high, decays on a miss or global + aging pass) + + CONTINUATION_SCALE * g_ContinuationHistory[(prev move, this + move)] (same growth/decay math as history, additionally + keyed by the previous move -- self-calibrating, no magic + constant needed; CONTINUATION_SCALE=1 found flat/sufficient + across a 256x sweep) + + FLEE_BONUS if this move's origin square is currently en + prise (flat same-tier nudge; the old unconditional GOOD_ + MOVE-tier promotion for these moves was retired after + evidence-calibration showed most such moves, unbacked by + real track record, perform identically to an ordinary + leftover -- see the RETIRED comment below). + 7. Losing captures -- negative, SEE-verified. + Parameters: IN MOVE_STACK *pStack, @@ -2454,7 +2504,9 @@ Return value: ULONG uHashMoveLoc = (ULONG)-1; ULONG uColor = pos->uToMove; PRECOMP_KILLERS sKillers[4]; - COOR cEnprise = FindEnprisePiece(ctx, uColor); + ULONG uCounterMoveIdx = 0; + ULONG uCounterMoveContKey = 0; + FLAG fHaveCounterMove = FALSE; // // We have generated all moves here. We also know that we are not @@ -2506,6 +2558,18 @@ Return value: sKillers[3].uBonus |= (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[3].mv) != 0)); + // EXPERIMENT: countermove-match tier. Precompute the previous + // move's countermove-table index once per node (mirrors killer + // precompute above) so the per-move loop below is just an + // IS_SAME_MOVE check, not a recompute. + fHaveCounterMove = FALSE; + if ((uPly > 0) && (0 != (ctx->sPlyInfo[uPly - 1]).mv.uMove)) + { + uCounterMoveIdx = MOVE_TO_INDEX((ctx->sPlyInfo[uPly - 1]).mv); + uCounterMoveContKey = MOVE_TO_CONT_KEY((ctx->sPlyInfo[uPly - 1]).mv); + fHaveCounterMove = TRUE; + } + // // Score moves // @@ -2587,8 +2651,51 @@ Return value: s |= (IS_SAME_MOVE(sKillers[1].mv, mv) * sKillers[1].uBonus); s |= (IS_SAME_MOVE(sKillers[2].mv, mv) * sKillers[2].uBonus); s |= (IS_SAME_MOVE(sKillers[3].mv, mv) * sKillers[3].uBonus); - s |= ((GOOD_MOVE + PIECE_VALUE(mv.pMoved) / 2) * - (mv.cFrom == cEnprise)); + + // RETIRED: hung-piece-escape used to get an unconditional + // (GOOD_MOVE + PIECE_VALUE/2) promotion here for any move + // whose origin square was flagged en-prise, regardless of + // any track record. Evidence-calibration data showed the + // overwhelming majority of triggers (the "zero accumulated + // history/continuation evidence" bucket -- 250-1000x more + // populous than the equivalent countermove-match bucket) + // had a fail-high rate statistically identical to an + // ordinary, unprivileged leftover move (~0.22-0.25% vs. + // ~0.19-0.21% baseline). The escape motif alone, with no + // verification the destination is actually safe or the + // threat was real, isn't a trustworthy enough signal to + // justify an unconditional tier promotion -- unlike + // killers (self-evidencing by construction) or a + // sufficiently-evidenced countermove match. Retired + // rather than evidence-gated: a well-evidenced escape + // still gets ranked via the existing, already-validated + // history/continuation scoring below, same as any other + // leftover -- no separate mechanism needed for that case. + + // Countermove-match tier, evidence-gated -- see chess.h's + // COUNTERMOVE_TIER_BONUS/COUNTERMOVE_EVIDENCE_THRESHOLD + // comment. Calibration data showed a raw match, with no + // track record, performs identically to an ordinary + // leftover (~0.6-0.85% FH) -- promoting on match alone + // repeats hung-piece-escape's mistake. Only promote once + // the same history+continuation evidence already used + // to score ordinary leftovers clears a threshold where + // it demonstrably beats killer-ply2's own average. + // Written into iValue itself (not a selection-time-only + // nudge) so a qualifying match actually escapes + // GOOD_MOVE/leftover classification. + if ((TRUE == fHaveCounterMove) && + (IS_SAME_MOVE(mv, ctx->mvCounter[uCounterMoveIdx][0]) || + IS_SAME_MOVE(mv, ctx->mvCounter[uCounterMoveIdx][1]))) + { + ULONG uCMEvidence = g_HistoryCounters[mv.pMoved][mv.cTo] + + g_ContinuationHistory[(uCounterMoveContKey * CONT_KEY_RANGE) + + MOVE_TO_CONT_KEY(mv)]; + if (uCMEvidence >= COUNTERMOVE_EVIDENCE_THRESHOLD) + { + s |= COUNTERMOVE_TIER_BONUS; + } + } ASSERT(s >= 0); } pStack->mvf[u].iValue = s; diff --git a/src/movesup.c b/src/movesup.c index dec090c..33deae2 100755 --- a/src/movesup.c +++ b/src/movesup.c @@ -1017,11 +1017,36 @@ Return value: SCORE iVal; MOVE mv; MOVE_STACK_MOVE_VALUE_FLAGS mvfTemp; + MOVE mvLast; + ULONG uPrevContKey = 0; + FLAG fHaveContinuation = FALSE; + COOR cEnprise; ASSERT(ctx->sMoveStack.uBegin[ctx->uPly] <= uEnd); ASSERT(u >= ctx->sMoveStack.uBegin[ctx->uPly]); ASSERT(u < uEnd); + // Continuation history: "did a move like this tend to fail high + // right after a move like that?", keyed by (previous move, this + // move) at the same [piece][to] coarseness g_HistoryCounters + // already uses. Same accumulation/decay math as g_HistoryCounters + // (see _IncrementContinuationCounter/_DecrementContinuationCounter, + // dynamic.c) so its magnitude is empirically self-calibrated rather + // than a hand-picked constant -- a pair seen once contributes + // almost nothing, a pair that's fail-highed repeatedly at real + // depth naturally grows to compete with PSQT+history. + if ((ctx->uPly > 0) && (0 != (mvLast = (ctx->sPlyInfo[ctx->uPly - 1]).mv).uMove)) + { + uPrevContKey = MOVE_TO_CONT_KEY(mvLast); + fHaveContinuation = TRUE; + } + + // Flee-to-safety: a small, same-tier selection-time nudge (not a + // GOOD_MOVE promotion -- that class was retired, see generate.c's + // RETIRED comment) for a quiet move whose origin square is + // currently en prise. + cEnprise = FindEnprisePiece(ctx, ctx->sPosition.uToMove); + // // Linear search from u..ctx->sMoveStack.uEnd[ctx->uPly] for the // move with the best value. @@ -1031,6 +1056,16 @@ Return value: if (!IS_CAPTURE_OR_PROMOTION(mv)) { iBestVal += g_HistoryCounters[mv.pMoved][mv.cTo]; + if (TRUE == fHaveContinuation) + { + iBestVal += CONTINUATION_SCALE * + g_ContinuationHistory[(uPrevContKey * CONT_KEY_RANGE) + + MOVE_TO_CONT_KEY(mv)]; + } + if (mv.cFrom == cEnprise) + { + iBestVal += FLEE_BONUS; + } } uLoc = u; @@ -1041,6 +1076,15 @@ Return value: if (!IS_CAPTURE_OR_PROMOTION(mv)) { iVal += g_HistoryCounters[mv.pMoved][mv.cTo]; + if (TRUE == fHaveContinuation) + { + iVal += g_ContinuationHistory[(uPrevContKey * CONT_KEY_RANGE) + + MOVE_TO_CONT_KEY(mv)]; + } + if (mv.cFrom == cEnprise) + { + iVal += FLEE_BONUS; + } } if (iVal > iBestVal) { @@ -1278,6 +1278,14 @@ Return value: ctx->sCounters.tree.u64BetaCutoffsOnFirstMove; g_Options.u64CounterMoveTries = ctx->sCounters.tree.u64CounterMoveTries; g_Options.u64CounterMoveHits = ctx->sCounters.tree.u64CounterMoveHits; + g_Options.u64LeftoverTries = ctx->sCounters.tree.u64LeftoverTries; + g_Options.u64LeftoverAlpha = ctx->sCounters.tree.u64LeftoverAlpha; + g_Options.u64LeftoverFH = ctx->sCounters.tree.u64LeftoverFH; + for (u = 0; u < CM_EVIDENCE_BUCKETS; u++) + { + g_Options.u64CMEvidenceTries[u] = ctx->sCounters.tree.u64CMEvidenceTries[u]; + g_Options.u64CMEvidenceFH[u] = ctx->sCounters.tree.u64CMEvidenceFH[u]; + } g_MoveTimer.dEndTime = SystemTimeStamp(); // diff --git a/src/script.c b/src/script.c index 142b42c..0bc09e4 100755 --- a/src/script.c +++ b/src/script.c @@ -59,6 +59,11 @@ typedef struct _SUITE_COUNTERS UINT64 u64TotalBetaCutoffsOnFirstMove; UINT64 u64TotalCounterMoveTries; UINT64 u64TotalCounterMoveHits; + UINT64 u64TotalLeftoverTries; + UINT64 u64TotalLeftoverAlpha; + UINT64 u64TotalLeftoverFH; + UINT64 u64TotalCMEvidenceTries[CM_EVIDENCE_BUCKETS]; + UINT64 u64TotalCMEvidenceFH[CM_EVIDENCE_BUCKETS]; double dSigmaEBF; // sum of per-problem nodes^(1/depth) ULONG uEBFCount; // number of problems with depth > 0 double dAverageTimeToSolution; @@ -420,6 +425,19 @@ Return value: g_Options.u64CounterMoveTries; g_SuiteCounters.u64TotalCounterMoveHits += g_Options.u64CounterMoveHits; + g_SuiteCounters.u64TotalLeftoverTries += + g_Options.u64LeftoverTries; + g_SuiteCounters.u64TotalLeftoverAlpha += + g_Options.u64LeftoverAlpha; + g_SuiteCounters.u64TotalLeftoverFH += + g_Options.u64LeftoverFH; + for (v = 0; v < CM_EVIDENCE_BUCKETS; v++) + { + g_SuiteCounters.u64TotalCMEvidenceTries[v] += + g_Options.u64CMEvidenceTries[v]; + g_SuiteCounters.u64TotalCMEvidenceFH[v] += + g_Options.u64CMEvidenceFH[v]; + } } else { @@ -448,6 +466,8 @@ Return value: " avg. eff. branching : %5.3f\n" " counter move hit %% : %5.2f percent (%" COMPILER_LONGLONG_UNSIGNED_FORMAT " tries)\n" + " leftover : %5.2f%% alpha, %5.2f%% FH (%" + COMPILER_LONGLONG_UNSIGNED_FORMAT " tries)\n" " script time : %6.1f sec\n\n", g_SuiteCounters.uCorrect, g_SuiteCounters.uIncorrect, @@ -467,8 +487,31 @@ Return value: (100.0 * (double)g_SuiteCounters.u64TotalCounterMoveHits / ((double)g_SuiteCounters.u64TotalCounterMoveTries + 1.0)), g_SuiteCounters.u64TotalCounterMoveTries, + (100.0 * (double)g_SuiteCounters.u64TotalLeftoverAlpha / + ((double)g_SuiteCounters.u64TotalLeftoverTries + 1.0)), + (100.0 * (double)g_SuiteCounters.u64TotalLeftoverFH / + ((double)g_SuiteCounters.u64TotalLeftoverTries + 1.0)), + g_SuiteCounters.u64TotalLeftoverTries, (SystemTimeStamp() - dSuiteStart)); - + + // Countermove evidence calibration -- FH% per evidence bucket, + // an ongoing check that COUNTERMOVE_EVIDENCE_THRESHOLD (chess.h) + // is still well-calibrated as the engine/data evolve. + { + static const ULONG uCMEvidenceFloors[CM_EVIDENCE_BUCKETS] = + { 0, 1, 100, 1000, 10000, 100000, 1000000 }; + Trace("\ncountermove evidence calibration:\n"); + for (v = 0; v < CM_EVIDENCE_BUCKETS; v++) + { + Trace(" evidence >= %8lu : %5.2f%% FH (%" + COMPILER_LONGLONG_UNSIGNED_FORMAT " tries)\n", + uCMEvidenceFloors[v], + (100.0 * (double)g_SuiteCounters.u64TotalCMEvidenceFH[v] / + ((double)g_SuiteCounters.u64TotalCMEvidenceTries[v] + 1.0)), + g_SuiteCounters.u64TotalCMEvidenceTries[v]); + } + } + // Histogram stuff if (g_SuiteCounters.uTotal > 0) { uMax = g_SuiteCounters.uHistogram[0]; 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; diff --git a/src/searchsup.c b/src/searchsup.c index 54e1814..72667c8 100644 --- a/src/searchsup.c +++ b/src/searchsup.c @@ -24,59 +24,6 @@ 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) /** diff --git a/src/split.c b/src/split.c index 17b77f6..8bc4e60 100755 --- a/src/split.c +++ b/src/split.c @@ -604,6 +604,9 @@ Return value: g_SplitInfo[u].sCounters.tree.u64TotalNodeCount = 0; g_SplitInfo[u].sCounters.tree.u64BetaCutoffs = 0; g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove = 0; + g_SplitInfo[u].sCounters.tree.u64LeftoverTries = 0; + g_SplitInfo[u].sCounters.tree.u64LeftoverAlpha = 0; + g_SplitInfo[u].sCounters.tree.u64LeftoverFH = 0; g_SplitInfo[u].PV[0] = NULLMOVE; // @@ -628,9 +631,10 @@ Return value: // work for naught. We also want to know as soon as // possible so that we can vacate this split point, // free up a worker thread and get back to the main - // search. So forget about the leftover-selection - // budget (NumLeftoverMovesToSelect in search.c) here - // and sort the whole list of moves from best..worst. + // search. So sort the whole list of moves from + // best..worst (search.c's main loop does the same + // unconditionally now too -- see its retired + // NumLeftoverMovesToSelect budget comment). // SelectBestWithHistory(ctx, v); ctx->sMoveStack.mvf[v].mv.bvFlags |= @@ -761,6 +765,12 @@ Return value: g_SplitInfo[u].sCounters.tree.u64BetaCutoffs; ctx->sCounters.tree.u64BetaCutoffsOnFirstMove = g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove; + ctx->sCounters.tree.u64LeftoverTries = + g_SplitInfo[u].sCounters.tree.u64LeftoverTries; + ctx->sCounters.tree.u64LeftoverAlpha = + g_SplitInfo[u].sCounters.tree.u64LeftoverAlpha; + ctx->sCounters.tree.u64LeftoverFH = + g_SplitInfo[u].sCounters.tree.u64LeftoverFH; #endif // // Pop off the split info ptr from the stack in the thread's @@ -932,8 +942,14 @@ Return value: ctx->sCounters.tree.u64TotalNodeCount; g_SplitInfo[u].sCounters.tree.u64BetaCutoffs += ctx->sCounters.tree.u64BetaCutoffs; - g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove += + g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove += ctx->sCounters.tree.u64BetaCutoffsOnFirstMove; + g_SplitInfo[u].sCounters.tree.u64LeftoverTries += + ctx->sCounters.tree.u64LeftoverTries; + g_SplitInfo[u].sCounters.tree.u64LeftoverAlpha += + ctx->sCounters.tree.u64LeftoverAlpha; + g_SplitInfo[u].sCounters.tree.u64LeftoverFH += + ctx->sCounters.tree.u64LeftoverFH; // // TODO: Any other counters we care about? |