Minimax Algorithm

The Minimax algorithm is a decision method for turn-based games between two opponents: it chooses the move that maximizes the minimum gain the player can guarantee, assuming the opponent plays optimally. This amounts to minimizing the maximum loss, hence its name.

How it works

Minimax explores the game tree and propagates values from the end positions back toward the current move, alternating two roles: at nodes where the player (MAX) decides, the maximum of the options is taken, and at nodes where the opponent (MIN) decides, the minimum. That alternation gives the algorithm its name and determines the best move assuming the worst possible opponent.

Its assumptions

Basic Minimax applies only under specific assumptions: a two-player, turn-taking, zero-sum game (what one gains the other loses), deterministic (no chance) and of perfect information (both see the whole state). Chess, checkers or tic-tac-toe satisfy this; poker, with hidden information, or backgammon, with dice, require variants such as expectimax.

Relation to game theory and efficiency

A nuance often confused is in order. There is a minimax theorem, proved by John von Neumann in 1928, which is a mathematical result: it guarantees that every finite two-player, zero-sum game has a well-defined value, and in that case its solution coincides with a Nash equilibrium. But the tree-search algorithm is a decision procedure, not a derivation of Nash equilibrium: Nash should not be presented as its “direct foundation.” As for efficiency, Minimax's cost grows exponentially with depth; alpha-beta pruning reduces it without changing the result, discarding branches that cannot affect the decision, and in huge games like chess or Go the search is cut off at a certain depth and an evaluation function is used.