Author: vitor
Date: 11:11:50 05/29/99
Go up one level in this thread
On May 29, 1999 at 10:07:33, Robert Hyatt wrote: >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. :) ah ok, i think i understand now. perfect hashing is like saying mature rgcc. every time i said perfect hashing , i meant perfect mapping. so are there any known chess programs using perfect mapping? it really doesnt seem too much more expensive unless your a node burner like fritz.
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.