The minimax algorithm is a decision-making strategy for two-player, zero-sum games where one player tries to maximize their score while the other tries to minimize it. At its core, it works by looking ahead through every possible sequence of moves, assuming both players play perfectly, and choosing the move that guarantees the best possible outcome against an optimal opponent. The idea traces back to a mathematical proof by John von Neumann in 1928, but the algorithm’s influence extends well beyond board games into fields like security, economics, and robust statistical decision-making.
How the Algorithm Thinks
Imagine you’re playing a game where you and your opponent alternate turns. On your turn, you want to pick the move that leads to the highest-scoring position for you. On your opponent’s turn, you assume they’ll pick the move that scores lowest for you (highest for them). The minimax algorithm formalizes this by building a tree of all possible future game states from the current position. At the bottom of the tree, each final position gets a score. Then the algorithm works backward: at levels where it’s your turn, it picks the maximum score among the options; at levels where it’s your opponent’s turn, it picks the minimum. The value that bubbles up to the top is the best score you can guarantee regardless of what your opponent does.
This sounds straightforward, and conceptually it is. The difficulty is practical. Even in a game as simple as tic-tac-toe, the full game tree has hundreds of thousands of positions. In chess, the number of possible positions is estimated to be in the range of 10 to the power of 47. No computer can search the entire tree for a complex game, which is why nearly all the interesting work on minimax has focused on searching smarter rather than searching everything.
Where Minimax Came From
The mathematical foundation was laid in 1928, when John von Neumann proved what is now called the minimax theorem: in any two-player, zero-sum game with a finite number of strategies, there exists a pair of strategies (one per player) that form a saddle point, meaning neither player can improve their outcome by unilaterally changing their approach.1International Game Theory Review. VON NEUMANN, VILLE, AND THE MINIMAX THEOREM This was a foundational result in game theory, establishing that such games always have a rational solution. The theorem tells you the solution exists; the minimax algorithm is the computational procedure for finding it by working backward through the game tree.
Von Neumann’s work dealt with the abstract mathematics. The algorithmic version, the one that actually searches game trees in software, emerged later in the context of early computer science and artificial intelligence research in the 1950s and 1960s. Researchers working on chess-playing programs needed a way to have computers evaluate positions several moves ahead, and minimax provided the logical framework for doing so.
Alpha-Beta Pruning
The single most important optimization to minimax is alpha-beta pruning, which dramatically reduces the number of positions the algorithm needs to examine without changing the result. The insight is simple: if you’ve already found a move that guarantees you a certain score, and you discover that an alternative branch of the tree can only lead to something worse, you can stop exploring that branch entirely. You “prune” it from the search.
In the best case, alpha-beta pruning lets you search roughly twice as deep as plain minimax in the same amount of time. That’s because it can reduce the effective branching factor of the tree from b to approximately the square root of b, where b is the number of moves available at each position. In practice, the amount of pruning depends on the order in which moves are examined. If you happen to look at the best move first, pruning is maximally effective. If you look at the worst move first, you get almost no benefit. This is why strong game-playing programs invest significant effort in move ordering, trying to guess which moves are most likely to be good so the pruner can cut more branches.
Research has shown that enhanced alpha-beta search can be remarkably efficient. A study examining chess, Othello, and checkers computed the size of the minimal tree (the smallest tree that still produces the correct minimax value) and the even smaller minimal graph (which accounts for positions reachable by different move sequences). The results showed that in all three games, well-tuned alpha-beta search built trees close in size to the theoretical minimal graph, suggesting the technique is already operating near its practical ceiling for these classic games.2arXiv. Nearly Optimal Minimax Tree Search?
Quiescence Search and the Horizon Problem
Even with alpha-beta pruning, minimax search has to stop at some depth. The program can’t look ahead forever, so it evaluates the position at the depth limit using a heuristic evaluation function, a scoring formula that estimates how good a position is without playing the game to completion. This creates a problem known as the horizon effect: the algorithm might stop searching right before something dramatic happens, like a piece being captured in chess or a big swing in territory in Go.
Quiescence search addresses this by extending the search past the normal depth limit in “noisy” positions. If the position at the search boundary involves a capture, a pawn promotion, or a king in check, the search continues one more level, and it keeps extending until the position calms down and there are no more such forcing moves to consider.3IGI Global. Artificial Intelligence in Chess-Playing Automata: A Paradigm for the Quiescence Phase of a-ß Search Only once the position has reached this quiet state does the evaluation function assign a score. Without quiescence search, a chess engine might think it’s winning material because its search stopped right before the opponent recaptured, leading to wildly inaccurate evaluations.
The Evaluation Function
Minimax is only as good as its evaluation function. The algorithm handles the logic of “what if I do this and they do that,” but at the leaves of the search tree, something has to judge whether the resulting position is good or bad. In early game programs, evaluation functions were handcrafted by human experts who assigned numerical weights to features they considered important: material balance, piece activity, king safety, pawn structure, and so on.
This process was labor-intensive and error-prone. Researchers explored ways to automate it. One approach, the generalized linear evaluation model, combined Boolean features (things like “does this side have a passed pawn” or “is the king exposed”) in a linear combination and used data-driven methods to find the best weights automatically. This freed programmers from having to manually determine which features mattered most and how much each should count.4Artificial Intelligence. Improving heuristic mini-max search by supervised learning A related technique, Minimax Tree Optimization, went further by allowing the evaluation function to be a nonlinear combination of weighted features, optimizing the parameters specifically for how well they performed within the context of alpha-beta search rather than in isolation.5Journal of Artificial Intelligence Research. Minimax Tree Optimization
These methods represent an interesting middle ground between the purely hand-tuned era and the modern deep-learning era. The search was still traditional alpha-beta minimax, but the evaluation function was learned from data rather than painstakingly coded by hand.
Games with Chance and Multiple Players
Standard minimax assumes a two-player game with no randomness. Many popular games violate one or both of those assumptions. Backgammon involves dice rolls. Poker involves hidden cards. Risk involves both dice and more than two players.
For games with random elements, the minimax algorithm is extended into what is called expectiminimax. In addition to “maximize” nodes (your turns) and “minimize” nodes (opponent turns), the tree includes “chance” nodes where the outcome is determined by probability. At a chance node, instead of taking the maximum or minimum, the algorithm computes the expected value: a weighted average of the outcomes, where the weights are the probabilities of each random event. Pruning becomes trickier in this setting because the averaging operation makes it harder to establish bounds that would let you cut branches. Researchers have developed techniques like gamma-pruning, which serves a role analogous to alpha-beta pruning but is designed to work with the expected-value calculations at chance nodes.6Acta Cybernetica. Optimal strategy in games with chance nodes
For games with more than two players, the zero-sum assumption breaks down. When three or more players compete, what’s bad for one opponent isn’t necessarily good for you, because the other opponents might benefit instead. Algorithms like Max-N generalize minimax to handle this by giving each player their own component in a multi-valued score vector, with each player maximizing their own component at their own turns. The analysis becomes considerably more complex, and the neat guarantees of two-player minimax weaken, but the core logic of looking ahead and reasoning about what each player will do remains.
Parallelizing the Search
Alpha-beta pruning is inherently sequential in a frustrating way: the value of one branch determines whether another branch needs to be searched at all. This makes it hard to split the work across multiple processors, because one processor’s result might render another processor’s work unnecessary. Despite this, parallel minimax search has been a research topic since the 1980s.
One well-studied approach is Principal Variation Splitting. The idea is to identify the “principal variation,” the sequence of moves the algorithm currently believes is best, and search that first on a single processor to establish good bounds. Once those bounds are known, the remaining branches can be distributed to other processors, each of which can prune more effectively because it already knows a strong baseline. Early work on this approach demonstrated measurable speedups on shared-memory multiprocessor systems, though the gains were less than the theoretical maximum because of the communication overhead and the inherent dependencies in pruning.7Parallel Computing. A parallel alpha/beta tree searching algorithm
Modern chess engines use variations of this idea, distributing the search across CPU cores. The parallelism is never perfectly efficient, you can’t just throw twice as many cores at the problem and search twice as deep, but it provides a meaningful boost that compounds with other optimizations.
The Rise of Monte Carlo Tree Search
For decades, minimax with alpha-beta pruning was the dominant paradigm for game-playing AI. Chess engines like Deep Blue and later Stockfish used it to devastating effect. But minimax has an Achilles’ heel: it requires a good evaluation function, and it struggles with games that have enormous branching factors. In Go, where the board is 19×19 and a typical position might have 200 or more legal moves, even aggressive pruning can’t compensate for the exponential explosion of the search tree.
Monte Carlo Tree Search, or MCTS, takes a fundamentally different approach. Instead of systematically searching all moves to a fixed depth, it repeatedly simulates random games from promising positions and uses the results to guide the search toward the most important branches. Combined with techniques for balancing exploration and exploitation, MCTS has an advantage over depth-limited minimax in games with high branching factors like Go.8University of Maryland Digital Repository. MONTE CARLO TREE SEARCH AND MINIMAX COMBINATION – APPLICATION OF SOLVING PROBLEMS IN THE GAME OF GO
The most dramatic demonstration of this came with DeepMind’s AlphaGo, which defeated the world champion at Go in 2016 using MCTS guided by deep neural networks. Its successor, AlphaZero, used the same MCTS-plus-neural-network framework to achieve superhuman play in chess, Go, and shogi, starting from nothing but the rules of each game.9arXiv. Neural Networks for Chess This was a paradigm shift: instead of hand-crafted evaluation functions searched by alpha-beta, you had learned evaluation functions searched by MCTS.
Yet minimax hasn’t disappeared. Stockfish, arguably the strongest chess engine in the world for most practical purposes, still uses alpha-beta search at its core, though it now uses a neural network for its evaluation function. The old framework proved flexible enough to absorb the new technology. And for games with lower branching factors where deep, precise search matters more than broad exploration, alpha-beta minimax remains competitive or superior.
Endgame Databases and Solved Games
When a game becomes simple enough, usually near the end when few pieces remain, it’s possible to solve it completely. Endgame databases store the exact minimax value (win, loss, or draw with best play from both sides) for every possible position with a small number of pieces. In chess, endgame tablebases cover all positions with seven or fewer pieces on the board, providing perfect play from those positions onward.
In checkers, endgame databases played an even more central role. The program Chinook, which challenged for the World Checkers Championship, relied heavily on databases containing hundreds of billions of positions. Because checkers positions from the database arose frequently during Chinook’s search, the databases needed to be accessible in real-time, a significant engineering challenge that involved distributing the data across a network of workstations.10Education & Research Archive. Solving Large Retrograde Analysis Problems Using a Network of Workstations Checkers was eventually completely solved in 2007 (by the same research group behind Chinook), proving that the game is a draw with perfect play from both sides. The proof relied on a combination of minimax search and these massive endgame databases.
Minimax in Decision Theory and Security
The minimax idea extends far beyond board games. In statistics and decision theory, a closely related concept called maximin has been influential since the 1940s, when Abraham Wald applied it to decision problems involving deep uncertainty. Rather than trying to maximize expected payoff (which requires knowing the probabilities of different outcomes), the maximin approach asks: what decision gives me the best worst-case outcome? This is the same logic as minimax, just framed from the perspective of a single decision-maker facing an uncertain or adversarial environment. Wald’s maximin paradigm has become a dominant tool in fields like robust optimization, where the goal is to make decisions that perform well even under the most unfavorable conditions.11International Transactions in Operational Research. Wald’s mighty maximin: a tutorial
In security, minimax thinking shows up in Stackelberg security games, where a defender (the “leader”) commits to a strategy for allocating limited resources, like police patrols or airport checkpoints, and an attacker (the “follower”) observes the strategy and responds optimally. Computing the defender’s best strategy is essentially a minimax problem: you want the allocation that performs best against the worst-case attacker response. These models have been deployed in real-world security systems, including at airports and for wildlife protection.
There’s a complication, though. Classical minimax assumes both players are perfectly rational. In security applications, the “adversary” is a human being who may not behave optimally. Research on Stackelberg games has shown that human adversaries often deviate from the expected optimal response because of bounded rationality and limited ability to observe the defender’s full strategy. Failing to account for these deviations can seriously degrade the defender’s outcomes.12Artificial Intelligence. Robust solutions to Stackelberg games: Addressing bounded rationality and limited observations in human cognition This has led to “robust” versions of minimax-based security models that account for the fact that real humans are not the perfectly calculating opponents the algorithm assumes.
When the Opponent Isn’t Rational
This limitation deserves a closer look, because it applies well beyond security. Minimax guarantees the best outcome against a perfect opponent, but many real situations involve imperfect ones. If your opponent plays poorly, minimax still wins, but it might not exploit their mistakes as aggressively as a different strategy would. A minimax player in poker, for example, won’t lose to anyone in the long run, but it also won’t maximize its profits against weak players the way an exploitative strategy would.
In competitive board games, this trade-off is usually acceptable because the minimax-based engine’s advantage in deep calculation overwhelms any gain from adjusting to the opponent’s style. But in domains like negotiation, business strategy, or military planning, where the “opponent” is a complex human actor with biases, emotions, and incomplete information, pure minimax thinking can be overly conservative. It prepares you perfectly for an opponent who never makes mistakes, which is an opponent you rarely face. The worst-case guarantee is real and valuable, but optimizing only for the worst case means leaving potential gains on the table in every other scenario.
This is where minimax’s philosophical stance becomes a choice rather than an inevitability. If you’re deeply risk-averse or the stakes of losing are catastrophic (nuclear strategy was one of the original motivations for game theory), the worst-case guarantee is exactly what you want. If the cost of losing is modest and the gains from exploiting opponent errors are large, you might prefer a strategy that sacrifices some worst-case protection for better average-case performance. Minimax gives you a floor. Whether that floor is all you need depends on the stakes.
Minimax in Everyday Software
You’ve probably encountered minimax without knowing it. The AI opponents in classic board-game apps, the computer player in a chess app on your phone, and the logic behind many turn-based strategy game AIs all use some version of minimax or its descendants. When you play tic-tac-toe against a computer and it never loses, that’s minimax at work, searching the entire (small) game tree to play perfectly.
Beyond games, the minimax idea shows up in any adversarial optimization problem. Spam filters can be thought of as minimax problems: the filter tries to maximize detection, the spammer tries to minimize it. Generative adversarial networks (GANs) in machine learning are explicitly framed as minimax games between a generator network and a discriminator network. Financial portfolio optimization sometimes uses minimax or maximin to construct portfolios that perform as well as possible under the worst market conditions. The algorithm itself is specific to tree-structured decision problems, but the underlying principle, planning for the best you can achieve against the worst your opponent can do, is one of the most broadly applicable ideas in strategic reasoning.