Lockless main hash table (Hyatt/Crafty scheme)

Replaces the sharded-spinlock protection around every main-hash probe
and store with the classic lockless-hashing technique: HASH_ENTRY's
existing 8-byte data word (mv/uDepth/bvFlags/iValue, now addressable
as u64Data via an anonymous union) and its 8-byte u64Sig are written
as two independent plain 64-bit stores -- u64Data first, then
u64Sig = realKey ^ u64Data -- instead of under a lock. Every probe
reads both words into a local snapshot and verifies
(storedSig ^ storedData) == realKey before trusting anything; a
concurrent writer racing a reader can only ever produce a
self-inconsistent pair that fails this check (an ordinary miss), not
corruption, except in the one documented, harmless case where the two
racing entries' data words happen to be bit-identical.

LockCompareExchange (the old spinlock's cost) was already showing up
at 0.51% self-time in a `bench` profile -- real, measured overhead on
a path hit roughly once per searched node, now removed.

HashLookup's contract changes from "return a pointer into the live
table, or NULL" to "return TRUE/FALSE, with *pOut holding a validated
local copy on TRUE" -- callers must never read back through a pointer
into the live table after this function returns, since there's no
longer a lock serializing that against a concurrent writer. The one
real caller (search.c) and the DEBUG-only VERIFY_HASH_HIT diagnostic
are updated accordingly.

testhash.c: AnalyzeFullHashTable's duplicate-entry check used to
compare two entries' raw u64Sig directly, which no longer means "same
position" now that u64Sig depends on each entry's own data word --
fixed to un-corrupt both sides first. Adds TestLocklessHashAlgebra, a
pure algebra test (no concurrency) verifying the XOR round-trip and
torn-write self-detection property over 200k random trials, wired
into the TEST=1 startup self-test suite.

Verified: TestLocklessHashAlgebra passes; single-threaded runs of the
locked and lockless binaries produce identical node counts and solve
scores across all three curated suites (ecm_ringers/confident_quick/
hard_quick); several minutes of real contention (tiny 4MB hash table,
12 threads at ~1200% CPU on a Ryzen 9 3900X, plus a 4-core run
locally) produced zero crashes/assertions/corruption on either
machine.

Co-Authored-By: Claude Sonnet 5 <[email protected]>

5 files changed, 443 insertions, 312 deletions

diff --git a/src/chess.h b/src/chess.h
index 7125cc7..d637905 100755
--- a/src/chess.h
+++ b/src/chess.h
@@ -3912,11 +3912,27 @@ TestWhoAttacksSquareMagic(void);
 
 typedef struct _HASH_ENTRY
 {
-    MOVE mv;                         // 0 1 2 3
-    UCHAR uDepth;                    // 4
-    UCHAR bvFlags;                   // 5 ==> d  d  d  d | thr up low exact
-    signed short iValue;             // 6 7
-    UINT64 u64Sig;                   // 8 9 A B C D E F == 16 bytes
+    // Lockless-hash data word (Hyatt/Crafty scheme, see hash.c's
+    // module comment): mv/uDepth/bvFlags/iValue pack into one aligned
+    // UINT64 (u64Data) so hash.c can read/write them as a single word
+    // alongside u64Sig, which stores (realKey ^ u64Data) rather than
+    // the plain key. Every existing pHash->mv/uDepth/bvFlags/iValue
+    // access keeps compiling unchanged via this anonymous union/struct
+    // (same idiom MOVE itself already uses above).
+    union
+    {
+        struct
+        {
+            MOVE mv;                     // 0 1 2 3
+            UCHAR uDepth;                 // 4
+            UCHAR bvFlags;                // 5 ==> d  d  d  d | thr up low exact
+            signed short iValue;         // 6 7
+        };
+        UINT64 u64Data;                  // 0 1 2 3 4 5 6 7, same 8 bytes
+    };
+    UINT64 u64Sig;                   // 8 9 A B C D E F == 16 bytes total;
+                                      // holds (realKey ^ u64Data), not the
+                                      // plain key -- see hash.c.
 } HASH_ENTRY;
 
 FLAG
@@ -3952,7 +3968,7 @@ StoreUpperBound(//MOVE mvBestMove,
            ULONG uDepth,
            FLAG fThreat);
 
-HASH_ENTRY *
+FLAG
 HashLookup(SEARCHER_THREAD_CONTEXT *ctx,
            ULONG uDepth,
            ULONG uNextDepth,
@@ -3961,7 +3977,8 @@ HashLookup(SEARCHER_THREAD_CONTEXT *ctx,
            FLAG *pfThreat,
            FLAG *pfAvoidNull,
            MOVE *pHashMove,
-           SCORE *piScore);
+           SCORE *piScore,
+           HASH_ENTRY *pOut);
 
 COOR
 CheckHashForDangerSquare(POSITION *pos);
@@ -3979,6 +3996,9 @@ extern HASH_ENTRY *g_pHashTable;
 void
 AnalyzeFullHashTable(void);
 
+FLAG
+TestLocklessHashAlgebra(void);
+
 //
 // dynamic.c -- enprise/trapped piece hints
 //
diff --git a/src/hash.c b/src/hash.c
index d5d9a03..887b6a1 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -23,7 +23,7 @@ Abstract:
     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
@@ -32,15 +32,44 @@ Abstract:
             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.
+    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
@@ -78,28 +107,6 @@ Revision History:
     
 #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;
@@ -202,9 +209,6 @@ Return value:
         g_pHashTable = SystemAllocateMemory(uBytesToAlloc);
         g_uHashTableSizeBytes = uBytesToAlloc;
         ClearHashTable();
-#ifdef MP
-        memset((BYTE *)g_uHashLocks, 0, sizeof(g_uHashLocks));
-#endif
     }
     return(TRUE);
 }
