6

Assume that the fifty-move rule does not require a player to claim a draw. Instead, the game is automatically declared a draw if no pawns have been moved and no pieces have been captured in the last 50 moves.

Hence, we don't need to maintain the entire game history to detect threefold repetitions. We only need to maintain a history of the last 100 positions. Out of these 100 positions, half of them are white-to-play and the other half are black-to-play. Hence, only 50 of these 100 positions could possibly be the same as the current position.

Now, out of these 50 candidate positions if each position is repeated twice then we only have 25 distinct positions which could possibly be the same as the current position. Hence, the upper bound on the maximum number of moves that could result in a threefold repetition is 25.

However, it's very unlikely (dare I say impossible?) that there's a position with 25 possible moves that would lead to a threefold repetition. I believe that the actual number is much smaller. We may never know the exact number. Nevertheless, can you prove that the upper bound is lower than 25?

NB. I'm asking this question because I'm developing a neural network that plays chess. Hence, I'd like to reduce the size of the input to the neural network as much as possible. Providing a history of 25 positions to the neural network is a lot.

Improve this question
12
  • You should note that the 50 move rule and 3-fold repetition are optional draws. One of the players has to decide to claim the draw. There are corresponding 75 move rule and 5-fold repetition. In these cases the arbiter is required to step in and declare the game drawn. If you are calculating when the game is automatically a draw then you should be using these figures. Note that if your logic is correct then this gives a much smaller number of positions
    – Brian Towers ♦
    Aug 9, 2018 at 11:57
  • 1
    @Evargalo Actually, if I remember correctly they are in the FIDE rules.
    – Aadit M Shah
    Aug 9, 2018 at 12:33
  • 2
    Not only does black have the move in half the positions, but he makes a move each of those times. So something changes about the black position each move, that can only be repaired one move later. That makes it impossible to reach 25, as with the final white move you can only reach a repeated position that has one particular layout of the black pieces. 12 or 13 is a nice challenge.
    – RemcoGerlich
    Aug 9, 2018 at 13:01
  • 1
    That said, I don't understand why you want to pass these positions to a neural network in the first place.
    – RemcoGerlich
    Aug 9, 2018 at 13:05
  • 1
    But does it only care about threefold positions that can be reached immediately with one move, or also ones that occur say two moves into the future? Because then you have to pass the whole history since the last time something irreversible happened. And don't engines like this usually combine some sort of traditional alpha/beta search (that can deal with threefold) combined with a neural network for evaluation or prioritizing moves?
    – RemcoGerlich
    Aug 10, 2018 at 7:07

3 Answers 3

Reset to default
9

Twelve moves is the maximum:

[FEN "5K1k/6p1/6pp/8/8/8/b7/Q7 w - - 0 1"]

1. Qxa2 Kh7 2. Qa3 Kh8 3. Qa4 Kh7 4. Qa5 Kh8 5. Qa6 Kh7 6. Qa7 Kh8 7. Qg1 Kh7 8. Qf1 Kh8 9. Qe1 Kh7 10. Qd1 Kh8 11. Qc1 Kh7 12. Qb1 Kh8 13. Qa2 Kh7 14. Qa3 Kh8 15. Qa4 Kh7 16. Qa5 Kh8 17. Qa6 Kh7 18. Qa7 Kh8 19. Qg1 Kh7 20. Qf1 Kh8 21. Qe1 Kh7 22. Qd1 Kh8 23. Qc1 Kh7 24. Qb2 Kh8 25. Qa3 Kh7 26. Qa4 Kh8 27. Qa5 Kh7 28. Qa6 Kh8 29. Qa7 Kh7 30. Qg1 Kh8 31. Qf1 Kh7 32. Qe1 Kh8 33. Qd1 Kh7 34. Qc1 Kh8 35. Qb1 Kh7 36. Qa2 Kh8 37. Qa3 Kh7 38. Qa4 Kh8 39. Qa5 Kh7 40. Qa6 Kh8 41. Qa7 Kh7 42. Qg1 Kh8 43. Qf1 Kh7 44. Qe1 Kh8 45. Qd1 Kh7 46. Qc1 Kh8 47. Qb1 Kh7 48. Qa1 Kh8

Moving the Queen to a2, a3, a4, a5, a6, a7, b1, c1, d1, e1, f1 or g1 all lead to threefold repetition.

As @RemcoGerlich explained the Black pieces have to reset for the positions to be the same. Black is resetting after every other move (on moves 2, 4, ..., 48) in the example above which is the quickest possible.

Thirteen moves would require the Black pieces to reset at least 26 times however Black can reset at most 25 times in 50 moves.

Improve this answer
1
  • 2
    Makes sense. There are 50 positions with white-to-play. Out of these, black has the same piece arrangement in only 25 positions. Hence, only 12 positions can be repeated twice. One position has to be unrepeated.
    – Aadit M Shah
    Aug 10, 2018 at 2:51
2

Maybe I don't understand your question very well. Obviously, there can be a threefold repetition with the first occurence of the repetition being 50 (or 49 so that the 50-moves rule doesn't apply) moves ago and the second occurence happening 25 moves ago.

