Author: Robert Hyatt
Date: 14:48:21 05/29/99
Go up one level in this thread
On May 29, 1999 at 14:11:50, vitor wrote: >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. I don't know of any. Years ago most did... Cray Blitz broke the tradition and used the simple 64 bit hash signature. Chess 4.x, Duchess, etc all used the full encoded position for transposition table verification.
This page took 0 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.