Author: David Rasmussen
Date: 04:56:20 04/05/01
Go up one level in this thread
On April 05, 2001 at 07:45:51, Matt McKnight wrote: >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. > Well, it takes longer to check for actual legality, as one has to ensure that the move doesn't leave the king in check. >>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 I know, but I will test with crafty when I get home. My hashing scheme is very similar to craftys, and the random numbers used in crafty are not checked in anyway, so I think crafty (and others) are experiencing the same thing, unless I have bugs.
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.