Does minimax search always inspect the entire game?

Exhaustive minimax does, but practical variants often use depth limits, pruning, or reused results.

Is every skipped branch an approximation?

No. A valid alpha-beta cutoff skips work without changing the minimax result for the specified search tree.

Why not just choose the largest leaf?

The opponent controls some intervening choices and may prevent that leaf from being reached.

AI Glossary / Graphs and symbolic AI / Intermediate

Minimax search

Definition

Minimax search is a game-tree search procedure that evaluates possible continuations by alternating maximizing and minimizing choices. It computes how well one player can do when an opponent makes the strongest available replies, then uses those values to select a move. Its classical setting is a deterministic, two-player, zero-sum game with perfect information.

What it means

The search explores sequences of actions rather than judging the immediate appearance of a move. A promising position may lead to a forced loss after an opponent's reply, while an unattractive-looking move may preserve a stronger outcome.

Each node records a game state and whose turn it is. Edges represent legal actions. Terminal nodes have known game utilities. Searching the tree and backing those utilities upward reveals the consequences of alternating control. This distinguishes adversarial search from a single-agent path search where the same decision maker effectively chooses every step along a candidate route.

How it works

A recursive implementation first checks whether a state is terminal. If so, it returns the utility from MAX's perspective. Otherwise, it generates legal successors, recursively evaluates them, and returns their maximum at a MAX node or minimum at a MIN node.

At the root, it also retains an action attaining the appropriate value. Depth-first traversal allows values to be computed as recursive calls return, without retaining the entire expanded tree at once. Naive search can still require exponentially many node evaluations as the depth grows.

Practical implementations often use a depth limit and an evaluation function for unfinished positions. Alpha-beta pruning removes branches whose values cannot affect the relevant choice. Unlike an arbitrary cutoff, valid alpha-beta pruning preserves the minimax result for the same leaves and evaluation scheme. State reuse can help, but cached results must respect relevant context such as remaining depth.

Three practical examples

Board-game development: inspect several alternating moves before choosing the next action.
Algorithm education: trace recursive calls to learn how local maximum and minimum operations produce a global adversarial decision.
Solver verification: compare an optimized search with exhaustive minimax on small trees whose answers can be checked independently.

Think of it this way

Think of examining a branching conversation in which you choose one response, a rival chooses the next, and the final outcome depends on the whole sequence. You cannot choose the rival's favorable lines on their behalf.

The analogy is limited because real conversations have hidden information and nonopposing interests. Classical minimax search needs an explicit game model, not assumptions that every human interaction is zero-sum.

Worked example

Consider a three-ply tree: MAX moves, then MIN, then MAX, followed by terminal outcomes. Root action L gives MIN two choices, L1 and L2. At L1, MAX can obtain 2 or 7; at L2, MAX can obtain 4 or 5. Root action R gives MIN choices R1 and R2. At R1, MAX can obtain 6 or 8; at R2, MAX can obtain 1 or 9.

First evaluate the four deepest MAX nodes: L1 is 7, L2 is 5, R1 is 8, and R2 is 9. Then evaluate the two MIN nodes: L is min(7,5)=5, while R is min(8,9)=8. The root therefore has value max(5,8)=8 and selects R.

One optimal continuation is R, then R1, then the terminal outcome 8. Notice that R2 contains a leaf valued 1, but MIN cannot force it: once at R2, MAX chooses 9. Taking the minimum across all terminal leaves under R would incorrectly return 1 and ignore who controls the final move.

The full toy tree contains one root, two MIN nodes, four deeper MAX nodes, and eight terminal nodes: fifteen nodes in total. These are hand-checked tree counts and backups, not a runtime benchmark.

Illustrative case study

Fictional case: a game studio adds a three-move preview to its strategy-game opponent. Early tests reveal that the implementation minimizes at every level below the root, causing it to avoid positions where it has a strong later reply.

The developers label each node with its controlling player and build small regression trees like the worked example. They also distinguish actual terminal utilities from estimates at the search horizon. The fictional case illustrates why turn ownership and cutoff semantics matter; it does not claim a measured improvement in playing strength.

Common misconceptions and mistakes

Searching deeper does not remove modeling mistakes. Incorrect legal actions, wrong turn transitions, or reversed utility signs can make a larger search confidently wrong.

A depth limit also needs a clear counting convention. One ply usually means one player's move; some software describes depth in complete rounds. Confusing the two changes how much of the game is explored.

Do not treat every revisited board arrangement as interchangeable. The player to move, repetition rules, or other state information can affect legal continuations and outcomes. A cache key must represent the actual game state, not merely its visible arrangement.

Business use

Minimax search is useful when a product needs explainable action selection in a controlled adversarial environment. Its operating cost depends on branching, depth, move generation, and evaluation work, so performance should be measured on representative positions.

A useful result record includes the chosen move, score, completed depth, and whether terminal search or heuristic evaluation produced the result. For time-limited operation, iterative deepening can provide a completed shallower result while a deeper search is attempted.

Check your understanding

At a MIN node, its two children are MAX nodes with leaves {1,8} and {4,6}. What is the MIN node's value?

Answer: min(max(1,8),max(4,6))=min(8,6)=6.

Related terms

Learn next

trace the complete worked tree in depth-first order, then add alpha-beta bounds and identify which evaluations can be skipped. Compare both procedures on the same terminal values.

Sources

University of California, Berkeley, CS 188, explains the search recursion, computational cost, pruning, and evaluation functions: https://inst.eecs.berkeley.edu/~cs188/textbook/games/minimax.html

Poole and Mackworth provide explicit game-tree and alpha-beta algorithms: https://artint.info/3e/html/ArtInt3e.Ch14.S3.html

The tree and fictional debugging case are original examples.

Previous: Minimax loss Next: Minimax value