Author: Robert Hyatt
Date: 20:03:40 11/14/01
Go up one level in this thread
On November 14, 2001 at 15:53:18, Koundinya Veluri wrote: >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? Sure.. but then you are not using a 32 bit hash signature any more. You are using 32 + log2(tablesize) which is probably at least 48 bits total. For a 32 bit hash test, the classic hashing explanation in a data structures book says that you use a pure 32 bit signature, which is used for everything. > >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? Crafty uses the right N bits of a 64 bit signature, just like Cray Blitz did. which means a 64 bit signature collision also goes to the same table address... > >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 I do not get the "bad move hashed" error in _any_ games using a full 64 bit signature, and using the low order N bits as the table address...
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.