src/hash.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     hash.c
   8
   9 Abstract:
  10
  11     The main transposition table code.  The table is a large range of
  12     memory organized into lines (64 bytes).  Each line contains four
  13     entries that are 16 bytes each (index 0..3).
  14
  15     After a search, data about the position's score and the depth we
  16     searched to determine this score can be stored in the hash table.
  17     When information is stored a hash replacement scheme is used to
  18     overwrite one of the four entries on a line.
  19
  20     Later, before embarking on a deep recursive search, we can check
  21     the hash table to see if information relevant to this position
  22     has been stored already (and can be reused).  If so, we can avoid
  23     repeating the same search and save time.
  24
  25     A hash entry is 16 bytes long and looks like this:
  26
  27         typedef struct _HASH_ENTRY
  28         {
  29             MOVE mv;                 // 0 1 2 3
  30             UCHAR uDepth;            // 4
  31             UCHAR bvFlags;           // 5 ==> d  i  r  t  | thr up low exact
  32             signed short iValue;     // 6 7
  33             UINT64 u64Sig;           // 8 9 A B C D E F == 16 bytes
  34         } HASH_ENTRY;
  35
  36     The mv is the best move in a position.  Even if we do not have a
  37     deep enough uDepth recorded to cut off, mv is searched first.
  38     uDepth is the depth searched to determine iValue.  iValue is
  39     either the exact score or a bound score -- depending on the
  40     value of bvFlag's low order 4 bits.  The high order 4 bits
  41     in bvFlags holds "dirty" information to aide the hash replacement
  42     scheme.  Finally the u64Sig value is used to absolutely identify
  43     the position to which the hash entry's information refers.
  44
  45     When screwing around with the hash code, turn on PERF_COUNTERS and
  46     watch the hash hit rate (and usable hash hit rate).  Also here is
  47     Fine position #70 which is a great sanity check for hash code:
  48
  49     8/k7/3p4/p2P1p2/P2P1P2/8/8/K7/ w - - 0 0 bm 1. Ka1-b1 Ka7-b7 2. Kb1-c1
  50
  51 Author:
  52
  53     Scott Gasch ([email protected]) 12 Jun 2004
  54
  55 Revision History:
  56
  57     $Id: hash.c 345 2007-12-02 22:56:42Z scott $
  58
  59 **/
  60
  61 #include "chess.h"
  62
  63 //
  64 // Hash entries are 16 bytes each and hash lines are 4 entries = 64
  65 // bytes.  This is done on purpose so that a hash line fits in a cpu
  66 // cache line.  My Athlons have 64 byte cache lines.  To adjust this
  67 // for other processors, change the constant below.
  68 //
  69 #define CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(x) \
  70     ASSERT(IS_VALID_DEPTH(x)); \
  71     (x) >>= 4; \
  72     ASSERT(((x) & 0xffffff00) == 0);
  73
  74 #define HASH_ENTRY_IS_DIRTY(x) \
  75     (((x).bvFlags & 0xF0) != g_cDirty)
  76
  77 #undef ADJUST_MATE_IN_N
  78
  79 #ifdef MP
  80 //
  81 // On MP builds we lock ranges of the hash table in order to mitigate
  82 // against two searcher threads colliding on the same entry at once.
  83 // I did not have a free bit to use in the hash entry so I lock every
  84 // 256th hash table entry at once.
  85 //
  86 #define NUM_HASH_LOCKS 256
  87 volatile static ULONG g_uHashLocks[NUM_HASH_LOCKS];
  88 #define HASH_IS_LOCKED(x) ((g_uHashLocks[(x)]) != 0)
  89 #define LOCK_HASH(x) \
  90     AcquireSpinLock(&(g_uHashLocks[(x)])); \
  91     ASSERT(HASH_IS_LOCKED(x));
  92 #define UNLOCK_HASH(x) \
  93     ASSERT(HASH_IS_LOCKED(x)); \
  94     ReleaseSpinLock(&(g_uHashLocks[(x)]));
  95 #else // no MP
  96 #define HASH_IS_LOCKED(x)
  97 #define LOCK_HASH(x)
  98 #define UNLOCK_HASH(x)
  99 #endif
 100
 101 ULONG g_uHashTableSizeEntries = 0;
 102 ULONG g_uHashTableSizeBytes = 0;
 103 HASH_ENTRY *g_pHashTable = NULL;
 104 UCHAR g_cDirty = 0;
 105
 106 void
 107 DirtyHashTable(void)
 108 /**
 109
 110 Routine description:
 111
 112     The dirty pattern is bitwise ored onto the bvFlags part of a
 113     hash table entry.  Since the low nibble is used to hold flags
 114     like upper bound, lower bound, exact score, and threat the
 115     dirty indicator is limited to operating in the upper nibble
 116     of bvFlags (giving it a range of 16 values)
 117
 118 Parameters:
 119
 120     void
 121
 122 Return value:
 123
 124     void
 125
 126 **/
 127 {
 128     ASSERT((g_cDirty & 0x0F) == 0);
 129     g_cDirty += 0x10;
 130     ASSERT((g_cDirty & 0x0F) == 0);
 131 #ifdef TEST
 132     if (g_Options.fShouldPost)
 133     {
 134         Trace("Hash table dirty char: 0x%02x\n", g_cDirty);
 135     }
 136 #endif
 137 }
 138
 139
 140 void
 141 CleanupHashSystem(void)
 142 /**
 143
 144 Routine description:
 145
 146     Cleanup the hash table by freeing the memory and zeroing some
 147     variables.  This is called before building an opening book in
 148     order to free some virtual address space up.
 149
 150 Parameters:
 151
 152     void
 153
 154 Return value:
 155
 156     void
 157
 158 **/
 159 {
 160     if (NULL != g_pHashTable)
 161     {
 162         ASSERT(g_uHashTableSizeBytes > 0);
 163         SystemFreeMemory(g_pHashTable);
 164         g_pHashTable = NULL;
 165         g_uHashTableSizeBytes = 0;
 166         g_uHashTableSizeEntries = 0;
 167     }
 168 }
 169
 170 FLAG
 171 InitializeHashSystem(void)
 172 /**
 173
 174 Routine description:
 175
 176     Initialize the hash system... allocate the table and get everything
 177     ready to go.
 178
 179 Parameters:
 180
 181     void
 182
 183 Return value:
 184
 185     FLAG
 186
 187 **/
 188 {
 189     ULONG uBytesToAlloc;
 190
 191     if (!IS_A_POWER_OF_2(g_Options.uNumHashTableEntries))
 192     {
 193         return(FALSE);
 194     }
 195     g_uHashTableSizeEntries = g_Options.uNumHashTableEntries;
 196     if (g_uHashTableSizeEntries != 0)
 197     {
 198         ASSERT(g_pHashTable == NULL);
 199         uBytesToAlloc = (sizeof(HASH_ENTRY) * g_uHashTableSizeEntries);
 200         g_pHashTable = SystemAllocateMemory(uBytesToAlloc);
 201         g_uHashTableSizeBytes = uBytesToAlloc;
 202         ClearHashTable();
 203 #ifdef MP
 204         memset((BYTE *)g_uHashLocks, 0, sizeof(g_uHashLocks));
 205 #endif
 206     }
 207     return(TRUE);
 208 }
 209
 210
 211 void
 212 ClearHashTable (void)
 213 /**
 214
 215 Routine description:
 216
 217     Zero out the entire hash table.  This function is called when a new
 218     position is loaded into the root board.
 219
 220 Parameters:
 221
 222     void
 223
 224 Return value:
 225
 226     void
 227
 228 **/
 229 {
 230     if (NULL != g_pHashTable)
 231     {
 232         g_cDirty = 0;
 233         ASSERT(0 != g_uHashTableSizeBytes);
 234         ASSERT(0 != g_uHashTableSizeEntries);
 235         memset(g_pHashTable, 0, g_uHashTableSizeBytes);
 236     }
 237 }
 238
 239
 240 //
 241 // (g_uHashTableSizeEntries) =>  1000 0000 ... 0000
 242 // NUM_HASH_ENTRIES_PER_LINE =>  -             0100
 243 // ------------------------------------------------
 244 //                               1111 1111 ... 1100 => Start of a hash line
 245 //
 246 #define KEY_TO_HASH_LINE_START(x) \
 247     ((x) & (g_uHashTableSizeEntries - NUM_HASH_ENTRIES_PER_LINE))
 248
 249 static HASH_ENTRY *
 250 _SelectHashLine(UINT64 u64Key)
 251 /**
 252
 253 Routine description:
 254
 255     On an MP system, this routine locks part of the hash table, the
 256     caller should do its thing and then unlock the locked portion of
 257     the hash table by calling _DeselectHashLine(u64Key).
 258
 259 Parameters:
 260
 261     UINT64 u64Key
 262
 263 Return value:
 264
 265     static HASH_ENTRY
 266
 267 **/
 268 {
 269     ULONG uLow = (ULONG)(u64Key >> 32);
 270     ULONG uLine = KEY_TO_HASH_LINE_START(uLow);
 271 #ifdef MP
 272     ULONG uLock = (uLine >> 2) & (NUM_HASH_LOCKS - 1);
 273     LOCK_HASH(uLock);
 274     ASSERT(IS_A_POWER_OF_2(NUM_HASH_LOCKS));
 275 #endif
 276     ASSERT(g_uHashTableSizeBytes != 0);
 277     ASSERT(g_uHashTableSizeEntries != 0);
 278     ASSERT(g_pHashTable != NULL);
 279     ASSERT(IS_A_POWER_OF_2(g_uHashTableSizeEntries));
 280     ASSERT(((g_uHashTableSizeEntries - NUM_HASH_ENTRIES_PER_LINE) &
 281             (NUM_HASH_ENTRIES_PER_LINE - 1)) == 0);
 282     return(&(g_pHashTable[uLine]));
 283 }
 284
 285 #ifdef MP
 286 static void
 287 _DeselectHashLine(UINT64 u64Key)
 288 /**
 289
 290 Routine description:
 291
 292     This releases the lock taken by _SelectHashLine
 293
 294 Parameters:
 295
 296     UINT64 u64Key
 297
 298 Return value:
 299
 300     static void
 301
 302 **/
 303 {
 304     ULONG uLow = (ULONG)(u64Key >> 32);
 305     ULONG uLine = KEY_TO_HASH_LINE_START(uLow);
 306     ULONG uLock = (uLine >> 2) & (NUM_HASH_LOCKS - 1);
 307
 308     ASSERT(IS_A_POWER_OF_2(NUM_HASH_LOCKS));
 309     ASSERT(MP);
 310     UNLOCK_HASH(uLock);
 311 }
 312 #endif
 313
 314
 315 static HASH_ENTRY *
 316 _SelectHashEntry(UINT64 u64Key,
 317                  ULONG uDepth,
 318                  ULONG uType,
 319                  SCORE iValue)
 320 /**
 321
 322 Routine description:
 323
 324     This routine takes a lock.  The caller should do its thing and then
 325     release the lock by calling _DeselectHashEntry.
 326
 327 Parameters:
 328
 329     UINT64 u64Key,
 330     ULONG uDepth
 331
 332 Return value:
 333
 334     static HASH_ENTRY
 335
 336 **/
 337 {
 338     HASH_ENTRY *pEntry;
 339     HASH_ENTRY *pStore;
 340
 341     ASSERT(g_uHashTableSizeBytes != 0);
 342     ASSERT(g_uHashTableSizeEntries != 0);
 343     ASSERT(g_pHashTable != NULL);
 344     ASSERT(IS_A_POWER_OF_2(g_uHashTableSizeEntries));
 345
 346     //
 347     // _SelectHashLine takes a lock on MP builds.
 348     //
 349     pEntry = _SelectHashLine(u64Key);
 350     ASSERT(pEntry != NULL);
 351 #ifdef DEBUG
 352     pStore = NULL;
 353 #endif
 354
 355     //
 356     // Note: Hash lines consist of four entries currently:
 357     //
 358     // 1. The first is a depth-priority hash entry (store here if you
 359     // can beat the depth of what's already in there).
 360     //
 361     // 2. The second is an always-store hash entry (store here if you
 362     // can't store in the depth-priority entry).
 363     //
 364     // 3. and 4. The last two entries are where we bump the data from
 365     // the depth- priority table and always-store table when they are
 366     // going to be overwritten by newer data.
 367     //
 368
 369     //
 370     // Replace the 0th entry on the line if:
 371     //
 372     // ...the new entry has greater depth
 373     // ...the current entry is stale (from an old search)
 374     //
 375     if ((pEntry[0].uDepth <= uDepth) ||
 376         HASH_ENTRY_IS_DIRTY(pEntry[0]))
 377     {
 378         //
 379         // Do we need to back up the entry we will overwrite?
 380         //
 381         if ((pEntry[0].u64Sig != u64Key) ||
 382             ((pEntry[0].bvFlags & HASH_FLAG_VALID_BOUNDS) != uType))
 383         {
 384             pEntry[2] = pEntry[0];
 385         }
 386         pStore = &(pEntry[0]);
 387         goto end;
 388     }
 389
 390     //
 391     // We could not replace the depth priority 0th entry; instead,
 392     // replace the "always replace" 1st entry on the line unless it
 393     // contains mate information and is not stale.
 394     //
 395     if (((abs(pEntry[1].iValue >= +NMATE)) &&
 396          (abs(iValue) < +NMATE)) &&
 397         (!HASH_ENTRY_IS_DIRTY(pEntry[1])))
 398     {
 399         pStore = &(pEntry[3]);
 400         goto end;
 401     }
 402     if ((pEntry[1].u64Sig != u64Key) ||
 403         ((pEntry[1].bvFlags & HASH_FLAG_VALID_BOUNDS) != uType))
 404     {
 405         pEntry[3] = pEntry[1];
 406     }
 407     pStore = &(pEntry[1]);
 408
 409  end:
 410     ASSERT(pStore != NULL);
 411     return(pStore);
 412 }
 413
 414
 415 #ifdef MP
 416 static void
 417 _DeselectHashEntry(UINT64 u64Key)
 418 /**
 419
 420 Routine description:
 421
 422     Releases the lock taken by _SelectHashEntry.
 423
 424 Parameters:
 425
 426     UINT64 u64Key
 427
 428 Return value:
 429
 430     static void
 431
 432 **/
 433 {
 434     _DeselectHashLine(u64Key);                // this releases a lock
 435 }
 436 #endif
 437
 438
 439 void
 440 StoreUpperBound(//MOVE mvBest,
 441     POSITION *pos,
 442     SCORE iValue,
 443     ULONG uDepth,
 444     FLAG fThreat)
 445 /**
 446
 447 Routine description:
 448
 449     Store an upper bound in the hash table.
 450
 451 Parameters:
 452
 453     MOVE mvBest : singular move from the node, if any
 454     POSITION *pos,
 455     SCORE iValue,
 456     ULONG uDepth,
 457     FLAG fThreat
 458
 459 Return value:
 460
 461     void
 462
 463 **/
 464 {
 465     UINT64 u64Key;
 466     HASH_ENTRY *pHash;
 467
 468     ASSERT(IS_VALID_SCORE(iValue));
 469     ASSERT(IS_VALID_DEPTH(uDepth));
 470
 471     //
 472     // It does not make sense to store hash positions that are worth
 473     // at best ~INFINITY.  Every position is and this is a waste of
 474     // hash space.  Ignore these.
 475     //
 476     if (iValue >= +NMATE) return;
 477     if (NULL == g_pHashTable) return;
 478
 479     CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uDepth);
 480     u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
 481
 482     //
 483     // _SelectHashEntry takes a lock on MP builds
 484     //
 485     pHash = _SelectHashEntry(u64Key, uDepth, HASH_FLAG_UPPER, iValue);
 486     ASSERT(pHash != NULL);
 487     pHash->uDepth = (UCHAR)uDepth;
 488     if (pHash->u64Sig != u64Key)
 489     {
 490         //
 491         // Note: don't overwrite a good hash move with "none" if we
 492         // are replacing a hash entry for the same position.  Also
 493         // if we are klobbering data about the same position save
 494         // a memory write to update the (same) sig.
 495         //
 496         pHash->mv.uMove = 0;
 497         pHash->u64Sig = u64Key;
 498     }
 499     ASSERT((g_cDirty & HASH_FLAG_UPPER) == 0);
 500     pHash->bvFlags = g_cDirty | HASH_FLAG_UPPER;
 501     ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
 502     if (TRUE == fThreat)
 503     {
 504         ASSERT((pHash->bvFlags & HASH_FLAG_THREAT) == 0);
 505         pHash->bvFlags |= HASH_FLAG_THREAT;
 506     }
 507
 508     if (iValue <= -NMATE)
 509     {
 510         //
 511         // If this is an upper bound near -INFINITY
 512         // (i.e. ~-INFINITY at best) convert it into -NMATE at
 513         // best (at best mate in N).
 514         //
 515         pHash->iValue = -NMATE;
 516     }
 517     else
 518     {
 519         //
 520         // Otherwise hash the exact value.
 521         //
 522         ASSERT(iValue > -NMATE);
 523         ASSERT(iValue < +NMATE);
 524         pHash->iValue = (signed short)iValue;
 525     }
 526 #ifdef MP
 527     //
 528     // Release the lock on MP builds
 529     //
 530     _DeselectHashEntry(u64Key);
 531 #endif
 532 }
 533
 534
 535 void
 536 StoreExactScore(MOVE mvBestMove,
 537                 POSITION *pos,
 538                 SCORE iValue,
 539                 ULONG uDepth,
 540                 FLAG fThreat,
 541                 ULONG uPly)
 542 /**
 543
 544 Routine description:
 545
 546     Store a best move and its exact score in the hash table.
 547
 548 Parameters:
 549
 550     MOVE mvBestMove,
 551     POSITION *pos,
 552     SCORE iValue,
 553     ULONG uDepth,
 554     FLAG fThreat,
 555     ULONG uPly
 556
 557 Return value:
 558
 559     void
 560
 561 **/
 562 {
 563     HASH_ENTRY *pHash;
 564     UINT64 u64Key;
 565
 566     ASSERT(IS_VALID_SCORE(iValue));
 567     ASSERT(IS_VALID_DEPTH(uDepth));
 568     if (NULL == g_pHashTable) return;
 569
 570     CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uDepth);
 571     u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
 572
 573     //
 574     // _SelectHashEntry takes a lock on MP builds.
 575     //
 576     pHash = _SelectHashEntry(u64Key, uDepth, HASH_FLAG_EXACT, iValue);
 577     ASSERT(pHash != NULL);
 578
 579     //
 580     // Populate the hash entry
 581     //
 582     pHash->uDepth = (UCHAR)uDepth;
 583     ASSERT(mvBestMove.uMove);
 584     pHash->mv.uMove = mvBestMove.uMove;
 585     ASSERT((g_cDirty & HASH_FLAG_EXACT) == 0);
 586     pHash->bvFlags = g_cDirty | HASH_FLAG_EXACT;
 587     ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
 588     if (TRUE == fThreat)
 589     {
 590         ASSERT((pHash->bvFlags & HASH_FLAG_THREAT) == 0);
 591         pHash->bvFlags |= HASH_FLAG_THREAT;
 592     }
 593     pHash->u64Sig = u64Key;
 594
 595     if (iValue >= +NMATE)
 596     {
 597 #ifdef ADJUST_MATE_IN_N
 598         ASSERT((iValue + (int)uPly) < +INFINITY);
 599         ASSERT((iValue + (int)uPly) > -INFINITY);
 600         pHash->iValue = (signed short)(iValue + (int)uPly);
 601 #else
 602         pHash->bvFlags = g_cDirty | HASH_FLAG_LOWER;
 603         ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
 604         pHash->iValue = +NMATE;
 605 #endif
 606     }
 607     else if (iValue <= -NMATE)
 608     {
 609 #ifdef ADJUST_MATE_IN_N
 610         ASSERT((iValue + (int)uPly) < +INFINITY);
 611         ASSERT((iValue - (int)uPly) > -INFINITY);
 612         pHash->iValue = (signed short)(iValue - (int)uPly);
 613 #else
 614         pHash->bvFlags = g_cDirty | HASH_FLAG_UPPER;
 615         ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
 616         pHash->iValue = +NMATE;
 617 #endif
 618     }
 619     else
 620     {
 621         ASSERT(iValue > -NMATE);
 622         ASSERT(iValue < +NMATE);
 623         pHash->iValue = (short signed)iValue;
 624     }
 625 #ifdef MP
 626     //
 627     // Release the lock on MP builds
 628     //
 629     _DeselectHashEntry(u64Key);               // Release the lock
 630 #endif
 631 }
 632
 633
 634 void
 635 StoreLowerBound(MOVE mvBestMove,
 636                 POSITION *pos,
 637                 SCORE iValue,
 638                 ULONG uDepth,
 639                 FLAG fThreat)
 640 /**
 641
 642 Routine description:
 643
 644     Store a lower bound score and move in the hash table.
 645
 646 Parameters:
 647
 648     MOVE mvBestMove,
 649     POSITION *pos,
 650     SCORE iValue,
 651     ULONG uDepth,
 652     FLAG fThreat
 653
 654 Return value:
 655
 656     void
 657
 658 **/
 659 {
 660     HASH_ENTRY *pHash;
 661     UINT64 u64Key;
 662
 663     ASSERT(IS_VALID_SCORE(iValue));
 664     ASSERT(IS_VALID_DEPTH(uDepth));
 665
 666     //
 667     // Do not bother to hash this node if it is telling us that the
 668     // value of this position is worth at least ~-INFINITY.  This is
 669     // useless information and a waste of hash space.
 670     //
 671     if (iValue <= -NMATE) return;
 672     if (NULL == g_pHashTable) return;
 673
 674     CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uDepth);
 675     u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
 676
 677     //
 678     // _SelectHashEntry takes a lock on MP builds
 679     //
 680     pHash = _SelectHashEntry(u64Key, uDepth, HASH_FLAG_LOWER, iValue);
 681     ASSERT(pHash != NULL);
 682
 683     //
 684     // Populate the entry
 685     //
 686     pHash->uDepth = (UCHAR)uDepth;
 687     if ((mvBestMove.uMove) || (pHash->u64Sig != u64Key))
 688     {
 689         //
 690         // Note: only overwrite the existing hash move if either we
 691         // have a move (i.e. not null move) or the entry we are
 692         // overwriting is for a different position.
 693         //
 694         pHash->mv.uMove = mvBestMove.uMove;
 695     }
 696     pHash->u64Sig = u64Key;
 697     ASSERT((g_cDirty & HASH_FLAG_LOWER) == 0);
 698     pHash->bvFlags = g_cDirty | HASH_FLAG_LOWER;
 699     ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
 700     pHash->bvFlags |= (HASH_FLAG_THREAT * (fThreat == TRUE));
 701     if (iValue < +NMATE)
 702     {
 703         ASSERT(iValue < +NMATE);
 704         ASSERT(iValue > -NMATE);
 705         pHash->iValue = (signed short)iValue;
 706     }
 707     else
 708     {
 709         //
 710         // If the value is greater than mate in N don't store how many
 711         // moves N is because this depends on where in the search we
 712         // have found this position.  Just say that this position is
 713         // worth at least mate in N.
 714         //
 715         pHash->iValue = +NMATE;
 716     }
 717 #ifdef MP
 718     //
 719     // Release the lock on MP builds
 720     //
 721     _DeselectHashEntry(u64Key);
 722 #endif
 723 }
 724
 725
 726 MOVE
 727 GetPonderMove(POSITION *pos)
 728 /**
 729
 730 Routine description:
 731
 732     Get a move to ponder.
 733
 734 Parameters:
 735
 736     POSITION *pos
 737
 738 Return value:
 739
 740     MOVE
 741
 742 **/
 743 {
 744     HASH_ENTRY *pHash;
 745     ULONG x;
 746     UINT64 u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
 747     MOVE mv;
 748
 749     mv.uMove = 0;
 750     if (NULL == g_pHashTable) return(mv);
 751
 752     //
 753     // _SelectHashLine takes a lock on MP builds
 754     //
 755     pHash = _SelectHashLine(u64Key);
 756     for (x = 0;
 757          x < NUM_HASH_ENTRIES_PER_LINE;
 758          x++)
 759     {
 760         if (u64Key == pHash->u64Sig)
 761         {
 762             mv = pHash->mv;
 763             if ((pHash->bvFlags & HASH_FLAG_VALID_BOUNDS) ==
 764                 HASH_FLAG_EXACT)
 765             {
 766                 goto end;
 767             }
 768         }
 769     }
 770
 771  end:
 772 #ifdef MP
 773     //
 774     // Release the lock.
 775     //
 776     _DeselectHashLine(u64Key);
 777 #endif
 778     return(mv);
 779 }
 780
 781
 782 HASH_ENTRY *
 783 HashLookup(SEARCHER_THREAD_CONTEXT *ctx,
 784            ULONG uDepth,
 785            ULONG uNextDepth,
 786            SCORE iAlpha,
 787            SCORE iBeta,
 788            FLAG *pfThreat,
 789            FLAG *pfAvoidNull,
 790            MOVE *pHashMove,
 791            SCORE *piScore)
 792 /**
 793
 794 Routine description:
 795
 796     Lookup any information we have about the current position in the
 797     hash table.  Cutoff if we can.
 798
 799 Parameters:
 800
 801     SEARCHER_THREAD_CONTEXT *ctx,
 802     ULONG uDepth,
 803     ULONG uNextDepth,
 804     SCORE iAlpha,
 805     SCORE iBeta,
 806     FLAG *pfThreat,
 807     FLAG *pfAvoidNull,
 808     MOVE *pHashMove,
 809     SCORE *piScore
 810
 811 Return value:
 812
 813     HASH_ENTRY
 814
 815 **/
 816 {
 817     HASH_ENTRY *pHash;
 818     ULONG x;
 819     POSITION *pos = &(ctx->sPosition);
 820     UINT64 u64Key = pos->u64NonPawnSig ^ pos->u64PawnSig;
 821     ULONG uMoveScore = 0;
 822     ULONG uThisScore;
 823
 824 #define COMPUTE_MOVE_SCORE(mv, depth) \
 825     ((depth) * 8 + PIECE_VALUE_OVER_100((mv).pCaptured) + 1)
 826
 827     ASSERT(IS_VALID_DEPTH(uDepth));
 828     ASSERT(IS_VALID_DEPTH(uNextDepth));
 829     ASSERT(uNextDepth <= uDepth);
 830     ASSERT(IS_VALID_SCORE(iAlpha));
 831     ASSERT(IS_VALID_SCORE(iBeta));
 832     ASSERT(iAlpha < iBeta);
 833     ASSERT(pHashMove->uMove == 0);
 834     ASSERT(NULL != g_pHashTable);
 835     INC(ctx->sCounters.hash.u64Probes);
 836
 837     //
 838     // These are out parameters for the caller, initialize them
 839     // saying we don't know anything.
 840     //
 841     *pfAvoidNull = FALSE;
 842     *pfThreat = FALSE;
 843
 844     CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uDepth);
 845     CONVERT_SEARCH_DEPTH_TO_HASH_DEPTH(uNextDepth);
 846
 847     //
 848     // _SelectHashLine takes a lock on MP builds.
 849     //
 850     pHash = _SelectHashLine(u64Key);
 851     for (x = 0;
 852          x < NUM_HASH_ENTRIES_PER_LINE;
 853          x++)
 854     {
 855         if (u64Key == pHash->u64Sig)
 856         {
 857             //
 858             // This entry hit, make it "clean" so it is harder to replace
 859             // later on.
 860             //
 861             pHash->bvFlags &= 0x0F;
 862             ASSERT((g_cDirty & 0x0F) == 0);
 863             pHash->bvFlags |= g_cDirty;
 864             ASSERT((pHash->bvFlags & 0xF0) == g_cDirty);
 865
 866             //
 867             // Parse the matching entry
 868             //
 869             *pfThreat |= ((pHash->bvFlags & HASH_FLAG_THREAT) > 0);
 870
 871             //
 872             // If we have an exact match and sufficient depth to
 873             // satisfy the depth to which we will later search after a
 874             // nullmove, see if the known value of this node is less
 875             // than beta.  If so, doing nothing in this position will
 876             // probably not be better than doing something therefore
 877             // its not wise to perform the nullmove search.  It's just
 878             // a waste of nodes and time.
 879             //
 880             if ((pHash->uDepth >= uNextDepth) &&
 881                 ((pHash->bvFlags & HASH_FLAG_UPPER) ||
 882                  (pHash->bvFlags & HASH_FLAG_EXACT)) &&
 883                 (pHash->iValue < iBeta))
 884             {
 885                 *pfAvoidNull = TRUE;
 886             }
 887
 888             // Because we can encounter several moves while looking for
 889             // a hash cutoff, have a semantic about which one we return
 890             // to the search.
 891             INC(ctx->sCounters.hash.u64OverallHits);
 892             if (pHash->mv.uMove) {
 893                 uThisScore = COMPUTE_MOVE_SCORE(pHash->mv, uDepth);
 894                 ASSERT(uThisScore != 0);
 895                 if (uThisScore > uMoveScore) {
 896                     uMoveScore = uThisScore;
 897                     *pHashMove = pHash->mv;
 898                     ASSERT(SanityCheckMove(pos, pHash->mv));
 899                 }
 900             }
 901
 902             //
 903             // We have a hit, but is it useful?
 904             //
 905             if (pHash->uDepth >= uDepth)
 906             {
 907                 switch (pHash->bvFlags & HASH_FLAG_VALID_BOUNDS)
 908                 {
 909                     case HASH_FLAG_EXACT:
 910                         *piScore = pHash->iValue;
 911                         INC(ctx->sCounters.hash.u64UsefulHits);
 912                         INC(ctx->sCounters.hash.u64ExactScoreHits);
 913 #ifdef ADJUST_MATE_IN_N
 914                         //
 915                         // Readjust mate in N scores.
 916                         //
 917                         if (pHash->iValue >= +NMATE)
 918                         {
 919                             *piScore -= (int)uPly;
 920                         }
 921                         else if (pHash->iValue <= -NMATE)
 922                         {
 923                             *piScore += (int)uPly;
 924                         }
 925 #endif
 926                         ASSERT(IS_VALID_SCORE(*piScore));
 927                         goto end;
 928                         break;
 929
 930                     case HASH_FLAG_LOWER:
 931                         if (pHash->iValue >= iBeta)
 932                         {
 933                             INC(ctx->sCounters.hash.u64UsefulHits);
 934                             INC(ctx->sCounters.hash.u64LowerBoundHits);
 935                             *piScore = pHash->iValue;
 936                             ASSERT(IS_VALID_SCORE(*piScore));
 937                             goto end;
 938                         }
 939                         break;
 940
 941                     case HASH_FLAG_UPPER:
 942                         if (pHash->iValue <= iAlpha)
 943                         {
 944                             INC(ctx->sCounters.hash.u64UsefulHits);
 945                             INC(ctx->sCounters.hash.u64UpperBoundHits);
 946                             *piScore = pHash->iValue;
 947                             ASSERT(IS_VALID_SCORE(*piScore));
 948                             goto end;
 949                         }
 950                         break;
 951 #ifdef DEBUG
 952                     default:
 953                         ASSERT(FALSE);
 954                         break;
 955 #endif
 956                 }
 957             }
 958         }
 959         pHash++;
 960     }
 961     pHash = NULL;
 962
 963  end:
 964 #ifdef MP
 965     //
 966     // Release the lock.
 967     //
 968     _DeselectHashLine(u64Key);
 969 #endif
 970     return(pHash);
 971 }