Answers.Body: <p>Although @user1583209 is on the right track. His approach would only work for a chess GUI but too <strong>slow</strong> for a chess engine. Modern engines only check for the last few moves, they won't go all the way back to the initial position because that'd be an almost waste of time.</p>
  
  <p>You have complicated your code too much. In reality, checking for repetition is very simple:</p>
  
  <blockquote>
    <p><a href="https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp" rel="noreferrer">https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp</a></p>
  </blockquote>
  
  <pre><code>int cnt = 0;
  for (int i = 4; i &lt;= end; i += 2)
  {
    stp = stp-&gt;previous-&gt;previous;
  
    // At root position ply is 1, so return a draw score if a position
    // repeats once earlier but after or at the root, or repeats twice
    // strictly before the root.
    if (   stp-&gt;key == st-&gt;key
        &amp;&amp; ++cnt + (ply - i &gt; 0) == 2)
        return true;
  }
  </code></pre>
  
  <p>You go back in the history and check the key for your position. <strong>Very simple</strong>. You may want to ignore the <code>ply</code> check.</p>
  
  <p>You should have a way to hash your position, if you don't you will need it for transposition table anyway. </p>
  
  <p>A useful reference link to prove my idea is correct:</p>
  
  <blockquote>
    <p><a href="http://talkchess.com/forum/viewtopic.php?t=59322&amp;highlight=move+repetitions" rel="noreferrer">http://talkchess.com/forum/viewtopic.php?t=59322&amp;highlight=move+repetitions</a></p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T09:30:43.290Z
