Author: vitor
Date: 16:33:55 05/28/99
Go up one level in this thread
On May 28, 1999 at 18:50:06, Dann Corbit wrote: >On May 28, 1999 at 18:34:18, Dave Gomboc wrote: > >>On May 28, 1999 at 18:07:17, vitor wrote: >> >>>as far as i can tell, zobrist hashing seems to be an imperfect(but fast) hashing >>>scheme, meaning it is possible that your program will mistake position X as >>>position Y. >>> >>>so my question is: >>>is zobrist hashing the current standard in computer chess? is it just an >>>accepted risk or are there any perfect hashing schemes that are used? >> >>Yes, it is the current standard... and an accepted risk. That risk can be >>minimized by using a large enough key. 64 bits is pretty normal today, though >>some people use 32+tricks, or 48+tricks. (Tricks like checking the best move to >>make sure it's legal in the position, which is probably a good idea in any >>event. :-) I don't know of anyone using a perfect hashing scheme for a playing >>program, but this doesn't mean it isn't possible. >For a perfect hashing scheme, the width of the key will have to be log2(possible >positions) bits wide. We could use it as our mapping to all possible chess >positions. If anybody finds one, please let me know. ;-) > >BTW, that would be one whopper of a hash table! even with a simple position represention of 256 bits, we would have perfect hashing that is about 4 times more expensive (both memory and speed-wise) than a 64bit zobrist. maybe perfection for $4 is too much when you can get good enough for $1.
This page took 0.01 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.