Author: Dieter Buerssner
Date: 11:58:03 12/08/02
Go up one level in this thread
On December 08, 2002 at 13:55:12, Sune Fischer wrote: >But for the sake of argument, you are right of course. The only way to >completely repair the problem of collisions on a full table the same size as the >key, would be to have the key large enough so as to be _unique_ for every >position. I think using 196 bits would be very close to achieving that. So there >is an easy solution if the situation one day calls for it. I agree. Some comments. Even less than 196 bits will be enough. One can encode any legal KK position including castling rights in 12 bits. For the remaining 62 squares, one can have a bit vector, that says occupied/not ocuupied (62 bits). Each occupied square can at most have 10 different states (white/black Q/R/B/P). 3 such states can practically easily be encoded in 10 bits (10^3 < 2^10). So for 30 such states, you need at most 100 bits. One bit for side to move, at most 4 bits for ep (but it should be possible to get away without those 4 bits even). Makes 12+62+100+1+4 = 189 bits. BTW. for legal chess positions, one would at most need 97 instead of 100 bits for encoding the material structure (the last piece is allways known, because there is exactly one legal material configuration for 32 pieces on the board). I guess such an encoding could even be used rather efficiently. One function could calculate a hash index from the 189 bits (Basically, it might be some pseudo random number generator, that has a state space of 189 bits or more). Further recuction will be possible, but perhaps not easy to efficiently implement. Nowadays, probalby many chess engines use 64 bit in the HT to store the Zorbrist key, and another 64 bit for other info. One would need about double size, to have no collisions at all anymore and avoid the problem for ever. All that said, I believe hash collisions (of the severe kind) play absolutely no role. They seem sometimes used as excuses for wrong moves (mainly by users, I cannot remember any author to argument like this). I don't buy that argument. Regards, Dieter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.