Syzygy and draw by repetition

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

jdart
Posts: 3488
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Syzygy and draw by repetition

Post by jdart » Fri Jul 22, 2016 4:41 pm

Following is a FICS game Arasan drew, despite getting mate scores from the TBs (Syzygy, 5-man). Apparently Komodo has a similar issue because it shows a mate score in analysis mode even after the last move 90. Qd5+. (This position is a Black win: Black can avoid repetition).

[pgn]
[Event "freechess.org"]
[Site "freechess.org"]
[Date "2016.07.19"]
[Round "?"]
[White "GnuCheese"]
[Black "Arasan 19.0.1"]
[Result "1/2-1/2"]
[ECO "B45"]
[WhiteElo "2547"]
[BlackElo "2659"]
[PlyCount "179"]
[EventDate "2016.??.??"]
[TimeControl "900+5"]

1. e4 c5 2. Nf3 Nc6 3. d4 cxd4 4.
Nxd4 e6 5. Nc3 d6 6. Be3 a6 7. g4 Bd7 8. Be2 Na5 9. O-O h6 10. Qd2 Rc8 11. f4
Nc4 12. Bxc4 Rxc4 13. g5 b5 14. a3 Ne7 15. gxh6 gxh6 16. Rf3 Rg8+ 17. Rg3 Qc7
18. Rb1 Rxg3+ 19. hxg3 Bg7 20. Rf1 Ng8 21. f5 Be5 22. fxe6 Bxe6 23. Qd3 Nf6 24.
Bf2 Qc8 25. Nce2 Bg4 26. Nc3 Bh3 27. Rd1 Ng4 28. Nce2 Bxd4 29. Bxd4 Rxc2 30.
Rd2 Rc4 31. Nc3 Qe6 32. Rc2 Ne5 33. Bxe5 dxe5 34. Nd5 Rc6 35. a4 Kf8 36. axb5
axb5 37. Rf2 Qg6 38. Qe3 Be6 39. Nf6 Bg4 40. Nd5 Ra6 41. b4 Ra1+ 42. Rf1 Qa6
43. Qf2 Rxf1+ 44. Kxf1 Bh3+ 45. Kg1 Kg7 46. Kh2 Bd7 47. Ne7 Qd6 48. Nf5+ Bxf5
49. Qxf5 Qf6 50. Qh5 Qf2+ 51. Kh3 Qd4 52. Qf5 Kf8 53. Qc8+ Ke7 54. Qf5 Qd7 55.
g4 Qd4 56. Kg3 Kf8 57. Qc8+ Kg7 58. Qe8 Qxb4 59. Qxe5+ Kh7 60. Qf4 Qc3+ 61. Kh2
Qc4 62. Qf5+ Kg8 63. Qf4 b4 64. Qxh6 Qb5 65. Qd6 Qe2+ 66. Kg3 Qe3+ 67. Kh4 Qxe4
68. Qb6 Kg7 69. Qa5 Qe1+ 70. Kh3 Qe3+ 71. Kh4 b3 72. Qa1+ f6 73. Qa8 Qf2+ 74.
Kh3 b2 75. Qe4 Kh6 76. g5+ fxg5 77. Qe6+ Kg7 78. Qe7+ Kg6 79. Qxg5+ Kf7 80.
Qd5+ Kf8 81. Qd8+ Kf7 82. Qd5+ Kg7 83. Qg5+ Kh7 84. Qh5+ Kg7 85. Qg5+ Kh7 86.
Qh5+ Kg8 87. Qg5+ Kh8 88. Qh6+ Kg8 89. Qg5+ Kf7 90. Qd5+ 1/2-1/2
[/pgn]

bob
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Syzygy and draw by repetition

Post by bob » Fri Jul 22, 2016 5:18 pm

jdart wrote:Following is a FICS game Arasan drew, despite getting mate scores from the TBs (Syzygy, 5-man). Apparently Komodo has a similar issue because it shows a mate score in analysis mode even after the last move 90. Qd5+. (This position is a Black win: Black can avoid repetition).

