Answers.Body: <p>You may want to consider third-repetition in your search. Stockfish does that:</p>
  
  <p><a href="https://github.com/official-stockfish/Stockfish/blob/30c583204f97da2c67b5042c30327013e70ae209/src/search.cpp" rel="nofollow noreferrer">https://github.com/official-stockfish/Stockfish/blob/30c583204f97da2c67b5042c30327013e70ae209/src/search.cpp</a></p>
  
  <pre><code>    // Step 2. Check for aborted search and immediate draw
      if (Signals.stop.load(std::memory_order_relaxed) || pos.is_draw(ss-&gt;ply) || ss-&gt;ply &gt;= MAX_PLY)
          return ss-&gt;ply &gt;= MAX_PLY &amp;&amp; !inCheck ? evaluate(pos)
                                                : DrawValue[pos.side_to_move()];
  </code></pre>
  
  <p><a href="https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp" rel="nofollow noreferrer">https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp</a></p>
  
  <pre><code>/// Position::is_draw() tests whether the position is drawn by 50-move rule
  /// or by repetition. It does not detect stalemates.
  
  bool Position::is_draw(int ply) const {
  </code></pre>
  
  <p>Implementing third-repetition is important, otherwise your engine might waste moves and think it can still keep the advantage after some meaningless checks.</p>
  
  <p><strong>EDITED</strong></p>
  
  <p>You should implement the check, otherwise your engine doesn't know the move it tries to make is just simple repetition draw. You will need to program the knowledge. Someone else had the problem  like you:</p>
  
  <blockquote>
    <p><a href="http://talkchess.com/forum/viewtopic.php?t=59322&amp;highlight=move+repetitions" rel="nofollow 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-27T07:38:11.097Z
Answers.Text: I'm a beginner and can't understand such complex codes. Describing what's necessary theoretically will help me make changes to my code.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T07:39:13.113Z
Answers.Text: @SrikaraKrishnaKanduri The Stockfish code is very simple to follow. Ok, I'll expand my answer later when I have more time (I'll busy now).
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T09:18:35.937Z
Answers.Text: @SrikaraKrishnaKanduri I was about to edit my answer. Since you have posted a new question, I'll switch to the other one.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-31T09:25:24.200Z
Answers.Text: The other question is based on "how" to implement rather than "why" to implement. So, answering in this post will be apt.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-06T19:22:26.413Z
Answers.Text: this is possibly a duplicate of my question: http://chess.stackexchange.com/questions/16402/engines-keep-playing-same-game, I solved this problem by implementing an opening book. Unless I am misunderstanding and this is a three-fold repetion problem for which the solution could be a Zobrist key method
Answers.UserDisplayName: nak3c
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T07:33:42.767Z
Answers.LastActivityDate: 2017-03-31T09:42:56.290Z
Answers.LastEditDate: 2017-03-31T09:42:56.290Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>Even top level engines could do this if they evaluate the position to be completely equal.  If your AIs evaluate this position to be equal, then there's nothing wrong with a three fold.  But in the position you posted it doesn't make much sense for White to go for a three fold, considering the 7 point advantage.</p>
  
  <p>Do your AIs do this in every game, or does it just happen once in a while?  What you could try is to build a method in your code called "Evaluate".  It finds the rough evaluation of the position, and if one AI is better then it should not repeat moves.  You could do this by making it not repeat the move it made two moves ago.  So at: Rg7 Ke6 Rg6 Kd7, since the position has repeated itself call the Evaluate method.  If the Evaluate method returns that White is ahead, do not let the AI repeat the move it made two moves ago (Rg7).</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T05:33:33.817Z
