Zobrist alternative?

[hgm]

Normally we construct a hash key by adding (or XORing) a number of Zobrist keys from a two-dimensional table key[coloredPieceType][square]. Now is the board gets large, and the number of piece types gets large too, this table would becoe intolarably large. For instance, in Taikyoku Shogi the board is 36x36 (1296 squares), and each side has 209 piece types (with somewhat less promoted types). That would make some 700,000 keys, which for a 64-bit key would require 5.6MB! That would not even fit the L2 or L3 cache! (OK, perhaps it can be compressed to 1 byte per key, by overlapping them, but that still nearly fills the L2 cache of the smaller CPUs....)

Do there exist less memory-hungry techniques for producing a hash key? E.g. if I would factorize the individual keys,

key[coloredPieceType][square] = key1[coloredPieceType]*key2[square]

so that I could do that multiplication during key update, would that result in any undesirable effects? I could not think of any obvious disadvantage, provided the key1 and key2 arrays are thoroughly random, with a range much larger than the number of pieces or squares (so that any pair of keys is extremely unlikely to have the same difference).

I'd much rather use a 10.4KB and a 4.8KB table, and do a multiplication in MakeMove, than having to access a 5.6MB table. Multiplications are pretty cheap, nowadays!

[kbhearn]

Rather than storing the table you could use a fast pseudorandom function and just feed it the seed for the value you want.

[Daniel Shawul]

Fortunately I didn't encounter such a high number of pieces, so other than the need to generate random number at runtime, I didn't need to reduce table size. I am sure the idea of hasing bitboard files/rank & diagonal states is used in some of the bb techniques to reduce table size. Your method that hashes the piece type and square should work fine in general I think but quality may not be good as multiplication can reduce number of set bits in the lower parts of the hash key. I think if the formula is modified as key[piece] * magic_number + key[square] it would look like an LCG generator. But I am not saying that this has advantages over what you are using. Ofcourse another way is to generate a unique set of random numbers every time the hashkey is required, but for efficiency nothing more than an LCG I think. That will have only one multiplication as the method you use now.

Edit
First I wrote about using one hashkey : key[piece] * magic + square but this will probably fail very badly. I am not sure if you do an "add" or "xor" to get your keys so an operation like multiplication should not have a problem I guess.

[wgarvin]

You can divide table size by 64 by using 6 of the input bits to rotate the 64-bit key from the zobrist table. My quick math suggests your Taikyoku Shogi zobrist table would then be around 66.2 KB.

[hgm]

I have bad experience with shifting keys by only 1 bit. I tried it in a simulator, and it drove up the number of key collisions enormously. When rotating keys by bits I could not detect any difference in collision statistics with truly random keys.

I have no explanation for this; it was just an observation.

[hgm]

...l I think but quality may not be good as multiplication can reduce number of set bits in the lower parts of the hash key.

This is a good point. When 50% of the factors has their last bit zero, only 25% of the products would have it 1. So perhaps I should bias the factors to have fewer trailing zeros. Like initializing the tables by ~rand()*rand(), which would only have 25% end in a zero. Then of their product 9/16 would end in 1. (Actually 1/4 in 00, 5/16 in 01, 3/16 in 10 and 1/4 in 11, which is much closer to complete randomness.)

[Daniel Shawul]

...l I think but quality may not be good as multiplication can reduce number of set bits in the lower parts of the hash key.

This is a good point. When 50% of the factors has their last bit zero, only 25% of the products would have it 1. So perhaps I should bias the factors to have fewer trailing zeros. Like initializing the tables by ~rand()*rand(), which would only have 25% end in a zero. Then of their product 9/16 would end in 1. (Actually 1/4 in 00, 5/16 in 01, 3/16 in 10 and 1/4 in 11, which is much closer to complete randomness.)