Answers.Text: I don't have a history on my engine. I may have to implement it like you suggested. Thank you.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T09:35:21.323Z
Answers.Text: @SrikaraKrishnaKanduri Check my edited link.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-02T02:01:36.167Z
Answers.Text: if you happen to have all the Fen positions stored in a move list object, I believe checking them backwards until the other 2 repetitions are found OR a 0 halfmove is found (while also only start looking when both the index move AND the halfmove is greater than 7) is faster than checking a key vs the rest of the keys? Maybe requires some string manipulation (splitting to remove clocks and see the halfmove clock) but they both just lighting fast, except to what I understood, keys are tested vs ALL keys?
Answers.UserDisplayName: ajax333221
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T09:25:20.817Z
Answers.LastActivityDate: 2017-03-31T09:35:13.643Z
Answers.LastEditDate: 2017-03-31T09:35:13.643Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>I would look at the source code for TSCP which implements zobrist keys. Basically you assign a unique number to each position and store the numbers in a list. Then check if the same number is in the list three times. you generate the unique number based on the position of the pieces, en passant square, side to move. here i have copied and pasted the TSCP code (authored by Tom Kerrigan). hash_piece is indexed by the color(2), piece type(6), and position(64). hash_side is the side to move. hash_ep is the en passant square. The initialization function populates a table of random numbers for each of these possible entries. To generate the unique position for a position<br>
  you look up all the entries correspoding to a given position and xor the numbers from the three tables (this is the set_hash function). You probably dont need the hash_rand on newer computers with better random number generators. </p>
  
  <pre><code>void init_hash()
      {
          int i, j, k;
  
          srand(0);
          for (i = 0; i &lt; 2; ++i)
              for (j = 0; j &lt; 6; ++j)
                  for (k = 0; k &lt; 64; ++k)
                      hash_piece[i][j][k] = hash_rand();
          hash_side = hash_rand();
          for (i = 0; i &lt; 64; ++i)
              hash_ep[i] = hash_rand();
      }
  
  
      /* hash_rand() XORs some shifted random numbers together to make sure
         we have good coverage of all 32 bits. (rand() returns 16-bit numbers
         on some systems.) */
  
      int hash_rand()
      {
          int i;
          int r = 0;
  
          for (i = 0; i &lt; 32; ++i)
              r ^= rand() &lt;&lt; i;
          return r;
      }
  
  
      /* set_hash() uses the Zobrist method of generating a unique number (hash)
         for the current chess position. Of course, there are many more chess
         positions than there are 32 bit numbers, so the numbers generated are
         not really unique, but they're unique enough for our purposes (to detect
         repetitions of the position). 
         The way it works is to XOR random numbers that correspond to features of
         the position, e.g., if there's a black knight on B8, hash is XORed with
         hash_piece[BLACK][KNIGHT][B8]. All of the pieces are XORed together,
         hash_side is XORed if it's black's move, and the en passant square is
         XORed if there is one. (A chess technicality is that one position can't
         be a repetition of another if the en passant state is different.) */
  
      void set_hash()
      {
          int i;
  
          hash = 0;   
          for (i = 0; i &lt; 64; ++i)
              if (color[i] != EMPTY)
                  hash ^= hash_piece[color[i]][piece[i]][i];
          if (side == DARK)
              hash ^= hash_side;
          if (ep != -1)
              hash ^= hash_ep[ep];
      }
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-04T15:50:13.730Z
Answers.Text: This is also my approach in my answer.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-04T17:08:00.503Z
Answers.Text: Cool, I upvoted you. Ive always liked the TSCP source code
Answers.UserDisplayName: nak3c
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-04T15:38:44.107Z
Answers.LastActivityDate: 2017-04-04T15:38:44.107Z
Answers.UserDisplayName: nak3c
Answers.Body: <p>Why not just keep a map indexed by the position hash pointing to a count of how many times it has been seen so far?  No iteration required... just update the hash as you traverse the move tree.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-01T02:13:55.480Z
Answers.Text: That's known as transposition table. It's possible.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-03T07:18:27.547Z
Answers.Text: I iterated through the list of FEN for now. I will try to update it to your idea later. Thanks for the answer.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T23:19:31.903Z
Answers.LastActivityDate: 2017-03-31T23:19:31.903Z
Answers.UserDisplayName: tbischel
Answers.Body: <p>Threefold-repetition is about <strong>a position</strong> (not moves) occurring three times. Those positions <strong>do not</strong> have to be reached by the same moves. </p>
  
  <p>Also (as this also seems to be confused sometimes) it is completely irrelevant when this happens, e.g. you can have the same positions after moves 10, 42 and 63 and it would still be a draw. </p>
  
  <p>You should check whether the position is repeated. So basically at every move you need to check whether the position occurred in the game before. By <em>position</em> I mean the same position of all pieces on the board <em>and</em> the same castling rights <em>and</em> the same player to move <em>and</em> the same enpassant rights. That is, basically you are checking whether the <a href="https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation" rel="noreferrer">FEN</a> are the same (except for halfmove clock and fullmove number).</p>
  
  <p>Something like:</p>
  
  <pre><code>int positionCount=0;
  while(iterate through game positions) {
      if ( positionToCheck.piecesPosition == iterationPosition.piecesPosition &amp;&amp; 
           positionToCheck.castleRights == iterationPosition.castleRights &amp;&amp; 
           positionToCheck.enPassantRights == iterationPosition.enPassantRights &amp;&amp;
           positionToCheck.playerToMove == iterationPosition.playerToMove ) {
        positionCount++;
      }
      if (positionCount==3) { return true; }
  }
  return false;
  </code></pre>
  
  <p>Of course you can simplify the above algorithm. E.g. you only need to iterate over position with the same player to move. Also you only need to iterate over positions back to the last pawn move, capture or castling move.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T09:12:51.157Z