Answers.Text: The Algorithm and evaluation function for both the AI players is the same and so, none of the two is better than the other. This scenario happens every time, even  for different depths in Minimax and only the pieces may differ. My engine also allows Human vs AI so won't your Evaluate method fail? I mean, a human can confuse the AI to remove its move.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T05:40:31.787Z
Answers.Text: My idea was the evaluate method would be used from an AI's specific side.  For example, assume the evaluate method returns "true" if White is better and "false" if black is better.  If "true" is returned then the AI playing White should not be allowed to go for the three fold.  If "false" is returned then the AI playing Black shouldn't be allowed to go for the three fold.  This way you can use the same method for both AIs.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T05:46:14.730Z
Answers.Text: "Shouldn't be allowed to go for the three fold" and so, what must the AI do? Play in a loop again?
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T06:01:03.320Z
Answers.Text: I would think it should play its second choice.  Although I see how that could be an endless loop if it keeps wanting to play its first choice but it's not allowed...  This may be a primitive solution but you could run a loop that checks a random move.  If that move gives an evaluation similar to the position beforehand, play it.  Else, run the loop again.  Eventually the random process should give a fairly good move.  Just remember to include in the random process that the three fold move isn't allowed.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T06:38:26.757Z
Answers.Text: How can I implement this random function for AlphaBeta pruning?
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T06:49:43.097Z
Answers.Text: I don't think you'd need too advanced a method for pruning this random function.  There's only a thousand or so possible moves for each side at a given position, so a random function without any advanced techniques should work.  If the same move is tested more than once that's fine, since the loop will only have to go a couple thousand times... that shouldn't take more than an instant.  Could I get an upvote though? :)
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T07:27:58.530Z
Answers.Text: I need to implement this engine using AlphaBeta pruning for my academic project. I think I'll just display a DRAW for now. I can't upvote you because my reputation is below 15 points.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T07:31:10.253Z
Answers.Text: Sure, no problem.  I think what you could do is make an array, and then store all the possible moves in it.  Then use a sorting technique to sort the array with the "best" evaluation move at the top and the "lowest" evaluation move at the bottom.  I'm not sure if this is the kind of pruning that is required for what you're doing though.  Probably just displaying a  draw is fine, I would think.  Is this a bug that frequently occurs in most of the games, or just a few?  Because in some cases it could actually be an equal position according to your AI.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T07:33:44.120Z
Answers.Text: Works fine with Human vs AI but not with AI vs AI. I suppose I must implement Alpha beta pruning with move ordering to sort out the moves. You've been a big help. Thank you.
Answers.UserDisplayName: Srikara Krishna Kanduri
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T07:35:04.817Z
Answers.Text: No problem, glad I could help.  Good luck on your project.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-27T05:24:54.043Z
Answers.LastActivityDate: 2017-03-27T05:24:54.043Z
Answers.UserDisplayName: Inertial Ignorance
Answers.Body: <p>Unfortunately, the only right answer to "How do I eliminate this scenario" is "fix your algorithm."  Yes, you could implement the 3-fold repetition rule, but you should also figure out what it tells you about your algorithm.</p>
  
  <p>This sort of repetition happens when there is an oscillating pattern that arises in your scoring.  Think of it like rock paper scissors.  White makes move to try to achieve a rock position, so black tries to make a counter-move that turns it into a paper position.  Then white tries to create a scissors position and black replies by creating a rock position.</p>
  
  <p>The only way to fix this is to look at your algorithm, and make the algorithm better.  My advice is to put your chess program into a debug mode and have it dump out an analysis of what it is "thinking" with each move.  Look at the factors which lead up to your final score, and understand how they're acting.</p>
  
  <p>Once you understand why the algorithm is doing what it's doing, you can fix it.  Look at the game and decide what move you'd rather see them do, and why you like that move.  See if you can add additional scoring which encourages the type of play you want to see.</p>
  
  <p>One thing in particular I've seen that can cause this sort of behavior is a discontinuity on the horizon.  If your scoring stops at your ply limit, and that position looks good from black's perspective, looking one ply further may show a good position for white instead!  This, of course, will always happen in real life, but you can try to minimize how often it happens by doing a better job of scoring each position.</p>
  
  <p>If all else fails, a little randomness can help nudge the game along.  One mode I implemented when I had to write one of these programs was a variable depth algorithm.  Sometimes it would look at 100,000 positions before making a decision, other times it might make 200,000.  That decreased the probability that I would run into a simple issue just past my horizon, because my horizon kept moving.  Instead, I might blunder into the bad move, but at least the game moved forward!</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-02T01:36:38.810Z