[pgn]
[Event "freechess.org"]
[Site "freechess.org"]
[Date "2016.07.19"]
[Round "?"]
[White "GnuCheese"]
[Black "Arasan 19.0.1"]
[Result "1/2-1/2"]
[ECO "B45"]
[WhiteElo "2547"]
[BlackElo "2659"]
[PlyCount "179"]
[EventDate "2016.??.??"]
[TimeControl "900+5"]

1. e4 c5 2. Nf3 Nc6 3. d4 cxd4 4.
Nxd4 e6 5. Nc3 d6 6. Be3 a6 7. g4 Bd7 8. Be2 Na5 9. O-O h6 10. Qd2 Rc8 11. f4
Nc4 12. Bxc4 Rxc4 13. g5 b5 14. a3 Ne7 15. gxh6 gxh6 16. Rf3 Rg8+ 17. Rg3 Qc7
18. Rb1 Rxg3+ 19. hxg3 Bg7 20. Rf1 Ng8 21. f5 Be5 22. fxe6 Bxe6 23. Qd3 Nf6 24.
Bf2 Qc8 25. Nce2 Bg4 26. Nc3 Bh3 27. Rd1 Ng4 28. Nce2 Bxd4 29. Bxd4 Rxc2 30.
Rd2 Rc4 31. Nc3 Qe6 32. Rc2 Ne5 33. Bxe5 dxe5 34. Nd5 Rc6 35. a4 Kf8 36. axb5
axb5 37. Rf2 Qg6 38. Qe3 Be6 39. Nf6 Bg4 40. Nd5 Ra6 41. b4 Ra1+ 42. Rf1 Qa6
43. Qf2 Rxf1+ 44. Kxf1 Bh3+ 45. Kg1 Kg7 46. Kh2 Bd7 47. Ne7 Qd6 48. Nf5+ Bxf5
49. Qxf5 Qf6 50. Qh5 Qf2+ 51. Kh3 Qd4 52. Qf5 Kf8 53. Qc8+ Ke7 54. Qf5 Qd7 55.
g4 Qd4 56. Kg3 Kf8 57. Qc8+ Kg7 58. Qe8 Qxb4 59. Qxe5+ Kh7 60. Qf4 Qc3+ 61. Kh2
Qc4 62. Qf5+ Kg8 63. Qf4 b4 64. Qxh6 Qb5 65. Qd6 Qe2+ 66. Kg3 Qe3+ 67. Kh4 Qxe4
68. Qb6 Kg7 69. Qa5 Qe1+ 70. Kh3 Qe3+ 71. Kh4 b3 72. Qa1+ f6 73. Qa8 Qf2+ 74.
Kh3 b2 75. Qe4 Kh6 76. g5+ fxg5 77. Qe6+ Kg7 78. Qe7+ Kg6 79. Qxg5+ Kf7 80.
Qd5+ Kf8 81. Qd8+ Kf7 82. Qd5+ Kg7 83. Qg5+ Kh7 84. Qh5+ Kg7 85. Qg5+ Kh7 86.
Qh5+ Kg8 87. Qg5+ Kh8 88. Qh6+ Kg8 89. Qg5+ Kf7 90. Qd5+ 1/2-1/2
[/pgn]
I gave this a quick look. Do you do anything regarding repetitions in your code where you probe the EGTBs? IE I assume you are probably calling tb_probe_root()? In looking at that code, repetitions are ignored, which I presume means you need to do that check for yourself and avoid moves that lead to a 3-fold rep.

I have added syzygy to Crafty, but have not yet looked at this specific issue. In looking, it looks like this check needs to be added into tb_probe_root() since it returns the suggested best move, without any consideration for repetitions (it does use the 50 move counter, obviously)...

In looking at this further, I am not quite sure what is going on, as once you reach a 5 piece ending, I can see no valid reason that Ronald's code would return a move that repeats the position the first time, much less the second.

Crafty will mis-annotate this game since 3-fold repetitions are not considered in the tb_probe_root() code, which will take some thought to solve, but once you are in a won ending, how did the position get repeated???

I can't get Crafty to play the same moves in normal game-playing mode. IE if I reset to move 80 and play Qd5+, I get an instant Kf6 from the syzygy probe code, not Kf8... I would expect the same moves considering DTZ and WDL are both available.

