Author: David Rasmussen
Date: 04:12:43 04/05/01
I just added partial collision detection to my hashtable. Partial, because it can't possibly find all collisions without sacrificing performance, which could be done for testing purposes, but not in real play. I just check the best move from the hash table, to see if it is indeed a pseudo-legal move in the position. If it isn't, it _must_ be a collision. On an apx. 3.000.000 node search from the initial position, I get apx. 433000 hashprobes, 30% of which are hits, and 5 collisions. On a 4.400.000 node search from fine70, I get 2936000 probes, 74% of which are hits, and 830 collisions. I have made no effort to minimize collisions, in choosing the hash components of particular pieces on particular squares etc., even though we had a thread about it a couple of months ago. My testing seems to indicate that 800 randomly generated 64-bit words will very easily have a hamming distance of 15-16, but above 24 is very hard. And I don't believe that hamming distance tells the whole story anyway. I am using the Mersenne Twister as PRNG, so nothing is wrong with the PRNG. 1. Are these collision numbers higher than usual? 2. If not, how come the search in most other programs, like crafty, doesn't suffer mentionable from this? My hashtable works fine in the many tests I have done. So there seems to be no problem in practice. I am just wondering how things can work with so many collisions.
This page took 0.01 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.