From 4ce6a76b0946e4ba943d29c506c9e2fb00601efd Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Thu, 27 Aug 2026 07:41:41 -0700 Subject: Baseline: uPositional data-calibrated fix, enprise/trapped hints, EBF/beta-cutoff/counter-move stats, script.c FPE fix. No LMR, no counter-move-driven move ordering (both explored separately, kept out for now -- counter-move measured worse, ~655->647 solved on ecm879 @ sn=4M with a leaner tree beforehand). Futility pruning restored. Verified: 647/879 solved, EBF 4.609 @ sn=4M; 684/879 solved, EBF 3.995 @ 20s/move, 1cpu, 256m hash (typhoon_baseline.log). The counter-move table is still written and its stats still tracked (dynamic.c) for diagnostic purposes, but generate.c no longer reads it for move ordering, so it has no effect on search behavior in this commit. lmr_testing/ holds the in-flight graded-LMR + counter-move code (not applied here) with notes on what was already tried and measured, so a future session can resume without re-deriving it. --- src/dynamic.c | 400 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 397 insertions(+), 3 deletions(-) (limited to 'src/dynamic.c') diff --git a/src/dynamic.c b/src/dynamic.c index 41b8cc1..33a673c 100755 --- a/src/dynamic.c +++ b/src/dynamic.c @@ -37,7 +37,13 @@ Revision History: #include "chess.h" +// Declared directly instead of #include -- that header +// #defines its own INFINITY, which collides with ours (chess.h:198, +// MAX_SHORT). Only needed once, at startup, to build g_iLMRQuietReduction. +extern double log(double); + ULONG g_HistoryCounters[14][128]; +SCORE g_iLMRQuietReduction[MAX_PLY_PER_SEARCH + 1][LMR_TABLE_MAX_MOVES + 1]; #define FH_STATS_TABLE_SIZE (0x20000) typedef struct _FH_STATS @@ -71,7 +77,54 @@ volatile static ULONG g_uDynamicLock; #endif -FLAG +void +InitLMRTable(void) +/** + +Routine description: + + Build the LMR reduction table once at startup -- log(depth) * + log(moves) formula (Ethereal's constants as a starting point, not + load-bearing; expect to retune), converted to ONE_PLY-scaled + integer ply-fractions so the search hot path never does floating + point. Quiet moves only; captures/promotions/checks/etc. are + excluded by GetLMRReduction's own gate before this table is ever + consulted. + +Parameters: + + void + +Return value: + + void + +**/ +{ + ULONG uDepth, uMoves; + double d; + + for (uDepth = 0; uDepth <= MAX_PLY_PER_SEARCH; uDepth++) + { + for (uMoves = 0; uMoves <= LMR_TABLE_MAX_MOVES; uMoves++) + { + if ((uDepth < 1) || (uMoves < 1)) + { + g_iLMRQuietReduction[uDepth][uMoves] = 0; + continue; + } + d = 0.7844 + (log((double)uDepth) * log((double)uMoves)) / 2.4696; + if (d < 0.0) + { + d = 0.0; + } + g_iLMRQuietReduction[uDepth][uMoves] = (SCORE)(d * (double)ONE_PLY); + } + } +} + + +FLAG InitializeDynamicMoveOrdering(void) /** @@ -254,8 +307,348 @@ Return value: } -static void -_IncrementMoveHistoryCounter(MOVE mv, +static void +_NewCounterMove(SEARCHER_THREAD_CONTEXT *ctx, MOVE mv, ULONG uRemainingDepth) +/** + +Routine description: + + Remember that mv refuted whatever move the opponent just played to + reach this node -- keyed by that previous move, not by ply, so it + generalizes across any branch where the opponent plays the same + move again, unlike killers. + + Depth-gated: a shallow fail-high (low uRemainingDepth, i.e. close + to the QSearch handoff) is much lower-confidence evidence than one + found with many plies still remaining, but unlike killers (which + are ply-scoped and self-correct locally), this table is global -- + keyed only by move identity, with nothing to stop a later, shallow + write from clobbering an earlier, deep one just because it's more + recent. Only overwrite when the new evidence is at least as deep + as what's already there. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + MOVE mv, + ULONG uRemainingDepth + +Return value: + + void + +**/ +{ + MOVE mvLast; + ULONG u; + ULONG uPly; + + ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); + ASSERT(mv.uMove); + + if (ctx->uPly == 0) + { + return; + } + mvLast = ctx->sPlyInfo[ctx->uPly - 1].mv; + if (0 == mvLast.uMove) + { + return; + } + u = MOVE_TO_INDEX(mvLast); + + // + // Hit-rate instrumentation: did the counter-move slot for this + // previous move already predict the move that just won here? + // Checked before the slot is (maybe) overwritten below. + // + if ((ctx->mvCounter[u][0].uMove != 0) || + (ctx->mvCounter[u][1].uMove != 0)) + { + INC(ctx->sCounters.tree.u64CounterMoveTries); + if (IS_SAME_MOVE(mv, ctx->mvCounter[u][0]) || + IS_SAME_MOVE(mv, ctx->mvCounter[u][1])) + { + INC(ctx->sCounters.tree.u64CounterMoveHits); + } + } + + // A/B test: write-gating by depth (reject shallower overwrites) + // measured *worse* hit rate with no EBF gain -- this table is + // global, not ply-scoped, so a frozen "deepest wins" entry can + // go stale while later, more locally-relevant evidence gets + // rejected. Always overwrite (recency); track depth instead to + // scale the read-time bonus. + uPly = uRemainingDepth / ONE_PLY; + if (!IS_SAME_MOVE(mv, ctx->mvCounter[u][0])) + { + ctx->mvCounter[u][1] = ctx->mvCounter[u][0]; + ctx->mvCounter[u][0] = mv; + } + ctx->uCounterDepth[u] = (UCHAR)MINU(uPly, 255); +} + + +void +RecordEnprisePieceAtPly(SEARCHER_THREAD_CONTEXT *ctx, ULONG uPly, COOR cSquare) +/** + +Routine description: + + Remember (at uPly, not necessarily the current ply) that the + piece sitting on cSquare in the *current* position -- which must + belong to whoever is to move at uPly -- looked en prise. + Ply-indexed and overwrite-in-place, exactly like killer moves: + this is a nice-to-have ordering/pruning hint, not a fact about the + current position, and readers must re-validate the recorded piece + is still on the recorded square before trusting it. + + Invariant: the recorded piece's color always matches the mover's + color at uPly -- same as a killer move's moved piece always does. + This only ever records *self* danger (the side to move at uPly + has a piece hanging), never "I can capture the opponent's piece" + -- that's a different fact, one no current reader wants, and + conflating the two would let noisy opponent-danger writes evict + the self-danger hints readers actually consume. + + uPly need not equal ctx->uPly: a fail-high capture is discovered + back at the capturing side's own ply (after UnmakeMove restores + the victim to cSquare), but the victim's color is the *other* + side's -- exactly the mover at ctx->uPly - 1 (ply parity + alternates), which is where "despite the move you're about to + make, this piece is still in trouble" actually belongs. Expected + mover is derived from the live ctx->uPly/ctx->sPosition.uToMove + (always in sync) via that parity offset, not from uPly directly. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + ULONG uPly, + COOR cSquare + +Return value: + + void + +**/ +{ + PIECE p = ctx->sPosition.rgSquare[cSquare].pPiece; + ULONG uExpectedMover = (((ctx->uPly - uPly) & 1) ? + FLIP(ctx->sPosition.uToMove) : + ctx->sPosition.uToMove); + + ASSERT(uPly < MAX_PLY_PER_SEARCH); + ASSERT(p && IS_VALID_PIECE(p) && !IS_PAWN(p)); + ASSERT(GET_COLOR(p) == uExpectedMover); + + if ((ctx->cEnprise[uPly][0] != cSquare) || + (ctx->pEnprise[uPly][0] != p)) + { + ctx->cEnprise[uPly][1] = ctx->cEnprise[uPly][0]; + ctx->pEnprise[uPly][1] = ctx->pEnprise[uPly][0]; + ctx->cEnprise[uPly][0] = cSquare; + ctx->pEnprise[uPly][0] = p; + } +} + + +void +RecordEnprisePiece(SEARCHER_THREAD_CONTEXT *ctx, COOR cSquare) +/** + +Routine description: + + RecordEnprisePieceAtPly at the current ply -- the common case + (self-danger found by a full Eval() at this exact node). + +**/ +{ + RecordEnprisePieceAtPly(ctx, ctx->uPly, cSquare); +} + + +void +RecordTrappedPiece(SEARCHER_THREAD_CONTEXT *ctx, COOR cSquare) +/** + +Routine description: + + Remember (at the current ply) that the piece sitting on cSquare -- + belonging to the side to move at this ply -- looked trapped. + Single slot -- trapped pieces are rarer than en prise ones. Same + freshness caveat and self-danger-only invariant as + RecordEnprisePiece. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + COOR cSquare + +Return value: + + void + +**/ +{ + ULONG uPly = ctx->uPly; + PIECE p = ctx->sPosition.rgSquare[cSquare].pPiece; + + ASSERT(uPly < MAX_PLY_PER_SEARCH); + ASSERT(p && IS_VALID_PIECE(p) && !IS_PAWN(p)); + ASSERT(GET_COLOR(p) == ctx->sPosition.uToMove); + + ctx->cTrapped[uPly] = cSquare; + ctx->pTrapped[uPly] = p; +} + + +static FLAG INLINE +_EnpriseSlotValid(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSlot, ULONG uSide) +{ + ULONG uPly = ctx->uPly; + COOR c = ctx->cEnprise[uPly][uSlot]; + + return(IS_ON_BOARD(c) && + (ctx->sPosition.rgSquare[c].pPiece == ctx->pEnprise[uPly][uSlot]) && + (GET_COLOR(ctx->pEnprise[uPly][uSlot]) == uSide)); +} + + +static FLAG INLINE +_TrappedSlotValid(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide) +{ + ULONG uPly = ctx->uPly; + COOR c = ctx->cTrapped[uPly]; + + return(IS_ON_BOARD(c) && + (ctx->sPosition.rgSquare[c].pPiece == ctx->pTrapped[uPly]) && + (GET_COLOR(ctx->pTrapped[uPly]) == uSide)); +} + + +COOR +FindEnprisePiece(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide) +/** + +Routine description: + + Look up an en prise piece of color uSide at the current ply, + re-validated against the live board (see RecordEnprisePiece). + Used by move ordering to boost moves that rescue the piece. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + ULONG uSide + +Return value: + + COOR : the square, or ILLEGAL_COOR if no valid hint + +**/ +{ + if (_EnpriseSlotValid(ctx, 0, uSide)) + { + return ctx->cEnprise[ctx->uPly][0]; + } + if (_EnpriseSlotValid(ctx, 1, uSide)) + { + return ctx->cEnprise[ctx->uPly][1]; + } + return ILLEGAL_COOR; +} + + +ULONG +ValueOfMaterialInTroubleDespiteMove(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide) +/** + +Routine description: + + Extended-futility safety net: how much material does uSide stand + to lose despite the move just made, per the en prise/trapped + hints at the current ply? Requires *both* en prise slots to be + valid for uSide (mirrors the old "more than one piece en prise" + threshold) before trusting the en prise value; the trapped hint + has no such threshold. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + ULONG uSide + +Return value: + + ULONG : material value in trouble, or 0 + +**/ +{ + ULONG uPly = ctx->uPly; + ULONG u = 0; + FLAG fHaveValue = FALSE; + COOR c, c1; + + if (_EnpriseSlotValid(ctx, 0, uSide) && _EnpriseSlotValid(ctx, 1, uSide)) + { + c = ctx->cEnprise[uPly][0]; + c1 = ctx->cEnprise[uPly][1]; + ASSERT(c != c1); + u = MINU(PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece), + PIECE_VALUE(ctx->sPosition.rgSquare[c1].pPiece)); + fHaveValue = TRUE; + } + if (_TrappedSlotValid(ctx, uSide)) + { + c = ctx->cTrapped[uPly]; + u = (fHaveValue ? + MINU(u, PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece)) : + PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece)); + } + return u; +} + + +ULONG +ValueOfMaterialInTroubleAfterNull(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide) +/** + +Routine description: + + Nullmove-pruning safety net: same as ValueOfMaterialInTroubleDespiteMove + but with a looser threshold (any valid en prise hint counts, not + just two) since this is guarding a cheaper, more speculative prune. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + ULONG uSide + +Return value: + + ULONG : material value in trouble, or 0 + +**/ +{ + ULONG uPly = ctx->uPly; + ULONG u = 0; + COOR c; + + if (_EnpriseSlotValid(ctx, 0, uSide)) + { + c = ctx->cEnprise[uPly][0]; + u = PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece); + } + if (_TrappedSlotValid(ctx, uSide)) + { + c = ctx->cTrapped[uPly]; + u = MAXU(u, PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece)); + } + return u; +} + + +static void +_IncrementMoveHistoryCounter(MOVE mv, ULONG uDepth) /** @@ -407,6 +800,7 @@ Return value: if (!IS_CAPTURE_OR_PROMOTION(mvBest)) { _NewKillerMove(ctx, mvBest, iScore); + _NewCounterMove(ctx, mvBest, uRemainingDepth); _IncrementMoveHistoryCounter(mvBest, uRemainingDepth); } -- cgit v1.3