Author: Dave Gomboc
Date: 06:53:43 05/29/99
Go up one level in this thread
On May 29, 1999 at 00:06:09, Robert Hyatt wrote: >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. I am confident he meant the case where N = M... the "null" hash. :-) Dave
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.