Author: Robert Hyatt
Date: 21:06:09 05/28/99
Go up one level in this thread
On May 28, 1999 at 19:33:55, vitor wrote: >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. I don't follow. The definition of hashing is to take an N bit quantity, and turn it into an M bit quantity, where N > M. Otherwise it isn't 'hashing' it is 'mapping'. There is no way to 'perfectly' squash N bits into M bits, when N > M.
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.