Initial checkin for typhoon chess engine.

1 files changed, 971 insertions, 0 deletions

diff --git a/src/hash.c b/src/hash.c
new file mode 100755
index 0000000..4b0cc0a
--- /dev/null
+++ b/src/hash.c
@@ -0,0 +1,971 @@
+/**
+
+Copyright (c) Scott Gasch
+
+Module Name:
+
+    hash.c
+
+Abstract:
+
+    The main transposition table code.  The table is a large range of 
+    memory organized into lines (64 bytes).  Each line contains four
+    entries that are 16 bytes each (index 0..3).
+    
+    After a search, data about the position's score and the depth we
+    searched to determine this score can be stored in the hash table.
+    When information is stored a hash replacement scheme is used to
+    overwrite one of the four entries on a line.
+    
+    Later, before embarking on a deep recursive search, we can check
+    the hash table to see if information relevant to this position 
+    has been stored already (and can be reused).  If so, we can avoid
+    repeating the same search and save time.
+    
+    A hash entry is 16 bytes long and looks like this:
+    
+        typedef struct _HASH_ENTRY
+        {
+            MOVE mv;                 // 0 1 2 3
+            UCHAR uDepth;            // 4
+            UCHAR bvFlags;           // 5 ==> d  i  r  t  | thr up low exact
+            signed short iValue;     // 6 7
+            UINT64 u64Sig;           // 8 9 A B C D E F == 16 bytes
+        } HASH_ENTRY;
+        
+    The mv is the best move in a position.  Even if we do not have a
+    deep enough uDepth recorded to cut off, mv is searched first.
+    uDepth is the depth searched to determine iValue.  iValue is
+    either the exact score or a bound score -- depending on the
+    value of bvFlag's low order 4 bits.  The high order 4 bits
+    in bvFlags holds "dirty" information to aide the hash replacement
+    scheme.  Finally the u64Sig value is used to absolutely identify
+    the position to which the hash entry's information refers.
+
+    When screwing around with the hash code, turn on PERF_COUNTERS and
+    watch the hash hit rate (and usable hash hit rate).  Also here is
+    Fine position #70 which is a great sanity check for hash code:
+    
+    8/k7/3p4/p2P1p2/P2P1P2/8/8/K7/ w - - 0 0 bm 1. Ka1-b1 Ka7-b7 2. Kb1-c1
+
+Author:
+
+    Scott Gasch ([email protected]) 12 Jun 2004
+
+Revision History:
+
+    $Id: hash.c 345 2007-12-02 22:56:42Z scott $
+
+**/
+
+#include "chess.h"
+
+//
+// Hash entries are 16 bytes each and hash lines are 4 entries = 64
+// bytes.  This is done on purpose so that a hash line fits in a cpu
+// cache line.  My Athlons have 64 byte cache lines.  To adjust this
+// for other processors, change the constant below.
+//
+#define CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(x) \
+    ASSERT(IS_VALID_DEPTH(x)); \
+    (x) >>= 4; \
+    ASSERT(((x) & 0xffffff00) == 0);
+
+#define HASH_ENTRY_IS_DIRTY(x) \
+    (((x).bvFlags & 0xF0) != g_cDirty)
+    
+#undef ADJUST_MATE_IN_N
+
+#ifdef MP
+//
+// On MP builds we lock ranges of the hash table in order to mitigate
+// against two searcher threads colliding on the same entry at once.
+// I did not have a free bit to use in the hash entry so I lock every
+// 256th hash table entry at once.
+// 
+#define NUM_HASH_LOCKS 256
+volatile static ULONG g_uHashLocks[NUM_HASH_LOCKS];
+#define HASH_IS_LOCKED(x) ((g_uHashLocks[(x)]) != 0)
+#define LOCK_HASH(x) \
+    AcquireSpinLock(&(g_uHashLocks[(x)])); \
+    ASSERT(HASH_IS_LOCKED(x));
+#define UNLOCK_HASH(x) \
+    ASSERT(HASH_IS_LOCKED(x)); \
+    ReleaseSpinLock(&(g_uHashLocks[(x)]));
+#else // no MP
+#define HASH_IS_LOCKED(x)
+#define LOCK_HASH(x)
+#define UNLOCK_HASH(x)
+#endif
+
+ULONG g_uHashTableSizeEntries = 0;
+ULONG g_uHashTableSizeBytes = 0;
+HASH_ENTRY *g_pHashTable = NULL;
+UCHAR g_cDirty = 0;
+
+void 
+DirtyHashTable(void)
+/**
+
+Routine description:
+
+    The dirty pattern is bitwise ored onto the bvFlags part of a 
+    hash table entry.  Since the low nibble is used to hold flags
+    like upper bound, lower bound, exact score, and threat the 
+    dirty indicator is limited to operating in the upper nibble
+    of bvFlags (giving it a range of 16 values)
+
+Parameters:
+
+    void
+
+Return value:
+
+    void
+
+**/
+{
+    ASSERT((g_cDirty & 0x0F) == 0);
+    g_cDirty += 0x10;
+    ASSERT((g_cDirty & 0x0F) == 0);
+#ifdef TEST
+    if (g_Options.fShouldPost)
+    {
+        Trace("Hash table dirty char: 0x%02x\n", g_cDirty);
+    }
+#endif
+}
+
+
+void 
+CleanupHashSystem(void)
+/**
+
+Routine description:
+
+    Cleanup the hash table by freeing the memory and zeroing some 
+    variables.  This is called before building an opening book in
+    order to free some virtual address space up.
+
+Parameters:
+
+    void
+
+Return value:
+
+    void
+
+**/
+{
+    if (NULL != g_pHashTable)
+    {
+        ASSERT(g_uHashTableSizeBytes > 0);
+        SystemFreeMemory(g_pHashTable);
+        g_pHashTable = NULL;
+        g_uHashTableSizeBytes = 0;
+        g_uHashTableSizeEntries = 0;
+    }
+}
+
+FLAG 
+InitializeHashSystem(void)
+/**
+
+Routine description:
+
+    Initialize the hash system... allocate the table and get everything
+    ready to go.
+
+Parameters:
+
+    void
+
+Return value:
+
+    FLAG
+
+**/
+{
+    ULONG uBytesToAlloc;
+    
+    if (!IS_A_POWER_OF_2(g_Options.uNumHashTableEntries))
+    {
+        return(FALSE);
+    }    
+    g_uHashTableSizeEntries = g_Options.uNumHashTableEntries;
+    if (g_uHashTableSizeEntries != 0)
+    {
+        ASSERT(g_pHashTable == NULL);
+        uBytesToAlloc = (sizeof(HASH_ENTRY) * g_uHashTableSizeEntries);
+        g_pHashTable = SystemAllocateMemory(uBytesToAlloc);
+        g_uHashTableSizeBytes = uBytesToAlloc;
+        ClearHashTable();
+#ifdef MP
+        memset((BYTE *)g_uHashLocks, 0, sizeof(g_uHashLocks));
+#endif
+    }
+    return(TRUE);
+}
+
+
+void 
+ClearHashTable (void) 
+/**
+
+Routine description:
+
+    Zero out the entire hash table.  This function is called when a new
+    position is loaded into the root board.
+
+Parameters:
+
+    void
+
+Return value:
+
+    void
+
+**/
+{
+    if (NULL != g_pHashTable)
+    {
+        g_cDirty = 0;
+        ASSERT(0 != g_uHashTableSizeBytes);
+        ASSERT(0 != g_uHashTableSizeEntries);
+        memset(g_pHashTable, 0, g_uHashTableSizeBytes);
+    }
+}
+
+
+//
+// (g_uHashTableSizeEntries) =>  1000 0000 ... 0000
+// NUM_HASH_ENTRIES_PER_LINE =>  -             0100
+// ------------------------------------------------
+//                               1111 1111 ... 1100 => Start of a hash line
+//
+#define KEY_TO_HASH_LINE_START(x) \
+    ((x) & (g_uHashTableSizeEntries - NUM_HASH_ENTRIES_PER_LINE))
+
+static HASH_ENTRY *
+_SelectHashLine(UINT64 u64Key)
+/**
+
+Routine description:
+
+    On an MP system, this routine locks part of the hash table, the
+    caller should do its thing and then unlock the locked portion of
+    the hash table by calling _DeselectHashLine(u64Key).
+
+Parameters:
+
+    UINT64 u64Key
+
+Return value:
+
+    static HASH_ENTRY
+
+**/
+{
+    ULONG uLow = (ULONG)(u64Key >> 32);
+    ULONG uLine = KEY_TO_HASH_LINE_START(uLow);
+#ifdef MP
+    ULONG uLock = (uLine >> 2) & (NUM_HASH_LOCKS - 1);
+    LOCK_HASH(uLock);
+    ASSERT(IS_A_POWER_OF_2(NUM_HASH_LOCKS));
+#endif
+    ASSERT(g_uHashTableSizeBytes != 0);
+    ASSERT(g_uHashTableSizeEntries != 0);
+    ASSERT(g_pHashTable != NULL);
+    ASSERT(IS_A_POWER_OF_2(g_uHashTableSizeEntries));
+    ASSERT(((g_uHashTableSizeEntries - NUM_HASH_ENTRIES_PER_LINE) &
+            (NUM_HASH_ENTRIES_PER_LINE - 1)) == 0);
+    return(&(g_pHashTable[uLine]));
+}
+
+#ifdef MP
+static void 
+_DeselectHashLine(UINT64 u64Key)
+/**
+
+Routine description:
+
+    This releases the lock taken by _SelectHashLine
+
+Parameters:
+
+    UINT64 u64Key
+
+Return value:
+
+    static void
+
+**/
+{
+    ULONG uLow = (ULONG)(u64Key >> 32);
+    ULONG uLine = KEY_TO_HASH_LINE_START(uLow);
+    ULONG uLock = (uLine >> 2) & (NUM_HASH_LOCKS - 1);
+    
+    ASSERT(IS_A_POWER_OF_2(NUM_HASH_LOCKS));
+    ASSERT(MP);
+    UNLOCK_HASH(uLock);
+}
+#endif
+
+
+static HASH_ENTRY *
+_SelectHashEntry(UINT64 u64Key,
+                 ULONG uDepth,
+                 ULONG uType,
+                 SCORE iValue)
+/**
+
+Routine description:
+
+    This routine takes a lock.  The caller should do its thing and then 
+    release the lock by calling _DeselectHashEntry.
+
+Parameters:
+
+    UINT64 u64Key,
+    ULONG uDepth
+
+Return value:
+
+    static HASH_ENTRY
+
+**/
+{
+    HASH_ENTRY *pEntry;
+    HASH_ENTRY *pStore;
+
+    ASSERT(g_uHashTableSizeBytes != 0);
+    ASSERT(g_uHashTableSizeEntries != 0);
+    ASSERT(g_pHashTable != NULL);
+    ASSERT(IS_A_POWER_OF_2(g_uHashTableSizeEntries));
+
+    //
+    // _SelectHashLine takes a lock on MP builds.
+    //
+    pEntry = _SelectHashLine(u64Key);
+    ASSERT(pEntry != NULL);
+#ifdef DEBUG
+    pStore = NULL;
+#endif
+    
+    //
+    // Note: Hash lines consist of four entries currently:
+    //
+    // 1. The first is a depth-priority hash entry (store here if you
+    // can beat the depth of what's already in there).
+    //
+    // 2. The second is an always-store hash entry (store here if you
+    // can't store in the depth-priority entry).
+    //
+    // 3. and 4. The last two entries are where we bump the data from
+    // the depth- priority table and always-store table when they are
+    // going to be overwritten by newer data.
+    // 
+
+    //
+    // Replace the 0th entry on the line if:
+    // 
+    // ...the new entry has greater depth
+    // ...the current entry is stale (from an old search)
+    //
+    if ((pEntry[0].uDepth <= uDepth) ||
+        HASH_ENTRY_IS_DIRTY(pEntry[0]))
+    {
+        //
+        // Do we need to back up the entry we will overwrite?
+        //
+        if ((pEntry[0].u64Sig != u64Key) ||
+            ((pEntry[0].bvFlags & HASH_FLAG_VALID_BOUNDS) != uType))
+        {
+            pEntry[2] = pEntry[0];
+        }
+        pStore = &(pEntry[0]);
+        goto end;
+    }
+
+    //
+    // We could not replace the depth priority 0th entry; instead,
+    // replace the "always replace" 1st entry on the line unless it
+    // contains mate information and is not stale.
+    //
+    if (((abs(pEntry[1].iValue >= +NMATE)) && 
+         (abs(iValue) < +NMATE)) &&
+        (!HASH_ENTRY_IS_DIRTY(pEntry[1])))
+    {
+        pStore = &(pEntry[3]);
+        goto end;
+    }
+    if ((pEntry[1].u64Sig != u64Key) ||
+        ((pEntry[1].bvFlags & HASH_FLAG_VALID_BOUNDS) != uType))
+    {
+        pEntry[3] = pEntry[1];
+    }
+    pStore = &(pEntry[1]);
+    
+ end:
+    ASSERT(pStore != NULL);
+    return(pStore);
+}
+
+
+#ifdef MP
+static void 
+_DeselectHashEntry(UINT64 u64Key)
+/**
+
+Routine description:
+
+    Releases the lock taken by _SelectHashEntry.
+
+Parameters:
+
+    UINT64 u64Key
+
+Return value:
+
+    static void
+
+**/
+{
+    _DeselectHashLine(u64Key);                // this releases a lock
+}
+#endif
+
+
+void 
+StoreUpperBound(//MOVE mvBest, 
+    POSITION *pos, 
+    SCORE iValue,
+    ULONG uDepth,
+    FLAG fThreat)
+/**
+
+Routine description:
+
+    Store an upper bound in the hash table.
+
+Parameters:
+
+    MOVE mvBest : singular move from the node, if any
+    POSITION *pos,
+    SCORE iValue,
+    ULONG uDepth,
+    FLAG fThreat
+
+Return value:
+
+    void
+
+**/
+{
+    UINT64 u64Key;
+    HASH_ENTRY *pHash;
+    
+    ASSERT(IS_VALID_SCORE(iValue));
+    ASSERT(IS_VALID_DEPTH(uDepth));
+    
+    //
+    // It does not make sense to store hash positions that are worth
+    // at best ~INFINITY.  Every position is and this is a waste of
+    // hash space.  Ignore these.
+    //
+    if (iValue >= +NMATE) return;
+    if (NULL == g_pHashTable) return;
+
+    CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uDepth);
+    u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
+
+    //
+    // _SelectHashEntry takes a lock on MP builds
+    //
+    pHash = _SelectHashEntry(u64Key, uDepth, HASH_FLAG_UPPER, iValue);
+    ASSERT(pHash != NULL);
+    pHash->uDepth = (UCHAR)uDepth;
+    if (pHash->u64Sig != u64Key)
+    {
+        //
+        // Note: don't overwrite a good hash move with "none" if we
+        // are replacing a hash entry for the same position.  Also
+        // if we are klobbering data about the same position save
+        // a memory write to update the (same) sig.
+        //
+        pHash->mv.uMove = 0;
+        pHash->u64Sig = u64Key;
+    }
+    ASSERT((g_cDirty & HASH_FLAG_UPPER) == 0);
+    pHash->bvFlags = g_cDirty | HASH_FLAG_UPPER;
+    ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
+    if (TRUE == fThreat)
+    {
+        ASSERT((pHash->bvFlags & HASH_FLAG_THREAT) == 0);
+        pHash->bvFlags |= HASH_FLAG_THREAT;
+    }
+    
+    if (iValue <= -NMATE)
+    {
+        //
+        // If this is an upper bound near -INFINITY
+        // (i.e. ~-INFINITY at best) convert it into -NMATE at
+        // best (at best mate in N).
+        // 
+        pHash->iValue = -NMATE;
+    }
+    else
+    {
+        //
+        // Otherwise hash the exact value.
+        //
+        ASSERT(iValue > -NMATE);
+        ASSERT(iValue < +NMATE);
+        pHash->iValue = (signed short)iValue;
+    }
+#ifdef MP
+    //
+    // Release the lock on MP builds
+    //
+    _DeselectHashEntry(u64Key);
+#endif
+}
+
+
+void 
+StoreExactScore(MOVE mvBestMove, 
+                POSITION *pos, 
+                SCORE iValue, 
+                ULONG uDepth, 
+                FLAG fThreat, 
+                ULONG uPly)
+/**
+  
+Routine description:
+
+    Store a best move and its exact score in the hash table.
+  
+Parameters:
+
+    MOVE mvBestMove,
+    POSITION *pos,
+    SCORE iValue,
+    ULONG uDepth,
+    FLAG fThreat,
+    ULONG uPly
+
+Return value:
+
+    void
+
+**/
+{
+    HASH_ENTRY *pHash;
+    UINT64 u64Key;
+    
+    ASSERT(IS_VALID_SCORE(iValue));
+    ASSERT(IS_VALID_DEPTH(uDepth));
+    if (NULL == g_pHashTable) return;
+
+    CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uDepth);
+    u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
+
+    //
+    // _SelectHashEntry takes a lock on MP builds.
+    //
+    pHash = _SelectHashEntry(u64Key, uDepth, HASH_FLAG_EXACT, iValue);
+    ASSERT(pHash != NULL);
+        
+    //
+    // Populate the hash entry
+    //
+    pHash->uDepth = (UCHAR)uDepth;
+    ASSERT(mvBestMove.uMove);
+    pHash->mv.uMove = mvBestMove.uMove;
+    ASSERT((g_cDirty & HASH_FLAG_EXACT) == 0);
+    pHash->bvFlags = g_cDirty | HASH_FLAG_EXACT;
+    ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
+    if (TRUE == fThreat)
+    {
+        ASSERT((pHash->bvFlags & HASH_FLAG_THREAT) == 0);
+        pHash->bvFlags |= HASH_FLAG_THREAT;
+    }
+    pHash->u64Sig = u64Key;
+        
+    if (iValue >= +NMATE)
+    {
+#ifdef ADJUST_MATE_IN_N
+        ASSERT((iValue + (int)uPly) < +INFINITY);
+        ASSERT((iValue + (int)uPly) > -INFINITY);
+        pHash->iValue = (signed short)(iValue + (int)uPly);
+#else
+        pHash->bvFlags = g_cDirty | HASH_FLAG_LOWER;
+        ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
+        pHash->iValue = +NMATE;
+#endif
+    }
+    else if (iValue <= -NMATE)
+    {
+#ifdef ADJUST_MATE_IN_N
+        ASSERT((iValue + (int)uPly) < +INFINITY);
+        ASSERT((iValue - (int)uPly) > -INFINITY);
+        pHash->iValue = (signed short)(iValue - (int)uPly);
+#else
+        pHash->bvFlags = g_cDirty | HASH_FLAG_UPPER;
+        ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
+        pHash->iValue = +NMATE;
+#endif
+    }
+    else
+    {
+        ASSERT(iValue > -NMATE);
+        ASSERT(iValue < +NMATE);
+        pHash->iValue = (short signed)iValue;
+    }
+#ifdef MP
+    //
+    // Release the lock on MP builds
+    //
+    _DeselectHashEntry(u64Key);               // Release the lock
+#endif
+}
+
+
+void 
+StoreLowerBound(MOVE mvBestMove, 
+                POSITION *pos, 
+                SCORE iValue,
+                ULONG uDepth, 
+                FLAG fThreat)
+/**
+
+Routine description:
+
+    Store a lower bound score and move in the hash table.
+
+Parameters:
+
+    MOVE mvBestMove,
+    POSITION *pos,
+    SCORE iValue,
+    ULONG uDepth,
+    FLAG fThreat
+
+Return value:
+
+    void
+
+**/
+{
+    HASH_ENTRY *pHash;
+    UINT64 u64Key;
+
+    ASSERT(IS_VALID_SCORE(iValue));
+    ASSERT(IS_VALID_DEPTH(uDepth));
+
+    //
+    // Do not bother to hash this node if it is telling us that the
+    // value of this position is worth at least ~-INFINITY.  This is
+    // useless information and a waste of hash space.
+    // 
+    if (iValue <= -NMATE) return;
+    if (NULL == g_pHashTable) return;
+    
+    CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uDepth);
+    u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
+
+    //
+    // _SelectHashEntry takes a lock on MP builds
+    //
+    pHash = _SelectHashEntry(u64Key, uDepth, HASH_FLAG_LOWER, iValue);
+    ASSERT(pHash != NULL);
+        
+    //
+    // Populate the entry
+    //
+    pHash->uDepth = (UCHAR)uDepth;
+    if ((mvBestMove.uMove) || (pHash->u64Sig != u64Key))
+    {
+        //
+        // Note: only overwrite the existing hash move if either we
+        // have a move (i.e. not null move) or the entry we are
+        // overwriting is for a different position.
+        //
+        pHash->mv.uMove = mvBestMove.uMove;
+    }
+    pHash->u64Sig = u64Key;
+    ASSERT((g_cDirty & HASH_FLAG_LOWER) == 0);
+    pHash->bvFlags = g_cDirty | HASH_FLAG_LOWER;
+    ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
+    pHash->bvFlags |= (HASH_FLAG_THREAT * (fThreat == TRUE));
+    if (iValue < +NMATE)
+    {
+        ASSERT(iValue < +NMATE);
+        ASSERT(iValue > -NMATE);
+        pHash->iValue = (signed short)iValue;
+    }
+    else
+    {
+        //
+        // If the value is greater than mate in N don't store how many
+        // moves N is because this depends on where in the search we
+        // have found this position.  Just say that this position is
+        // worth at least mate in N.
+        // 
+        pHash->iValue = +NMATE;
+    }
+#ifdef MP
+    //
+    // Release the lock on MP builds
+    //
+    _DeselectHashEntry(u64Key);
+#endif
+}
+
+
+MOVE 
+GetPonderMove(POSITION *pos)
+/**
+
+Routine description:
+
+    Get a move to ponder.
+
+Parameters:
+
+    POSITION *pos
+
+Return value:
+
+    MOVE
+
+**/
+{
+    HASH_ENTRY *pHash;
+    ULONG x;
+    UINT64 u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
+    MOVE mv;
+    
+    mv.uMove = 0;
+    if (NULL == g_pHashTable) return(mv);
+
+    //
+    // _SelectHashLine takes a lock on MP builds
+    //
+    pHash = _SelectHashLine(u64Key);
+    for (x = 0;
+         x < NUM_HASH_ENTRIES_PER_LINE;
+         x++)
+    {
+        if (u64Key == pHash->u64Sig)
+        {
+            mv = pHash->mv;
+            if ((pHash->bvFlags & HASH_FLAG_VALID_BOUNDS) == 
+                HASH_FLAG_EXACT)
+            {
+                goto end;
+            }
+        }
+    }
+
+ end:
+#ifdef MP
+    //
+    // Release the lock.
+    //
+    _DeselectHashLine(u64Key);
+#endif
+    return(mv);
+}
+
+
+HASH_ENTRY *
+HashLookup(SEARCHER_THREAD_CONTEXT *ctx, 
+           ULONG uDepth, 
+           ULONG uNextDepth, 
+           SCORE iAlpha, 
+           SCORE iBeta, 
+           FLAG *pfThreat, 
+           FLAG *pfAvoidNull, 
+           MOVE *pHashMove, 
+           SCORE *piScore)
+/**
+
+Routine description:
+
+    Lookup any information we have about the current position in the
+    hash table.  Cutoff if we can.
+
+Parameters:
+
+    SEARCHER_THREAD_CONTEXT *ctx,
+    ULONG uDepth,
+    ULONG uNextDepth,
+    SCORE iAlpha,
+    SCORE iBeta,
+    FLAG *pfThreat,
+    FLAG *pfAvoidNull,
+    MOVE *pHashMove,
+    SCORE *piScore
+
+Return value:
+
+    HASH_ENTRY
+
+**/
+{
+    HASH_ENTRY *pHash;
+    ULONG x;
+    POSITION *pos = &(ctx->sPosition);
+    UINT64 u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
+    ULONG uMoveScore = 0;
+    ULONG uThisScore;
+    
+#define COMPUTE_MOVE_SCORE(mv, depth) \
+    ((depth) * 8 + PIECE_VALUE_OVER_100((mv).pCaptured) + 1)
+
+    ASSERT(IS_VALID_DEPTH(uDepth));
+    ASSERT(IS_VALID_DEPTH(uNextDepth));
+    ASSERT(uNextDepth <= uDepth);
+    ASSERT(IS_VALID_SCORE(iAlpha));
+    ASSERT(IS_VALID_SCORE(iBeta));
+    ASSERT(iAlpha < iBeta);
+    ASSERT(pHashMove->uMove == 0);
+    ASSERT(NULL != g_pHashTable);
+    INC(ctx->sCounters.hash.u64Probes);
+    
+    //
+    // These are out parameters for the caller, initialize them
+    // saying we don't know anything.
+    //
+    *pfAvoidNull = FALSE;
+    *pfThreat = FALSE;
+    
+    CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uDepth);
+    CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uNextDepth);
+
+    //
+    // _SelectHashLine takes a lock on MP builds.
+    //
+    pHash = _SelectHashLine(u64Key);
+    for (x = 0;
+         x < NUM_HASH_ENTRIES_PER_LINE;
+         x++)
+    {
+        if (u64Key == pHash->u64Sig)
+        {
+            //
+            // This entry hit, make it "clean" so it is harder to replace
+            // later on.
+            // 
+            pHash->bvFlags &= 0x0F;
+            ASSERT((g_cDirty & 0x0F) == 0);
+            pHash->bvFlags |= g_cDirty;
+            ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
+            
+            //
+            // Parse the matching entry
+            //
+            *pfThreat |= ((pHash->bvFlags & HASH_FLAG_THREAT) > 0);
+            
+            //
+            // If we have an exact match and sufficient depth to
+            // satisfy the depth to which we will later search after a
+            // nullmove, see if the known value of this node is less
+            // than beta.  If so, doing nothing in this position will
+            // probably not be better than doing something therefore
+            // its not wise to perform the nullmove search.  It's just
+            // a waste of nodes and time.
+            // 
+            if ((pHash->uDepth >= uNextDepth) &&
+                ((pHash->bvFlags & HASH_FLAG_UPPER) ||
+                 (pHash->bvFlags & HASH_FLAG_EXACT)) &&
+                (pHash->iValue < iBeta))
+            {
+                *pfAvoidNull = TRUE;
+            }
+
+            // Because we can encounter several moves while looking for
+            // a hash cutoff, have a semantic about which one we return
+            // to the search.
+            INC(ctx->sCounters.hash.u64OverallHits);
+            if (pHash->mv.uMove) {
+                uThisScore = COMPUTE_MOVE_SCORE(pHash->mv, uDepth);
+                ASSERT(uThisScore != 0);
+                if (uThisScore > uMoveScore) {
+                    uMoveScore = uThisScore;
+                    *pHashMove = pHash->mv;
+                    ASSERT(SanityCheckMove(pos, pHash->mv));
+                }
+            }
+            
+            //
+            // We have a hit, but is it useful?
+            //
+            if (pHash->uDepth >= uDepth)
+            {
+                switch (pHash->bvFlags & HASH_FLAG_VALID_BOUNDS)
+                {
+                    case HASH_FLAG_EXACT:
+                        *piScore = pHash->iValue;
+                        INC(ctx->sCounters.hash.u64UsefulHits);
+                        INC(ctx->sCounters.hash.u64ExactScoreHits);
+#ifdef ADJUST_MATE_IN_N
+                        //
+                        // Readjust mate in N scores.
+                        //
+                        if (pHash->iValue >= +NMATE)
+                        {
+                            *piScore -= (int)uPly;
+                        }
+                        else if (pHash->iValue <= -NMATE)
+                        {
+                            *piScore += (int)uPly;
+                        }
+#endif
+                        ASSERT(IS_VALID_SCORE(*piScore));
+                        goto end;
+                        break;
+                        
+                    case HASH_FLAG_LOWER:
+                        if (pHash->iValue >= iBeta)
+                        {
+                            INC(ctx->sCounters.hash.u64UsefulHits);
+                            INC(ctx->sCounters.hash.u64LowerBoundHits);
+                            *piScore = pHash->iValue;
+                            ASSERT(IS_VALID_SCORE(*piScore));
+                            goto end;
+                        }
+                        break;
+                    
+                    case HASH_FLAG_UPPER:
+                        if (pHash->iValue <= iAlpha)
+                        {
+                            INC(ctx->sCounters.hash.u64UsefulHits);
+                            INC(ctx->sCounters.hash.u64UpperBoundHits);
+                            *piScore = pHash->iValue;
+                            ASSERT(IS_VALID_SCORE(*piScore));
+                            goto end;
+                        }
+                        break;
+#ifdef DEBUG
+                    default:
+                        ASSERT(FALSE);
+                        break;
+#endif
+                }
+            }
+        }
+        pHash++;
+    }
+    pHash = NULL;
+    
+ end:
+#ifdef MP
+    //
+    // Release the lock.
+    //
+    _DeselectHashLine(u64Key);
+#endif
+    return(pHash);
+}