/** 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" // 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]; // 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]; #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 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) /** 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 **/ { ULONG u; memset(g_HistoryCounters, 0, sizeof(g_HistoryCounters)); for (u = 0; u < FH_STATS_TABLE_SIZE; u++) { g_FailHighs[u].uWholeThing = 0x00010001; } } 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; if (ctx->mvKillerEscapes[uPly][1].uMove == 0) { ctx->mvKillerEscapes[uPly][1] = ctx->mvNullmoveRefutations[uPly]; } } 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) { ctx->mvKiller[uPly][1] = ctx->mvNullmoveRefutations[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. 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) /** 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 x, y; ULONG uVal; ULONG *pu; ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); uVal = uDepth / ONE_PLY; ASSERT(uVal >= 0); ASSERT(uVal <= MAX_PLY_PER_SEARCH); uVal += 1; uVal *= uVal; ASSERT(uVal > 0); pu = &(g_HistoryCounters[mv.pMoved][mv.cTo]); LOCK_DYN; *pu += uVal; // // Make sure that the history weight doesn't get large enough to // affect the move flags or else our move ordering algorithm is // screwed. // while (*pu & ~STRIP_OFF_FLAGS) { for (x = 0; x <= WHITE_KING; x++) { FOREACH_SQUARE(y) { g_HistoryCounters[x][y] >>= 4; } } } #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. Parameters: MOVE mv, ULONG uDepth Return value: void **/ { ULONG uVal; ULONG *pu; ASSERT(!IS_CAPTURE_OR_PROMOTION(mv)); uVal = uDepth / ONE_PLY; ASSERT(uVal >= 0); ASSERT(uVal <= MAX_PLY_PER_SEARCH); uVal /= 4; uVal += 1; ASSERT(uVal > 0); pu = &(g_HistoryCounters[mv.pMoved][mv.cTo]); LOCK_DYN; if (*pu >= uVal) { *pu -= uVal; } else { *pu = 0; } _RecordMoveFailure(mv); 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; // // 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); } // // 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); } } } ULONG GetMoveFailHighPercentage(IN MOVE mv, OUT ULONG *puAttempts) /** Routine description: Lookup a move in the fail high percentage history table and return its approximate fail high percentage. Parameters: MOVE mv ULONG *puAttempts : optional (may be NULL) -- receives the number of observations the percentage is based on, so callers can weight by sample confidence instead of trusting a percentage computed from as few as one attempt. Return value: ULONG **/ { 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 *= 100; return(n / d); } 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; } } UNLOCK_DYN; }