2x Faster Zobrist Hash - slightly bigger lookup

[dangi12012]

When calculation Zobrist I see the implementation is mostly like this:

Code: Select all

hash ^= Zobrist[piece][squarefrom]
hash ^= Zobrist[piece][squareto]
hash ^= Zobrist[Hash for Black to move]

First of all this is not very compatible with bitboards since this type of lookup wants to have a squarefrom and squareto in square coordinates and second of all I think there is a faster alternative:
When you look at it this is: Remove the hash FROM and Add the Hash TO. But this can be done in one operation less
The hashes stay the same - but the lookup table is expanded to include all elements of from/to possible with all pieces.

Now the math here is off but the factor should be the same:

Code: Select all

1	64
2	2016
3	41664

Nowadays a 64 slot lookup table is used. One per square - while we can easily expand this to a 2048 table (with 2016 slots maximum) to include both from + to squares for each piece type. 2016 is really much too big since no piece can jump anywhere on the board (which is how many ways can 2 bits be set in 64 bits). It will depend on the piece and pawn table will have only a few entries and queen table many more - but only a few hundred.

The code would look like this:

Code: Select all

hash ^= (Zobrist[piece][squarefrom << 6 | squareto] | Hash for Black to move)

This is not done only because its faster but for bitboards where you have from and to square bits in the same uint64_t. All 2016 possibilities can be perfectly hashed into a lookup table of size 2048. Then a zobrist operation in bitboards can look like this:

Code: Select all

hash ^= (Zobrist[(fromto * pieceseed) >> 53] | Hash for Black to move)

Yes it also depends on the piece that is taken but thats not too difficult to include too. As long as its only (target piece killed + piece from + piece to) it fits in a few hundred slots anyway (per square).

Which is a bigger lookup - but could be in included in the same table as the general attack table (because we find the pieceseed) and thus its cached all the time.

[hgm]

I usually optimize in the opposit way: make the Zobrist table smaller (to make sure everything fits in the L1 cache). In micro-Max I use overlapping Zobrist keys, (so that they effectively only require one byte per key), by accessing the table as *(uint64_t *)(Zobrist + sqr), while Zobrist[] was defined as an array of char.

I sometimes also use 'on-the-fly' calculation of keys, pieceKey[piece]*squareKey[sqr], so that I only need number-of-pieces + number-of-squares instead of the product. (And the keys can be made 32 bits, while still getting a 64-bit key in total. This is especially helpful in variants with many piece types and large boards.

Note that the flipping of the side-to-move key can actually be eliminated, by giving (the same) non-zero key to empty squares. All moves are then treated as captures, the non-captures 'capturing' the empty square.