Back

Min/MaxAdversarial game-tree search

Two players take turns. MAX wants the biggest score, MIN wants the smallest. Minimax searches the tree depth-first and passes the best value up to the root. Turn on pruning to see which branches can be skipped.

MAX turn MIN turn Leaf score (click to edit) Pruned Color shows depth.

Speed

Result

The best line of play appears when the search finishes.

The algorithm

Highlighted lines are running in the current step. Lines 6 and 7 only run with pruning on.

Minimax is a decision rule for two-player, turn-based games. It assumes both players play perfectly: MAX picks the move with the highest score and MIN picks the move with the lowest. The search goes down to the leaves (end positions with a score) and passes values back up, so the root ends up with the best score MAX can guarantee.

O(b^d)

Time: b branches per move, d moves deep

O(b·d)

Space: depth-first, one path at a time

O(b^d/2)

Alpha-beta with best move ordering

Optimal

Against a perfect opponent

How it works

Build the game tree. Levels alternate between MAX and MIN turns.
Give every leaf a score from MAX's point of view.
At a MAX node, take the largest value among its children.
At a MIN node, take the smallest value among its children.
Repeat up to the root. The child that gave the root its value is the best move.

Alpha-beta pruning

Alpha is the best value MAX can already guarantee on this path.
Beta is the best value MIN can already guarantee on this path.
When beta is at most alpha, the current player would never allow this branch, so the rest of it is skipped.
The answer is identical to plain minimax, with fewer leaves examined.

Worked example

Same tree as the default example in the Visualizer, with alpha-beta pruning on. The root A is a MAX node and levels alternate MAX / MIN. Leaf scores are from MAX's point of view.

Default tree. Dashed branches (//) are the ones pruned.

Go down A → B → C. Leaves D = 3 and E = 5; MAX at C takes 5.
B (MIN) now has a value of at most 5 (beta = 5). Go to F (MAX): leaf G = 6, so F is at least 6.
6 is above beta 5, so MIN at B will never pick F. Prune H (9). B = min(5, 6) = 5.
Back at A (MAX): A is at least 5 (alpha = 5). Go to I (MIN), then J (MAX): leaves K = 1, L = 2, so J = 2.
I (MIN) is now at most 2, which is below alpha 5. MAX at A will never pick I, so prune M (N, O).
A = max(5, I) = 5, since I is at most 2.

Result: the root is worth 5; best play is A → B → C → E. Only 5 of 8 leaves were examined (H, N, O skipped); plain minimax gives the same answer.

Where it is used

Board games

Tic-tac-toe, checkers, and chess engines.

Game AI

Computer opponents that pick a move by looking ahead.

Decision making

Planning against a worst-case adversary.