Author: Dieter Buerssner
Date: 17:37:50 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 depends, how you define things. You use the same number as key and for index calculation. So, with 32 bits, and 2^20 entries, you actually only have a hash key of 12 bit. I think often, for example in Dennis Breuker's thesis, the terminoligy is used differently, than you use it here. >it is harder to make the root score change, but it will in a critical case. In some runs I have found not a case with 16 bit hash keys (index is independent of this), where the root move changed. But there were a lot of collisions detected. IIRC even with 12 bit hash keys, no root move changed. Regards, Dieter
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.