@@ -254,9 +258,9 @@ _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).
+    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:
 
@@ -270,11 +274,6 @@ Return value:
 {
     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);
@@ -284,35 +283,17 @@ Return value:
     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
 
+// 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,
@@ -323,8 +304,9 @@ _SelectHashEntry(UINT64 u64Key,
 
 Routine description:
 
-    This routine takes a lock.  The caller should do its thing and then 
-    release the lock by calling _DeselectHashEntry.
+    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:
 
@@ -345,15 +327,12 @@ Return value:
     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:
     //
@@ -366,11 +345,11 @@ Return value:
     // 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)
     //
@@ -378,12 +357,16 @@ Return value:
         HASH_ENTRY_IS_DIRTY(pEntry[0]))
     {
         //
-        // Do we need to back up the entry we will overwrite?
+        // 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 ((pEntry[0].u64Sig != u64Key) ||
+        if ((FALSE == ENTRY_MATCHES_KEY(&pEntry[0], u64Key)) ||
             ((pEntry[0].bvFlags & HASH_FLAG_VALID_BOUNDS) != uType))
         {
-            pEntry[2] = pEntry[0];
+            pEntry[2].u64Data = pEntry[0].u64Data;
+            pEntry[2].u64Sig  = pEntry[0].u64Sig;
         }
         pStore = &(pEntry[0]);
         goto end;
@@ -401,10 +384,11 @@ Return value:
         pStore = &(pEntry[3]);
         goto end;
     }
-    if ((pEntry[1].u64Sig != u64Key) ||
+    if ((FALSE == ENTRY_MATCHES_KEY(&pEntry[1], u64Key)) ||
         ((pEntry[1].bvFlags & HASH_FLAG_VALID_BOUNDS) != uType))
     {
-        pEntry[3] = pEntry[1];
+        pEntry[3].u64Data = pEntry[1].u64Data;
+        pEntry[3].u64Sig  = pEntry[1].u64Sig;
     }
     pStore = &(pEntry[1]);
 
@@ -414,30 +398,6 @@ Return value:
 }
 
 
-#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, 
@@ -481,56 +441,53 @@ Return value:
     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)
+
+    //
+    // 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.  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)
-    {
+        // are replacing a hash entry for the same position.
         //
-        // 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).
-        // 
-        pHash->iValue = -NMATE;
-    }
-    else
-    {
-        //
-        // Otherwise hash the exact value.
-        //
-        ASSERT(iValue > -NMATE);
-        ASSERT(iValue < +NMATE);
-        pHash->iValue = (signed short)iValue;
+        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;
     }
