Author: Robert Hyatt
Date: 11:16:49 11/14/01
Go up one level in this thread
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.
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.