Author: Koundinya Veluri
Date: 12:53:18 11/14/01
Go up one level in this thread
On November 14, 2001 at 14:16:49, Robert Hyatt wrote: >On November 14, 2001 at 03:52:31, Uri Blass wrote: > >>On November 14, 2001 at 02:37:45, Dann Corbit wrote: >> >>>On November 14, 2001 at 02:03:47, Gian-Carlo Pascutto wrote: >>> >>>>On November 13, 2001 at 19:34:44, Dann Corbit wrote: >>>> >>>>>64 bits is generally recognized as a good size for a hash, and 32 bits is >>>>>*definitely* too small. >>>> >>>>I am still eagerly waiting to see someone actually produce >>>>valid proof for this claim. >>> >>>Some programs may have a much bigger problem (e.g. fast searchers). >>>Imagine a program that searches 1M nodes/second. There are plenty that can >>>manage that, on steamy hardware. >>>In 1000 seconds, there are 1 billion nodes, and in 4000 seconds (a bit over an >>>hour) a 32 bit integer has been exhausted. By this time, it is absolutely sure >>>to have collisions. Now, imagine a correspondence player, letting the computer >>>think overnight. Each position will have been randomly overwritten 20 times a >>>day (roughly speaking). >>> >>>I saw a rough mathematical justification somewhere (but I can't remember where >>>it was). >> >>It is not a proof. >>A valid proof is to show that the same available program practically generate >>worse moves with 32 bits for hash. >> >>Uri > > >This is _a_ proof. And it was done a few years ago. On longer runs on a Cray, >I got horrible results using 32 bit hash signatures. The first thing that was >noticable was that the hash move validation code complained often. As in >hundreds of thousands of times in endings (per minute). And scores also changed >and best moves changed. Note that this was not a parallel run so SMP issues >were not present. > >It should be easy to test on Crafty with no problems... just take the >initialization code and AND every random number with 2^32 - 1, and leave >everything else alone... > >I tried it just on fine #70 and got thousands of "bad move hashed" error >messages, which means a hash signature matched but the move was not illegal, >indicating a collision. > >it is harder to make the root score change, but it will in a critical case. Hi Bob, I have a question. If the hash table index is computed from the hash of the position then wouldn't collisions happen a lot more often than if the index is computed independantly of the hash key? If two positions have an identical hash key, then the indeces generated from this key (say by taking the lowest 8 bits) will also be identical and therefore the positions hash into the same index in the hash table, causing a collision. However, if the indeces are generated independantly of the hash keys, chances are that the indeces of the two positions won't also be identical, so the positions won't be stored in the same index, which doesn't cause a collision. So to get a collision with this, the position hash keys must be identical and the indeces must also be identical, which is far less probable. How do Cray Blitz and Crafty generate the indeces? I was just trying the two methods with my program (which uses 64-bit hash keys) and I'm noticing a lot of collisions after changing my code to generate the indeces from the position hash keys. It could be but I doubt that it is a bug, because if I disable the "try hash move before generating moves" code, then there are no errors. Regards, Koundinya
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.