Author: Eugene Nalimov
Date: 15:01:34 02/05/99
Go up one level in this thread
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
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.