Author: Jim Bumgardner
Date: 13:15:26 11/08/02
I recently discovered a strange effect in my hash tables, which had an unintentional bug. I was using a 'replace always' replacement strategy with my hash tables, and the following flags: #define HF_EXACT 0 #define HF_ALPHA 1 #define HF_BETA 2 Note that HF_EXACT is set to 0. The bug was that I was checking the flag by using (hashEntry->flag & HF_EXACT) - I was ANDing with a 0, thus the condition would never be true. To compound the error, I was always ORing my hash flag with HF_EXACT. The end-result of this was that my hash-table treated all "EXACT" values exactly the same as "ALPHA" values. When probed with the current alpha/beta values, if the flag was not set to "BETA", it would return the passed-in alpha value, rather than the actual score in the table. Now here's the weird part -- this actually worked okay! The amount of pruning I was seeing on my test suites, and the number of correct answers was not bad. On a fixed five-ply search I was getting the following results on a 1.8ghz machine: "BUGGED" (replace-always, exact acts like alpha-flag) Bratko-Kopec-5-Ply Correct: 7 Avg Time: 0.32secs Avg Nodes: 40k When I "Corrected" the flags (to use 1,2,4) and stopped using "AND" in my checks, more like a "typical" hash strategy, the time and the number of nodes doubled, and the number of correct answers dropped to 5. "CORRECT" (replace-always, exact acts like exact) Bratko-Kopec-5-Ply Correct: 5 Avg Time: 0.60secs Avg Nodes: 80k Only after I switched to a "replace if depth > stored->depth" strategy did I get results comparable to the "bugged" results. And only just slightly better. "CORRECT" (replace-if-deeper, exact acts like exact) Bratko-Kopec-5-Ply Correct: 7 Avg Time: 0.31secs Avg Nodes: 39.5k Also, I noticed that "replace if depth >= stored-depth" performed poorly as well. So in effect, the bug acted a lot like a "replace if deeper" strategy. Bizarre, huh? - Jim Bumgardner
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.