Answers.LastActivityDate: 2017-04-02T01:36:38.810Z
Answers.UserDisplayName: Cort Ammon
Body: <p>I've built a chess game engine using Minimax and when I play AI against the AI, everything goes fine(for sometime) until both the AI players make the same set of moves again and again. </p>
  
  <p>Observe the moves made by the AI players in the move-log(Right panel).<a href="https://i.sstatic.net/k34ry.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/k34ry.png" alt="AI vs AI repeats moves"></a></p>
  
  <p>How do I eliminate this scenario?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-03-27T04:40:39.773Z
Comments.Text: If those are the best moves the engine can find, even though the game repeats, what would you do? Find a worse move? I'd have the game terminate after the same position has been reached 3 times.
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-03-27T04:42:00.237Z
Comments.Text: First, it looks like you are missing the draw by 3-fold repetition of positions. Does your program have a method to choose from multiple moves that have an equal score, or does it just pick the first one generated?
Comments.UserDisplayName: Herb
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-03-27T05:25:14.100Z
Comments.Text: @TonyEnnis I am not sure if its correct to terminate the game because there are scenarios where the number of pieces in the board are more (Eg. White player lost only 2 of its pawns and the same scenario happens). So, I'm confused.
Comments.UserDisplayName: Srikara Krishna Kanduri
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-03-27T05:25:59.720Z
Comments.Text: @HerbWolfe I pick the first one generated.
Comments.UserDisplayName: Srikara Krishna Kanduri
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-03-27T07:34:29.330Z
Comments.Text: @TonyEnnis In this example, the move can't be the best. White is up by a bishop and some pawns!!!
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-03-27T09:17:44.187Z
Comments.Text: You need to understand _why_ the computer chooses to repeat the moves -- check the score that it gives each possible move. Its evaluation must not be very good, as white has moves available that bring the win closer.
Comments.UserDisplayName: RemcoGerlich
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-03-27T17:26:04.773Z
Comments.Text: I recommend you to try stackoverflow also. Only a few people knows about programming&game algorithms in this subforum. But you can find more than few people who knows game algorithms in stackoverflow. Good luck.
Comments.UserDisplayName: ferit
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-03-30T14:29:23.650Z
Comments.Text: @Saibot Not exactly. In fact very few people in all sites know too much about chess programming. Talkchess would be a better place.
Comments.UserDisplayName: SmallChess
Tags: <engines><programming><chess-algorithms>
Title: My chess AI makes the same repeated moves
ThreadText: # My chess AI makes the same repeated moves
  
  (Asked by: username_0 on 2017-03-27)
  
  I've built a chess game engine using Minimax and when I play AI against the AI, everything goes fine(for sometime) until both the AI players make the same set of moves again and again.
  
  Observe the moves made by the AI players in the move-log(Right panel).[![AI vs AI repeats moves](https://i.sstatic.net/k34ry.png)](https://i.sstatic.net/k34ry.png)
  
  How do I eliminate this scenario?
  
  **Tags:** engines, programming, chess-algorithms
  
  > **Comments:**
  > **username_1**: If those are the best moves the engine can find, even though the game repeats, what would you do? Find a worse move? I'd have the game terminate after the same position has been reached 3 times.  
  > **username_2**: First, it looks like you are missing the draw by 3-fold repetition of positions. Does your program have a method to choose from multiple moves that have an equal score, or does it just pick the first one generated?  
  > **username_0**: @TonyEnnis I am not sure if its correct to terminate the game because there are scenarios where the number of pieces in the board are more (Eg. White player lost only 2 of its pawns and the same scenario happens). So, I'm confused.  
  > **username_0**: @username_2Wolfe I pick the first one generated.  
  > **username_3**: @TonyEnnis In this example, the move can't be the best. White is up by a bishop and some pawns!!!  
  > **username_4**: You need to understand _why_ the computer chooses to repeat the moves -- check the score that it gives each possible move. Its evaluation must not be very good, as white has moves available that bring the win closer.  
  > **username_5**: I recommend you to try stackoverflow also. Only a few people knows about programming&game algorithms in this subforum. But you can find more than few people who knows game algorithms in stackoverflow. Good luck.  
  > **username_3**: @Saibot Not exactly. In fact very few people in all sites know too much about chess programming. Talkchess would be a better place.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_8 on 2017-04-02. Score: 5 | Accepted answer
  
  Unfortunately, the only right answer to "How do I eliminate this scenario" is "fix your algorithm." Yes, you could implement the 3-fold repetition rule, but you should also figure out what it tells you about your algorithm.
  
  This sort of repetition happens when there is an oscillating pattern that arises in your scoring. Think of it like rock paper scissors. White makes move to try to achieve a rock position, so black tries to make a counter-move that turns it into a paper position. Then white tries to create a scissors position and black replies by creating a rock position.
  
  The only way to fix this is to look at your algorithm, and make the algorithm better. My advice is to put your chess program into a debug mode and have it dump out an analysis of what it is "thinking" with each move. Look at the factors which lead up to your final score, and understand how they're acting.
  
  Once you understand why the algorithm is doing what it's doing, you can fix it. Look at the game and decide what move you'd rather see them do, and why you like that move. See if you can add additional scoring which encourages the type of play you want to see.
  
  One thing in particular I've seen that can cause this sort of behavior is a discontinuity on the horizon. If your scoring stops at your ply limit, and that position looks good from black's perspective, looking one ply further may show a good position for white instead! This, of course, will always happen in real life, but you can try to minimize how often it happens by doing a better job of scoring each position.
  
  If all else fails, a little randomness can help nudge the game along. One mode I implemented when I had to write one of these programs was a variable depth algorithm. Sometimes it would look at 100,000 positions before making a decision, other times it might make 200,000. That decreased the probability that I would run into a simple issue just past my horizon, because my horizon kept moving. Instead, I might blunder into the bad move, but at least the game moved forward!
  
  
  ---
  
  ### Answer by username_3 on 2017-03-27. Score: 1
  
  You may want to consider third-repetition in your search. Stockfish does that:
  https://github.com/official-stockfish/Stockfish/blob/30c583204f97da2c67b5042c30327013e70ae209/src/search.cpp
      // Step 2. Check for aborted search and immediate draw
      if (Signals.stop.load(std::memory_order_relaxed) || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY)
          return ss->ply >= MAX_PLY && !inCheck ? evaluate(pos)
                                                : DrawValue[pos.side_to_move()];
  
  https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp
  /// Position::is_draw() tests whether the position is drawn by 50-move rule
  /// or by repetition. It does not detect stalemates.
  
  bool Position::is_draw(int ply) const {
  
  Implementing third-repetition is important, otherwise your engine might waste moves and think it can still keep the advantage after some meaningless checks.
  EDITED
  You should implement the check, otherwise your engine doesn't know the move it tries to make is just simple repetition draw. You will need to program the knowledge. Someone else had the problem  like you:
  
  http://talkchess.com/forum/viewtopic.php?t=59322&highlight=move+repetitions
  
  > **Comments:**
  > **username_0**: I'm a beginner and can't understand such complex codes. Describing what's necessary theoretically will help me make changes to my code.  
  > **username_3**: @SrikaraKrishnaKanduri The Stockfish code is very simple to follow. Ok, I'll expand my answer later when I have more time (I'll busy now).  
  > **username_3**: @SrikaraKrishnaKanduri I was about to edit my answer. Since you have posted a new question, I'll switch to the other one.  
  > **username_0**: The other question is based on "how" to implement rather than "why" to implement. So, answering in this post will be apt.  
  > **username_6**: this is possibly a duplicate of my question: http://chess.stackexchange.com/questions/16402/engines-keep-playing-same-game, I solved this problem by implementing an opening book. Unless I am misunderstanding and this is a three-fold repetion problem for which the solution could be a Zobrist key method  
  
  ---
  
  ### Answer by username_7 on 2017-03-27. Score: -1
  
  Even top level engines could do this if they evaluate the position to be completely equal. If your AIs evaluate this position to be equal, then there's nothing wrong with a three fold. But in the position you posted it doesn't make much sense for White to go for a three fold, considering the 7 point advantage.
  
  Do your AIs do this in every game, or does it just happen once in a while? What you could try is to build a method in your code called "Evaluate". It finds the rough evaluation of the position, and if one AI is better then it should not repeat moves. You could do this by making it not repeat the move it made two moves ago. So at: Rg7 Ke6 Rg6 Kd7, since the position has repeated itself call the Evaluate method. If the Evaluate method returns that White is ahead, do not let the AI repeat the move it made two moves ago (Rg7).
  
  > **Comments:**
  > **username_0**: The Algorithm and evaluation function for both the AI players is the same and so, none of the two is better than the other. This scenario happens every time, even  for different depths in Minimax and only the pieces may differ. My engine also allows Human vs AI so won't your Evaluate method fail? I mean, a human can confuse the AI to remove its move.  
  > **username_7**: My idea was the evaluate method would be used from an AI's specific side.  For example, assume the evaluate method returns "true" if White is better and "false" if black is better.  If "true" is returned then the AI playing White should not be allowed to go for the three fold.  If "false" is returned then the AI playing Black shouldn't be allowed to go for the three fold.  This way you can use the same method for both AIs.  
  > **username_0**: "Shouldn't be allowed to go for the three fold" and so, what must the AI do? Play in a loop again?  
  > **username_7**: I would think it should play its second choice.  Although I see how that could be an endless loop if it keeps wanting to play its first choice but it's not allowed...  This may be a primitive solution but you could run a loop that checks a random move.  If that move gives an evaluation similar to the position beforehand, play it.  Else, run the loop again.  Eventually the random process should give a fairly good move.  Just remember to include in the random process that the three fold move isn't allowed.  
  > **username_0**: How can I implement this random function for AlphaBeta pruning?  
  > **username_7**: I don't think you'd need too advanced a method for pruning this random function.  There's only a thousand or so possible moves for each side at a given position, so a random function without any advanced techniques should work.  If the same move is tested more than once that's fine, since the loop will only have to go a couple thousand times... that shouldn't take more than an instant.  Could I get an upvote though? :)  
  > **username_0**: I need to implement this engine using AlphaBeta pruning for my academic project. I think I'll just display a DRAW for now. I can't upvote you because my reputation is below 15 points.  
  > **username_7**: Sure, no problem.  I think what you could do is make an array, and then store all the possible moves in it.  Then use a sorting technique to sort the array with the "best" evaluation move at the top and the "lowest" evaluation move at the bottom.  I'm not sure if this is the kind of pruning that is required for what you're doing though.  Probably just displaying a  draw is fine, I would think.  Is this a bug that frequently occurs in most of the games, or just a few?  Because in some cases it could actually be an equal position according to your AI.  
  > **username_0**: Works fine with Human vs AI but not with AI vs AI. I suppose I must implement Alpha beta pruning with move ordering to sort out the moves. You've been a big help. Thank you.  
  > **username_7**: No problem, glad I could help.  Good luck on your project.  
  
  ---
  
  