How to handle cycles in minimax algorithm

Question

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.

Answer 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 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.