Author: José de Jesús García Ruvalcaba
Date: 10:03:40 02/06/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...
>
96... Kc5 is not a legal move. Also, at this point *no* move allows a
three-fold repetition, as white's last move was a pawn capture. I guess you mean
black's hundreth move.
Is 100. Qd2+ a decisive mistake by white? What should white play at this point?
>'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
Is it neccesary to search deeper a branch of the tree for which you know the
theoretical value of the game?
I mean, if you hit a tablebase position at some depth, you do not need to look
at its sons in the next iteration (unless you are in swindle mode, of course). I
think it is posible to concentrate efforts on other branches, and that may lead
to finding the theoretical value of non-tablebase positions (perhaps even the
root).
I know that tablebase probes are slower than normal evaluation. Is it a good
idea to store the result of a tablebase probe in the hash table? (that would
require doing a hash probe before each tablebase probe, but can save a lot of
tablebase probes).
I see that time is a critical resource, and particularly the rate of access to
tablebases is critical and should be kept under a reasonable bound.
How does 'dynamic depth adjustment' adjust the depth of tablebase probesto
achieve that? (it should be different when you get a faster harddisk).
José.
This page took 0.01 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.