Minimax Algorithm in AI

Minimax is an approach to decision making whereby the strategy that minimizes the maximum possible loss in a two-player, zero sum game is selected. In such games, MAX chooses the moves that make the score go up while MIN makes the moves that lower the score.

What Is the Minimax Algorithm?

The minimax algorithm is a recursive search algorithm that determines the optimal move for the player in an adversarial game by exploring all future states of the game.

The minimax algorithm consists of two players:

• MAX: Player who aims to get the maximum score.
• MIN: Player who tries to make sure that MAX gets the minimum possible score.

The minimax algorithm considers that the opponent always chooses the move which is the worst for MAX. This is why minimax is helpful in playing games like chess, checkers, and tic-tac-toe, in which both players play for opposite scores.

The minimax algorithm is a part of the broader category of techniques known as adversarial search. Adversarial Search Algorithms determine future moves in an environment where there is an agent who tries to prevent the first agent from achieving its goals.

Where Minimax Comes From: A Quick Word on Game Theory

The word “minimax” was coined from game theory and not computer science. The proof of the minimax theorem was done by mathematician John von Neumann way back in 1928 in a paper titled “Zur Theorie der Gesellschaftsspiele.” The theorem proves that there is a strategy whereby players can minimize their maximum loss in any two-player zero sum game.

In 1950, Claude Shannon used the theory of game in computer chess in his paper “Programming a Computer for Playing Chess” which was published in Philosophical Magazine. The paper discussed a technique used in analyzing chess position through a limited-depth tree using a static evaluation function.

How Minimax Works, Step by Step

Minimax consists of four steps which get repeated recursively until reaching the root of the game tree.

Step 1 — Build the Game Tree

An algorithm constructs a game tree that represents a given game. Every node in the game tree is a game state. An edge stands for a legal move. The root of a game tree is the current state of the game while the child nodes represent all possible states from a single move.

Step 2 — Score the Terminal States

A terminal state is the game state in which the game is over: win, loss, or tie. Every terminal state gets assigned a numeric score according to a utility function. The standard evaluation method for a terminal state is:

Outcome	Utility Value
MAX wins	+1
Draw	0
MIN wins	−1

For those games that are too big to be able to explore to a terminal state, for example, chess, the algorithm uses the Heuristic Evaluation Function to a fixed depth level rather than exploring to a terminal state. The Heuristic Evaluation Function determines the value of a non-terminal state by taking into consideration domain-related issues, for instance, in chess these might include the count of material, positions of pieces and king safety.

Step 3 — Propagate Values Up the Tree

The algorithm propagates backward from the terminal/cutoff states up to the root. At the MAX states, the algorithm chooses the highest valued children. On the other hand, at the MIN states, the algorithm chooses the lowest valued children. This process is known as back propagation of utility values.

Step 4 — Select the Optimal Move

At the root state, the algorithm chooses the move leading to the child state with the value selected in Step 3. This move is the best possible move since it assumes that the opponent moves optimally after that.

A Worked Example You Can Follow By Hand

The following example uses a game tree with a branching factor of 2 and a depth of 3. The root is a MAX node. Terminal values appear at the bottom row.

Level	Node	Type	Children Values	Result
3 (terminal)	E, F	—	3, 5	fixed values
3 (terminal)	G, H	—	2, 9	fixed values
2	C	MIN	E=3, F=5	min(3, 5) = 3
2	D	MIN	G=2, H=9	min(2, 9) = 2
1	B	MAX	C=3, D=2	max(3, 2) = 3
0 (root)	A	MAX	B=3	3

The process works as follows:

• Node C is a MIN node having child nodes E (3) and F (5). MIN chooses the smaller value: 3.
• Node D is a MIN node having child nodes G (2) and H (9). MIN chooses the smaller value: 2.
• Node B is a MAX node having child nodes C (3) and D (2). MAX chooses the larger value: 3.

The root chooses the path that leads to node C, resulting in the final value of the game being 3.

The optimal path for MAX at the root is the one leading to node C, since it ensures a value of 3, which is the best value that MAX can guarantee given the optimal behavior of MIN.

Minimax Pseudocode and Python Implementation

Pseudocode

function minimax(node, depth, isMaximizing):
    if depth == 0 or node is terminal:
        return evaluate(node)

    if isMaximizing:
        bestValue = -infinity
        for each child of node:
            value = minimax(child, depth - 1, false)
            bestValue = max(bestValue, value)
        return bestValue
    else:
        bestValue = +infinity
        for each child of node:
            value = minimax(child, depth - 1, true)
            bestValue = min(bestValue, value)
        return bestValue

The function alternates between maximizing and minimizing at each recursive call, matching the alternating turns of the two players.

Python Implementation: Tic-Tac-Toe

