Author: Robert Hyatt
Date: 06:22:26 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. I do this also. I can't stand to make an illegal move as it can create a new piece and screw things up badly. > >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. You have a bug. Or you are not using a 64 bit hash signature. I just checked 300 log files from games played on ICC. If I detect an illegal move as above, I write an entry to the log file. I had _zero_ such entries in the log file. > >On a 4.400.000 node search from fine70, I get 2936000 probes, 74% of which are >hits, and 830 collisions. I get zero here if I let it search for 30 minutes. > >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. It actually does. Just use 800 numbers with a hamming distance of 1 between them and see what happens to your illegal move counter. > >I am using the Mersenne Twister as PRNG, so nothing is wrong with the PRNG. > >1. Are these collision numbers higher than usual? Yes they are. My number is _zero_ over the 300 games I gave above. If I see the "bad move from hash table" message, I assume a bug. It always is. >2. If not, how come the search in most other programs, like crafty, doesn't > suffer mentionable from this? Easy. It isn't getting that many collisions. :) Perhaps you are screwing up and storing a best move in a fail-low position, and where you get that move is the problem since there is no best move there. > >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. Believe me, it is _not_ working fine. You have a serious bug that you need to find as that many collisions will certainly cause problems.
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.