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!
Zobrist alternative?
Moderators: hgm, Rebel, chrisw
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
- Posts: 411
- Joined: Thu Dec 30, 2010 4:48 am
Re: Zobrist alternative?
Rather than storing the table you could use a fast pseudorandom function and just feed it the seed for the value you want.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Zobrist alternative?
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.
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.
Last edited by Daniel Shawul on Tue Jun 12, 2012 10:28 pm, edited 1 time in total.
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: Zobrist alternative?
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.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Zobrist alternative?
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.
I have no explanation for this; it was just an observation.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Zobrist alternative?
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 wrote:...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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Zobrist alternative?
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).hgm wrote: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 wrote:...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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Zobrist alternative?
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:
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.
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.
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
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
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Zobrist alternative?
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 ..
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
Re: Zobrist alternative?
why not: key(piece,square) := key(piece, column) ^ key(piece, row)