Author: Robert Hyatt
Date: 07:06:25 05/29/99
Go up one level in this thread
On May 29, 1999 at 05:01:02, vitor wrote: >On May 29, 1999 at 00:03:09, Robert Hyatt 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? >> >> >>The term "perfect hashing scheme" is an oxymoron. There is no such animal, >>_by definition_. Because you are reducing an N-bit quantity (if I recall, >>from a mathematical discussion a few years ago, a chess board can be >>represented in something just over 160 bits [I have not followed the discussion >>here as this isn't a burning issue with me]) to an M-bit quantity, where >>N >> M. IE I hash using 64 bits everywhere... which means there is _no_ way >>to represent a chess board accurately in only 64 bits... since the original is >>> 64 bits... > >im probably using the wrong terminology. what i meant by perfect hashing is that >every position gets a unique id key. without a unique key as in zobrist, a >program might mistake a collision for a match. No.. your terminology was ok... but if it takes 160+ bits to represent a complete chess position, then reducing it to something less is, by necessity, a 'lossy' operation. And you will end up with several different 160+ bit positions that hash to the same 64 bit hash signature. If you have an M-bit position, and hash to an N-bit hash signature (M > N) then each hash signature should have M/N 'collision' points. with 64 bits, it is rare enough to ignore. With 32 bits, it will kill you...
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.