Minimax Algorithm

Minimax is a recursive algorithm for determining the optimal strategy in a two-player, zero-sum, perfect-information game by exhaustively searching the game tree. Unlike the minimax theorem — which is a statement about the existence of equilibrium strategies — the minimax algorithm is a computational procedure: it assigns a utility value to each terminal position, then propagates these values backward through the tree, with the maximizing player selecting the highest value and the minimizing player selecting the lowest. At the root, the algorithm returns the move that guarantees the best possible outcome against an optimal opponent.

The algorithm is simple but computationally devastating. Its time complexity is O(b^d), where b is the branching factor and d is the maximum depth of the tree. For chess, with b ≈ 35 and typical game lengths exceeding 50 moves, this is approximately 10^85 operations — a number that exceeds the number of atoms in the observable universe. The minimax algorithm, in its pure form, is a theoretical construct rather than a practical tool. Every implementation is an approximation.

Bounded Rationality and the Truncated Tree

In practice, the minimax algorithm is always applied with a depth limit and an evaluation function that estimates the value of non-terminal positions. The search proceeds to a fixed depth, the evaluation function assigns a heuristic score to each leaf, and minimax propagates these scores as if they were true utilities. This is not merely a computational shortcut; it is a structural transformation of the problem. The algorithm is no longer searching for the optimal move in the true game. It is searching for the optimal move in a different game — one whose terminal positions are defined by the evaluation function rather than the actual rules.

This is the exact architecture of bounded rationality: an agent with limited computational resources replaces an intractable problem with a tractable surrogate. The quality of play depends entirely on the quality of the surrogate. A perfect evaluation function would make the truncated search equivalent to the full search; a poor evaluation function makes the search worthless regardless of depth. The chess engine community has discovered that deep search with a mediocre evaluation can be outplayed by shallow search with a superior evaluation. Depth is not the variable that matters; the alignment between the evaluation function and the true utility landscape is.

Beyond Games: Minimax as Free Energy Principle

The minimax algorithm has a precise analogue in the free energy principle and active inference. In the free energy framework, an agent minimizes variational free energy — a bound on the surprisal of sensory outcomes — by selecting actions that minimize the expected free energy of future states. The minimax algorithm is the adversarial limit of this process: instead of minimizing expected free energy under a generative model of the environment, the agent minimizes the maximum expected free energy under a worst-case model of the opponent.

This reframes the minimax algorithm not as a game-playing technique but as a robust inference procedure. An agent playing minimax is not assuming the opponent is optimal; it is assuming the opponent is adversarial and constructing a policy that is robust to that adversarial assumption. The same logic appears in minimax control theory, where controllers are designed to perform adequately under the worst-case disturbance, and in adversarial machine learning, where models are trained against worst-case perturbations.

The connection to precision weighting is direct. In active inference, the precision of a policy is the confidence with which the agent expects that policy to produce low free energy. In minimax, precision is binary: the agent assigns infinite precision to the opponent's worst-case response and zero precision to all other possibilities. Minimax is the limiting case of Bayesian inference where the prior over opponent behavior is a delta function on the adversarial extreme. This is not rationality; it is paranoia formalized as computation. And like paranoia, it is sometimes justified and sometimes pathological.

Pathologies of the Algorithm

The horizon effect is the most instructive pathology. When a depth-limited search encounters a position whose true value depends on events beyond the horizon, the evaluation function can be systematically wrong. A move that sacrifices material for a decisive attack five moves later is evaluated as a blunder because the attack is invisible to the search. The algorithm does not know what it does not know; it simply optimizes the surrogate. This is not a bug of the implementation but a feature of the epistemology: any system that replaces the world with a model inherits the model's blind spots.

Iterative deepening and transposition tables are standard engineering responses, but they do not solve the fundamental problem. They make the search deeper and more efficient; they do not make the evaluation function more aligned with reality. The deeper point is that the minimax algorithm, like any optimization procedure, is a tool for navigating a landscape. It tells you where the peaks and valleys are in the landscape you have given it. It does not tell you whether that landscape resembles the one you actually face.

The minimax algorithm is often taught as the foundation of artificial intelligence. It is better understood as a cautionary example: a procedure that is mathematically correct, computationally intractable, and practically useful only to the extent that it is betrayed by the heuristics that make it feasible. The intelligence is not in the algorithm. The intelligence is in the approximation.