Author: David Rasmussen
Date: 06:28:55 12/07/02
Go up one level in this thread
On December 07, 2002 at 08:01:46, Brian Richardson wrote: > >There are two situations that are sometimes called hash collisions. >One is when just the first n bits of the hash index or key are the same. >This happens quite a lot, and I don't personally consider it a collision. >The other is when all bits of the hash signature are the same. In both of these cases, the term "collision" is correct, but refers to different things. The first one is general for the concept of hash tables. If your hashing function (in this case a mod or and of the zobrist signature) maps to different entries to the same slot, you have a "collision" (hashing collision), and in many applications you simply have a linked list or some other container, of the values with this hash value. In most chess programs, we replace by some replacement scheme. The second one is special for our purpose. Using a zobrist scheme for position signatures, we hope to obtain unique signatures for unique positions, at least as far as the search will take us in the lifetime of a hash entry. That is, some position in the opening might have the same signature as one in the late endgame, that doesn't matter, but we hope that no two positions that are "near" eachother have the same signature. Because we can't tell the difference between them in any other way than by looking at the signature. If it happens, we have a "collision" (signature collision). This is what happened here. And these are what I am asking about. How many of these do people experience in the course of 1000000 games? Of course we can't be sure that only the ones caught by pseudo legality are there. There could be two different positions with the same signature and in which the stored move is pseudo legal. If so, we just hope that the score or bound stored in the hash table isn't too far off compared to the real value for this position. If it is, it could end up influencing the PV, and even the first move of the PV. We never know, unless we do some testing where we store the entire position with the hash entry. >I have never seen this with 64 bit values. I hadn't either until now. But I am pretty sure that Bob sais something about this happening once in 100 games or so. >I would not exit in either case, but just continue searching. I wouldn't either if it was important. In this case, it hadn't bothered me before, and I thought it was nice that it happened, because otherwise I wouldn't have known. If I just wrote it to a log etc. I would have stopped looking for it months ago, since it hasn't happened in nearly 2 years, when I started this rewrite. /David
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.