Answers.Text: @SrikaraKrishnaKanduri: If the position of the pieces on the board is the same, the "same set of legal moves"  just means that there should be the same castling rights, same player to move and the same enpassant rights. I believe these are much easier/faster to check than having to compare all possible moves. I updated my answer.
Answers.UserDisplayName: user1583209
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T09:25:23.567Z
Answers.Text: @SrikaraKrishnaKanduri: Not sure what you mean. You could store the FEN strings for all positions that occurred in the game. That would typically be around 100 strings of up to around 100 characters each. But there are more efficient ways to implement this as you can read about here: https://chessprogramming.wikispaces.com/Repetitions
Answers.UserDisplayName: user1583209
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T09:28:57.087Z
Answers.Text: I suppose FEN will do the work. Thank you.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T12:03:39.523Z
Answers.Text: And you can stop looking back any time something non-reversible happens: pawn moves, captures and castling.
Answers.UserDisplayName: David Richerby
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T12:57:48.520Z
Answers.Text: @DavidRicherby I will consider that. Thank you.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T21:54:08.467Z
Answers.Text: @SrikaraKrishnaKanduri A note about using the FEN string: the en passant portion of the string is listed even if no pawn is able to capture this way. In this case, the en passant portion should be disregarded.
Answers.UserDisplayName: Mark H
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-03T07:16:40.877Z
Answers.Text: @MarkH Wont we mark the enPassant portion with a "-" if no pawn is able to capture the enPassant pawn in the next move?
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-03T13:47:07.910Z
Answers.Text: @SrikaraKrishnaKanduri According to the FEN specification, the en passant position is always recorded in the FEN string after a pawn double move, even if there is no pawn that can capture en passant. In my program, when checking for 3-fold repetition, I edit the FEN string to remove the en passant field if there is no way to capture.
Answers.UserDisplayName: Mark H
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-04T05:47:07.790Z
Answers.Text: @MarkH I am storing the enPassant only for the next move. So, its all good.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T08:14:42.180Z
Answers.LastActivityDate: 2017-04-04T07:45:54.720Z
Answers.LastEditDate: 2017-04-04T07:45:54.720Z
Answers.UserDisplayName: user1583209
Body: <p>I'm making a chess engine that has to implement a three-fold repetition as my AI vs AI engine repeats the same moves over and over again (Have a look at my post here - <a href="https://chess.stackexchange.com/questions/17075/my-chess-ai-makes-the-same-repeated-moves">My chess AI makes the same repeated moves</a>). I've read the rules of this scenario from the wiki and would like to implement it. I'm not sure if I have understood the rules thoroughly, so what I'm doing here is - </p>
  
  <ol>
  <li>Checking if the present move made (from the movelog I have) has already occurred before.</li>
  <li>If it did, check for one more occurrence (as we need three in total).</li>
  <li>If the moves pattern for all the three re-occurred moves is same, return true.</li>
  </ol>
  
  <p>Please have a look at my Java code and suggest me the corrections.</p>
  
  <pre><code>    boolean isThreeFoldRepetition() {
          List&lt;Move&gt; allMoves = Table.get().getMoveLog().getMoves();
          int currentMoveIndex = allMoves.size()-1;
          int secondFoldMoveIndex = currentMoveIndex - 4;
          int firstFoldMoveIndex = secondFoldMoveIndex - 4;
          int distance = currentMoveIndex - secondFoldMoveIndex - 1;
  
          while(firstFoldMoveIndex &gt;= 0){
              Move thirdFoldMoveMade = allMoves.get(currentMoveIndex);
              Move secondFoldMoveMade = allMoves.get(secondFoldMoveIndex);
              Move firstFoldMoveMade = allMoves.get(firstFoldMoveIndex);
  
              if(thirdFoldMoveMade.equals(secondFoldMoveMade) &amp;&amp;
                 secondFoldMoveMade.equals(firstFoldMoveMade) &amp;&amp;
                 firstFoldMoveIndex - distance &gt;= 0){
                  int gap;
                  for(gap = 1; gap &lt;= distance; gap++){
                      thirdFoldMoveMade = allMoves.get(currentMoveIndex - gap);
                      secondFoldMoveMade = allMoves.get(secondFoldMoveIndex - gap);
                      firstFoldMoveMade = allMoves.get(firstFoldMoveIndex - gap);
  
                      if(!thirdFoldMoveMade.equals(secondFoldMoveMade) || !secondFoldMoveMade.equals(firstFoldMoveMade))
                          break;
                  }
                  if(gap == distance)
                      return true;
              }
  
              secondFoldMoveIndex -= 2;
              firstFoldMoveIndex = secondFoldMoveIndex - distance - 3;
          }
          return false;
      }
  </code></pre>
  
