On-the fly hash key generation?

[Aleks Peshkov]

Aleks Peshkov seems to have tried a scheme for normal Chess where you had just 12 hash keys, one for each piece type, and then rotated those by the square number:

Zobrist(piece, square) = key[piece] << square | key[piece] >> 63-square;

n << sq | n >> (64-sq);

Opposite side pieces encoded as ~bswap(k). So two same pieces either same or opposite colors on the same square has exactly 0 hash.

I have 7 keys. One extra key is necessary to encode en-passant and Chess960 castling rights.

[hgm]

One idea could be to share 7 of 8 bytes (or 4 of 8...) with the next key, thus saving roughly 7/8 of memory. If this works, should suffice for wildest chess variants.

Indeed, micro-Max and Shokidoki do this. Shokidoki because with an 81-square board and 2x14 piece types a full Zobrist table would provide a rather heavy cache load (28x81*8 = 18KB, while at the time the usual L1 size was still 16KB). In micro-Max mainly because the rand() function delivered only 16-bit values, so that it would be a lot of work to fill 8-byte variables.

Code: Select all

int BOARDSIZE=256;
char T[8200];

// during the engine initialization
 N=32*BOARDSIZE+7;while(N-->BOARDSIZE+3)T[N]=rand()>>9;

// access
*(int*)(T + square + BOARDSIZE*pieceType)

Note this acces them as 32-bit integers, because micro-Max keeps the two halves of the hash key in separate variables (one used for indexing, the other stored in the entry as signature). The second key is then using square+4 instead of square for its update.

If you would want to do 64-bit acces, you would just have to write *(long long int*) in stead of *(int*). The unaligned accesses turned out to have no speed penalty as long as they do not straddle two 64-byte cache lines. If they do, it just requires an extra cycle. But with 0x88 square numbering there is no need to ever straddle a cache line.

However, with 2x100 piece types and 625 board squares it would still require 125KB, far exceding L1. So I did not consider it suitable for HaChu.

[AlvaroBegue]

I wonder if you could make them independent enough, that way. If you would have an additive key, rather than and XOR key, this would certainly not work. As the pieceType*BOARD_SIZE + square attains any value, so there would always be a pair of pieces with low piece types that would add up to a value still in the range that could be reached by a single piece with a large pieceType. And the MAGIC multiplication then would not change that.

So apparently the scheme hinges on the rather subtle difference between XOR and addition.

Of course this is true. The purpose of my formula was to compute a hash of the number (piece_type * BOARD_SIZE + square) in some quick and dirty way. I ran a simple test and I found out these linear relations are more problematic than I expected.

Here's my simple test: To see how good a table of 64*12 32-bit numbers is at not producing collisions, I try to find sets of 4 different indices whose entries XOR to 0.

If the table were filled up with 32-bit random integers, you expect the number of such sets to be around 5 (I simply measured this experimentally). Using the formula I proposed, I get numbers in the thousands. So that's not very good. I tried a few other things and this one seems to be good:

h = piece_type * BOARD_SIZE + square + 1;
return (h * (h + MAGIC1)) * MAGIC2;

A particular choice of constants that works very well is MAGIC1 = 16045690984833335023 and MAGIC2 = 11400714819323198485.

[AlvaroBegue]

Another idea: Just use the mixing function of MurmurHash2.

h = piece_type * BOARD_SIZE + square;
h *= 0xc6a4a7935bd1e995ULL;
h ^= h >> 47;
h *= 0xc6a4a7935bd1e995ULL;

This works really well with my test: Only 1 collision if I use the lower 32 bits, 2 if I use the higher 32 bits.

[hgm]

Now the question is, how many arithmetic operations are you willing to do to replace one table lookup. If the size of the table is no issue, I think a memory load is not any slower than a multiply, and it would just depend on whether the multiply unit or the memory unit is more in demand by the rest of your program.

Aleks' method with a table of just 7 keys, seems rather hard to beat. Even when you extend it to 32 piece types, the amount of storage required is still totally negligible. Extending the number of board squares would be less straightforward, though. Perhaps using the higher-order bits of the square number as part of the index for the piece key.

[AlvaroBegue]

Now the question is, how many arithmetic operations are you willing to do to replace one table lookup. If the size of the table is no issue, I think a memory load is not any slower than a multiply, and it would just depend on whether the multiply unit or the memory unit is more in demand by the rest of your program.

Aleks' method with a table of just 7 keys, seems rather hard to beat. Even when you extend it to 32 piece types, the amount of storage required is still totally negligible. Extending the number of board squares would be less straightforward, though. Perhaps using the higher-order bits of the square number as part of the index for the piece key.

EDIT: Never mind. I implemented a buggy version of Aleks's idea.

[Aleks Peshkov]

Aleks' method with a table of just 7 keys, seems rather hard to beat.

But you have to explore a better key set then random.

I personally brute-force test a subset of Zobrist numbers with decent Hamming Distances to find a key combination. They seems to be as good (and probably better) as random 800 keys, but I do not know a good metric how to prove.

[hgm]

A suitable quantitative measure of the quality of a set of keys could be the number of 6-key dependencies you could detect on several (randomly picked, but then kept fixed) subsets of the bits, chosen to have sufficiently few bits that you actually expect a fair number of such dependencies.

The 6-key dependencies are efficiently detected by storing all combinations of 3 different keys in a hash table. If two combinations map to the same entry, you found a 6-key dependency. For a set of 800 keys there are 800^3/6! = 21M 3-key combinations (170MB). According to the birthday paradox that makes 220e12 collision attempts. So you should start to see collisions when you consider 48-bit sub-sets of the key, and get a fair number when you consider 44-bit subsets.

[mar]

n << sq | n >> (64-sq);

That's an awesome idea!
Rotations will be folded into just one instruction on x64, cutting down memory requirement to practically a negligible amount (nearly by a factor of 64).
Does it work well in your engine compared to traditional full tables?
I can imagine it might work very well.

[Aleks Peshkov]

n << sq | n >> (64-sq);

That's an awesome idea!
Rotations will be folded into just one instruction on x64, cutting down memory requirement to practically a negligible amount (nearly by a factor of 64).
Does it work well in your engine compared to traditional full tables?
I can imagine it might work very well.

We are talking about micro-optimizations. I could not measure the speed difference between rotation and full table version.

I wanted to skip random factor from Zobrist keys and hoped to find better keys. The set of just 7 numbers is much easier to optimize.