src/poshash.c

   1 /*++
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     poshash.c
   8
   9 Abstract:
  10
  11     A hash table of information about positions.
  12
  13 Author:
  14
  15     Scott Gasch (SGasch) 11 Nov 2006
  16
  17 Revision History:
  18
  19 --*/
  20
  21 #include "chess.h"
  22
  23 #define NUM_POSITION_HASH_ENTRIES (1048576) // 16Mb
  24 POSITION_HASH_ENTRY g_PositionHash[NUM_POSITION_HASH_ENTRIES];
  25
  26 #ifdef MP
  27 #define NUM_POSITION_HASH_LOCKS (512)
  28 volatile static ULONG g_uPositionHashLocks[NUM_POSITION_HASH_LOCKS];
  29 #define POSITION_HASH_IS_LOCKED(x) ((g_uPositionHashLocks[(x)]) != 0)
  30 #define LOCK_POSITION_HASH(x) \
  31     AcquireSpinLock(&(g_uPositionHashLocks[(x)])); \
  32     ASSERT(POSITION_HASH_IS_LOCKED(x))
  33 #define UNLOCK_POSITION_HASH(x) \
  34     ASSERT(POSITION_HASH_IS_LOCKED(x)); \
  35     ReleaseSpinLock(&(g_uPositionHashLocks[(x)]))
  36 #else
  37 #define POSITION_HASH_IS_LOCKED(x)
  38 #define LOCK_HASH(x)
  39 #define UNLOCK_HASH(x)
  40 #endif
  41
  42 void
  43 InitializePositionHashSystem(void)
  44 {
  45     memset(&g_PositionHash, 0, sizeof(g_PositionHash));
  46 #ifdef MP
  47     memset(&g_uPositionHashLocks, 0, sizeof(g_uPositionHashLocks));
  48 #endif
  49 }
  50
  51 void
  52 CleanupPositionHashSystem(void)
  53 {
  54     ; // do nothing
  55 }
  56
  57 static INLINE UINT64 PositionToSignatureIgnoringMove(POSITION *pos)
  58 {
  59     return((pos->u64NonPawnSig ^ pos->u64PawnSig) >> 1);
  60 }
  61
  62 // Note: sig must be pre-shifted to ignore the side-to-move bit.
  63 static INLINE ULONG PositionSigToHashPosition(UINT64 u64Sig)
  64 {
  65     ULONG u = (ULONG)u64Sig;
  66     u &= (NUM_POSITION_HASH_ENTRIES - 1);
  67     ASSERT(u < NUM_POSITION_HASH_ENTRIES);
  68     return u;
  69 }
  70
  71 #ifdef MP
  72 static INLINE ULONG HashPositionToLockNumber(ULONG u)
  73 {
  74     u &= (NUM_POSITION_HASH_LOCKS - 1);
  75     ASSERT(u < NUM_POSITION_HASH_LOCKS);
  76     return u;
  77 }
  78 #endif
  79
  80 void
  81 StoreEnprisePiece(POSITION *pos, COOR cSquare)
  82 {
  83     UINT64 u64Sig = PositionToSignatureIgnoringMove(pos);
  84     ULONG uEntry = PositionSigToHashPosition(u64Sig);
  85     POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]);
  86     PIECE p = pos->rgSquare[cSquare].pPiece;
  87     ULONG uColor = GET_COLOR(p);
  88 #ifdef MP
  89     ULONG uLock = HashPositionToLockNumber(uEntry);
  90     LOCK_POSITION_HASH(uLock);
  91 #endif
  92     ASSERT(p && IS_VALID_PIECE(p));
  93     ASSERT(!IS_PAWN(p));
  94     ASSERT(CAN_FIT_IN_UCHAR(cSquare));
  95     ASSERT(IS_ON_BOARD(cSquare));
  96     pHash->cEnprise[uColor] = (UCHAR)cSquare;
  97     ASSERT(pHash->uEnpriseCount[uColor] < 16);
  98     pHash->uEnpriseCount[uColor] += 1;
  99     if (pHash->u64Sig != u64Sig)
 100     {
 101         pHash->u64Sig = u64Sig;
 102         pHash->uEnpriseCount[uColor] = 1;
 103         pHash->cTrapped[uColor] = ILLEGAL_COOR;
 104         uColor = FLIP(uColor);
 105         pHash->cEnprise[uColor] = ILLEGAL_COOR;
 106         pHash->cTrapped[uColor] = ILLEGAL_COOR;
 107         pHash->uEnpriseCount[uColor] = 0;
 108     }
 109 #ifdef MP
 110     UNLOCK_POSITION_HASH(uLock);
 111 #endif
 112 }
 113
 114 void
 115 StoreTrappedPiece(POSITION *pos, COOR cSquare)
 116 {
 117     UINT64 u64Sig = PositionToSignatureIgnoringMove(pos);
 118     ULONG uEntry = PositionSigToHashPosition(u64Sig);
 119     POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]);
 120     PIECE p = pos->rgSquare[cSquare].pPiece;
 121     ULONG uColor = GET_COLOR(p);
 122 #ifdef MP
 123     ULONG uLock = HashPositionToLockNumber(uEntry);
 124     LOCK_POSITION_HASH(uLock);
 125 #endif
 126     ASSERT(p && IS_VALID_PIECE(p));
 127     ASSERT(!IS_PAWN(p));
 128     ASSERT(CAN_FIT_IN_UCHAR(cSquare));
 129     ASSERT(IS_ON_BOARD(cSquare));
 130     pHash->cTrapped[uColor] = cSquare;
 131     if (pHash->u64Sig != u64Sig)
 132     {
 133         pHash->u64Sig = u64Sig;
 134         pHash->cEnprise[uColor] = ILLEGAL_COOR;
 135         pHash->uEnpriseCount[uColor] = 0;
 136         uColor = FLIP(uColor);
 137         pHash->cEnprise[uColor] = ILLEGAL_COOR;
 138         pHash->cTrapped[uColor] = ILLEGAL_COOR;
 139         pHash->uEnpriseCount[uColor] = 0;
 140     }
 141 #ifdef MP
 142     UNLOCK_POSITION_HASH(uLock);
 143 #endif
 144 }
 145
 146 COOR
 147 GetEnprisePiece(POSITION *pos, ULONG uSide)
 148 {
 149     UINT64 u64Sig = PositionToSignatureIgnoringMove(pos);
 150     ULONG uEntry = PositionSigToHashPosition(u64Sig);
 151     POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]);
 152     COOR c = ILLEGAL_COOR;
 153 #ifdef MP
 154     ULONG uLock = HashPositionToLockNumber(uEntry);
 155     LOCK_POSITION_HASH(uLock);
 156 #endif
 157     if (pHash->u64Sig == u64Sig)
 158     {
 159         c = pHash->cEnprise[uSide];
 160     }
 161 #ifdef MP
 162     UNLOCK_POSITION_HASH(uLock);
 163 #endif
 164     return c;
 165 }
 166
 167 COOR
 168 GetTrappedPiece(POSITION *pos, ULONG uSide)
 169 {
 170     UINT64 u64Sig = PositionToSignatureIgnoringMove(pos);
 171     ULONG uEntry = PositionSigToHashPosition(u64Sig);
 172     POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]);
 173     COOR c = ILLEGAL_COOR;
 174 #ifdef MP
 175     ULONG uLock = HashPositionToLockNumber(uEntry);
 176     LOCK_POSITION_HASH(uLock);
 177 #endif
 178     if (pHash->u64Sig == u64Sig)
 179     {
 180         c = pHash->cTrapped[uSide];
 181     }
 182 #ifdef MP
 183     UNLOCK_POSITION_HASH(uLock);
 184 #endif
 185     return c;
 186 }
 187
 188 FLAG
 189 SideCanStandPat(POSITION *pos, ULONG uSide)
 190 {
 191     UINT64 u64Sig = PositionToSignatureIgnoringMove(pos);
 192     ULONG uEntry = PositionSigToHashPosition(u64Sig);
 193     POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]);
 194     FLAG fStand = TRUE;
 195 #ifdef MP
 196     ULONG uLock = HashPositionToLockNumber(uEntry);
 197     LOCK_POSITION_HASH(uLock);
 198 #endif
 199     if (pHash->u64Sig == u64Sig)
 200     {
 201         fStand = ((pHash->cTrapped[uSide] == ILLEGAL_COOR) &&
 202                   (pHash->uEnpriseCount[uSide] < 2));
 203     }
 204 #ifdef MP
 205     UNLOCK_POSITION_HASH(uLock);
 206 #endif
 207     return fStand;
 208 }
 209
 210 ULONG
 211 ValueOfMaterialInTroubleDespiteMove(POSITION *pos, ULONG uSide)
 212 {
 213     UINT64 u64Sig = PositionToSignatureIgnoringMove(pos);
 214     ULONG uEntry = PositionSigToHashPosition(u64Sig);
 215     POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]);
 216     ULONG u = 0;
 217     COOR c;
 218 #ifdef MP
 219     ULONG uLock = HashPositionToLockNumber(uEntry);
 220     LOCK_POSITION_HASH(uLock);
 221 #endif
 222     if (pHash->u64Sig == u64Sig)
 223     {
 224         if (pHash->uEnpriseCount[uSide] > 1)
 225         {
 226             c = pHash->cEnprise[uSide];
 227             ASSERT(IS_ON_BOARD(c));
 228             u = PIECE_VALUE(pos->rgSquare[c].pPiece);
 229             ASSERT(u);
 230         }
 231         c = pHash->cTrapped[uSide];
 232         if (IS_ON_BOARD(c))
 233         {
 234             u = MAXU(u, PIECE_VALUE(pos->rgSquare[c].pPiece));
 235             ASSERT(u);
 236         }
 237     }
 238 #ifdef MP
 239     UNLOCK_POSITION_HASH(uLock);
 240 #endif
 241     return u;
 242 }
 243
 244 ULONG
 245 ValueOfMaterialInTroubleAfterNull(POSITION *pos, ULONG uSide)
 246 {
 247     UINT64 u64Sig = PositionToSignatureIgnoringMove(pos);
 248     ULONG uEntry = PositionSigToHashPosition(u64Sig);
 249     POSITION_HASH_ENTRY *pHash = &(g_PositionHash[uEntry]);
 250     ULONG u = 0;
 251     COOR c;
 252 #ifdef MP
 253     ULONG uLock = HashPositionToLockNumber(uEntry);
 254     LOCK_POSITION_HASH(uLock);
 255 #endif
 256     if (pHash->u64Sig == u64Sig)
 257     {
 258         if (pHash->uEnpriseCount[uSide])
 259         {
 260             c = pHash->cEnprise[uSide];
 261             ASSERT(IS_ON_BOARD(c));
 262             u += PIECE_VALUE(pos->rgSquare[c].pPiece);
 263             ASSERT(u);
 264         }
 265         c = pHash->cTrapped[uSide];
 266         if (IS_ON_BOARD(c))
 267         {
 268             u = MAXU(PIECE_VALUE(pos->rgSquare[c].pPiece), u);
 269             ASSERT(u);
 270         }
 271     }
 272 #ifdef MP
 273     UNLOCK_POSITION_HASH(uLock);
 274 #endif
 275     return u;
 276 }