jdart
Posts: 3488
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Syzygy and draw by repetition

Post by jdart » Fri Jul 22, 2016 5:43 pm

I am still looking at it. I am using the Fathom library, which is a repackaging of the Stockfish code (https://github.com/basil00/Fathom). Apparently the library does not consider repetitions, so it has no way of knowing when scoring root moves whether any might play into a repetition.

Good question how you got to repetition in the first place, but when I look at the logs Arasan first produced some large scores but not +TbWin, and then later started showing TbWin. So maybe that is another issue that needs fixing and contributes to this draw problem.

One possible fix is to do your own filtering: if the score is a tablebase win and if any moves repeat a previous position, filter out those moves. But it is then theoretically possible I think that all available moves repeat, and then you have no moves left. (Maybe with everything fixed this would not occur in a game, however).

--Jon

syzygy
Posts: 4221
Joined: Tue Feb 28, 2012 10:56 pm

Re: Syzygy and draw by repetition

Post by syzygy » Fri Jul 22, 2016 8:42 pm

bob wrote:I gave this a quick look. Do you do anything regarding repetitions in your code where you probe the EGTBs? IE I assume you are probably calling tb_probe_root()? In looking at that code, repetitions are ignored, which I presume means you need to do that check for yourself and avoid moves that lead to a 3-fold rep.
I'm not sure which we are looking at now (that in Arasan?), but my example code has this:

Code: Select all

  if (dtz > 0) { // winning (or 50-move rule draw)
    int best = 0xffff;
    for &#40;size_t i = 0; i < Search&#58;&#58;RootMoves.size&#40;); i++) &#123;
      int v = Search&#58;&#58;RootMoves&#91;i&#93;.score;
      if &#40;v > 0 && v < best&#41;
	best = v;
    &#125;
    int max = best;
    // If the current phase has not seen repetitions, then try all moves
    // that stay safely within the 50-move budget, if there are any.
    if (!has_repeated&#40;st.previous&#41; && best + cnt50 <= 99&#41;
      max = 99 - cnt50;
    for &#40;size_t i = 0; i < Search&#58;&#58;RootMoves.size&#40;); i++) &#123;
      int v = Search&#58;&#58;RootMoves&#91;i&#93;.score;
      if &#40;v > 0 && v <= max&#41;
	Search&#58;&#58;RootMoves&#91;j++&#93; = Search&#58;&#58;RootMoves&#91;i&#93;;
    &#125;
  &#125;
If the current "phase" (since the last pawn move or capture) has seen a repetition (on the board), then "max" remains equal to "best" and only those root moves are selected that are "best" in terms of DTZ. ("max" should be understood as the maximum DTZ value allowed.)

Ah, we are probably looking at the Fathom library. The probe_root() function of that library seems not to check for repetitions.
I have added syzygy to Crafty, but have not yet looked at this specific issue. In looking, it looks like this check needs to be added into tb_probe_root() since it returns the suggested best move, without any consideration for repetitions (it does use the 50 move counter, obviously)...
If the root postiion is a TB win, then root_probe() returns the moves that win within the 50-move rule. The exception is if one repetition has occurred, because then it should be avoided that the same position is repeated again. (By playing the optimal DTZ moves until the next capture or pawn move, it is certain that DTZ decreases on every move, so that it is impossible that earlier positions are repeated.)

Many variations are of course possible.
In looking at this further, I am not quite sure what is going on, as once you reach a 5 piece ending, I can see no valid reason that Ronald's code would return a move that repeats the position the first time, much less the second.
So a first repetition is not excluded.
I can't get Crafty to play the same moves in normal game-playing mode. IE if I reset to move 80 and play Qd5+, I get an instant Kf6 from the syzygy probe code, not Kf8... I would expect the same moves considering DTZ and WDL are both available.
https://syzygy-tables.info/?fen=8/5k2/8 ... _b_-_-_0_1

Both Ke7 and Kf6 are optimal in this position. Ke8/Kf8/Kg7 also win, but lead to a somewhat higher DTZ (and could therefore repeat the position, either immediately or some moves later).

Note that simply refusing to play repeating moves is not a solution. If an earlier move increased DTZ, it is possible that the engine is forced to repeat the position later in order to return to a lower DTZ.

In positions like these DTZ is rather high and it is fairly certain that the DTZ-optimal move is also a very sane-looking move. If DTZ is much lower, then the DTZ-optimal move might look much less sane.

syzygy
Posts: 4221
Joined: Tue Feb 28, 2012 10:56 pm

Re: Syzygy and draw by repetition

Post by syzygy » Fri Jul 22, 2016 8:50 pm

jdart wrote:One possible fix is to do your own filtering: if the score is a tablebase win and if any moves repeat a previous position, filter out those moves. But it is then theoretically possible I think that all available moves repeat, and then you have no moves left. (Maybe with everything fixed this would not occur in a game, however).
Exactly, that is possible and probably not even unlikely.

Repetitions can be prevented by playing only DTZ-optimal moves. That is the easiest solution, but the engine will play funny moves in some endgames.

Once you're not always playing DTZ-optimal moves, (rare) single repetitions have to be accepted.

bob
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Syzygy and draw by repetition

Post by bob » Fri Jul 22, 2016 9:56 pm

syzygy wrote:
jdart wrote:One possible fix is to do your own filtering: if the score is a tablebase win and if any moves repeat a previous position, filter out those moves. But it is then theoretically possible I think that all available moves repeat, and then you have no moves left. (Maybe with everything fixed this would not occur in a game, however).
Exactly, that is possible and probably not even unlikely.

Repetitions can be prevented by playing only DTZ-optimal moves. That is the easiest solution, but the engine will play funny moves in some endgames.

Once you're not always playing DTZ-optimal moves, (rare) single repetitions have to be accepted.
If you look at the game he posted, it ended in a 5 piece ending and the repetition happened inside that. Which I don't understand at all, since after the capture that takes it to 5 pieces, how a repetition could happen based on the move returned by tb_probe_root(). So to me, something appears to be broken in this case.

I would assume tb_probe_root() only returns DTZ-optimal moves? Yet something went wrong here...

bob
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Syzygy and draw by repetition

Post by bob » Fri Jul 22, 2016 10:00 pm

syzygy wrote:
bob wrote:I gave this a quick look. Do you do anything regarding repetitions in your code where you probe the EGTBs? IE I assume you are probably calling tb_probe_root()? In looking at that code, repetitions are ignored, which I presume means you need to do that check for yourself and avoid moves that lead to a 3-fold rep.
I'm not sure which we are looking at now (that in Arasan?), but my example code has this:

Code: Select all

  if &#40;dtz > 0&#41; &#123; // winning &#40;or 50-move rule draw&#41;
    int best = 0xffff;
    for &#40;size_t i = 0; i < Search&#58;&#58;RootMoves.size&#40;); i++) &#123;
      int v = Search&#58;&#58;RootMoves&#91;i&#93;.score;
      if &#40;v > 0 && v < best&#41;
	best = v;
    &#125;
    int max = best;
    // If the current phase has not seen repetitions, then try all moves
    // that stay safely within the 50-move budget, if there are any.
    if (!has_repeated&#40;st.previous&#41; && best + cnt50 <= 99&#41;
      max = 99 - cnt50;
    for &#40;size_t i = 0; i < Search&#58;&#58;RootMoves.size&#40;); i++) &#123;
      int v = Search&#58;&#58;RootMoves&#91;i&#93;.score;
      if &#40;v > 0 && v <= max&#41;
	Search&#58;&#58;RootMoves&#91;j++&#93; = Search&#58;&#58;RootMoves&#91;i&#93;;
    &#125;
  &#125;
If the current "phase" (since the last pawn move or capture) has seen a repetition (on the board), then "max" remains equal to "best" and only those root moves are selected that are "best" in terms of DTZ. ("max" should be understood as the maximum DTZ value allowed.)

Ah, we are probably looking at the Fathom library. The probe_root() function of that library seems not to check for repetitions.
I have added syzygy to Crafty, but have not yet looked at this specific issue. In looking, it looks like this check needs to be added into tb_probe_root() since it returns the suggested best move, without any consideration for repetitions (it does use the 50 move counter, obviously)...
If the root postiion is a TB win, then root_probe() returns the moves that win within the 50-move rule. The exception is if one repetition has occurred, because then it should be avoided that the same position is repeated again. (By playing the optimal DTZ moves until the next capture or pawn move, it is certain that DTZ decreases on every move, so that it is impossible that earlier positions are repeated.)

Many variations are of course possible.
In looking at this further, I am not quite sure what is going on, as once you reach a 5 piece ending, I can see no valid reason that Ronald's code would return a move that repeats the position the first time, much less the second.
So a first repetition is not excluded.
I can't get Crafty to play the same moves in normal game-playing mode. IE if I reset to move 80 and play Qd5+, I get an instant Kf6 from the syzygy probe code, not Kf8... I would expect the same moves considering DTZ and WDL are both available.
https://syzygy-tables.info/?fen=8/5k2/8 ... _b_-_-_0_1

Both Ke7 and Kf6 are optimal in this position. Ke8/Kf8/Kg7 also win, but lead to a somewhat higher DTZ (and could therefore repeat the position, either immediately or some moves later).

Note that simply refusing to play repeating moves is not a solution. If an earlier move increased DTZ, it is possible that the engine is forced to repeat the position later in order to return to a lower DTZ.

In positions like these DTZ is rather high and it is fairly certain that the DTZ-optimal move is also a very sane-looking move. If DTZ is much lower, then the DTZ-optimal move might look much less sane.
So somehow Arasan played a sub-optimal move (Kf8) (which looks wrong to me as a human as if the king stays on the edge, it will get checked forever anyway.

Crafty immediately spits out Kf6 in the position, where Arasan played Kf8 for unknown reasons...

I've not seen any issues at all other than I had to carefully handle the case where the mate is delivered on move 50 (both sides have played exactly 50 reversible moves, but the last move delivered mate which takes precedence).

Seems to be working just fine for me, so far.

BTW, I have no requirement that "the move looks sane." I have been seeing nonsensical moves for almost 50 years now. It got a bit worse when I switched to Steven's 4 (and a few 5) piece files and then Nalimov, and then when we started to use 6's, it became more irrational looking. But computers play strangely anyway, and the goal is to win for me. Wasting time and effort trying to somehow "make the computer more human-like" seems pointless since humans can't announce mates in these positions anyway.

jdart
Posts: 3488
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Syzygy and draw by repetition

Post by jdart » Fri Jul 22, 2016 10:15 pm

Yes, I am using Fathom (a slightly modified version of it). So nothing special is done for repetition.

[D] 8/5k2/8/3Q4/8/7K/1p3q2/8 b - - 0 1

Arasan plays Kf6 here (correctly) if searched outside of the game, with no repetition context. But with the context it apparently behaves differently.

--Jon

Dirt
Posts: 2851
Joined: Wed Mar 08, 2006 9:01 pm
Location: Irvine, CA, USA

Re: Syzygy and draw by repetition

Post by Dirt » Fri Jul 22, 2016 11:19 pm

bob wrote:BTW, I have no requirement that "the move looks sane."
Good. It doesn't bother me either. Moving from DTM to DTZ makes the endings look a lot more insane, though. People will complain.
Deasil is the right way to go.

Dann Corbit
Posts: 8587
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Syzygy and draw by repetition

Post by Dann Corbit » Fri Jul 22, 2016 11:36 pm

Dirt wrote:
bob wrote:BTW, I have no requirement that "the move looks sane."
Good. It doesn't bother me either. Moving from DTM to DTZ makes the endings look a lot more insane, though. People will complain.
When you are playing a chess game, you only want to win. So people who use their chess engines to win ratings online won't give a hoot if the output is strange looking.

But if you analyze games then you want optimal output. If there is a mate in 7 and your engine generates a mate in 13 with weird looking wanderings they won't like it.

Hence, a combination of GTB and Syzygy is optimal (IMO) because the GTB files give perfect move advice like Nalimov (but are much easier to license).
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Post Reply