Anyone know of a good detailed document or website that explains Zobrist keys and the Zobrist hash function?
From what little that I've read it sounds like it uses bitboards, so can you use it even if your engine doesn't use bitboards?
I'm tinkering with various hash functions I'm finding online and so far with a 5.6 million board state dataset I'm getting collision rates from 15% even as high as 65%.
-Josh
Zobrist Hashing
Moderators: hgm, Rebel, chrisw
-
jshriver
- Posts: 1342
- Joined: Wed Mar 08, 2006 9:41 pm
- Location: Morgantown, WV, USA
-
Greg McGlynn
Re: Zobrist Hashing
Here's the chess programming wiki's take: http://chessprogramming.wikispaces.com/Zobrist+Hashing
It has some links to other pages too.
Zobrist keys don't have anything to do with bitboards, unless maybe you want them too. The idea is that you have a random sequence of 32 or 64 bits (not a bitboard!) associated to each possible feature of the position: i.e. pawn on e6, or knight on e7, or en-passant target square at f3, or white to move. Then you construct a key corresponding to an overall position by XORing together all the bit sequences corresponding to the features. This gives you a pseudo-unique key corresponding to the position as a whole (the probability of two random positions hashing to the same 64-bit number is 2^-64, if you do it right). Thus if you calculate the Zobrist key for a position and find it's the same as one you calculated earlier, you can be virtually certain that the current position is identical to the earlier position.
It has some links to other pages too.
Zobrist keys don't have anything to do with bitboards, unless maybe you want them too. The idea is that you have a random sequence of 32 or 64 bits (not a bitboard!) associated to each possible feature of the position: i.e. pawn on e6, or knight on e7, or en-passant target square at f3, or white to move. Then you construct a key corresponding to an overall position by XORing together all the bit sequences corresponding to the features. This gives you a pseudo-unique key corresponding to the position as a whole (the probability of two random positions hashing to the same 64-bit number is 2^-64, if you do it right). Thus if you calculate the Zobrist key for a position and find it's the same as one you calculated earlier, you can be virtually certain that the current position is identical to the earlier position.
-
wgarvin
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: Zobrist Hashing
From the wayback machine, here is Bruce Moreland's old page explaining Zobrist keys.
Its just a convenience that 64-bit numbers are used for the Zobrist hash.. you could use any number of bits, but more bits means less chance of a collision. For chess engines, 32 bits is not enough to avoid getting tonnes of collisions, but 64 is enough.
Edit: also, don't rely on the C library function rand(), most existing implementations of it really suck. Something like the Mersenne twister is much better. If you include your own PRNG in your chess engine, then you can guarantee that it will generate the exact same "random" keys on every platform (which is nice if you want to use them as keys in your opening book for example). There are lots of PRNGs to choose from, almost anything is better than rand().
There have been several threads about Zobrist keys here. Search for the word "hamming" to find a bunch of them (it always gets mentioned...)
Its just a convenience that 64-bit numbers are used for the Zobrist hash.. you could use any number of bits, but more bits means less chance of a collision. For chess engines, 32 bits is not enough to avoid getting tonnes of collisions, but 64 is enough.
Edit: also, don't rely on the C library function rand(), most existing implementations of it really suck. Something like the Mersenne twister is much better. If you include your own PRNG in your chess engine, then you can guarantee that it will generate the exact same "random" keys on every platform (which is nice if you want to use them as keys in your opening book for example). There are lots of PRNGs to choose from, almost anything is better than rand().
There have been several threads about Zobrist keys here. Search for the word "hamming" to find a bunch of them (it always gets mentioned...)