python
def evaluate(board):
    for row in range(3):
        if board[row][0] == board[row][1] == board[row][2] != None:
            return 1 if board[row][0] == 'X' else -1
    for col in range(3):
        if board[0][col] == board[1][col] == board[2][col] != None:
            return 1 if board[0][col] == 'X' else -1
    if board[0][0] == board[1][1] == board[2][2] != None:
        return 1 if board[0][0] == 'X' else -1
    if board[0][2] == board[1][1] == board[2][0] != None:
        return 1 if board[0][2] == 'X' else -1
    if all(board[r][c] is not None for r in range(3) for c in range(3)):
        return 0
    return None

def minimax(board, is_max):
    score = evaluate(board)
    if score is not None:
        return score

    if is_max:
        best = -float('inf')
        for r in range(3):
            for c in range(3):
                if board[r][c] is None:
                    board[r][c] = 'X'
                    best = max(best, minimax(board, False))
                    board[r][c] = None
        return best
    else:
        best = float('inf')
        for r in range(3):
            for c in range(3):
                if board[r][c] is None:
                    board[r][c] = 'O'
                    best = min(best, minimax(board, True))
                    board[r][c] = None
        return best

This function evaluates every open cell, simulates a move, and recursively scores the resulting position. The evaluate function checks all eight winning lines: three rows, three columns, and two diagonals.

Common Bugs When Implementing Minimax

Implementation flaws causing minimax errors can be grouped into four.

• Board state not restored following simulation. The move needs to be reverted once the board is evaluated. Failure to revert the cell back to its original position following the recursive call leads to the evaluation of the wrong future board positions.
• Inaccurate initialization of best. The maximizing player must initialize best to minus infinity. The minimizing player must initialize best to plus infinity. This reversal leads to all possible moves being rejected by the algorithm.
• Failure to decrement depth. In depth limited search, the recursive call must reduce the depth parameter by one. Leaving the depth constant leads to either an infinite recursive call or unbounded search.
• Terminal test placed after move generation. The test for the terminal state must be performed before the generation of child moves. This will waste processing and lead to errors if there are no available moves left.

Alpha-Beta Pruning: Making Minimax Faster

Alpha-beta pruning is an optimization mechanism that cuts off some of the nodes that the minimax algorithm will evaluate because it is clear that certain branches will have no impact on the decision that will ultimately be made. Alpha-beta pruning gives the same output as the regular minimax algorithm but searches through fewer nodes.

What Alpha and Beta Track

The algorithm keeps track of two numbers as it is searching through the tree:

• Alpha – the best value that the maximizing player can ensure at the current position in the search process.
• Beta – the best value that the minimizing player can ensure at the current position in the search process.

When beta becomes less than or equal to alpha, then the algorithm performs pruning on that branch.

function alphabeta(node, depth, alpha, beta, isMaximizing):
    if depth == 0 or node is terminal:
        return evaluate(node)

    if isMaximizing:
        value = -infinity
        for each child of node:
            value = max(value, alphabeta(child, depth - 1, alpha, beta, false))
            alpha = max(alpha, value)
            if beta <= alpha:
                break
        return value
    else:
        value = +infinity
        for each child of node:
            value = min(value, alphabeta(child, depth - 1, alpha, beta, true))
            beta = min(beta, value)
            if beta <= alpha:
                break
        return value

Pruning in Action, on the Same Tree

With respect to the worked example’s tree presented above, alpha-beta pruning results in the following modification to the search:

1. The algorithm begins by evaluating node C: E (3), then F (5). Node C gives 3. Alpha at the root changes to 3.
2. The algorithm considers node D. Beta at node D is initially set to infinity.
3. The algorithm evaluates node G, giving 2. Beta at node D is changed to 2.
4. Here, beta (2) is less than alpha (3). Thus, beta ≤ alpha holds.
5. Node H is pruned. The algorithm will not examine node H as node D ensures that it can return a value of at most 2, which is inferior to the 3 already guaranteed via node C.

In this case, pruning leads to avoiding evaluation of one out of four terminal nodes. In large trees, with correct ordering of moves, alpha-beta pruning results in reducing the effective branching factor from b to about √b and thus lowers time complexity from O(b^d) to about O(b^(d/2)).

Move Ordering: The Optimization Nobody Mentions

The process of ordering moves affects how effective alpha-beta pruning is. Alpha-beta pruning cuts off the most branches if the moves that are analyzed are evaluated by their actual strength.

If the algorithm analyzes the moves in an order close to their strength, the process of alpha-beta pruning approaches the optimal case, resulting in time complexity of O(b^(d/2)). If the moves are analyzed in the worst order possible, there will be no pruning at all, and the algorithm will perform as many analyses as the minimax with the complexity of O(b^d).

These move-ordering algorithms are usually used in chess:

