Author: martin fierz
Date: 15:26:33 07/09/02
Go up one level in this thread
On July 09, 2002 at 17:59:17, Robert Hyatt wrote: >I have been running some tests after prompting by Bruce, and the results >have been interesting. > >The question posed by him was "how many hash collisions (signatures match >but positions do not) can we tolerate in a search without having serious >problems?" > >I did the following: I made my HashProbe() routine use the node counter, >and every N nodes, I would "match" a hash entry even if the signatures were >not the same, simulating a collision. I got all the way down to a collision >every 1000 nodes without seeing even a score change at the root, which was >surprising. i'm surprised that you're surprised :-) i have found and stomped so many bugs in my checkers program's evaluation (and surely there are lots more in there...) that i wonder how it ever played a decent game at all. but of course, the answer is that an alpha-beta search masks such trouble. i guess that as long as your hash collisions don't occur close to the root, they will have a similar effect as a badly misevaluated position at a leaf node - none at all, in most cases. i also would guess that if you try long enough (on a whole set of test positions), you should find something. i also have a question about the experiment you suggest: you are producing random hash collisions; i.e. let's say a hash collision you get in one search causes a fail-low, and on the research it disappears again, so you get the normal eval & pv. i think real hash collisions are deterministic, so you will always collide with the same positions, so i think your experiment does not represent a real-world hash collision problem scenario. i always thought i should do the following experiment one day: reduce the number of bits in my "hash lock" (the number i compare to see if the position in the hashtable matches the one i'm looking for), and look when the search starts to change. that's a one-line change, instead of if(hashtable[index].lock == hashlock) you just & both sides with something like 1<<N-1. you can check the frequency of your hash collision by checking the whole lock which should under normal circumstances give close to 0 collisions. aloha martin
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.