Author: Ricardo Gibert
Date: 18:48:48 07/10/02
Go up one level in this thread
On July 10, 2002 at 21:31:24, martin fierz 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. > >i made a small experiment: my checkers program uses 2 32-bit numbers as hash >signature, the first is used to compute the table position with number%hashtable >size, the second is stored in the table for verification. i ran a test suite, 78 >positions, each searched to depth 13 and depth 19. then i used only 10 bits of >the 32-bit verification number to verify and did this thing again. result: out >of 156 scores and moves, 3 scores were different, by a very small amount (0.02, >0.04 and 0.04) and the moves were the same, and in one instance the score was >the same but the move different. i checked and the 10-bit move was actually an >error. of course using 10 bits for verification purposes is ridiculously little. >i repeated the experiment using 20 bits, and now all scores and all moves were >identical, although the node counts sometimes were slightly different. >anybody want to claim 32 bits is too little for a hash signature? :-) > > >if my math doesnt let me down, this type of experiment actually should produce a >fixed error rate: if you use 10 bits, the probability that you have the same >number in your signature as the one in the table is 1/1024 (if you have a >different position of course...). so you should be seeing 1 error in 1024 with >this setup, if you have a single probe in the hashtable. > >implementation details: my program uses MTD(f) and has a bucket size of 2, i.e. >it always probes two consecutive hashtable entries. so maybe my error rate was >even higher than 1 in 1024 in the 10-bit-signature experiment. > >aloha > martin This looks like a better test than RH's, but I think we are getting the cart before the horse. It would make more sense to test a plain vanilla alpha-beta program first before going on to tackle PVS and/or MTD(f). Also, if what I think is going on is correct, then any kind of forward pruning should affect the results somewhat. The variables complicating the result ought to be minimized. What I expect is going on is alpha-beta examines mostly really crappy continuations and as one might expect with really crappy continuations, there is more than one way to refute them at more than one point in a continuation. This is a type of redundancy that mitigates the errors. I believe only a miniscule percentage of all continuations are sensitive to collision error. This percentage is miniscule enough to make even a 1 in 1000 chance of collision to be not so bad.
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.