Author: Dann Corbit
Date: 13:25:37 04/07/04
Go up one level in this thread
On April 07, 2004 at 08:33:59, Renze Steenhuisen wrote: >On April 07, 2004 at 08:27:59, martin fierz wrote: > >>On April 07, 2004 at 06:49:59, Renze Steenhuisen wrote: >> >>> >>>Hi all, >>> >>>could someone give me some numbers that are common with hashkey collisions? >>>Because I guess my % is little too high... >>> >>>I'm getting like 0.03% [which is 1 every 3000, if I'm not mistaken] >>> >>>This is when using TT=32MB (haven't got the exact number of entries) >>> >>>If you think it is an error, any suggestions on where to start looking? >>> >>>Thanks! >>> >>> Renze >> >>hi renze, >> >>your number is much too high. a good estimate for the hash collision probability >>is 1/sqrt(hashkey_range); which in your case comes out as 2^-32 or about >>somewhere around one in a billion... >> >>make sure you're not doing anything wrong with the hashkey updating like >>suggested by others - compare with a computed-from-scratch key. also make sure >>that your nullmove doesn't break your hashkey. and just to be sure, check that >>you haven't got 32-bit numbers instead of 64 bit numbers by accident... >> >>cheers >> martin > >I am using uint64_t for that (standard C), so it is 64-bit... > >I'm going to verify (just to make sure) the incremental with the from-scratch >key, so I'll post with in the hour an update... > >one in a billion was what I recollected from previous posts (long time ago), so >I remembered correctly If you are using a 64 bit hash, the expected collision is one per sqrt(2^64)*1.17 = 1.99e-10 probability of collision. From the frequency of your collisions, I wonder if you are using just the modulus remainder as your hash (and not storing the other part). That would explain the absurd collision rate. Another possibility is a bad hash algorithm. What algorithm are you using to compute the hash? For instance the algorithm in K&R C is a real stinker.
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.