• Evaluation of capturing moves first.
• First evaluation of moves that have caused cutoff at the same level of the search tree, known as killer move heuristics.
• Use of transposition tables to remember the strongest move for a previously visited position.

Minimax vs. Expectimax: What About Games With Dice?

Minimax does not consider any form of randomness. In this algorithm, both the players make their decisions using deterministic strategies. There are games that have some random features and need a modified version of minimax, called the Expectimax algorithm.

The Expectimax algorithm uses an extra type of node in its search tree known as the chance node. In a chance node, the algorithm does not pick up the maximum or minimum values but computes the expected values by multiplying the probability and value of each outcome.

Node Type	Selection Rule
MAX node	Highest child value
MIN node	Lowest child value
Chance node	Probability-weighted average of child values

Expectimax is used in Backgammon-playing programs and in card games where the deck order is unknown to at least one player.

Strengths and Limitations of Minimax

Strengths

• The algorithm will provide the best move if the entire game tree is searched, and the opponent also plays optimally.
• Does not require any training data. The algorithm calculates its moves using only the game rules and the evaluation function.
• Ensures the same result every time. The same game position will always lead to the same recommendation.

Limitations

• Exponential time complexity. The number of nodes searched will increase in O(b^d) fashion, where b represents the branching factor, and d represents the search depth. A branching factor of about 35 applies in chess games, which makes the search problem impossible to solve using exhaustive search technique.
• No handling of hidden information. For a minimax algorithm to work, all information regarding the game should be available to both sides. Hence, games like poker, where each player keeps some of his/her information secret, cannot use the algorithm.
• No handling of randomness, addressed only through the Expectimax variant described above.
• Depends on the quality of the evaluation function at cutoff depths. The performance of an algorithm depends on the quality of the evaluation function used.

How Minimax Compares to Other Algorithms

Algorithm	Search Method	Handles Randomness	Handles Hidden Information	Common Use Case
Minimax	Full or depth-limited tree search	No	No	Chess, checkers, tic-tac-toe
Alpha-Beta Pruning	Minimax with branch elimination	No	No	Chess engines, checkers
Monte Carlo Tree Search (MCTS)	Random sampling and simulation	Yes	Partial	Go, complex board games
Negamax	Minimax with a single unified function	No	No	Chess engines (implementation detail)
Reinforcement Learning	Trial-and-error learning from rewards	Yes	Yes	Robotics, real-time strategy, AlphaGo

Minimax vs. Monte Carlo Tree Search

Minimax explores all branches of the game tree to a fixed depth. In MCTS, sampling is done by performing random simulations on a selected number of branches, and then the outcome guides future sampling towards good moves. MCTS has the advantage over minimax in the scalability of solving games which have large branching factors, for example, in Go where the branching factor is around 250.

Minimax vs. Reinforcement Learning

Minimax is an algorithm for planning. Before the execution of the algorithm, it needs a complete description of the game’s rules and an evaluation function. Reinforcement learning is an algorithm for learning. It learns by interacting with the environment and through the use of rewards and punishment.

Minimax vs. Negamax

Negamax is just another form of minimax and not an entirely new approach altogether. In negamax, the score is negated at each level in order to use a single function for both players, unlike the two functions used in minimax.

Real-World Uses Beyond Board Games

Minimax and its variants apply to several domains outside board games:

• Robotics. Robots employ adversarial search to find their way through an environment containing obstacles or agents working against the objective of the robot, such as avoiding collisions within an area.
• Economics. The minimax concept can be applied to decision-making when there are two individuals with opposite objectives, like some forms of negotiations and pricing.
• Cybersecurity. Adversarial search is used to model attack-defense systems, in which the defense system chooses a strategy that maximizes its performance against the maximum damage the attacker can do.
• Resource allocation and scheduling. Minimax concepts are used in scheduling applications where the allocation of a fixed number of resources is considered under worst-case demand conditions.

Minimax in AI History: Deep Blue to AlphaZero

IBM’s Deep Blue defeated the world chess champion, Garry Kasparov, through the use of minimax search along with alpha-beta pruning in 1997. The IBM computer was capable of analyzing up to 200 million chess positions in a second through the use of specialized chess hardware in addition to the extension of the alpha-beta search with domain knowledge of chess.

One of the earliest adversarial searches was designed by Arthur Samuel in 1959, which consisted of a checkers-playing program that used minimax-style search with a self-modifying evaluation function.

Today’s chess engines, such as Stockfish, still use alpha-beta search along with a learned neural network function for evaluation, instead of writing an evaluation function manually.

Google DeepMind’s programs, namely AlphaGo and AlphaZero, both designed in 2016 and 2017 respectively, use Monte Carlo tree search with the help of a neural network, instead of using minimax. The difference is important since AlphaZero uses sampling of promising branches based on move prediction provided by the network, while minimax searches the entire tree.

Frequently Asked Questions