Author: Robert Hyatt
Date: 17:07:34 07/09/02
Go up one level in this thread
On July 09, 2002 at 19:48:32, Will Singleton wrote: >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 would like to ask others to try this as well. It only adds a couple of >>lines to your HashProbe() code. I started at one "collision" every 100K >>nodes, but that did nothing. Then one every 10K. And finally one every >>1K. This seems surprising to me. I ran several positions, with and without >>the "collision problem" and compared my logfile output. Scores did not change >>at all. I used tactical positions like Kopec22, opening positions, and even >>the classic fine #70. >> >>Seems that the search is far more resistant to such errors than anybody has >>thought previously. It would be interesting to see if this is just a result >>of Crafty, or if it holds for others. Particularly for someone that hashes >>in the q-search, which I do not do... Note that I did not false match every >>N calls to HashProbe() rather I false matched on the next call to HashProbe() >>after having searched N nodes since the previous call. Sometimes this would >>be less frequently than once per 1000 nodes obviously, since I could burn >>several thousand nodes in the q-search and not do another false match until I >>get back out of that mess and back into the normal non-qsearch part. > > >Hmmm.. I wonder is this might mean that many parts of the search tree are >unimportant (get pruned anyway). Scary thought. Maybe this is a good way to >figure out how to prune better. > >btw, as I always say, "hash collision" isn't the best term to describe two >distinct positions mapping to the same hash signature. You refer to it above as >a "false match", which seems correct. The term "hash collision" should mean two >distinct positions which map to the same indexed bucket (memory location). One >can handle hash collisions, one cannot handle false matches (without >performance-killing effort). > >Will I agree with the terminology. "collision" is not necessarily a bad thing in the world of hashing. "false matches" are, of course.
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.