Author: Pat King
Date: 07:43:42 04/12/02
Go up one level in this thread
On April 10, 2002 at 20:47:06, Will Singleton wrote: >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. The definition of collision being used in this thread was clearly spelled out by Bob, and lurks above in all the re:s above. It is especially relevant to this thread, where we humble beginners (please don't notice how long I've been in that category) struggle to get even the basics right. > >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.