Author: Robert Hyatt
Date: 18:53:35 02/05/99
Go up one level in this thread
On February 05, 1999 at 18:01:34, Eugene Nalimov wrote:
>On February 05, 1999 at 17:51:43, Robert Hyatt wrote:
>
>>On February 05, 1999 at 14:55:49, José de Jesús García Ruvalcaba wrote:
>>
>>>On February 04, 1999 at 09:40:32, Robert Hyatt wrote:
>>>
>>>>
>>>>I found a pretty neat bug (not really a bug, more like a design problem)
>>>>last night. Crafty had played zarkovx on ICC, and was in a reduced material
>>>>position. It was getting close to repeating a position for the third time
>>>>when it announced a mate in 70 (tablebase hit). The next move it announced a
>>>>mate in 73, and after the opponent's next move it realized this was a dead draw
>>>>by repetition.
>>>>
>>>>Here's what was wrong, which might serve as a warning for those of you doing
>>>>this in your program.
>>>>
>>>>I obviously don't do a repetition check at ply=1 in the search, because by the
>>>>time I get there, I _must_ choose a move. If it is drawn at the root, I don't
>>>>even call search. The first time I do a repetition check is at ply=2. In this
>>>>game, crafty could make 1 move and not repeat, but after any _other_ move, the
>>>>next move by the opponent would repeat. What happened was it tried each root
>>>>move (remember, move A is a mate in 72 that does not allow a repeat of a prior
>>>>position, while any other move leads to a mate in 70, but the next opponent move
>>>>is a draw by repetition for any of them)
>>>>
>>>>Back to the idea (the previous sentence was too long to continue, IMHO) when it
>>>>tried move A, at ply=2 it did the rep check and found 'no rep' and then it
>>>>probed the database and found mate in 73. OK so far. But then it tried the
>>>>next choice (again no rep, but if it does this the opponent can choose a move
>>>>that is a 3rd rep) and found no rep, but a database hit with a mate in 70. 70
>>>>is better than 73, so it took this move. And played it, and found that the
>>>>opponent instantly repeated and drew.
>>>>
>>>>The fix was to _not_ probe at ply=2 any more... which means that now, Crafty
>>>>has to make a move, _and_ the opponent has to make a move without repeating the
>>>>position, _before_ I probe the database at ply=3 after the rep check. Solved
>>>>this rather ugly (and uncommon) problem.
>>>>
>>>>My search looks like this:
>>>>
>>>>Search(alpha,beta,etc){
>>>> if (repcheck) return;
>>>> if (EGTBprobe) return;
>>>> do {
>>>> normal move selection/recursive search
>>>> }
>>>> return;
>>>>}
>>>>
>>>>The problem was that I did the EGTB probe at ply=2, _before_ my opponent had a
>>>>chance to make a move. And EGTB has _no clue_ about what has already happened
>>>>in the game. This has been around a while, hope this explanation is clear
>>>>enough to help others avoid debugging it. :)
>>>>
>>>>Let me know if there are questions...
>>>>
>>>>Bob
>>>>
>>>>(and yes, I said mate in 70. The record on ICC (for crafty, anyway) is now a
>>>>mate announcement of mate in 138. This in a fairly complex ending that Crafty
>>>>managed to turn into a ugly KPP vs K ending that was a mate in over 120. But it
>>>>had already searched _very_ deep before it found the TB hit, to give that huge
>>>>mate in 138 score.)
>>>>
>>>>If anyone is interested, I now have a 'dynamic depth adjustment' algorithm in
>>>>crafty to prevent the database probes from taking my normal 600-800K nodes per
>>>>second down to 10K or so. I now usually never drop under 300K and it is working
>>>>very well...
>>>>
>>>>Bob
>>>
>>>Could you please post the score of the game and point the moves you are
>>>referring to?
>>>Also, a brief description of the "dynamic depth adjustment" would be
>>>appreciated.
>>>
>>>José.
>>
>>
>>Here is the game:
>>
>>[Event "ICC 5 0"]
>>[Site "Internet Chess Club"]
>>[Date "1999.01.29"]
>>[Round "-"]
>>[White "ZarkovX"]
>>[Black "crafty"]
>>[Result "1/2-1/2"]
>>[WhiteElo "2829"]
>>[BlackElo "2936"]
>>[Opening "Sicilian: Scheveningen, 6.Be2"]
>>[ECO "B83"]
>>[NIC "SI.19"]
>>[Time "21:22:33"]
>>[TimeControl "300+0"]
>>
>>1. e4 c5 2. Nf3 e6 3. d4 cxd4 4. Nxd4 Nf6 5. Nc3 d6 6. Be2 Be7 7. O-O O-O 8. f4
>>a6 9. Kh1 Qc7 10. a4 Nc6 11. Be3 Re8 12. Bg1 Rb8 13. f5 Nb4 14. fxe6 fxe6 15.
>>Be3 Bd7 16. Qd2 Rbd8 17. Nf3 d5 18. Bf4 Qc5 19. Be3 Qa5 20. exd5 Nfxd5 21. Nxd5
>>Qxd5 22. Bd4 Bc6 23. Qc3 Qe4 24. Bc4 Qg4 25. Qb3 Bf8 26. c3 b5 27. axb5 axb5 28.
>>Be2 Qg6 29. Rfc1 Nd3 30. Bxd3 Qxd3 31. Ne5 Qe4 32. Nxc6 Qxc6 33. Rd1 Qc4 34. Qc2
>>e5 35. Bb6 Rxd1+ 36. Qxd1 Re6 37. Be3 Re8 38. Qd7 Re7 39. Qf5 g6 40. Qg5 Qe2 41.
>>b4 Qd3 42. Ra8 Kf7 43. h3 Qd5 44. Rc8 Re8 45. Rc7+ Kg8 46. Qh4 Bg7 47. Bh6 Bh8
>>48. Bg5 h5 49. Qg3 e4 50. Bf4 Re6 51. Rc8+ Kh7 52. Qe1 Bf6 53. Rc5 Qd3 54. Kh2
>>e3 55. Rc7+ Kg8 56. Rc8+ Kf7 57. Rc7+ Be7 58. Ra7 e2 59. Bg5 Qd6+ 60. g3 Kg7 61.
>>Bxe7 Rxe7 62. Rxe7+ Qxe7 63. Kg2 Qe3 64. h4 Kh7 65. Kh1 Qf3+ 66. Kg1 Kg7 67. Qf2
>>Qxc3 68. Qxe2 Qxg3+ 69. Kf1 Qf4+ 70. Kg2 Qxb4 71. Qe5+ Kf7 72. Qd5+ Kf8 73. Qd8+
>>Kg7 74. Qc7+ Kf6 75. Qc6+ Ke5 76. Qc7+ Qd6 77. Qc3+ Qd4 78. Qg3+ Kd5 79. Qg5+
>>Kc4 80. Qxg6 Qd2+ 81. Kg1 Qd4+ 82. Kg2 Qxh4 83. Qc2+ Kb4 84. Qb2+ Ka5 85. Qa3+
>>Qa4 86. Qc3+ b4 87. Qc7+ Ka6 88. Qd6+ Kb7 89. Qe7+ Kb6 90. Qe3+ Ka6 91. Qe6+ Ka5
>>92. Qd5+ Kb6 93. Qd4+ Kb7 94. Qg7+ Kc6 95. Qg6+ Kd5 96. Qxh5+ Kc4 97. Qe2+ Kc3
>>98. Qe5+ Kc4 99. Qe2+ Kd4 100. Qd2+ Kc4 101. Qe2+ {Game drawn by repetition}
>>1/2-1/2
>>
>>
>>the problem is black's move 96, Kc4. Kc5 is a mate in 73 moves. Kc4 is a mate
>>in 70 but allows Qe2 which is an instant 3-fold repetition... Current version
>>does not make this mistake...
>>
>>'dynamic depth adjustment' simply limits the depth in the tree that tablebase
>>probes are done, based on the overall speed of the program. What normally used
>>to happen is that the search would 'stall' when you reach a point where the
>>tablebase probes are at the max rate possible on your hardware. And there is
>>no way to do another iteration since that takes you a ply deeper, which means
>>even _more_ probes. The current plan finds some 'level of comfort' in the
>>tree where probing beyond that point slows the search to an unacceptable level.
>>Crafty limits the probes to that depth and below, which allows it to continue
>>searching deeper and deeper (on successive iterations) without hitting that
>>I/O "wall" and stalling.
>>
>>The danger is that tablebase probes can slow you enough that you walk into
>>tactical traps because the depth is limited. This way I probe the databases
>>at about the same depth as when it 'stalled' but I can continue to go deeper
>>and deeper (iterations).
>>
>>If you need more info or clarification, feel free to ask...
>>
>>Bob
>
>Does that mean that when you'll reuse that information stored in
>tha hash table during the next iteration (or after correctly
>predicted opponents' move), you will use results of the search
>that did not probe TB? Even if now ply is shallower, and you should
>probe if you'd allowed to search?
>
>Eugene
It is certainly possible... But this was true anyway. However, the next
iteration goes 1 ply deeper, so that such things ought not have a big effect,
even though it can cause a quirk here and there. The alternative is to not
search nearly so deeply, in order to probe everywhere. I ran a lot of tests
with special set-up positions and this was able to win over 65% of the games
vs the normal prober. Mainly because it was searching significantly deeper
overall and when the tablebases don't matter, the new approach was significantly
stronger...
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.