-#ifdef MP
-    //
-    // Release the lock on MP builds
-    //
-    _DeselectHashEntry(u64Key);
-#endif
 }
 
 
@@ -572,64 +529,59 @@ Return value:
     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
+    // 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.
     //
-    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)
     {
+        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);
-        pHash->iValue = (signed short)(iValue + (int)uPly);
+            ASSERT((iValue + (int)uPly) < +INFINITY_SCORE);
+            ASSERT((iValue + (int)uPly) > -INFINITY_SCORE);
+            sNew.iValue = (signed short)(iValue + (int)uPly);
 #else
-        pHash->bvFlags = g_cDirty | HASH_FLAG_LOWER;
-        ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
-        pHash->iValue = +NMATE;
+            sNew.bvFlags = g_cDirty | HASH_FLAG_LOWER |
+                (HASH_FLAG_THREAT * (TRUE == fThreat));
+            sNew.iValue = +NMATE;
 #endif
-    }
-    else if (iValue <= -NMATE)
-    {
+        }
+        else if (iValue <= -NMATE)
+        {
 #ifdef ADJUST_MATE_IN_N
-        ASSERT((iValue + (int)uPly) < +INFINITY_SCORE);
-        ASSERT((iValue - (int)uPly) > -INFINITY_SCORE);
-        pHash->iValue = (signed short)(iValue - (int)uPly);
+            ASSERT((iValue + (int)uPly) < +INFINITY_SCORE);
+            ASSERT((iValue - (int)uPly) > -INFINITY_SCORE);
+            sNew.iValue = (signed short)(iValue - (int)uPly);
 #else
-        pHash->bvFlags = g_cDirty | HASH_FLAG_UPPER;
-        ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
-        pHash->iValue = +NMATE;
+            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;
     }
-    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
 }
 
 
@@ -676,52 +628,53 @@ Return value:
     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
+    // 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.
     //
-    pHash->uDepth = (UCHAR)uDepth;
-    if ((mvBestMove.uMove) || (pHash->u64Sig != u64Key))
     {
+        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.
         //
-        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;
+        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;
     }
-#ifdef MP
-    //
-    // Release the lock on MP builds
-    //
-    _DeselectHashEntry(u64Key);
-#endif
 }
 
 
@@ -751,18 +704,23 @@ Return value:
     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)
+        //
+        // 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 = pHash->mv;
-            if ((pHash->bvFlags & HASH_FLAG_VALID_BOUNDS) == 
+            mv = sLocal.mv;
+            if ((sLocal.bvFlags & HASH_FLAG_VALID_BOUNDS) ==
                 HASH_FLAG_EXACT)
             {
                 goto end;
@@ -772,26 +730,21 @@ Return value:
     }
 
  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)
+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:
@@ -799,6 +752,17 @@ 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,
@@ -809,11 +773,12 @@ Parameters:
     FLAG *pfThreat,
     FLAG *pfAvoidNull,
     MOVE *pHashMove,
-    SCORE *piScore
+    SCORE *piScore,
+    HASH_ENTRY *pOut : out, only valid when this function returns TRUE
 
 Return value:
 
-    HASH_ENTRY
+    FLAG : TRUE if a usable bound was found (see *piScore), else FALSE
 
 **/
 {
@@ -823,6 +788,7 @@ Return value:
     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)
@@ -842,44 +808,56 @@ Return value:
     // probe despite being a supported init-time configuration.
     if (NULL == g_pHashTable)
     {
-        return(NULL);
+        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);
 
