Author: Komputer Korner
Date: 20:00:30 12/26/98
Go up one level in this thread
On December 26, 1998 at 18:51:46, Richard A. Fowell (fowell@netcom.com) wrote: >Do hash tables confuse your matefinding routines? > >I tried this mate in 7: >8/krK5/p7/P7/6P1/8/7Q/8 w - - > >on two different chess programs, by two different authors, >and both reported erroneously short mates when their hash tables were on. > >With hash tables off, the correct solution was given by both programs. > >In both cases, the programs were using special-purpose matefinding logic >that had no known problems before. > >Can anyone shed any light on this? > >Since this problem showed up in the only two programs I tested >for this, it seems like it may be a widespread issue. > >When I use Sigma Chess 4.01 Lite with hash off, >using the "mate in 7" setting, I get the right answer: > >Hash off (Mate in 7) - Kc7-c8, Mate in 7, 948.7 seconds >Kc7-c8 Rb7-b3 >Qh2-h7 Ka7-a8 >Qh7-e4 Ka8-a7 >Qe4-d4 Ka7-a8 >Qd4-d5 Ka8-a7 >Qd5xb3 Ka7-a8 >Qb3-b7 > >When I enable hash, Sigma Chess (erroneously) reports mate in 6 - >with pretty much a different PV for every hash table setting I tried. >The key move is right, and the time is much shorter >(2.4 sec, 6.9 sec, 8.0 sec, 11.1 sec, 12.5 sec, 32.6 sec in the cases I tried), >but the evaluation is wrong. > >When I use MacChess 5.0 EN, at level "mate in 7", (which uses hash tables) >it reports a mate in 4. >When I use MacChess 4.0 at level "mate in 7", (which does not use hash tables) >it reports the correct mate in 7, e.g.: > >MacChess 4.0 EN > >1. Kc8 Rb3 >2. Qc7+ Ka8 >3. Qc6+ Ka7 >4. Qd7+ Ka8 >5. Qd5+ Ka7 >6. Qxb3 Ka8 >7. Qb7# > >So ... what's going on, here? > >Richard A. Fowell (fowell@netcom.com) A known problem for a long time. See Bruce's response from a while back. "Hashing bugs that I've seen have involved the following: 1) You have to be careful when hashing mate scores, since they are depth-specific. When you implement distance-to-mate endgame databases, these problems can get really awful since you are dealing with mate scores so often. 2) The effect of things that aren't hashed. It makes no sense to hash the entire path to get to a node, so there is always a risk that you can make a wrong decision based upon a hash table node, because some position appears in the path you took to get to one node that didn't appear in the path you took to get to the other. What this means is that certain moves that will appear below this node may lead to repetitions in one case and not the other. This happens enough to be annoying, and I think that it is impossible to fix. Simply not hashing draw scores will not do it, although it may make a problem (usually a fail-high followed by a failed resolution of the fail-high) stop manifesting in a specific case. 3) Failure to hash en-passant square (if present), castling flags, or side to move, can cause problems, especially this last one if you use null-move search, I'd think. 4) General bugs having to do with failure to store or interpret the bound info properly. It's amazing how often you'll hear that someone got something backwards in here, and stored some nodes as "less than 40" rather than "greater than 40" or whatever. I'm sure there are a lot more, since I have had a lot more than four bugs. bruce" -- Komputer Korner
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.