Author: José de Jesús García Ruvalcaba
Date: 10:12:01 02/07/99
Go up one level in this thread
On February 06, 1999 at 21:26:32, Robert Hyatt wrote:
>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...
>
Was crafty using the full 3+2 five men tablebases?
If the position after 100...Kc4 is a mate in 70 moves, then the position after
101.Qe2+ should allow black a move which is a mate in at most 69 moves. But this
position appeared *twice* before in the game. I wonder why crafty did not go for
the mate in 69 *before*.
>
>>>'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...
>
>
Is it possible to have a queue of tablebase positions which need to be scored
waiting for the harddisk to respond?
>
>
>> 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_...
Currently there are no faster drives available, but there will...
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.