There are lots of cases when you can reduce the input to the neural network, for instance each time a pawn is move or a capture is made or castle rights are lost the count is reset to one position. But the upper bound remains 25.

Check positions after moves 1, 26 and 50 in this fantastic game, a fighting draw:

[FEN ""] 
1.e4 e5 {first occurence} 2.Ba6 Ba3 Bb5 Bb4 Bc4 Bc5 Bd3 Bd6 Be2 Be7 Bh5 Bh4 Bg4 Bg5 Bf3 Bf6 Nh3 Nh6 Be2 Be7 Ba6 Ba3 Bb5 Bb4 Bc4 Bc5 Bd3 Bd6 Ng1 Nc6 Be2 Be7 Bh5 Bh4 Bg4 Bg5 Bf3 Bf6 Qe2 Nb8 Bh5 Be7 Qd1 Ba3 Be2 Bb4 Ba6 Bf8 Bf1 Ng8 {second occurence} Nc3 Nc6 Ba6 Ba3 Bb5 Bb4 Bc4 Bc5 Bd3 Bd6 Be2 Be7 Bh5 Bh4 Bg4 Bg5 Bf3 Bf6 Nh3 Nh6 Be2 Be7 Ba6 Ba3 Bb5 Bb4 Bc4 Bc5 Bd3 Bd6 Ng1 Nd4 Nb1 Ng8 Ba6 Ba3 Bb5 Bb4 Bc4 Bc5 Bd3 Bd6 Be2 Nc6 Bb5 Bf8 Bf1 Nb8 {third occurence}

Thanks to @RemcoGerlich comment, I understand now that your question was very different. Here is a game situation where 12 different moves can lead to a threefold repetition. I think it is the upper bound; as explained by Remco in a comment to your question.

[FEN ""] 
1.e4 e5 a4 Nh6 Qh5 Ng8 Ba6 Nh6 Qd1 Ng8 Qg4 Nh6 Bf1 Ng8 Bb5 Nh6 Qd1 Ng8 Qf3 Nh6 Bf1 Ng8 Bc4 Nh6 Qd1 Ng8 Nh3 Nh6 Bf1 Ng8 Bd3 Nh6 Ng1 Ng8 Na3 Nh6 Bf1 Ng8 Ra2 Nh6 Nb1 Ng8 Nc3 Nh6 Ra1 Ng8 Ra3 Nh6 Nb1 Ng8 Qh5 Nh6 Ra1 Ng8 Ba6 Nh6 Qd1 Ng8 Qg4 Nh6 Bf1 Ng8 Bb5 Nh6 Qd1 Ng8 Qf3 Nh6 Bf1 Ng8 Bc4 Nh6 Qd1 Ng8 Nh3 Nh6 Bf1 Ng8 Bd3 Nh6 Ng1 Ng8 Na3 Nh6 Bf1 Ng8 Ra2 Nh6 Nb1 Ng8 Nc3 Nh6 Ra1 Ng8 Ra3 Nh6 Nb1 Ng8 Ra1 Nh6

Now any of the 12 moves Qh5, Qg4, Qf3, Ba6, Bb5, Bc4, Bd3, Ra2, Ra3, Na3, Nc3 or Nh3 would lead to a threefold repetition.

Improve this answer
4
  • 1
    He wants to achieve a position that has the most possible legal moves at that point that would lead to an immediate three time repetition. Your game has many positions that occur twice but they can't all be reached from the end position in one move.
    – RemcoGerlich
    Aug 9, 2018 at 12:57
  • @RemcoGerlich : hmmm, in that case I was indeed very far from understanding the question !
    – Evargalo
    Aug 9, 2018 at 13:16
  • I'm not sure, you do show that you need to know potentially a whole game to decide whether there's going to be repetition, maybe that's more helpful to his problem than the actual question.
    – RemcoGerlich
    Aug 9, 2018 at 13:19
  • For pawn moves and captures, I do indeed flush out the entire game history. The issue, as you know by now is having to provide the neural network the last 100 positions as input in order to detect threefold repetitions. As Remco explained, the maximum number of moves is indeed 12 (although positions with 12 possible ways to reach a threefold repetition are very contrived).
    – Aadit M Shah
    Aug 10, 2018 at 3:02
2

NB. I'm asking this question because I'm developing a neural network that plays chess. Hence, I'd like to reduce the size of the input to the neural network as much as possible. Providing a history of 25 positions to the neural network is a lot.

There are simpler ways to check for 3-fold repetition than feed the game history to a neural network -- you should not do that, it's very odd design decision, and in my opinion you'd better focus on getting NN playing chess better than solving the edge cases that can easily be dealt with in just a few lines of code.

Improve this answer
1
  • 1
    The neural network doesn't only detect threefold repetitions. It gives the best possible move given a certain game state, and due to the graph history interaction problem, the history of a position is a part of the game state. For example, in a given position p the best move might be x, leading to position q. However, if we know that q has been repeated then the neural network might be incentivized to select move y which doesn't lead to a threefold repetition.
    – Aadit M Shah
    Aug 10, 2018 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.