Author: Koundinya Veluri
Date: 20:25:38 11/14/01
Go up one level in this thread
On November 14, 2001 at 23:03:40, Robert Hyatt wrote: >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. > Ah I see, that makes a lot of sense. So for a 64 MB hash table I was actually using an 86 bit key and I never got an illegal move from the hash table. > > > >> >>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... Then it probably is a bug in my program... Thanks, 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.