Minimax
A game-tree search strategy that minimizes an opponent's best possible outcome.
Minimax is a recursive decision-making algorithm used in adversarial settings where two players compete with opposing objectives. The core idea is straightforward: one player (the maximizer) seeks to maximize their score, while the other (the minimizer) seeks to minimize it. The algorithm explores a game tree by alternating between these two roles at each level of the tree, propagating utility values upward from terminal states to determine the optimal move at the root. This process assumes both players act rationally and always choose the move that best serves their respective goals.
In practice, the algorithm assigns a numerical utility to every reachable terminal state — win, loss, or draw — and then works backward through the tree. At maximizing nodes, the algorithm selects the child with the highest value; at minimizing nodes, it selects the child with the lowest. The result is a move choice that guarantees the best outcome under the assumption of a perfectly adversarial opponent. This worst-case optimality is what makes minimax theoretically sound for zero-sum games, where one player's gain is exactly the other's loss.
Minimax became foundational to AI game-playing research in the 1950s and 1960s, when researchers like Claude Shannon and Alan Turing began formalizing computer chess strategies. The algorithm's computational cost grows exponentially with search depth, which motivated the development of alpha-beta pruning — an optimization that eliminates branches of the game tree that cannot influence the final decision, dramatically reducing the number of nodes evaluated without changing the result.
Beyond board games, minimax thinking underpins robust optimization and adversarial machine learning. Generative Adversarial Networks (GANs), for instance, frame training as a minimax game between a generator and a discriminator. Minimax also connects to Nash equilibrium theory in economics and multi-agent reinforcement learning, where agents must reason about the strategies of other self-interested actors. Its influence across AI, game theory, and modern deep learning makes it one of the most enduring ideas in the field.
