Answers.Body: <p>Indeed, if your game allows cycles, your tree is more of a graph.</p>
  <p>A simple approach to avoiding infinite loops is to have a hard cap on how far down the tree you explore. If you reach it before the end of the tree, you can use a heuristic to compute your leaf value. But I understand you'd like to compute the full game tree.</p>
  <p>First things first, how do you detect cycles? You can store explored game states and check whether you've encountered them. A way to do this relatively efficiently is to use <a href="https://en.wikipedia.org/wiki/Zobrist_hashing" rel="nofollow noreferrer">Zobrist hashing</a> to represent each game state.</p>
  <p>What happens when you reach a cycle?</p>
  <ul>
  <li>One simple approach is declaring a draw when you end up at a cycle and end the game there. After all, your &quot;ideal&quot; player should not make many moves to end up in the same position, so marking a cycle as a draw makes sense.</li>
  <li>If you've stored your previous positions and already have a value for that position, you can simply use it as your leaf value.</li>
  <li>You could try to discourage moves leading to cycles altogether. If you detect a cycle, you could penalize that move so your player doesn't go through it.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-30T12:31:00.250Z
Answers.LastActivityDate: 2023-12-30T12:31:00.250Z
Answers.UserDisplayName: Valentin Calomme
Body: <p>For example, I am implementing AI for turn based game and have enough computational resources for build full game tree. My problem is the game can be infinite if both players will repeat moves and my minimax implementation stucks because game tree is infinite respectively.</p>
  <p>For example, my game is in state S1, player 1 do action A1, player 2 do action A2 and we are again in state S1. I can't evaluate S1 node because I need to evaluate all subnodes.</p>
  <p>I have no idea how to handle this.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-17T16:26:33.247Z
Comments.Text: Did you find a solution? I'm trying to do the exact same thing.
Comments.UserDisplayName: Umomps
Tags: <game-ai><minimax>
Title: How to handle cycles in minimax algorithm
UserDisplayName: Terri Erickson
ThreadText: # How to handle cycles in minimax algorithm
  
  (Asked by: username_0 on 2021-07-09)
  
  For example, I am implementing AI for turn based game and have enough computational resources for build full game tree. My problem is the game can be infinite if both players will repeat moves and my minimax implementation stucks because game tree is infinite respectively.
  
  For example, my game is in state S1, player 1 do action A1, player 2 do action A2 and we are again in state S1. I can't evaluate S1 node because I need to evaluate all subnodes.
  
  I have no idea how to handle this.
  
  **Tags:** game-ai, minimax
  > **Comments:**
  > **username_1**: Did you find a solution? I'm trying to do the exact same thing.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2023-12-30. Score: 1
  
  Indeed, if your game allows cycles, your tree is more of a graph.
  
  A simple approach to avoiding infinite loops is to have a hard cap on how far down the tree you explore. If you reach it before the end of the tree, you can use a heuristic to compute your leaf value. But I understand you'd like to compute the full game tree.
  
  First things first, how do you detect cycles? You can store explored game states and check whether you've encountered them. A way to do this relatively efficiently is to use [Zobrist hashing](https://en.wikipedia.org/wiki/Zobrist_hashing) to represent each game state.
  
  What happens when you reach a cycle?
  
  * One simple approach is declaring a draw when you end up at a cycle and end the game there. After all, your "ideal" player should not make many moves to end up in the same position, so marking a cycle as a draw makes sense.
  * If you've stored your previous positions and already have a value for that position, you can simply use it as your leaf value.
  * You could try to discourage moves leading to cycles altogether. If you detect a cycle, you could penalize that move so your player doesn't go through it.
  
  
  ---
  
  