Initial checkin for typhoon chess engine.

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;
+}