path: root/src/hash.c

/**

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.

    2026-10-05: LOCKLESS HASHING (Hyatt/Crafty scheme -- see Crafty's
    own hash.c for the reference this was checked against). The first
    8 bytes above (mv/uDepth/bvFlags/iValue) are addressable as one
    aligned UINT64 via HASH_ENTRY's u64Data union member. u64Sig does
    NOT hold the plain position key anymore -- it holds (realKey ^
    u64Data). Every store writes u64Data, THEN u64Sig = key ^ u64Data,
    as two independent plain 64-bit stores (naturally atomic on x86-64
    for aligned accesses, no lock needed). Every probe reads both
    words into LOCAL variables first, then verifies (storedSig ^
    storedData) == realKey before trusting anything -- never re-reads
    the live table after that check. A concurrent writer racing a
    reader can only ever produce a self-inconsistent (word,sig) pair
    that fails this check (treated as an ordinary miss), UNLESS the
    two entries' data words happen to be bit-identical, in which case
    the "corrupted" match is harmless by construction (both entries
    agree on the data anyway). This is what removes the old
    AcquireSpinLock/ReleaseSpinLock pair from every single probe and
    store, previously taken 18-27M+ times per search (measured: the
    old LockCompareExchange cost already showed up at 0.51% self-time
    in a `bench` gprof profile) -- see CLAUDE.md for the fuller
    rationale and the test plan this shipped with.

    IMPORTANT: because of this, every write to this struct's data
    fields MUST go through the full "compute locally, then write
    u64Data, then write u64Sig = key ^ u64Data" sequence below -- a
    bare `pHash->bvFlags = ...` or similar single-field write would
    silently desync u64Sig from u64Data and make the entry fail to
    verify on every subsequent probe (a silent, permanent false-miss
    for that slot, not a crash -- easy to reintroduce by accident).

    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) \
    do { \
        ASSERT(IS_VALID_DEPTH(x)); \
        (x) >>= 4; \
        ASSERT(((x) & 0xffffff00) == 0); \
    } while (0)

#define HASH_ENTRY_IS_DIRTY(x) \
    (((x).bvFlags & 0xF0) != g_cDirty)

#undef ADJUST_MATE_IN_N

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();
    }
    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:

    Return a pointer to the hash line (4 entries) this key maps to.
    Lockless (see this file's module comment) -- no lock to take or
    release, nothing for a caller to pair this with anymore.

Parameters:

    UINT64 u64Key

Return value:

    static HASH_ENTRY

**/
{
    ULONG uLow = (ULONG)(u64Key >> 32);
    ULONG uLine = KEY_TO_HASH_LINE_START(uLow);
    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]));
}


// Lockless-hash key check (see this file's module comment): a plain
// u64Sig == u64Key compare no longer means anything, since u64Sig
// holds (realKey ^ u64Data). This un-corrupts it first. Used only for
// the replacement-policy judgment below (which entry looks like it
// already holds this same position) -- a wrong answer from a race
// here just means a slightly suboptimal replacement choice, never a
// correctness issue (the entry actually written below is always
// self-consistent regardless).
#define ENTRY_MATCHES_KEY(pEntry, uKey) \
    (((pEntry)->u64Sig ^ (pEntry)->u64Data) == (uKey))

static HASH_ENTRY *
_SelectHashEntry(UINT64 u64Key,
                 ULONG uDepth,
                 ULONG uType,
                 SCORE iValue)
