Back to Study Material Artificial Intelligence

Minimax algorithm

The minimax algorithm computes the optimal strategy for a rational agent playing a two-player zero-sum game against an equally rational opponent. It works ...

Minimax algorithm

Computing Optimal Play

The minimax algorithm computes the optimal strategy for a rational agent playing a two-player zero-sum game against an equally rational opponent. It works by performing a depth-first search of the entire game tree, evaluating terminal states with their utility values, and propagating those values upward through the tree. At MAX nodes, the parent node takes the maximum value of its children. At MIN nodes, the parent takes the minimum value. This ensures that MAX always chooses the move that leads to the best outcome assuming MIN also plays optimally.

Consider a simple game tree where MAX has two moves at the root. The left subtree evaluates to utility three after MIN makes their best response. The right subtree evaluates to utility five after MIN makes their best response. Minimax selects the right move because five is greater than three. If MIN at the right subtree had two responses with values two and five, MIN would choose two, making the right branch worth two, and MAX would then prefer the left branch with value three.

The correctness of minimax rests on the zero-sum assumption. If the game were cooperative rather than competitive, the MIN player would not minimise. In practice, minimax is extended to handle multi-player games using n-tuples of utility values rather than a single scalar, and to handle stochastic games using chance nodes that average outcomes weighted by probability.

Depth-Limited Minimax

For games like chess where the full tree is astronomically large, minimax is applied only to a fixed depth. Nodes at the depth limit are evaluated with a heuristic evaluation function rather than exact utility values. The accuracy of this function and the depth of search together determine the strength of the player.

Exam Tip

Exam questions typically provide a partially drawn game tree with leaf values and ask you to back-propagate values to the root using minimax, then identify the optimal move. Work bottom-up systematically, filling in the value of each internal node correctly: the maximum of children at MAX nodes and the minimum at MIN nodes. Drawing arrows from the chosen child to the parent helps keep the work organised and shows the examiner your reasoning.