I think that is a good solution with an explanation. By the way are key1 and key2 also 64 bits? In that case it means a 128bit hash key is required to store the result. Ofcourse we have only the lower 64 bit as a hash key and I don't know how that would affect ,if at all, the quality of the resulting key. If the multiplier key is not a prime (worst case being power of 2), then the lower bits would be all zero (or garbage I am not sure).

[Daniel Shawul]

I took an extra interest in this and wrote a little test code. I measured the frequency of the lowest 8 bits using rand(). Rand() gives 50% chance for all bits . That reminds me that last time I forgot to take the highest bits after MAD in my LCG, I got bad results at the opening position using monte carlo simulation when it should have been 50%. Anyway here are the results after 10million trials, using rand() that returns short integer:

Code: Select all

rand()         r1=~rand() * rand()      r1 * r2 
1   0.500015   0.249955              0.06296 
2   0.499983   0.375055              0.155924 
3   0.500005   0.437514              0.248571 
4   0.499998   0.468718              0.328706 
5   0.499981   0.48429              0.386027 
6   0.500082   0.492275              0.427995 
7   0.499948   0.496016              0.455158 
8   0.499935   0.497959              0.472277 

If the keys for square and piece are both filled with ~rand*rand the chance that the lowest bit will get set is very small. I don't think it is possible to sustain 50% for all bits but maybe arrive at something not easily predictable. Btw do you have like a small test code to test hash collisions ? The test for frequency of bits may not directly translate to hash collision..
Edit Two problems. First, I see you may have meant r1 = rand() multiplied with ~r1, different from what I did above which generates new random number for the latter too. So I could have just multiplied two random numbers without negating. Problem is this new one always gets a 0 for the least significant bit. Maybe a shift by 1 will solve this as the rest seem be set at 50% chance except for the highest bits.
Second it seems that the highest bits are also affected in a similar way. I measure frequency of all the 30 bits. Rand max is 0x7fff so only 30 bits of the product could be set.

Code: Select all

Bit   [r1=rand(),r2=rand()]    [r1=rand(),r2 = (~r1) & 0x7fff] 
1   0.250054   0.000000 
2   0.374985   0.500005 
3   0.437510   0.499987 
4   0.468870   0.500044 
5   0.484449   0.499945 
6   0.492297   0.500008 
7   0.496262   0.500049 
8   0.498176   0.500159 
9   0.498911   0.499984 
10   0.499621   0.499799 
11   0.500088   0.500017 
12   0.500143   0.499806 
13   0.500047   0.499941 
14   0.499961   0.500114 
15   0.499888   0.500181 
16   0.499835   0.503597 
17   0.499586   0.502350 
18   0.499757   0.507884 
19   0.499498   0.510974 
20   0.498695   0.516191 
21   0.497637   0.522700 
22   0.495937   0.532792 
23   0.492516   0.545493 
24   0.486483   0.563126 
25   0.475728   0.587190 
26   0.456686   0.618694 
27   0.424067   0.658800 
28   0.370417   0.707027 
29   0.284377   0.000000 
30   0.153438   0.000000 
31   0.000000   0.000000 
32   0.000000   0.000000 

Edit 2 I think it can be assumed (r * ~r) gives good uniform distribution for the lowest half of the bits. I tested it on U64 and that is the case.

[Daniel Shawul]

From the available operations, those that sustain uniform distribution of bits are : add , sub , xor. The rest i.e mul, div,and,or all change the distribution in some way. So a hash table constructed with the latter operators will show some clustering unlike those that maintain uniform distribution. Why not mix the first group of operators (say add and xor ) to get a key like this : key = key1[piece] + key2[square] and then use xor to form the final key for the position. I am not sure if add and xor are "dependent" somehow so this may not work. For example, if I just used an add for all operations, then a position like : Bishop at d4 Pawn at c3 will be equivalent to Bishop at c3 and Pawn at d4... An xor for the final hash key will solve this problem, but I am not sure. Anyway I just wanted to clearly describe what the problem is ..

[smrf]

why not: key(piece,square) := key(piece, column) ^ key(piece, row)