Author: Robert Hyatt
Date: 18:26:32 02/06/99
Go up one level in this thread
On February 06, 1999 at 13:03:40, José de Jesús García Ruvalcaba 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...
>>
>
> 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?
>
sorry... move 100. for black was the error... Kc5 is a mate in 73, while
Kc4 allows the instant 3rd repetition. Thru all of this white was lost,
but black let him repeat due to the bug I mentioned...
I have no idea why I said move 96...
>>'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?
no... but there are lots of positions that you _don't_ know about. IE I
probe after _any_ capture reduces the material to 5 or fewer pieces, and
I get a perfect score back. But many paths don't include trades that take
me to the tablebases. And searching _those_ deeper is critical to avoid
mistakes...
> 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).
that is why I limit the probe depth.. so that on the positions I can't resolve
to win/lose/draw, I can search them deeper...
> 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 already do this, because the result of a tablebase probe is just like doing
a normal search and getting a score back. It gets stored in the hash so that
future probes from that position won't be done.
> 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.
it initially sets the max depth to a large number (32 plies). Then it
monitors the NPS value as the game moves along, and so long as there are
no probes, it updates a "average NPS" variable. When it starts probing, it
'freezes' this value and then starts comparing current NPS to the average NPS
for the game. When the current NPS drops too much, the max depth for database
probes is reduced... If the average NPS speeds back up, it slowly increases
the TB probe depth.. to keep it right on the threshold where the NPS is no
worse than roughly 1/2 that which it was with no probes...
> How does 'dynamic depth adjustment' adjust the depth of tablebase probesto
>achieve that? (it should be different when you get a faster harddisk).
>
>José.
it considers this, because it only notices how much the search is slowed
down (btw, for my machine, there are _no_ faster drives available. These are
10K rpm, 5ms access, 80 mbyte/second ultra-2 (LVDS) SCSI drives. Each drive
has a 4mb on-drive cache, plus the cache in the tablebase probe code. They
_scream_...
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.