Tags: <engines><programming><threefold-repetition>
Title: Programming three-fold repetition for my chess engine
ThreadText: # Programming three-fold repetition for my chess engine
  
  (Asked by: username_0 on 2017-03-31)
  
  I'm making a chess engine that has to implement a three-fold repetition as my AI vs AI engine repeats the same moves over and over again (Have a look at my post here - My chess AI makes the same repeated moves). I've read the rules of this scenario from the wiki and would like to implement it. I'm not sure if I have understood the rules thoroughly, so what I'm doing here is - 
  
  Checking if the present move made (from the movelog I have) has already occurred before.
  If it did, check for one more occurrence (as we need three in total).
  If the moves pattern for all the three re-occurred moves is same, return true.
  
  Please have a look at my Java code and suggest me the corrections.
      boolean isThreeFoldRepetition() {
          List allMoves = Table.get().getMoveLog().getMoves();
          int currentMoveIndex = allMoves.size()-1;
          int secondFoldMoveIndex = currentMoveIndex - 4;
          int firstFoldMoveIndex = secondFoldMoveIndex - 4;
          int distance = currentMoveIndex - secondFoldMoveIndex - 1;
  
          while(firstFoldMoveIndex >= 0){
              Move thirdFoldMoveMade = allMoves.get(currentMoveIndex);
              Move secondFoldMoveMade = allMoves.get(secondFoldMoveIndex);
              Move firstFoldMoveMade = allMoves.get(firstFoldMoveIndex);
  
              if(thirdFoldMoveMade.equals(secondFoldMoveMade) &&
                 secondFoldMoveMade.equals(firstFoldMoveMade) &&
                 firstFoldMoveIndex - distance >= 0){
                  int gap;
                  for(gap = 1; gap <= distance; gap++){
                      thirdFoldMoveMade = allMoves.get(currentMoveIndex - gap);
                      secondFoldMoveMade = allMoves.get(secondFoldMoveIndex - gap);
                      firstFoldMoveMade = allMoves.get(firstFoldMoveIndex - gap);
  
                      if(!thirdFoldMoveMade.equals(secondFoldMoveMade) || !secondFoldMoveMade.equals(firstFoldMoveMade))
                          break;
                  }
                  if(gap == distance)
                      return true;
              }
  
              secondFoldMoveIndex -= 2;
              firstFoldMoveIndex = secondFoldMoveIndex - distance - 3;
          }
          return false;
      }
  
  **Tags:** engines, programming, threefold-repetition
  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_5 on 2017-03-31. Score: 14 | Accepted answer
  
  Threefold-repetition is about a position (not moves) occurring three times. Those positions do not have to be reached by the same moves. 
  Also (as this also seems to be confused sometimes) it is completely irrelevant when this happens, e.g. you can have the same positions after moves 10, 42 and 63 and it would still be a draw. 
  You should check whether the position is repeated. So basically at every move you need to check whether the position occurred in the game before. By position I mean the same position of all pieces on the board and the same castling rights and the same player to move and the same enpassant rights. That is, basically you are checking whether the FEN are the same (except for halfmove clock and fullmove number).
  Something like:
  int positionCount=0;
  while(iterate through game positions) {
      if ( positionToCheck.piecesPosition == iterationPosition.piecesPosition && 
           positionToCheck.castleRights == iterationPosition.castleRights && 
           positionToCheck.enPassantRights == iterationPosition.enPassantRights &&
           positionToCheck.playerToMove == iterationPosition.playerToMove ) {
        positionCount++;
      }
      if (positionCount==3) { return true; }
  }
  return false;
  
  Of course you can simplify the above algorithm. E.g. you only need to iterate over position with the same player to move. Also you only need to iterate over positions back to the last pawn move, capture or castling move.
  
  > **Comments:**
  > **username_5**: @SrikaraKrishnaKanduri: If the position of the pieces on the board is the same, the "same set of legal moves"  just means that there should be the same castling rights, same player to move and the same enpassant rights. I believe these are much easier/faster to check than having to compare all possible moves. I updated my answer.  
  > **username_5**: @SrikaraKrishnaKanduri: Not sure what you mean. You could store the FEN strings for all positions that occurred in the game. That would typically be around 100 strings of up to around 100 characters each. But there are more efficient ways to implement this as you can read about here: https://chessprogramming.wikispaces.com/Repetitions  
  > **username_0**: I suppose FEN will do the work. Thank you.  
  > **username_6**: And you can stop looking back any time something non-reversible happens: pawn moves, captures and castling.  
  > **username_0**: @DavidRicherby I will consider that. Thank you.  
  > **username_7**: @SrikaraKrishnaKanduri A note about using the FEN string: the en passant portion of the string is listed even if no pawn is able to capture this way. In this case, the en passant portion should be disregarded.  
  > **username_0**: @MarkH Wont we mark the enPassant portion with a "-" if no pawn is able to capture the enPassant pawn in the next move?  
  > **username_7**: @SrikaraKrishnaKanduri According to the FEN specification, the en passant position is always recorded in the FEN string after a pawn double move, even if there is no pawn that can capture en passant. In my program, when checking for 3-fold repetition, I edit the FEN string to remove the en passant field if there is no way to capture.  
  > **username_0**: @MarkH I am storing the enPassant only for the next move. So, its all good.  
  
  ---
  
  ### Answer by username_1 on 2017-03-31. Score: 6
  
  Although @username_5 is on the right track. His approach would only work for a chess GUI but too slow for a chess engine. Modern engines only check for the last few moves, they won't go all the way back to the initial position because that'd be an almost waste of time.
  You have complicated your code too much. In reality, checking for repetition is very simple:
  
  https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp
  
  int cnt = 0;
  for (int i = 4; i <= end; i += 2)
  {
    stp = stp->previous->previous;
  
    // At root position ply is 1, so return a draw score if a position
    // repeats once earlier but after or at the root, or repeats twice
    // strictly before the root.
    if (   stp->key == st->key
        && ++cnt + (ply - i > 0) == 2)
        return true;
  }
  
  You go back in the history and check the key for your position. Very simple. You may want to ignore the ply check.
  You should have a way to hash your position, if you don't you will need it for transposition table anyway. 
  A useful reference link to prove my idea is correct:
  
  http://talkchess.com/forum/viewtopic.php?t=59322&highlight=move+repetitions
  
  > **Comments:**
  > **username_0**: I don't have a history on my engine. I may have to implement it like you suggested. Thank you.  
  > **username_1**: @SrikaraKrishnaKanduri Check my edited link.  
  > **username_2**: if you happen to have all the Fen positions stored in a move list object, I believe checking them backwards until the other 2 repetitions are found OR a 0 halfmove is found (while also only start looking when both the index move AND the halfmove is greater than 7) is faster than checking a key vs the rest of the keys? Maybe requires some string manipulation (splitting to remove clocks and see the halfmove clock) but they both just lighting fast, except to what I understood, keys are tested vs ALL keys?  
  
  ---
  
  ### Answer by username_3 on 2017-04-04. Score: 2
  
  I would look at the source code for TSCP which implements zobrist keys. Basically you assign a unique number to each position and store the numbers in a list. Then check if the same number is in the list three times. you generate the unique number based on the position of the pieces, en passant square, side to move. here i have copied and pasted the TSCP code (authored by Tom Kerrigan). hash_piece is indexed by the color(2), piece type(6), and position(64). hash_side is the side to move. hash_ep is the en passant square. The initialization function populates a table of random numbers for each of these possible entries. To generate the unique position for a position
  you look up all the entries correspoding to a given position and xor the numbers from the three tables (this is the set_hash function). You probably dont need the hash_rand on newer computers with better random number generators. 
  void init_hash()
      {
          int i, j, k;
  
          srand(0);
          for (i = 0; i < 2; ++i)
              for (j = 0; j < 6; ++j)
                  for (k = 0; k < 64; ++k)
                      hash_piece[i][j][k] = hash_rand();
          hash_side = hash_rand();
          for (i = 0; i < 64; ++i)
              hash_ep[i] = hash_rand();
      }
  
  
      /* hash_rand() XORs some shifted random numbers together to make sure
         we have good coverage of all 32 bits. (rand() returns 16-bit numbers
         on some systems.) */
  
      int hash_rand()
      {
          int i;
          int r = 0;
  
          for (i = 0; i < 32; ++i)
              r ^= rand() << i;
          return r;
      }
  
  
      /* set_hash() uses the Zobrist method of generating a unique number (hash)
         for the current chess position. Of course, there are many more chess
         positions than there are 32 bit numbers, so the numbers generated are
         not really unique, but they're unique enough for our purposes (to detect
         repetitions of the position). 
         The way it works is to XOR random numbers that correspond to features of
         the position, e.g., if there's a black knight on B8, hash is XORed with
         hash_piece[BLACK][KNIGHT][B8]. All of the pieces are XORed together,
         hash_side is XORed if it's black's move, and the en passant square is
         XORed if there is one. (A chess technicality is that one position can't
         be a repetition of another if the en passant state is different.) */
  
      void set_hash()
      {
          int i;
  
          hash = 0;   
          for (i = 0; i < 64; ++i)
              if (color[i] != EMPTY)
                  hash ^= hash_piece[color[i]][piece[i]][i];
          if (side == DARK)
              hash ^= hash_side;
          if (ep != -1)
              hash ^= hash_ep[ep];
      }
  
  > **Comments:**
  > **username_1**: This is also my approach in my answer.  
  > **username_3**: Cool, I upvoted you. Ive always liked the TSCP source code  
  
  ---
  
  ### Answer by username_4 on 2017-03-31. Score: 0
  
  Why not just keep a map indexed by the position hash pointing to a count of how many times it has been seen so far? No iteration required... just update the hash as you traverse the move tree.
  
  > **Comments:**
  > **username_1**: That's known as transposition table. It's possible.  
  > **username_0**: I iterated through the list of FEN for now. I will try to update it to your idea later. Thanks for the answer.  
  
  ---
  
  