From 0b12137376929d96da81cd088d3d288cb1eec32d Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Sat, 29 Aug 2026 15:03:54 -0700 Subject: 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 Claude-Session: https://claude.ai/code/session_014XePz6Sk4qQsTaP2jVJWJu --- src/chess.h | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 73 insertions(+), 3 deletions(-) (limited to 'src/chess.h') 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); -- cgit v1.3