Author: Robert Hyatt
Date: 07:07:33 05/29/99
Go up one level in this thread
On May 29, 1999 at 09:53:43, Dave Gomboc wrote: >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 In that case, just use hash(M) = M as the mapping function. :)
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.