Answers.Body: <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-10T03:15:03.533Z
Answers.Text: 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](https://chessprogramming.wikispaces.com/Graph+History+Interaction), 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.
Answers.UserDisplayName: Aadit M Shah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-09T23:39:37.433Z
Answers.LastActivityDate: 2019-07-11T10:29:47.823Z
Answers.LastEditDate: 2019-07-11T10:29:47.823Z
Answers.UserDisplayName: lenik
Answers.Body: <p>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. </p>
  
  <p>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.</p>
  
  <p>Check positions after moves 1, 26 and 50 in this fantastic game, a fighting draw:</p>
  
  <pre><code>[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}
  </code></pre>
  
  <hr>
  
  <p>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.</p>
  
  <pre><code>[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
  </code></pre>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-09T12:57:04.117Z
Answers.Text: 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.
Answers.UserDisplayName: RemcoGerlich
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-09T13:16:47.453Z
Answers.Text: @RemcoGerlich : hmmm, in that case I was indeed very far from understanding the question !
Answers.UserDisplayName: Evargalo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-09T13:19:19.380Z
Answers.Text: 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.
Answers.UserDisplayName: RemcoGerlich
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-10T03:02:09.803Z
Answers.Text: 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).
Answers.UserDisplayName: Aadit M Shah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-09T12:11:19.187Z
Answers.LastActivityDate: 2018-08-09T13:44:01.070Z
Answers.LastEditDate: 2018-08-09T13:44:01.070Z
Answers.UserDisplayName: Evargalo
Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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?</p>
  
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-09T11:57:47.697Z
Comments.Text: 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
Comments.UserDisplayName: Brian Towers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-09T12:14:54.003Z
Comments.Text: @BrianTowers : those 75 move and 5-fold repetition rules are not in the FIDE rules. Maybe it is a specificity of the USCF. Anyway, the first line of the question adress that issue.
Comments.UserDisplayName: Evargalo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-09T12:31:13.797Z
Comments.Text: @BrianTowers Thanks. With the 75-move rule and the 5-fold repetition rule the number is indeed brought down to 18 (i.e. `floor(75 / (5 - 1))`). However, for chess engines it makes more sense to interpret the 50-move rule and the threefold repetition rule as non-optional because the optionality of these rules messes with the evaluations of the chess engine. For example, you may have a win in 74 moves (but without any pawn moves or captures) and another win in 99 moves but with pawn moves and captures. If you naively select the 74 move win variation then the opponent can claim a draw on move 50.
Comments.UserDisplayName: Aadit M Shah
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-09T12:33:55.207Z
Comments.Text: @Evargalo Actually, if I remember correctly they are in the FIDE rules.
Comments.UserDisplayName: Aadit M Shah
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-09T13:01:30.613Z
Comments.Text: 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.
Comments.UserDisplayName: RemcoGerlich
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-09T13:04:17.857Z
Comments.Text: In practice I can't recall ever seeing a position where 2 different moves would each lead to three time repetition.
Comments.UserDisplayName: RemcoGerlich
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-09T13:05:54.580Z
Comments.Text: That said, I don't understand why you want to pass these positions to a neural network in the first place.
Comments.UserDisplayName: RemcoGerlich
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-09T13:26:56.950Z
Comments.Text: @AaditMShah : you are right and I stand corrected. This is rule 9.6 here: http://fide.com/fide/handbook.html?id=208&view=article
Comments.UserDisplayName: Evargalo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-10T02:43:51.980Z
Comments.Text: @RemcoGerlich Makes perfect sense. Thank you. I want to pass these positions to a neural network so that it can detect threefold repetitions.
Comments.UserDisplayName: Aadit M Shah
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-10T07:07:16.457Z
Comments.Text: 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?
Comments.UserDisplayName: RemcoGerlich
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-10T09:26:22.637Z
Comments.Text: @RemcoGerlich Now that I think about it, it does only care about threefold repetitions one ply deep. Indeed, I need to provide the entire history since the last pawn move or capture for correct behavior. We can pack an entire board position into four 8x8 bitboards (i.e. 256 bits). With 100 board positions that means we require 400 bitboards or 25600 bits of input. That seems doable. Thanks.
Comments.UserDisplayName: Aadit M Shah
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-10T09:33:54.600Z
Comments.Text: @AaditMShah: changes in castling rights (due to castling or otherwise) are also irreversible.
Comments.UserDisplayName: RemcoGerlich
Tags: <mathematics><threefold-repetition><50-move-rule>
Title: What's the maximum number of moves that can result in a threefold repetition from an arbitrary position?
ThreadText: # What's the maximum number of moves that can result in a threefold repetition from an arbitrary position?
  
  (Asked by: username_0 on 2018-08-09)
  
  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.
  
  **Tags:** mathematics, threefold-repetition, 50-move-rule
  
  > **Comments:**
  > **username_1**: 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  
  > **username_2**: @BrianTowers : those 75 move and 5-fold repetition rules are not in the FIDE rules. Maybe it is a specificity of the USCF. Anyway, the first line of the question adress that issue.  
  > **username_0**: @BrianTowers Thanks. With the 75-move rule and the 5-fold repetition rule the number is indeed brought down to 18 (i.e. `floor(75 / (5 - 1))`). However, for chess engines it makes more sense to interpret the 50-move rule and the threefold repetition rule as non-optional because the optionality of these rules messes with the evaluations of the chess engine. For example, you may have a win in 74 moves (but without any pawn moves or captures) and another win in 99 moves but with pawn moves and captures. If you naively select the 74 move win variation then the opponent can claim a draw on move 50.  
  > **username_0**: @username_2 Actually, if I remember correctly they are in the FIDE rules.  
  > **username_3**: 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.  
  > **username_3**: In practice I can't recall ever seeing a position where 2 different moves would each lead to three time repetition.  
  > **username_3**: That said, I don't understand why you want to pass these positions to a neural network in the first place.  
  > **username_2**: @AaditMShah : you are right and I stand corrected. This is rule 9.6 here: http://fide.com/fide/handbook.html?id=208&view=article  
  > **username_0**: @username_3 Makes perfect sense. Thank you. I want to pass these positions to a neural network so that it can detect threefold repetitions.  
  > **username_3**: 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?  
  > **username_0**: @username_3 Now that I think about it, it does only care about threefold repetitions one ply deep. Indeed, I need to provide the entire history since the last pawn move or capture for correct behavior. We can pack an entire board position into four 8x8 bitboards (i.e. 256 bits). With 100 board positions that means we require 400 bitboards or 25600 bits of input. That seems doable. Thanks.  
  > **username_3**: @AaditMShah: changes in castling rights (due to castling or otherwise) are also irreversible.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2018-08-09. Score: 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.
  
  > **Comments:**
  > **username_0**: 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](https://chessprogramming.wikispaces.com/Graph+History+Interaction), 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.  
  
  ---
  
  ### Answer by username_2 on 2018-08-09. Score: 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 @username_3 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.
  
  > **Comments:**
  > **username_3**: 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.  
  > **username_2**: @username_3 : hmmm, in that case I was indeed very far from understanding the question !  
  > **username_3**: 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.  
  > **username_0**: 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).  
  
  ---
  
  