summaryrefslogtreecommitdiff
path: root/src/dynamic.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/dynamic.c')
-rwxr-xr-xsrc/dynamic.c515
1 files changed, 515 insertions, 0 deletions
diff --git a/src/dynamic.c b/src/dynamic.c
new file mode 100755
index 0000000..1c1e741
--- /dev/null
+++ b/src/dynamic.c
@@ -0,0 +1,515 @@
+/**
+
+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 ([email protected]) 24 Jun 2004
+
+Revision History:
+
+ $Id: dynamic.c 345 2007-12-02 22:56:42Z scott $
+
+**/
+
+#include "chess.h"
+
+ULONG g_HistoryCounters[14][128];
+#define FH_STATS_TABLE_SIZE (0x20000)
+
+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
+
+
+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_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_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;
+ }
+ 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
+_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);
+ _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)
+/**
+
+Routine description:
+
+ Lookup a move in the fail high percentage history table and return
+ its approximate fail high percentage.
+
+Parameters:
+
+ MOVE mv
+
+Return value:
+
+ ULONG
+
+**/
+{
+ ULONG u = MOVE_TO_INDEX(mv);
+ ULONG n, d;
+
+ n = g_FailHighs[u].u16FailHighs;
+ d = g_FailHighs[u].u16Attempts;
+ 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;
+}
generated by cgit v1.3 (git 2.53.0) at 2026-07-17 13:59:56 +0000