Author: Matt McKnight
Date: 04:45:51 04/05/01
Go up one level in this thread
On April 05, 2001 at 07:12:43, David Rasmussen wrote: >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. why pseudo-legal... just check for legality period, because you shouldn't be inserting anything other than legal moves into the HT. >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. I use a 64 bit key also, but I have never seen a collision. I think according to Dr. Hyatt, it could only ever happen once a year. Matt
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.