-    //
-    // _SelectHashLine takes a lock on MP builds.
-    //
     pHash = _SelectHashLine(u64Key);
     for (x = 0;
          x < NUM_HASH_ENTRIES_PER_LINE;
          x++)
     {
-        if (u64Key == pHash->u64Sig)
+        //
+        // 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.
-            // 
-            pHash->bvFlags &= 0x0F;
+            // 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);
-            pHash->bvFlags |= g_cDirty;
-            ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
-            
+            sLocal.bvFlags |= g_cDirty;
+            ASSERT((sLocal.bvFlags & 0xF0) == g_cDirty);
+            pHash->u64Data = sLocal.u64Data;
+            pHash->u64Sig  = u64Key ^ sLocal.u64Data;
+
             //
             // Parse the matching entry
             //
-            *pfThreat |= ((pHash->bvFlags & HASH_FLAG_THREAT) > 0);
-            
+            *pfThreat |= ((sLocal.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
@@ -888,11 +866,11 @@ Return value:
             // 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))
+            //
+            if ((sLocal.uDepth >= uNextDepth) &&
+                ((sLocal.bvFlags & HASH_FLAG_UPPER) ||
+                 (sLocal.bvFlags & HASH_FLAG_EXACT)) &&
+                (sLocal.iValue < iBeta))
             {
                 *pfAvoidNull = TRUE;
             }
@@ -901,62 +879,68 @@ Return value:
             // 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, pHash->uDepth);
+            if (sLocal.mv.uMove) {
+                uThisScore = COMPUTE_MOVE_SCORE(sLocal.mv, sLocal.uDepth);
                 ASSERT(uThisScore != 0);
                 if (uThisScore > uMoveScore) {
                     uMoveScore = uThisScore;
-                    *pHashMove = pHash->mv;
-                    ASSERT(SanityCheckMove(pos, pHash->mv));
+                    *pHashMove = sLocal.mv;
+                    ASSERT(SanityCheckMove(pos, sLocal.mv));
                 }
             }
-            
+
             //
             // We have a hit, but is it useful?
             //
-            if (pHash->uDepth >= uDepth)
+            if (sLocal.uDepth >= uDepth)
             {
-                switch (pHash->bvFlags & HASH_FLAG_VALID_BOUNDS)
+                switch (sLocal.bvFlags & HASH_FLAG_VALID_BOUNDS)
                 {
                     case HASH_FLAG_EXACT:
-                        *piScore = pHash->iValue;
+                        *piScore = sLocal.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)
+                        if (sLocal.iValue >= +NMATE)
                         {
                             *piScore -= (int)uPly;
                         }
-                        else if (pHash->iValue <= -NMATE)
+                        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 (pHash->iValue >= iBeta)
+                        if (sLocal.iValue >= iBeta)
                         {
                             INC(ctx->sCounters.hash.u64UsefulHits);
                             INC(ctx->sCounters.hash.u64LowerBoundHits);
-                            *piScore = pHash->iValue;
+                            *piScore = sLocal.iValue;
                             ASSERT(IS_VALID_SCORE(*piScore));
+                            fFoundUsableBound = TRUE;
+                            *pOut = sLocal;
                             goto end;
                         }
                         break;
-                    
+
                     case HASH_FLAG_UPPER:
-                        if (pHash->iValue <= iAlpha)
+                        if (sLocal.iValue <= iAlpha)
                         {
                             INC(ctx->sCounters.hash.u64UsefulHits);
                             INC(ctx->sCounters.hash.u64UpperBoundHits);
-                            *piScore = pHash->iValue;
+                            *piScore = sLocal.iValue;
                             ASSERT(IS_VALID_SCORE(*piScore));
+                            fFoundUsableBound = TRUE;
+                            *pOut = sLocal;
                             goto end;
                         }
                         break;
@@ -970,14 +954,7 @@ Return value:
         }
         pHash++;
     }
-    pHash = NULL;
-    
+
  end:
-#ifdef MP
-    //
-    // Release the lock.
-    //
-    _DeselectHashLine(u64Key);
-#endif
-    return(pHash);
+    return(fFoundUsableBound);
 }
diff --git a/src/main.c b/src/main.c
index ecc9430..5135b7a 100644
--- a/src/main.c
+++ b/src/main.c
@@ -635,6 +635,7 @@ Return value:
     TestIsAttacked();
     TestMakeUnmakeMove();
     TestSearch();
+    TestLocklessHashAlgebra();
     TestSearchHashConsistency();
     TestQSearchSanity();
 
diff --git a/src/search.c b/src/search.c
index c434f48..d8ece8d 100644
--- a/src/search.c
+++ b/src/search.c
@@ -391,8 +391,8 @@ _NullCalibBucketIndex(ULONG uNullDepth,     // probe's own post-reduction depth
 #ifdef DEBUG
 #define VERIFY_HASH_HIT                                \
     ASSERT(IS_VALID_SCORE(iScore));                    \
-    ASSERT(((ULONG)pHash->uDepth << 4) >= uDepth);     \
-    switch (pHash->bvFlags & HASH_FLAG_VALID_BOUNDS)   \
+    ASSERT(((ULONG)sHash.uDepth << 4) >= uDepth);      \
+    switch (sHash.bvFlags & HASH_FLAG_VALID_BOUNDS)    \
     {                                                  \
         case HASH_FLAG_LOWER:                          \
             ASSERT(iScore >= iBeta);                   \
@@ -528,7 +528,8 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
     ULONG uThisMoveJointExtraTier = 0;
     FLAG fThisMoveJointExtraEligible = FALSE;
 #endif
-    HASH_ENTRY *pHash;
+    HASH_ENTRY sHash;
+    FLAG fHashHit;
     FLAG fThreat;
     FLAG fSkipNull;
     FLAG fIsDraw;
@@ -643,7 +644,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
     // below) based on uNextDepth to inform us that a nullmove search
     // is unlikely to succeed here.
     mvHash.uMove = 0;
-    pHash = HashLookup(ctx,
+    fHashHit = HashLookup(ctx,
                        uDepth,
                        uNextDepth,
                        iAlpha,
@@ -651,11 +652,12 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
                        &fThreat,
                        &fSkipNull,
                        &mvHash,
-                       &iScore);
-    if (NULL != pHash)
+                       &iScore,
+                       &sHash);
+    if (TRUE == fHashHit)
     {
         VERIFY_HASH_HIT;
-        u = pHash->bvFlags & HASH_FLAG_VALID_BOUNDS;
+        u = sHash.bvFlags & HASH_FLAG_VALID_BOUNDS;
         if (0 != mvHash.uMove)
         {
             // This is an idea posted by Dieter Brusser on CCC: If we
diff --git a/src/testhash.c b/src/testhash.c
index 6059a1b..6ea2fee 100644
--- a/src/testhash.c
+++ b/src/testhash.c
@@ -91,7 +91,131 @@ Return value:
 }
 
 
-void 
+FLAG
+TestLocklessHashAlgebra(void)
+/**
+
+Routine description:
+
+    Pure algebra test for the lockless-hash scheme (Hyatt/Crafty --
+    see hash.c's module comment) -- no concurrency involved, just
+    verifies the XOR round-trip and the self-detection property a
+    concurrent writer's torn update relies on. Operates directly on
+    bare HASH_ENTRY structs, nothing from the real hash table.
+
+    Three things checked, each over many random (key, data) pairs:
+
+      1. Round-trip: write u64Data, write u64Sig = key ^ u64Data,
+         then verify (u64Sig ^ u64Data) == key. This is the whole
+         scheme -- if this doesn't hold, nothing else about the
+         lockless rewrite can be trusted.
+
+      2. Torn-write detection: simulate two threads' writes
+         interleaving (data from one, sig from the other) and confirm
+         the un-corrupted key essentially never matches either real
+         key -- the self-check that makes the scheme safe without a
+         lock.
+
+      3. The one documented, harmless exception: when the two
+         "threads'" data words happen to be bit-identical, the torn
+         read un-corrupts to the SAME key either real writer would
+         have produced -- confirmed explicitly, not just allowed to
+         slip through the random sampling in (2).
+
+Parameters:
+
+    void
+
+Return value:
+
+    FLAG
+
+**/
+{
+    const ULONG uIterations = 200000;
+    ULONG u;
+    FLAG fRet = TRUE;
+    UINT64 u64FalsePositives = 0;
+
+    Trace("Testing lockless hash algebra...\n");
+
+    for (u = 0; u < uIterations; u++)
+    {
+        UINT64 u64Key1 = (((UINT64)randomMT()) << 32) | randomMT();
+        UINT64 u64Data1 = (((UINT64)randomMT()) << 32) | randomMT();
+        UINT64 u64Key2 = (((UINT64)randomMT()) << 32) | randomMT();
+        UINT64 u64Data2 = (((UINT64)randomMT()) << 32) | randomMT();
+        UINT64 u64Sig1, u64Sig2;
+        UINT64 u64TornKey;
+
+        // 1. Plain round-trip, both "entries" independently.
+        u64Sig1 = u64Key1 ^ u64Data1;
+        u64Sig2 = u64Key2 ^ u64Data2;
+        if (((u64Sig1 ^ u64Data1) != u64Key1) ||
+            ((u64Sig2 ^ u64Data2) != u64Key2))
+        {
+            Trace("TestLocklessHashAlgebra: round-trip failed for "
+                  "iteration %lu\n", u);
+            fRet = FALSE;
+        }
+
+        // 2. Torn write: data from "writer 2", sig from "writer 1"
+        // (as if a reader's two plain loads landed on either side of
+        // a concurrent full update). Must not un-corrupt to either
+        // writer's real key, UNLESS the two data words happen to
+        // coincide (case 3, checked separately below) -- that's the
+        // one case this random sampling could legitimately hit, so
+        // it's explicitly excluded here rather than miscounted as a
+        // false positive.
+        u64TornKey = u64Sig1 ^ u64Data2;
+        if (u64Data1 != u64Data2)
+        {
+            if ((u64TornKey == u64Key1) || (u64TornKey == u64Key2))
+            {
+                u64FalsePositives++;
+            }
+        }
+        else if (u64TornKey != u64Key1)
+        {
+            // This is case 3 by construction (u64Data1 == u64Data2)
+            // -- the torn read MUST un-corrupt to u64Key1 here (and,
+            // since the data words are equal, u64Key1's own sig1 is
+            // exactly what a from-scratch write of u64Key2 with this
+            // same data would have produced too -- not checked
+            // separately, same algebra).
+            Trace("TestLocklessHashAlgebra: case-3 coincidence did not "
+                  "verify at iteration %lu\n", u);
+            fRet = FALSE;
+        }
+    }
+
+    // u64FalsePositives should be *exactly* zero -- a torn (sig1,
+    // data2) pair un-corrupting to a real key by pure chance (data1
+    // != data2) would require a specific 64-bit XOR coincidence,
+    // astronomically unlikely across 200k random trials. Any nonzero
+    // count here across a large sample is a red flag that the
+    // algebra isn't what this comment thinks it is, not expected
+    // noise -- hence ASSERT(FALSE), not just a logged warning.
+    if (0 != u64FalsePositives)
+    {
+        Trace("TestLocklessHashAlgebra: %" COMPILER_LONGLONG_UNSIGNED_FORMAT
+              " torn-write false positive(s) out of %lu trials\n",
+              u64FalsePositives, uIterations);
+        ASSERT(FALSE);
+        fRet = FALSE;
+    }
+
+    if (FALSE == fRet)
+    {
+        UtilPanic(TESTCASE_FAILURE,
+                  NULL, "TestLocklessHashAlgebra", NULL, NULL,
+                  __FILE__, __LINE__);
+    }
+    return(fRet);
+}
+
+
+void
 AnalyzeFullHashTable(void)
 /**
 
@@ -160,11 +284,18 @@ Return value:
             //
             if (uEntry % NUM_HASH_ENTRIES_PER_LINE)
             {
+                // Lockless hash (see hash.c's module comment): u64Sig
+                // no longer holds the plain key, it holds (realKey ^
+                // u64Data), so two entries for the SAME position don't
+                // have equal raw .u64Sig unless their .u64Data also
+                // happens to match -- un-corrupt each side before
+                // comparing.
                 fUnique = TRUE;
                 u = uEntry - 1;
                 do
                 {
-                    if (p->u64Sig == g_pHashTable[u].u64Sig)
+                    if ((p->u64Sig ^ p->u64Data) ==
+                        (g_pHashTable[u].u64Sig ^ g_pHashTable[u].u64Data))
                     {
                         fUnique = FALSE;
                         break;