Author: Dan Newman
Date: 17:56:02 12/07/01
Go up one level in this thread
On December 07, 2001 at 14:57:52, Frank Phillips wrote: >On December 06, 2001 at 21:13:35, Dan Newman wrote: > >>On December 06, 2001 at 17:29:43, Severi Salminen wrote: >> >>>Hi >>> >>>How many collisions crafty gets on average using 32-bit keys? So how many nodes >>>Crafty searchs on average to get 1 collision? I'm now using plain Visual C++ 6.0 >>>rand() with no hamming distance tests and I get about 80 collisions out of >>>10'000'000 evaluations from initial position. I'd like to know if that is more >>>or less than Robert and David were seeing. Funny thing was that first I searched >>>about 5'000'000 nodes with no collisions, then I saw 40 collisions in a short >>>time, then again no collisions and finally 40 more in a short time. >>> >>>Severi >> >>I did this test on my program, Shrike, and got 62 collisions out of >>66 million pawn hash probes with a 32-bit hash code, so I get about >>1 collision per million probes. This was on the WAC test suite and >>so may vary in actual games... >> >>-Dan. > >I store the lower 32bits as the hash key and use (some of) the top bits as the >index. This is effectively more than 32bits, but I feel I now feel the need to >check it is enought. > That's exactly what I do. I typically have an 18-bit index (taken from one half of the 64-bit hash code) plus the 32-bit key, which gives an effective 50 bits of hash code. I calculate the full 64-bits, so I could use the whole thing (and may do so if it doesn't hurt the speed too much). I haven't run a long test yet to test the 50-bit code. >How did you test for clashes: did you store the board along with the hash entry >and check that the position on the board and stored board were the same - or is >there a smarter way? > >Frank For testing I just modified the code to calculate the pawn evalation even when there is a hit from the pawn hash table and then compare results. I guess a more sure way of getting an exact collision count or rate would be to store the pawn structure itself in the table (easy to do with bitboards), but the score is enough to show that 32 bits isn't enough to prevent collisions. As to whether the collisions matter, I don't know, but I suspect they could cost the occasional game. It's quite possible that a 32-bit pawn hash code would have a negligible effect on ELO, but the idea of losing the occasional game at random due to this is enough to make me want to eliminate the collisions :). -Dan.
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.