Author: martin fierz
Date: 20:44:40 07/10/02
Go up one level in this thread
On July 10, 2002 at 21:48:48, Ricardo Gibert wrote: >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). i'm not sure i agree. after all, i want to know how hash collisions could affect my program. and that uses MTD. so i don't really care about what the result in pure alpha-beta is. of course it is an interesting question if moving from alpa-beta to PVS or MTD makes your program more or less sensitive to this kind of error. but since i'm not a computer scientist, i won't spend lots of time trying to find out about this :-) my personal opinion is that it would affect all searches in the same order of magnitude. i'd be very surprised if it were different. >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. yes, but what about the situation where one of the child nodes of the current position is "found" in the hashtable during the search with a wildly wrong result? if that happens you are busted for sure. 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.