src/sig.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     sig.c
   8
   9 Abstract:
  10
  11     Position signature code... the algorithm is a Zobrist hash scheme.
  12     Every piece has a different 64-bit "seed" for every different
  13     square.  Plus some non-piece/location features of a position (such
  14     as legal castling rights or the en passant location) have 64-bit
  15     "seed" keys.  The position's signature is the xor sum of all these
  16     seeds.  A position's pawn hash signature is the xor sum of all
  17     pawn-related seeds.  These signatures, once computed, can be
  18     incrementally maintained by just xoring off the seed of a moving
  19     piece's from location and xoring on the seed of its to location.
  20     These signatures are used as the basis for the pawn hash and main
  21     transposition table code.
  22
  23 Author:
  24
  25     Scott Gasch ([email protected]) 09 May 2004
  26
  27 Revision History:
  28
  29     $Id: sig.c 345 2007-12-02 22:56:42Z scott $
  30
  31 **/
  32
  33 #include "chess.h"
  34
  35 UINT64 g_u64SigSeeds[128][7][2];
  36 UINT64 g_u64PawnSigSeeds[128][2];
  37 UINT64 g_u64CastleSigSeeds[16];
  38 UINT64 g_u64EpSigSeeds[9];
  39
  40 void
  41 InitializeSigSystem(void)
  42 /**
  43
  44 Routine description:
  45
  46     Populate the arrays of signature keys (see above) used to generate
  47     normal and pawn signatures for POSITIONs.
  48
  49 Parameters:
  50
  51     void
  52
  53 Return value:
  54
  55     void
  56
  57 **/
  58 {
  59     ULONG x, y, z;
  60     UINT uChecksum = 0;
  61     ULONG uRandom;
  62
  63     memset(g_u64SigSeeds, 0, sizeof(g_u64SigSeeds));
  64     memset(g_u64PawnSigSeeds, 0, sizeof(g_u64PawnSigSeeds));
  65     memset(g_u64CastleSigSeeds, 0, sizeof(g_u64CastleSigSeeds));
  66     memset(g_u64EpSigSeeds, 0, sizeof(g_u64EpSigSeeds));
  67     seedMT(2222);
  68
  69     for (x = A; x <= H+1; x++)
  70     {
  71         //
  72         // Do en-passant sig
  73         //
  74         uRandom = randomMT();
  75         uChecksum ^= uRandom;
  76         g_u64EpSigSeeds[x] = (UINT64)uRandom << 32;
  77         uRandom = randomMT();
  78         uChecksum ^= uRandom;
  79         g_u64EpSigSeeds[x] |= uRandom;
  80         g_u64EpSigSeeds[x] &= ~1;
  81     }
  82
  83     //
  84     // Foreach square on the board.
  85     //
  86     for (x = 0; x < 128; x++)
  87     {
  88         //
  89         // For both colors
  90         //
  91         FOREACH_COLOR(z)
  92         {
  93             //
  94             // Do the pawn sigs
  95             //
  96             uRandom = randomMT();
  97             uChecksum ^= uRandom;
  98             g_u64PawnSigSeeds[x][z] = (UINT64)uRandom << 32;
  99
 100             uRandom = randomMT();
 101             uChecksum ^= uRandom;
 102             g_u64PawnSigSeeds[x][z] |= uRandom;
 103             g_u64PawnSigSeeds[x][z] &= ~1;
 104
 105             //
 106             // Do the piece sigs
 107             //
 108             for (y = 0; y < 7; y++)
 109             {
 110                 uRandom = randomMT();
 111                 uChecksum ^= uRandom;
 112                 g_u64SigSeeds[x][y][z] = (UINT64)uRandom << 32;
 113
 114                 uRandom = randomMT();
 115                 uChecksum ^= uRandom;
 116                 g_u64SigSeeds[x][y][z] |= uRandom;
 117                 g_u64SigSeeds[x][y][z] &= ~1;
 118             }
 119         }
 120     }
 121
 122     //
 123     // For all castle permissions
 124     //
 125     for (x = 0; x < 16; x++)
 126     {
 127         uRandom = randomMT();
 128         uChecksum ^= uRandom;
 129         g_u64CastleSigSeeds[x] = (UINT64)uRandom << 32;
 130
 131         uRandom = randomMT();
 132         uChecksum ^= uRandom;
 133         g_u64CastleSigSeeds[x] |= uRandom;
 134         g_u64CastleSigSeeds[x] &= ~1;
 135     }
 136
 137     //
 138     // Make sure we got what we expected.
 139     //
 140     if (uChecksum != 0xac19ab2b)
 141     {
 142         UtilPanic(DETECTED_INCORRECT_INITIALIZATION,
 143                   NULL,
 144                   "signature system",
 145                   (void *)uChecksum,
 146                   (void *)0xac19ab2b,
 147                   __FILE__, __LINE__);
 148     }
 149 }
 150
 151
 152 UINT64
 153 ComputePawnSig(POSITION *pos)
 154 /**
 155
 156 Routine description:
 157
 158     Given a board, recompute the pawn signature from scratch.
 159
 160 Parameters:
 161
 162     POSITION *pos
 163
 164 Return value:
 165
 166     UINT64
 167
 168 **/
 169 {
 170     register COOR c;
 171     PIECE p;
 172     UINT64 u64Sum = 0;
 173
 174     FOREACH_SQUARE(c)
 175     {
 176         if (!IS_ON_BOARD(c)) continue;
 177
 178         p = pos->rgSquare[c].pPiece;
 179         if (IS_PAWN(p))
 180         {
 181             u64Sum ^= g_u64PawnSigSeeds[c][GET_COLOR(p)];
 182         }
 183     }
 184     return(u64Sum);
 185 }
 186
 187
 188 UINT64
 189 ComputeSig(POSITION *pos)
 190 /**
 191
 192 Routine description:
 193
 194     Given a board, recompute the main signature from scratch.
 195
 196 Parameters:
 197
 198     POSITION *pos
 199
 200 Return value:
 201
 202     UINT64
 203
 204 **/
 205 {
 206     register COOR c;
 207     UINT64 u64Sum = 0;
 208     PIECE p;
 209
 210     FOREACH_SQUARE(c)
 211     {
 212         if (!IS_ON_BOARD(c)) continue;
 213
 214         p = pos->rgSquare[c].pPiece;
 215
 216         if (!IS_EMPTY(p) && !IS_PAWN(p))
 217         {
 218             ASSERT(IS_VALID_PIECE(p));
 219             u64Sum ^= g_u64SigSeeds[c][PIECE_TYPE(p)][GET_COLOR(p)];
 220         }
 221     }
 222
 223     //
 224     // Update the signature to reflect the castle permissions and ep
 225     // square at this point.
 226     //
 227     u64Sum ^= g_u64CastleSigSeeds[pos->bvCastleInfo];
 228     u64Sum ^= g_u64EpSigSeeds[FILE(pos->cEpSquare)];
 229
 230     //
 231     // Update the low order bit to reflect the side to move.
 232     //
 233     if (pos->uToMove == WHITE)
 234     {
 235         u64Sum |= 1;
 236     }
 237     else
 238     {
 239         u64Sum &= ~1;
 240     }
 241     ASSERT((u64Sum & 1) == pos->uToMove);
 242
 243     return(u64Sum);
 244 }