/** Copyright (c) Scott Gasch Module Name: dynamic.c Abstract: Dynamic move ordering functions/structures. By "dynamic move ordering" I mean killer moves and history heuristic stuff. Note 1: there are two history tables here. One is used for move ordering and the other is used for pruning decisions. Both only contain data about non-capture/promote moves. The former is updated with roughly remaining_depth^2 at a fail high while the latter is updated so as to maintain an approximate answer to "what percent of the time does this move fail high." Note 2: the globals in this module may be accessed by more than one searcher thread at the same time; spinlocks used to synchronize. Note 3: All of these tables must be cleared when a new game is started or a new position is loaded onto the board. Author: Scott Gasch (scott.gasch@gmail.com) 24 Jun 2004 Revision History: $Id: dynamic.c 345 2007-12-02 22:56:42Z scott $ **/ #include "chess.h" // Only needed once, at startup, to build g_iLMRQuietReduction and // g_uWilsonUpperBoundThousandths below -- math.h's own INFINITY macro // used to collide with ours before chess.h's was renamed to // INFINITY_SCORE (2026-10-23). #include 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 // than MOVE_TO_INDEX's (cFrom, cTo, color) so that e.g. a king shuffle // and a queen sac to the same square/color aren't folded into the same // fail-high bucket. pMoved's low bit is already the color, so this // subsumes MOVE_TO_INDEX's color term for free. #define MOVE_TO_FH_INDEX(mv) ((mv).uMove & 0xFFFFF) #define FH_STATS_TABLE_SIZE (0x100000) typedef struct _FH_STATS { union { ULONG uWholeThing; struct { USHORT u16FailHighs; USHORT u16Attempts; }; }; } FH_STATS; FH_STATS g_FailHighs[FH_STATS_TABLE_SIZE]; // Precomputed Wilson-score upper-confidence-bound table for the dynamic // per-move-identity fail-high rate, in the same "thousandths of a // percent" unit g_uJointFHThousandths uses -- so a caller can feed this // straight into the same reduction-magnitude formula without any unit // conversion. See GetLMRReduction's 2026-10-23 dynamic-blend comment for // why an upper CONFIDENCE BOUND (not the raw FailHighs/Attempts ratio) // is the right thing to feed that formula: a bound widens automatically // for a thin sample (0 fail-highs in 2 tries proves almost nothing) and // narrows toward the true rate as real evidence accumulates (0 fail- // highs in 65,000 tries is real evidence of safety), which is exactly // the asymmetric trust a raw point estimate can't express on its own. // // Computing the real Wilson formula (one divide for p-hat, several more // for the z^2/n terms, one sqrt) per move at Search's call frequency is // a non-starter -- this is the hottest function in the engine. Instead: // bucket both inputs onto small, branchless-indexable ranges and pay // the real formula's cost exactly once per cell, at startup, in // InitializeWilsonBoundTable below. At the one call site that matters // (GetLMRReduction's hot path), the whole lookup is two bit-length/min // ops and one array index -- no FP divide, no sqrt, nothing branchy // keyed on "essentially random move metadata" the way a comparison // chain would be. // // Bucket shape, chosen to be cheap to compute rather than retrofitted // onto one (contrast with _ShipDepthBucket/_ShipLateBucket's comparison // chains elsewhere in this file's sibling searchsup.c, which can't be // changed this way without also re-baking the static table they index -- // not a problem here, this table has no offline-baked counterpart to // stay in lockstep with): // - Attempts bucket = FastLastBit(Attempts | 1) (chess.h) -- a single // bsr/clz instruction, 1-based bit-length, so bucket b covers the // power-of-two range [2^(b-1), 2^b - 1]. u16Attempts is at most // 65535, so b runs 1..16; index 0 is unused (kept so the raw // FastLastBit result can be used directly with no decrement). // - FailHigh bucket = MIN(FailHighs, 3) -- a single branchless min // (MINU already compiles to cmov elsewhere in this codebase), 0/1/2 // exact, 3 meaning "3 or more". Finer resolution buys little here: // by the time a move identity has a handful of real fail-highs on // record, the formula this feeds already treats it as maximally // dangerous regardless of the exact count (see the 10%/50%/90% // finding from the same day's design discussion -- all three // already clamp to zero extra reduction against the 0.4% baseline, // so distinguishing "3 fail-highs" from "30" buys nothing further). #define WILSON_ATTEMPTS_BUCKETS (17) #define WILSON_FH_BUCKETS (4) USHORT g_uWilsonUpperBoundThousandths[WILSON_ATTEMPTS_BUCKETS][WILSON_FH_BUCKETS]; #ifdef MP volatile static ULONG g_uDynamicLock; #define DYN_IS_LOCKED (g_uDynamicLock != 0) #define LOCK_DYN \ AcquireSpinLock(&g_uDynamicLock); \ ASSERT(DYN_IS_LOCKED) #define UNLOCK_DYN \ ASSERT(DYN_IS_LOCKED); \ ReleaseSpinLock(&g_uDynamicLock) #else // no MP #define DYN_IS_LOCKED (1) #define LOCK_DYN #define UNLOCK_DYN #endif void InitializeWilsonBoundTable(void) /** Routine description: Build g_uWilsonUpperBoundThousandths once at startup -- see that table's own comment for why (cost: real Wilson-score math, paid once per bucket cell here, never at Search's call frequency). z=2.0 (~95.4% one-sided confidence) chosen as a simple round constant, same spirit as InitializeLMRTable's own Ethereal-derived starting constants a few lines down: a reasonable starting shape, not load-bearing, expect to retune once this is actually wired into a reduction decision and measured. Representative (n, k) per cell: n = the bucket's own lower power- of-two bound (2^(bucket-1) for bucket >= 1) -- deliberately the SMALLER end of the bucket's range, so the bound computed is the more cautious (wider) one a real Attempts value anywhere in that bucket could justify, never an optimistic extrapolation past what the smallest member of the bucket actually earns. k = the FH bucket's own index (0, 1, 2, or 3), capped to n (k can't exceed attempts) -- using 3 as the representative for the "3+" bucket rather than something larger only makes that cell's bound MORE cautious than reality, which is the safe direction to be wrong in. Parameters: void Return value: void **/ { ULONG uAttemptsBucket, uFhBucket; double z = 2.0; double z2 = z * z; for (uAttemptsBucket = 0; uAttemptsBucket < WILSON_ATTEMPTS_BUCKETS; uAttemptsBucket++) { double n = (uAttemptsBucket == 0) ? 1.0 : (double)(1UL << (uAttemptsBucket - 1)); for (uFhBucket = 0; uFhBucket < WILSON_FH_BUCKETS; uFhBucket++) { double k = (double)uFhBucket; double phat, center, spread, denom, upper; ULONG uThousandths; if (k > n) { k = n; } phat = k / n; denom = 1.0 + z2 / n; center = phat + z2 / (2.0 * n); spread = z * sqrt((phat * (1.0 - phat) / n) + (z2 / (4.0 * n * n))); upper = (center + spread) / denom; if (upper > 1.0) { upper = 1.0; } uThousandths = (ULONG)((upper * 100000.0) + 0.5); if (uThousandths > 100000) { uThousandths = 100000; } g_uWilsonUpperBoundThousandths[uAttemptsBucket][uFhBucket] = (USHORT)uThousandths; } } } // Branchless lookup into g_uWilsonUpperBoundThousandths -- see that // table's own comment for the design rationale. FastLastBit (chess.h) // is a single bsr/clz instruction; MINU is this codebase's existing // branchless-min macro (compiles to cmov). No divide, no sqrt, no // comparison chain, at this call site -- all of that cost was paid // once, at startup, in InitializeWilsonBoundTable above. ULONG GetMoveFailHighWilsonUpperBoundThousandths(IN MOVE mv) /** Routine description: Look up a move identity's dynamic fail-high rate as a Wilson-score upper confidence bound (thousandths of a percent, same unit g_uJointFHThousandths uses) rather than the raw FailHighs/Attempts ratio GetMoveFailHighPctThousandths returns -- see g_uWilsonUpperBoundThousandths's comment for why that distinction matters for feeding a reduction-magnitude formula specifically. Parameters: MOVE mv Return value: ULONG : Wilson upper bound, thousandths of a percent (0-100000) **/ { ULONG u = MOVE_TO_FH_INDEX(mv); ULONG uAttempts = g_FailHighs[u].u16Attempts; ULONG uFailHighs = g_FailHighs[u].u16FailHighs; ULONG uAttemptsBucket = FastLastBit((BITBOARD)(uAttempts | 1)); ULONG uFhBucket = MINU(uFailHighs, (ULONG)(WILSON_FH_BUCKETS - 1)); return(g_uWilsonUpperBoundThousandths[uAttemptsBucket][uFhBucket]); } void InitializeLMRTable(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) /** Routine description: Initialize dynamic move ordering structures. Parameters: void Return value: FLAG **/ { #ifdef MP g_uDynamicLock = 0; #endif ClearDynamicMoveOrdering(); return(TRUE); } void ClearDynamicMoveOrdering(void) /** Routine description: Clear the global history table. Killer moves are per-context structures and must be cleared on a per-context basis. Parameters: void Return value: void **/ { memset(g_HistoryCounters, 0, sizeof(g_HistoryCounters)); memset(g_ContinuationHistory, 0, sizeof(g_ContinuationHistory)); // 2026-10-02: was 0x00010001 (1 FH / 1 attempt, i.e. a faked 100% // rate) so that GetMoveFailHighPercentage's callers had something // non-zero to gate on even with no real evidence. That made the // table dishonest -- a move's reported percentage didn't track its // actual observed rate until enough real attempts diluted the // fake prior back out. Zeroing it means GetMoveFailHighPercentage // returns a genuine 0/0 until the first real observation; callers // that need to withhold judgement on a cold move must check // *puAttempts themselves rather than relying on an inflated // starting percentage (see GetLMRReduction, searchsup.c). memset(g_FailHighs, 0, sizeof(g_FailHighs)); } static void _RecordMoveFailHigh(MOVE mv) /** Routine description: Update the "fail high percentage" history table for this move. The table is used to make pruning decisions, not to rank moves. Parameters: MOVE mv Return value: static void **/ { ULONG u = MOVE_TO_FH_INDEX(mv); ULONG v = g_FailHighs[u].uWholeThing; ASSERT(DYN_IS_LOCKED); if (((v & 0x0000FFFF) == 0x0000FFFF) || ((v & 0xFFFF0000) == 0xFFFF0000)) { g_FailHighs[u].u16FailHighs >>= 1; g_FailHighs[u].u16Attempts >>= 1; } g_FailHighs[u].u16FailHighs++; g_FailHighs[u].u16Attempts++; ASSERT(g_FailHighs[u].u16FailHighs != 0); ASSERT(g_FailHighs[u].u16Attempts != 0); ASSERT(g_FailHighs[u].u16Attempts >= g_FailHighs[u].u16FailHighs); } static void _RecordMoveFailure(MOVE mv) /** Routine description: Update the fail high percentage table with the information that a move has not produced a fail high cutoff when it was considered. Parameters: MOVE mv Return value: static void **/ { ULONG u = MOVE_TO_FH_INDEX(mv); ASSERT(DYN_IS_LOCKED); if (g_FailHighs[u].u16Attempts == 0xFFFF) { g_FailHighs[u].u16FailHighs >>= 1; g_FailHighs[u].u16Attempts >>= 1; } g_FailHighs[u].u16Attempts++; ASSERT(g_FailHighs[u].u16Attempts != 0); ASSERT(g_FailHighs[u].u16Attempts >= g_FailHighs[u].u16FailHighs); } static void _NewKillerMove(SEARCHER_THREAD_CONTEXT *ctx, MOVE mv, SCORE iScore) /** Routine description: Add a new killer move at a ply. Parameters: SEARCHER_THREAD_CONTEXT *ctx, MOVE mv, SCORE iScore Return value: void **/ { ULONG uPly = ctx->uPly; ASSERT(uPly >= 0); ASSERT(uPly < MAX_PLY_PER_SEARCH); ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); ASSERT(mv.uMove); if (mv.bvFlags & MOVE_FLAG_ESCAPING_CHECK) { if (!IS_SAME_MOVE(mv, ctx->mvKillerEscapes[uPly][0])) { ctx->mvKillerEscapes[uPly][1] = ctx->mvKillerEscapes[uPly][0]; ctx->mvKillerEscapes[uPly][0] = mv; // No mvNullmoveQuietRefutations backfill here, unlike the // regular killer table below: TryNullmovePruning asserts // !InCheck() before probing, and a null move doesn't move // any piece, so the move that refutes it is necessarily // played from a position where the opponent was *not* in // check either -- it can never legitimately be a check // evasion. Backfilling with it here wouldn't be dead code // the way the old capture-into-quiet-slot bug was (that // was mathematically guaranteed to never match); since // IS_SAME_MOVE ignores bvFlags, an ordinary quiet move // from some unrelated non-check position could coincide // with a real escaping candidate by cFrom/cTo/pMoved/ // pCaptured/pPromoted alone and pick up an undeserved // SECOND_KILLER bonus in evasion ordering. Leave the slot // empty instead of risking that. } ASSERT(!IS_SAME_MOVE(ctx->mvKillerEscapes[uPly][0], ctx->mvKillerEscapes[uPly][1])); } else { mv.bvFlags |= ((iScore >= +NMATE) * MOVE_FLAG_KILLERMATE); if (!IS_SAME_MOVE(mv, ctx->mvKiller[uPly][0])) { ctx->mvKiller[uPly][1] = ctx->mvKiller[uPly][0]; ctx->mvKiller[uPly][0] = mv; if ((ctx->mvKiller[uPly][1].uMove == 0) && (!IS_SAME_MOVE(ctx->mvNullmoveQuietRefutations[uPly], mv))) { // Guard against backfilling slot[1] with the same move // just placed in slot[0] -- e.g. this ply's recorded // null-move quiet refutation happens to coincide with // the move causing the current fail-high. Without this // check both slots would hold the identical move, // wasting a killer slot (and, in a DEBUG build, // tripping the assert below) for no ordering benefit. ctx->mvKiller[uPly][1] = ctx->mvNullmoveQuietRefutations[uPly]; } } ASSERT(!IS_SAME_MOVE(ctx->mvKiller[uPly][0], ctx->mvKiller[uPly][1])); } } 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. 2026-10-02: corrected -- this used to claim depth-gated writes ("only overwrite when the new evidence is at least as deep as what's already there"), but that was already stale: an A/B test (see the inline comment below) measured depth-gating as *worse* (lower hit rate, no EBF gain) than unconditional recency-based overwrite, and the code was changed accordingly without this routine description being updated to match. Always overwrites on recency now; there is no depth gate. Parameters: SEARCHER_THREAD_CONTEXT *ctx, MOVE mv, ULONG uRemainingDepth Return value: void **/ { MOVE mvLast; ULONG u; 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); #ifdef MOVE_ORDERING_EVIDENCE_COLLECTION // // 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)) { MOI_INC(ctx->sCounters.tree.u64CounterMoveTries); if (IS_SAME_MOVE(mv, ctx->mvCounter[u][0]) || IS_SAME_MOVE(mv, ctx->mvCounter[u][1])) { MOI_INC(ctx->sCounters.tree.u64CounterMoveHits); } } #endif // 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). if (!IS_SAME_MOVE(mv, ctx->mvCounter[u][0])) { ctx->mvCounter[u][1] = ctx->mvCounter[u][0]; ctx->mvCounter[u][0] = mv; } } 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; #ifdef DEBUG ULONG uExpectedMover = (((ctx->uPly - uPly) & 1) ? FLIP(ctx->sPosition.uToMove) : ctx->sPosition.uToMove); #endif ASSERT(uPly < MAX_PLY_PER_SEARCH); ASSERT(p && IS_VALID_PIECE(p) && !IS_PAWN(p)); ASSERT(GET_COLOR(p) == uExpectedMover); // 2026-09-18: dedup on SQUARE alone, not (square, piece) -- the // two slots are meant to hold the last two DISTINCT en-prise // squares (see ValueOfMaterialInTroubleDespiteMove's "two // different pieces hanging" use, which ASSERTs the two recorded // squares differ). A same-square re-record with a different // recorded piece -- legitimate per this function's own doc // comment (a fail-high capture's victim is restored to cSquare by // UnmakeMove, and can differ across calls at the same ply) -- // used to compare piece identity too, so it shifted the old // (cSquare, oldPiece) entry down into slot 1 instead of updating // slot 0 in place, leaving BOTH slots holding the same square. // Found via fuzzing tests/cross_sectional_200k.ep_ (DEBUG build, // sd 3): tripped ValueOfMaterialInTroubleDespiteMove's // ASSERT(c != c1) from a live QSearch call, not a display path. if (ctx->cEnprise[uPly][0] != cSquare) { 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]; // Was a live-board piece-identity re-check (same piece still on // that square); replaced with a direct signature compare against // the full eval that populated this slot (see PLY_INFO's // u64FullEvalSig comment, chess.h) -- cheaper, and exact rather // than an approximation that could false-positive on an unrelated // position coincidentally holding the same piece on the same // square at this ply. return((ctx->sPlyInfo[uPly].u64FullEvalSig == (ctx->sPosition.u64NonPawnSig ^ ctx->sPosition.u64PawnSig)) && IS_ON_BOARD(c) && (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]; // See _EnpriseSlotValid's comment -- same replacement. return((ctx->sPlyInfo[uPly].u64FullEvalSig == (ctx->sPosition.u64NonPawnSig ^ ctx->sPosition.u64PawnSig)) && IS_ON_BOARD(c) && (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; // Two different pieces hanging. 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; } // A trapped piece under attack with nowhere to run. 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; } static void _IncrementMoveHistoryCounter(MOVE mv, ULONG uDepth) /** Routine description: Increase a move's history counter in the global history table. Also affect the history pruning counters in prune.c. Parameters: MOVE mv, ULONG uDepth Return value: void **/ { ULONG *pu; ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); // // EXPERIMENT: flat/saturating update (see HISTORY_MAX/ // HISTORY_UPDATE_SHIFT comment, chess.h) -- depth-independent, // asymptotically approaches HISTORY_MAX, never exceeds it. // pu = &(g_HistoryCounters[mv.pMoved][mv.cTo]); LOCK_DYN; *pu += (HISTORY_MAX - *pu) >> HISTORY_UPDATE_SHIFT; #ifdef MP // // The purpose of this restriction is to ease contention for the // memory bandwidth of the machine on dual-core / dual proc // systems. The net result is positive. // if (uDepth > THREE_PLY) { _RecordMoveFailHigh(mv); } #else _RecordMoveFailHigh(mv); #endif UNLOCK_DYN; } static void _DecrementMoveHistoryCounter(MOVE mv, ULONG uDepth) /** Routine description: Decrease a move's history counter in the global history table. EXPERIMENT: flat/saturating decay, depth-independent -- see HISTORY_MAX/HISTORY_UPDATE_SHIFT comment in chess.h. Parameters: MOVE mv, ULONG uDepth Return value: void **/ { ULONG *pu; ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); ASSERT(uDepth <= MAX_PLY_PER_SEARCH * ONE_PLY); // param kept for signature parity w/ increment pu = &(g_HistoryCounters[mv.pMoved][mv.cTo]); LOCK_DYN; *pu -= (*pu >> HISTORY_UPDATE_SHIFT); _RecordMoveFailure(mv); UNLOCK_DYN; } static void _IncrementContinuationCounter(MOVE mvPrev, MOVE mv, ULONG uRemainingDepth) /** Routine description: Continuation-history counterpart to _IncrementMoveHistoryCounter -- EXPERIMENT: same flat/saturating depth-independent update (see HISTORY_MAX/HISTORY_UPDATE_SHIFT, chess.h), 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 *pu; ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); if (0 == mvPrev.uMove) { return; } ASSERT(uRemainingDepth <= MAX_PLY_PER_SEARCH * ONE_PLY); // unused by design now pu = &(g_ContinuationHistory[(MOVE_TO_CONT_KEY(mvPrev) * CONT_KEY_RANGE) + MOVE_TO_CONT_KEY(mv)]); LOCK_DYN; *pu += (HISTORY_MAX - *pu) >> HISTORY_UPDATE_SHIFT; UNLOCK_DYN; } static void _DecrementContinuationCounter(MOVE mvPrev, MOVE mv, ULONG uRemainingDepth) /** Routine description: Continuation-history counterpart to _DecrementMoveHistoryCounter -- EXPERIMENT: flat/saturating decay, depth-independent. No-op if there was no previous move (root). Parameters: MOVE mvPrev, MOVE mv, ULONG uRemainingDepth Return value: void **/ { ULONG *pu; ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); if (0 == mvPrev.uMove) { return; } ASSERT(uRemainingDepth <= MAX_PLY_PER_SEARCH * ONE_PLY); // unused by design now pu = &(g_ContinuationHistory[(MOVE_TO_CONT_KEY(mvPrev) * CONT_KEY_RANGE) + MOVE_TO_CONT_KEY(mv)]); LOCK_DYN; *pu -= (*pu >> HISTORY_UPDATE_SHIFT); UNLOCK_DYN; } void UpdateDynamicMoveOrdering(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uRemainingDepth, IN MOVE mvBest, IN SCORE iScore, IN ULONG uCurrent) /** Routine description: Update dynamic move ordering structs for a particular move (and, possibly, the other moves that were considered prior to this move in the move ordering). This is called when a move beats alpha at the root or in Search (but not in QSearch). Parameters: SEARCHER_THREAD_CONTEXT *ctx, ULONG uRemainingDepth, MOVE mvBest, SCORE iScore, ULONG uCurrent Return value: void **/ { 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 // if (!IS_CAPTURE_OR_PROMOTION(mvBest)) { _NewKillerMove(ctx, mvBest, iScore); _NewCounterMove(ctx, mvBest, uRemainingDepth); _IncrementMoveHistoryCounter(mvBest, uRemainingDepth); _IncrementContinuationCounter(mvPrev, mvBest, uRemainingDepth); } // // If this move was not the first we considered at this node, // decrement the history counters of moves we considered before // it. // uCurrent -= (uCurrent != 0); for (u = ctx->sMoveStack.uBegin[ctx->uPly]; u < uCurrent; u++) { ASSERT(IS_SAME_MOVE(ctx->sMoveStack.mvf[uCurrent].mv, mvBest)); mv = ctx->sMoveStack.mvf[u].mv; ASSERT(!IS_SAME_MOVE(mv, mvBest)); if (!IS_CAPTURE_OR_PROMOTION(mv)) { _DecrementMoveHistoryCounter(mv, uRemainingDepth); _DecrementContinuationCounter(mvPrev, mv, uRemainingDepth); } } } ULONG GetMoveFailHighPctThousandths(IN MOVE mv, OUT ULONG *puAttempts) /** Routine description: Lookup a move identity (see MOVE_TO_FH_INDEX -- (cFrom, cTo, pMoved), NOT a specific position) in the fail-high history table and return its observed fail-high rate in THOUSANDTHS OF A PERCENT (0-100000), the same unit g_uJointFHThousandths (data.c) uses, so a caller can compare this move's own dynamic rate directly against the static table's bucket-specific prediction for the situation it's in right now. 2026-10-03: this routine used to return per-mille (0-1000) while claiming, in this very comment, to share the static table's unit -- which is thousandths of a PERCENT, 100x finer. Every caller was individually correct (each compared against a constant calibrated in per-mille), but the two families were impossible to tell apart by name: ShouldLatePrune held LMP_DYNAMIC_MAX_THOUSANDTHS (1, meaning 0.1%) and LMP_STATIC_MAX_THOUSANDTHS (1, meaning 0.001%) side by side. Converted to the static table's unit so the comparison this comment always advertised is now literally valid, and every threshold constant renamed to ..._PCT_THOUSANDTHS. Returns a genuine 0/0 -- 0, *puAttempts 0 -- for a move identity with no observations since the last ClearDynamicMoveOrdering; callers that need to withhold judgement on a cold move must check *puAttempts themselves, not assume a low return value means "safe." Renamed from GetMoveFailHighPercentage (whole-percent resolution) 2026-10-02 -- whole-percent granularity can't distinguish 0% from the sub-1%-of-the-time baseline rate (data.c:1209's "Overall eligible FH%: 0.400%"), which matters once this is compared against the joint table's own thousandths-resolution predictions rather than a hand-picked whole-percent threshold. Parameters: MOVE mv ULONG *puAttempts : optional (may be NULL) -- receives the number of observations the rate is based on, so callers can weight by sample confidence instead of trusting a rate computed from as few as one attempt. Return value: ULONG : fail-high rate in thousandths of a percent (0-100000) **/ { ULONG u = MOVE_TO_FH_INDEX(mv); ULONG n, d; n = g_FailHighs[u].u16FailHighs; d = g_FailHighs[u].u16Attempts; if (puAttempts) *puAttempts = d; if (d == 0) { return(0); } n *= 100000; return(n / d); } void GetMoveFailHighRawCounts(IN MOVE mv, OUT ULONG *puFailHighs, OUT ULONG *puAttempts) /** Routine description: 2026-10-02, one-off diagnostic support: raw (unrounded) FailHighs/ Attempts counts behind GetMoveFailHighPctThousandths, needed to reconstruct HEAD's old (pre-honest-init) equivalent percentage exactly -- (rawFH+1)*100/(rawAttempts+1) -- without the rounding GetMoveFailHighPctThousandths' integer division already introduces. Not meant for any other caller; remove once the HEAD-vs-candidate reduction-rate comparison this supports is done. Parameters: MOVE mv ULONG *puFailHighs ULONG *puAttempts Return value: void **/ { ULONG u = MOVE_TO_FH_INDEX(mv); *puFailHighs = g_FailHighs[u].u16FailHighs; *puAttempts = g_FailHighs[u].u16Attempts; } void CleanupDynamicMoveOrdering(void) /** Routine description: Cleanup dynamic move ordering structs -- basically a noop for now. Parameters: void Return value: void **/ { NOTHING; } void MaintainDynamicMoveOrdering(void) /** Routine description: Perform routine maintenance on dynamic move ordering data by reducing the magnitude of the history counters. Parameters: Return value: void **/ { ULONG x, y; LOCK_DYN; for (x = 0; x <= WHITE_KING; x++) { FOREACH_SQUARE(y) { g_HistoryCounters[x][y] >>= 1; } } for (x = 0; x < CONTINUATION_TABLE_SIZE; x++) { g_ContinuationHistory[x] >>= 1; } UNLOCK_DYN; }