Author: David Rasmussen
Date: 15:00:36 04/05/01
Go up one level in this thread
On April 05, 2001 at 09:22:26, Robert Hyatt 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. > >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. > Of course not. But you don't check in the probe, if the move stored, is legal even if the hashkeys match. So if you get a cutoff, you never get around to checking whether the move was actually legal or not. So you might have collisions after all. > >> >>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. > > It's nice to know that it is not supposed to happen. Then I know what to look for. Still, I don't believe I have a bug (unless I find one ;) ). Instead, I fear I have to bad hashkey components, as mentioned elsewhere. >> >>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 know that. I didn't say that a certain minimum hamming distance wasn't required. I just said that it is not the ultimate characteristic that defines good numbers. The dimension of the space spanned by the 64-bit vectors, that is, the number of them that you can make a linear combination with, and still not get one of the others, is equally important. The extended BCH code that I posted about some months ago, has a dimension of 27 if I remember correctly. That means that you can xor 27 of these numbers without getting one of the others. Thats very hard to get with just a random set. And the minimum hamming distance is also high, of course (I don't remember how high). I will try with this code some day. >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. > I did that for a minute in the beginning, but quickly realized my error. In that case, I had 30% collisions or so :)
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.