Minimax is an algorithm for choosing actions in competitive situations, particularly two-player games in which one player’s gain is the other’s loss. In artificial intelligence, it evaluates possible moves by assuming that an opponent will choose the response least favorable to the decision-maker. The algorithm propagates values backward through a game tree, alternating maximization and minimization. Its broader mathematical foundation belongs to game theory, where minimax strategies protect against the worst outcome an adversary can enforce. (inst.eecs.berkeley.edu)
Game model and assumptions
The standard game-search formulation applies to deterministic, sequential, two-player games with perfect information: both players know the position and previous moves. In a zero-sum game, their interests are directly opposed, allowing outcomes to be measured using a single numerical payoff. One player, conventionally called MAX, seeks larger values; the other, MIN, seeks smaller values. A game tree represents positions as nodes and legal moves as edges. Nodes identify whose turn it is, while terminal nodes carry known outcome values. (inst.eecs.berkeley.edu)
All values must use a consistent perspective, normally MAX’s. For example, a win may receive (+1), a draw (0), and a loss (-1). MIN then minimizes this same score rather than using a separately defined evaluation. The optimality claim is conditional: exhaustive minimax gives the best achievable result against optimal opposition, not necessarily a win. If the opponent makes mistakes, the actual outcome can be better than the guaranteed value. (inst.eecs.berkeley.edu)
Recursive definition
Let (V(s)) be the value function of position (s), (U(s)) its terminal payoff, and (C(s)) its legal successor positions. For a finite game tree,
[ V(s)= \begin{cases} U(s), & \text{if }s\text{ is terminal},\ \max_{t\in C(s)}V(t), & \text{if MAX moves at }s,\ \min_{t\in C(s)}V(t), & \text{if MIN moves at }s. \end{cases} ]
At a MAX root, the selected move leads to a successor with the largest value. The calculation uses recursion to evaluate descendants before their parents; a conventional implementation therefore follows a postorder depth-first traversal. (inst.eecs.berkeley.edu)
As an illustrative example, suppose MAX chooses between two moves. After the first, MIN can select terminal payoffs of 3 or 5; after the second, MIN can select 2 or 9. The first move has value (\min(3,5)=3), and the second has value (\min(2,9)=2). MAX chooses the first, guaranteeing 3. The attractive payoff of 9 is irrelevant to that guarantee because MIN can avoid it. This example follows directly from the recurrence. (inst.eecs.berkeley.edu)
Search cost and alpha–beta pruning
The principal difficulty is exponential time complexity. With branching factor (b) and search depth (d), exhaustive minimax visits (O(b^d)) nodes in a regular tree. Even moderate branching makes complete searches impractical in many board games. The relevant computational complexity depends on the size of the explored tree, not merely the number of moves available immediately. (inst.eecs.berkeley.edu)
Alpha–beta pruning avoids exploring branches that cannot affect the final minimax value. It tracks bounds on what MAX and MIN can already secure. Once these bounds show that a branch cannot improve the relevant choice, further exploration is unnecessary. Unlike a heuristic cutoff, valid alpha–beta pruning preserves the minimax result for the same tree. (inst.eecs.berkeley.edu)
Its effectiveness depends strongly on move ordering. Searching promising moves first exposes useful bounds sooner. Under ideal ordering, the search cost can approach (O(b^{d/2})); unfavorable ordering may leave the original exponential cost largely unchanged. This reduction can permit substantially deeper searches within the same computational budget. (inst.eecs.berkeley.edu)
Depth limits and evaluation functions
Practical implementations commonly stop at a fixed depth rather than reaching every terminal position. A heuristic evaluation function estimates the value of each cutoff position. Terminal outcomes remain exact, while nonterminal evaluations are approximations. Depth-limited minimax consequently optimizes the truncated, evaluated tree rather than necessarily solving the underlying game. (inst.eecs.berkeley.edu)
A common evaluation design uses a linear combination of measurable features:
[ E(s)=\sum_i w_i f_i(s). ]
In checkers, features might count each side’s ordinary pieces and kings, with signs and weights reflecting their estimated contribution to the position. Such a heuristic is useful because it replaces an otherwise infeasible continuation search, but inaccurate estimates remove the guarantee of optimal play. Search depth and evaluation quality therefore jointly influence performance. (inst.eecs.berkeley.edu)
Relationship to the minimax theorem
Tree-search minimax is related to, but distinct from, the minimax theorem proved by John von Neumann in 1928. For a finite two-player zero-sum game with payoff matrix (A), the theorem states
[ \max_p\min_q p^\mathsf{T}Aq
\min_q\max_p p^\mathsf{T}Aq, ]
where (p) and (q) range over each player’s mixed strategies. These are probability distributions over available pure strategies, and the expression measures expected payoff. The common quantity is the game’s value. (cs.cmu.edu)
Allowing randomized strategies is essential: equality need not hold when both players are restricted to pure strategies. Optimal mixed strategies form a Nash equilibrium in the zero-sum setting. The theorem concerns strategic guarantees, whereas recursive game-tree search computes values through sequential choices; the two should not be treated as identical procedures. (cs.cmu.edu)
Chance and opponent models
Minimax treats opposing choices as deliberately adverse. If outcomes instead follow known probabilities, expectimax replaces minimizing nodes with probability-weighted averages; games combining adversaries and random events may contain both minimizing and chance nodes. Thus choosing between these methods depends on the model of the environment. Minimax’s worst-case assumption is not a prediction that every real opponent will always choose the strongest move. (inst.eecs.berkeley.edu)
References
- 2 Minimax | Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
- CS 188, Spring 2023, Note 9inst.eecs.berkeley.edu
- CS 188, Summer 2023, Note 5inst.eecs.berkeley.edu
- Von Neumann’s Minimax Theoremcs.cmu.edu
- Session 8: Playing gamescs.cmu.edu
- Game theorycs.cmu.edu
- Game Theorycs.cmu.edu