/**

Routine description:

    Lockless (see this file's module comment) -- just picks which of
    the line's four entries to store into. Nothing to release
    afterward anymore.

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));

    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? Plain
        // whole-entry copy (both words) -- copying a possibly-racy
        // snapshot of entry 0 into entry 2 is fine either way, same
        // self-consistency argument as everywhere else in this file.
        //
        if ((FALSE == ENTRY_MATCHES_KEY(&pEntry[0], u64Key)) ||
            ((pEntry[0].bvFlags & HASH_FLAG_VALID_BOUNDS) != uType))
        {
            pEntry[2].u64Data = pEntry[0].u64Data;
            pEntry[2].u64Sig  = pEntry[0].u64Sig;
        }
        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 ((FALSE == ENTRY_MATCHES_KEY(&pEntry[1], u64Key)) ||
        ((pEntry[1].bvFlags & HASH_FLAG_VALID_BOUNDS) != uType))
    {
        pEntry[3].u64Data = pEntry[1].u64Data;
        pEntry[3].u64Sig  = pEntry[1].u64Sig;
    }
    pStore = &(pEntry[1]);

 end:
    ASSERT(pStore != NULL);
    return(pStore);
}


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_SCORE.  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;

    pHash = _SelectHashEntry(u64Key, uDepth, HASH_FLAG_UPPER, iValue);
    ASSERT(pHash != NULL);

    //
    // Lockless hash (see module comment): compute the whole new entry
    // locally first, then write u64Data and u64Sig = key ^ u64Data as
    // the last two steps -- never a bare single-field write to *pHash.
    //
    {
        HASH_ENTRY sNew;

        sNew.uDepth = (UCHAR)uDepth;

        //
        // Note: don't overwrite a good hash move with "none" if we
        // are replacing a hash entry for the same position.
        //
        sNew.mv.uMove = (TRUE == ENTRY_MATCHES_KEY(pHash, u64Key)) ?
            pHash->mv.uMove : 0;

        ASSERT((g_cDirty & HASH_FLAG_UPPER) == 0);
        sNew.bvFlags = g_cDirty | HASH_FLAG_UPPER |
            (HASH_FLAG_THREAT * (TRUE == fThreat));
        ASSERT((sNew.bvFlags & 0xF0) == g_cDirty);

        if (iValue <= -NMATE)
        {
            //
            // If this is an upper bound near -INFINITY_SCORE
            // (i.e. ~-INFINITY_SCORE at best) convert it into -NMATE
            // at best (at best mate in N).
            //
            sNew.iValue = -NMATE;
        }
        else
        {
            //
            // Otherwise hash the exact value.
            //
            ASSERT(iValue > -NMATE);
            ASSERT(iValue < +NMATE);
            sNew.iValue = (signed short)iValue;
        }

        pHash->u64Data = sNew.u64Data;
        pHash->u64Sig = u64Key ^ sNew.u64Data;
    }
}


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;

    pHash = _SelectHashEntry(u64Key, uDepth, HASH_FLAG_EXACT, iValue);
    ASSERT(pHash != NULL);

    //
    // Lockless hash (see module comment): compute the whole new entry
    // locally first, then write u64Data and u64Sig = key ^ u64Data as
    // the last two steps -- never a bare single-field write to *pHash.
    //
    {
        HASH_ENTRY sNew;

        sNew.uDepth = (UCHAR)uDepth;
        ASSERT(mvBestMove.uMove);
        sNew.mv.uMove = mvBestMove.uMove;
        ASSERT((g_cDirty & HASH_FLAG_EXACT) == 0);
        sNew.bvFlags = g_cDirty | HASH_FLAG_EXACT |
            (HASH_FLAG_THREAT * (TRUE == fThreat));

        if (iValue >= +NMATE)
        {
#ifdef ADJUST_MATE_IN_N
            ASSERT((iValue + (int)uPly) < +INFINITY_SCORE);
            ASSERT((iValue + (int)uPly) > -INFINITY_SCORE);
            sNew.iValue = (signed short)(iValue + (int)uPly);
#else
            sNew.bvFlags = g_cDirty | HASH_FLAG_LOWER |
                (HASH_FLAG_THREAT * (TRUE == fThreat));
            sNew.iValue = +NMATE;
#endif
        }
        else if (iValue <= -NMATE)
        {
#ifdef ADJUST_MATE_IN_N
            ASSERT((iValue + (int)uPly) < +INFINITY_SCORE);
            ASSERT((iValue - (int)uPly) > -INFINITY_SCORE);
            sNew.iValue = (signed short)(iValue - (int)uPly);
#else
            sNew.bvFlags = g_cDirty | HASH_FLAG_UPPER |
                (HASH_FLAG_THREAT * (TRUE == fThreat));
            sNew.iValue = +NMATE;
#endif
        }
        else
        {
            ASSERT(iValue > -NMATE);
            ASSERT(iValue < +NMATE);
            sNew.iValue = (short signed)iValue;
        }
        ASSERT((sNew.bvFlags & 0xF0) == g_cDirty);

        pHash->u64Data = sNew.u64Data;
        pHash->u64Sig = u64Key ^ sNew.u64Data;
    }
}


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_SCORE.  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;

    pHash = _SelectHashEntry(u64Key, uDepth, HASH_FLAG_LOWER, iValue);
    ASSERT(pHash != NULL);

    //
    // Lockless hash (see module comment): compute the whole new entry
    // locally first, then write u64Data and u64Sig = key ^ u64Data as
    // the last two steps -- never a bare single-field write to *pHash.
    //
    {
        HASH_ENTRY sNew;

        sNew.uDepth = (UCHAR)uDepth;

        //
        // 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.
        //
        sNew.mv.uMove = ((0 != mvBestMove.uMove) ||
                         (FALSE == ENTRY_MATCHES_KEY(pHash, u64Key))) ?
            mvBestMove.uMove : pHash->mv.uMove;

        ASSERT((g_cDirty & HASH_FLAG_LOWER) == 0);
        sNew.bvFlags = g_cDirty | HASH_FLAG_LOWER |
            (HASH_FLAG_THREAT * (fThreat == TRUE));
        ASSERT((sNew.bvFlags & 0xF0) == g_cDirty);

        if (iValue < +NMATE)
        {
            ASSERT(iValue < +NMATE);
            ASSERT(iValue > -NMATE);
            sNew.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.
            //
            sNew.iValue = +NMATE;
        }

        pHash->u64Data = sNew.u64Data;
        pHash->u64Sig = u64Key ^ sNew.u64Data;
    }
}


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);

    pHash = _SelectHashLine(u64Key);
    for (x = 0;
         x < NUM_HASH_ENTRIES_PER_LINE;
         x++)
    {
        //
        // Lockless hash (see module comment): snapshot both words into
        // a local copy and verify via XOR before trusting anything --
        // never re-read the live entry after the check.
        //
        HASH_ENTRY sLocal;
        sLocal.u64Data = pHash->u64Data;
        sLocal.u64Sig  = pHash->u64Sig;
        if (u64Key == (sLocal.u64Sig ^ sLocal.u64Data))
        {
            mv = sLocal.mv;
            if ((sLocal.bvFlags & HASH_FLAG_VALID_BOUNDS) ==
                HASH_FLAG_EXACT)
            {
                goto end;
            }
        }
        pHash++;
    }

 end:
    return(mv);
}


FLAG
HashLookup(SEARCHER_THREAD_CONTEXT *ctx,
           ULONG uDepth,
           ULONG uNextDepth,
           SCORE iAlpha,
           SCORE iBeta,
           FLAG *pfThreat,
           FLAG *pfAvoidNull,
           MOVE *pHashMove,
           SCORE *piScore,
           HASH_ENTRY *pOut)
/**

Routine description:

    Lookup any information we have about the current position in the
    hash table.  Cutoff if we can.

    Lockless hash (see this file's module comment): returns TRUE only
    for a genuinely usable bound (old contract: non-NULL return), and
    on TRUE, *pOut holds a validated LOCAL copy of the matching entry
    -- the caller must never go back and read the live table entry
    itself (there's no pointer to it anymore, by design: a pointer
    into the live table would let a caller's later read race a
    concurrent writer with no XOR-verification of its own). pfThreat,
    pfAvoidNull and pHashMove are still set as side effects on a MISS
    too, exactly as before -- callers already rely on that (e.g.
    search.c's move-ordering hash-move hint survives a cutoff miss).

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx,
    ULONG uDepth,
    ULONG uNextDepth,
    SCORE iAlpha,
    SCORE iBeta,
    FLAG *pfThreat,
    FLAG *pfAvoidNull,
    MOVE *pHashMove,
    SCORE *piScore,
    HASH_ENTRY *pOut : out, only valid when this function returns TRUE

Return value:

    FLAG : TRUE if a usable bound was found (see *piScore), else FALSE

**/
{
    HASH_ENTRY *pHash;
    ULONG x;
    POSITION *pos = &(ctx->sPosition);
    UINT64 u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
    ULONG uMoveScore = 0;
    ULONG uThisScore;
    FLAG fFoundUsableBound = FALSE;

#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);
    // 2026-09-17: NULL here is not a bug -- it's the legitimate "--hash
    // none" state (InitializeHashSystem deliberately skips allocation
    // when uNumHashTableEntries == 0, since IS_A_POWER_OF_2(0) is true
    // by that macro's bitwise definition). This ASSERT used to fire
    // unconditionally, making "--hash none" crash on the very first
    // probe despite being a supported init-time configuration.
    if (NULL == g_pHashTable)
    {
        return(FALSE);
    }
    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);

    pHash = _SelectHashLine(u64Key);
    for (x = 0;
         x < NUM_HASH_ENTRIES_PER_LINE;
         x++)
    {
        //
        // Lockless hash (see module comment): snapshot both words into
        // a local copy and verify via XOR before trusting anything --
        // every read below this point uses sLocal, never pHash, until
        // the "clean the dirty bits" write-back, which re-derives
        // u64Sig from the (locally mutated) data word rather than
        // touching bvFlags alone.
        //
        HASH_ENTRY sLocal;
        sLocal.u64Data = pHash->u64Data;
        sLocal.u64Sig  = pHash->u64Sig;
        if (u64Key == (sLocal.u64Sig ^ sLocal.u64Data))
        {
            //
            // This entry hit, make it "clean" so it is harder to
            // replace later on. Mutate the local copy, then write
            // BOTH words back -- a bare pHash->bvFlags store here
            // would desync u64Sig from u64Data.
            //
            sLocal.bvFlags &= 0x0F;
            ASSERT((g_cDirty & 0x0F) == 0);
            sLocal.bvFlags |= g_cDirty;
            ASSERT((sLocal.bvFlags & 0xF0) == g_cDirty);
            pHash->u64Data = sLocal.u64Data;
            pHash->u64Sig  = u64Key ^ sLocal.u64Data;

            //
            // Parse the matching entry
            //
            *pfThreat |= ((sLocal.bvFlags & HASH_FLAG_THREAT) > 0);

            // See if we can advise against performing a nullmove search.
            if ((sLocal.uDepth >= uNextDepth) &&
                ((sLocal.bvFlags & HASH_FLAG_UPPER) ||
                 (sLocal.bvFlags & HASH_FLAG_EXACT)) &&
                (sLocal.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 (sLocal.mv.uMove) {
                uThisScore = COMPUTE_MOVE_SCORE(sLocal.mv, sLocal.uDepth);
                ASSERT(uThisScore != 0);
                if (uThisScore > uMoveScore) {
                    uMoveScore = uThisScore;
                    *pHashMove = sLocal.mv;
                    ASSERT(SanityCheckMove(pos, sLocal.mv));
                }
            }

            //
            // We have a hit, but is it useful?
            //
            if (sLocal.uDepth >= uDepth)
            {
                switch (sLocal.bvFlags & HASH_FLAG_VALID_BOUNDS)
                {
                    case HASH_FLAG_EXACT:
                        *piScore = sLocal.iValue;
                        INC(ctx->sCounters.hash.u64UsefulHits);
                        INC(ctx->sCounters.hash.u64ExactScoreHits);
#ifdef ADJUST_MATE_IN_N
                        //
                        // Readjust mate in N scores.
                        //
                        if (sLocal.iValue >= +NMATE)
                        {
                            *piScore -= (int)uPly;
                        }
                        else if (sLocal.iValue <= -NMATE)
                        {
                            *piScore += (int)uPly;
                        }
#endif
                        ASSERT(IS_VALID_SCORE(*piScore));
                        fFoundUsableBound = TRUE;
                        *pOut = sLocal;
                        goto end;
                        break;

                    case HASH_FLAG_LOWER:
                        if (sLocal.iValue >= iBeta)
                        {
                            INC(ctx->sCounters.hash.u64UsefulHits);
                            INC(ctx->sCounters.hash.u64LowerBoundHits);
                            *piScore = sLocal.iValue;
                            ASSERT(IS_VALID_SCORE(*piScore));
                            fFoundUsableBound = TRUE;
                            *pOut = sLocal;
                            goto end;
                        }
                        break;

                    case HASH_FLAG_UPPER:
                        if (sLocal.iValue <= iAlpha)
                        {
                            INC(ctx->sCounters.hash.u64UsefulHits);
                            INC(ctx->sCounters.hash.u64UpperBoundHits);
                            *piScore = sLocal.iValue;
                            ASSERT(IS_VALID_SCORE(*piScore));
                            fFoundUsableBound = TRUE;
                            *pOut = sLocal;
                            goto end;
                        }
                        break;
#ifdef DEBUG
                    default:
                        ASSERT(FALSE);
                        break;
#endif
                }
            }
        }
        pHash++;
    }

 end:
    return(fFoundUsableBound);
}