Author: Will Singleton
Date: 17:47:06 04/10/02
Go up one level in this thread
On April 10, 2002 at 17:31:20, Andrew Williams wrote: >On April 10, 2002 at 15:28:26, Pat King wrote: > >>On April 09, 2002 at 12:11:08, Andrew Williams wrote: >> >>>On April 09, 2002 at 11:56:45, Pat King wrote: >>> >>>>On April 08, 2002 at 15:17:46, Robert Hyatt wrote: >>>> >>>>>How do you define "collision"? Normally this means two different board >>>>>positions produce the same hash signature. If you are getting _those_ you >>>>>have a Zobrist hashing bug. >>>> >>>>How do you detect collisions, then? Record the entire position in the hash >>>>table? Even for a debug build, that seems like it would be impractical. >>Although undetected hash bugs are even less practical :) >>>> >>> >>>You check to see if the move stored in the hash entry is legal or not. If >>>the hash keys match but the move isn't legal in the position, it means that >>>you have a hash collision. >>> >>>Andrew >> >>But you rely on the hashed positions being different enough for that move to be >>illegal. Certainly, your technique detects collisions, but not all collisions!? >> >>Pat > >Yes. I should have been clearer. I don't have any code in PM to detect >collisions. As you say, what I described wouldn't catch all collisions. > >Andrew As always seem to be the case in computer chess, there are competing definitions for the same terms (collisions of collisions, if you will). In the Dec 1996 issue of ICCAJ, Beal and Smith discuss collisions in their article on multiple-probe hashing. Your definition of a collision, if I read you correctly, is what Beal & Smith would call a false-match error (negligible, in their opinion). Collisions, otoh, they say occur when two positions gen the same hash >index<, but different keys. This, they say, can occur frequently, and requires a replacement scheme to determine which is kept and which discarded. Their definition implies than collisions only occur during hash store, but it seems correct that they can also occur during probes. That is, you probe based on the index, but find a different key stored there. So, it appears that collisions can occur during probe and store, and are reduced by multiple entries per index (if you count only failures after exhausting the multiple probes/stores). Reductions also are made with increasing the hash size, and possibly the hamming distance in the random number list (though this isn't clear, as I get better results with maximizing the hamming distance between the indexes rather than the full number). I seem to get a lot of collisions, but I don't really know what a lot of collisons are, since people count things (and define things) differently. What we need is a uniform definition for every chess term. This would help beginning and experienced programmers alike. Will
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.