Minimax Algorithm : AI In Game Theory

Most 2-player games need to have an in-built AI to play against when there is only a single player. A general algorithm that is widely used in most strategy games is called the Minimax Algorithm.

What is the Minimax Algorithm?

The minimax algorithm is a decision-making algorithm used to determine the most optimal move of a player in a two-player game against their opponent. Games are non-cooperative in nature like Chess, Go, etc.

The minimax algorithm is an example of artificial intelligence which does not use machine learning. The minimax algorithm is simply a recursive backtracking algorithm that uses the depth-first search to explore the entire tree while selecting the most optimal path for a player.

Predictions : The Intuition

The intuition behind the Minimax algorithm is that we look ahead in time and predict the best possible move using the information for the next move in the game. The possible moves in the game can be represented by a tree as shown:

The depth of the tree represents how far ahead in time we want to look to base our predictions on. For more complex games with more choices, the branching factor can be very high. Interesting, a complex game tree like the one above, was used by Deep Blue, the first computer system to defeat a reigning world champion in a match under standard chess tournament time controls.

Optimal Path Finding Logic

So, how does the computer determine which path is optimal?

We must initially determine the ‘score’ of each move. This is entirely up to the programmer. As an example, we could use number of blank spaces on the board, number of pawns remaining, positioning of opponent pawns, number of moves to win, etc. Let’s call the function that is used to determine the score of any move, evaluator().

Both players in the game have conflicting goals. One player (maximizer) aims to get the maximized value from the algorithm while the other (minimizer) aims to get the minimized value from the algorithm.

The initial values of the maximizer & minimizer are set to their worst case values of -infinity & +infinity. The maximizer selects the maximum possible value from its children while the minimizer selects the minimum possible value from its children.

The components of the algorithm can ne summarized as follows:

1. It’s recursive in nature. The Maximizer and Minimizer functions are called alternately
2. Exit Condition in the Recursion : this could occur either when a player has won or the board is fully occupied or when the players have completed a pre-determined number of moves
3. Base Condition in the Recursion: when the terminal nodes/leaves are reached, the evaluator function is called

Representation of the Code Algorithm in Python:

I designed a simple dots and boxes game and implemented the minimax algorithm to play against the computer.

Below is my code for the evaluator function for a game of Dots & Boxes in Python. The evaluator function returns the difference between the number of boxes possessed by player2 and the number of boxes possessed by player1.

Drawbacks:

Time Complexity scales exponentially as game complexity increases as O(b^m) where b is the number of branches (or choices) at each stage and m is the total number of moves by the players. Time complexity can be reduced by using Alpha-Beta pruning. Alpha-Beta Pruning is a dynamic programming optimization to the recursive Minimax algorithm.