Author: Robert Hyatt
Date: 19:28:02 11/14/01
Go up one level in this thread
On November 14, 2001 at 20:37:50, Dieter Buerssner 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 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. I don't think that you can define a 32 bit signature any other way. If you store 32 bits, and use a different set of bits for the address, you are using more than 32 bits, plain and simple. > >>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 Goes to show how robust a really big tree search is to odd wrong scores...
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.