What is alpha-beta pruning in minimax?
The minimax algorithm alpha-beta pruning is a decision-making technique for two-player zero-sum games: minimax chooses the move that minimizes the maximum possible loss, and alpha-beta pruning skips branches of the game tree that cannot influence the final decision.
Opinion when it's worth implementing: If your game tree has a branching factor above roughly 4–5 and a depth beyond 3–4 plies, alpha-beta pruning is almost always worth the modest implementation cost over plain minimax. For trivially small trees (e.g., Tic-Tac-Toe with a naive coder), plain minimax is simpler and fast enough reach for alpha-beta only when the tree size actually hurts.
What is the minimax algorithm?
Minimax is a recursive algorithm for choosing an optimal move in a two-player, zero-sum game of perfect information. One player (MAX) tries to maximize the score; the other (MIN) tries to minimize it. The algorithm assumes both players play optimally, builds a game tree of possible future positions, assigns utility values at the terminal states, and propagates those values back up the tree. At each MAX node, the algorithm picks the child with the highest value; at each MIN node, the child with the lowest.
Is minimax BFS or DFS?
Minimax is a depth-first search (DFS). It descends recursively from the root along one branch until it reaches a terminal state (or a cutoff depth), evaluates that leaf, and backtracks to explore siblings. Breadth-first search would require storing an exponential number of nodes at each level, which is intractable for even modestly deep game trees. DFS keeps memory use linear in the depth, which is why minimax and by extension alpha-beta pruning is implemented recursively or with an explicit stack.
What is the minimax algorithm used for in AI?
Minimax underpins adversarial search in classical AI. Common uses include:
- Board game engines: Chess, Checkers, Go (prior to deep-learning approaches), Othello, and Tic-Tac-Toe.
- Decision-making under adversarial conditions: Any domain where an agent must plan against an opponent who is also planning — security games, auction bidding against a rational adversary, and some forms of worst-case robust planning.
- Teaching AI foundations: Minimax is a standard first example of adversarial search in curricula such as Berkeley's CS188 and Stanford's introductory AI courses.
What is the difference between minimax and alpha-beta pruning?
Minimax and alpha-beta pruning are not two competing algorithms alpha-beta pruning is an optimization layered on top of minimax.
- Minimax evaluates every node in the game tree up to the cutoff depth. The result is the optimal move under the assumption of perfect play.
- Alpha-beta pruning returns the same move as minimax, but skips branches that provably cannot change the final decision. It does this by tracking two bounds (alpha and beta) as the search descends and pruning any subtree whose outcome falls outside those bounds.
The outputs are identical; the work done to produce them is often dramatically different. With good move ordering, alpha-beta can roughly double the depth searchable in the same time budget.
Alpha and beta: what the two bounds mean
- Alpha: the best (highest) value the maximizer can currently guarantee at this level or above. Alpha is initialized to -infinity and updated upward as the maximizer finds larger values.
- Beta: the best (lowest) value the minimizer can currently guarantee at this level or below. Beta is initialized to +infinity and updated downward as the minimizer finds smaller values.
- Pruning condition: when alpha becomes greater than or equal to beta at a node, the remaining children of that node cannot affect the final decision and are skipped.
What are the conditions for alpha-beta pruning in the minimax algorithm?
Alpha-beta pruning requires:
- A minimax-style game tree: a tree of alternating MAX and MIN nodes with utility values at the leaves (either terminal utilities or outputs of an evaluation function at a cutoff depth).
- Two running bounds: alpha (best value for MAX found so far on the path from the root) and beta (best value for MIN found so far on the path from the root), passed down the recursion.
- The cutoff test
alpha >= beta: once this is true at a node, the remaining children are pruned. At a MAX node this is called a beta cutoff; at a MIN node, an alpha cutoff. - Depth-first traversal: the bounds are meaningful only along a single root-to-node path, so the algorithm must evaluate one branch fully (or until it prunes) before moving to the next.
Note: alpha can be updated only at MAX nodes, and beta can be updated only at MIN nodes.
How alpha-beta pruning works with the minimax algorithm: a solved example
The following walkthrough is a solved example of alpha-beta pruning on a small game tree. Minimax descends the tree depth-first; alpha-beta pruning uses the running alpha/beta bounds to skip subtrees that cannot change the root's minimax value.
Step-by-step walkthrough
- Initialize alpha = -infinity and beta = infinity as the worst possible cases. The condition to prune a node is when alpha becomes greater than or equal to beta.
- Start with assigning the initial values of alpha and beta to root and since alpha is less than beta we don't prune it.
- Carry these values of alpha and beta to the child node on the left. From the utility value of the terminal state, we will update the value of alpha, and we don't need to update the value of beta at this point. We don't prune because the condition (alpha >= beta) is not met. The same applies to the second and third child nodes. Backtracking to the root, we set alpha=3 because that is the highest value seen so far, which becomes the guaranteed lower bound the maximizer can secure at this node.
Applying the pruning condition
- Now, alpha=3 and beta=infinity at the root. So, we don't prune. Carrying alpha=3 down to the center node, we compute MIN{2, infinity}=2 to update beta at this node. So at the center node, alpha=3 (inherited from the root) and beta=2 (newly computed).
- Prune the second and third child nodes because alpha is now greater than beta.
- Alpha at the root remains 3 because it is greater than 2. Carrying this to the rightmost child node, evaluate MIN{infinity,2}=2. Update beta to 2 and alpha remains 3.
- Prune the second and third child nodes because alpha is now greater than beta.
- Hence, we get 3, 2, 2 at the left, center, and right MIN nodes, respectively. And calculating MAX{3,2,2}, we get 3. Therefore, without even looking at four leaves we could correctly find the minimax decision.
Additional solved examples in AI
Alpha-beta pruning shows up repeatedly across adversarial-search problems in AI, with the same core mechanics:
- Tic-Tac-Toe: Search descends to terminal states (+1, 0, -1) and prunes any opening move whose subtree contains a forced loss once a losing branch is confirmed.
- Connect Four: Depth-limited alpha-beta with an evaluation function based on open three-in-a-row threats. Pruning is especially effective because many moves are symmetric or transpose into previously searched positions.
- Chess endgames: Alpha-beta drives engines to deep ply counts in simplified endgame positions, often combined with transposition tables and killer-move heuristics.
In each case, the algorithm propagates minimax values up the tree while applying the alpha >= beta cutoff — the walkthrough above is the general pattern.
How is alpha-beta pruning used in Tic-Tac-Toe?
Tic-Tac-Toe has a small enough game tree (at most 9! = 362,880 move sequences, and far fewer distinct positions) that alpha-beta pruning can search all the way to terminal states — wins, losses, and draws — without needing an evaluation function or depth cutoff. At each terminal state, the algorithm assigns a utility value directly: +1 for an X win, -1 for an O win, and 0 for a draw. Alpha-beta pruning then propagates these values back up the tree, cutting off branches whenever a MAX node has already found a move at least as good as any the MIN opponent would allow (or vice versa). Concretely, if X's first move to the center guarantees at least a draw against best play, alpha at the root is set to 0, and any sibling opening move whose subtree contains a forced loss for X can be pruned as soon as one losing branch is discovered. This is why a Tic-Tac-Toe engine with alpha-beta pruning can play perfectly in real time: the pruned tree is small enough to search exhaustively.
In larger games like Checkers and Chess, the tree is far too large to reach terminal states, so engines pair alpha-beta pruning with a depth cutoff and an evaluation function for non-terminal positions — the same category of game playing programs that rely on heuristic cutoffs because exhaustive search is intractable.
Pseudocode
Pseudocode adapted from the NPTEL Artificial Intelligence course by IIT Kharagpur (Source: NPTEL Artificial Intelligence course):
Pseudocode — not runnable:
evaluate (node, alpha, beta)
if node is a leaf
return the utility value of node
if node is a minimizing node
for each child of node
beta = min (beta, evaluate (child, alpha, beta))
if beta <= alpha
return beta
return beta
if node is a maximizing node
for each child of node
alpha = max (alpha, evaluate (child, alpha, beta))
if beta <= alpha
return alpha
return alpha
Implementation note: This is the conceptual textbook pseudocode, which passes alpha and beta by value into each recursive call. Production implementations typically either pass the bounds by reference or use an explicit alpha-beta window scoping model so that updates within a subtree influence sibling evaluations correctly — the by-value form shown here is fine for teaching but is not what you would ship.
Minimax with alpha-beta pruning in Python
The following runnable Python snippet implements minimax with alpha-beta pruning on a toy game tree represented as nested lists (internal nodes) with integer leaves. It alternates MAX and MIN layers starting from the root.
import math
def alpha_beta(node, depth, alpha, beta, maximizing_player):
# Leaf: return its utility value
if isinstance(node, int) or depth == 0:
return node
if maximizing_player:
value = -math.inf
for child in node:
value = max(value, alpha_beta(child, depth - 1, alpha, beta, False))
alpha = max(alpha, value)
if alpha >= beta:
break # beta cutoff
return value
else:
value = math.inf
for child in node:
value = min(value, alpha_beta(child, depth - 1, alpha, beta, True))
beta = min(beta, value)
if alpha >= beta:
break # alpha cutoff
return value
# Example tree matching the walkthrough: root is MAX, children are MIN nodes,
# grandchildren are leaves with utility values.
tree = [
[3, 5, 6], # left MIN subtree
[2, 4, 7], # center MIN subtree -> prunes after reading 2
[2, 8, 9], # right MIN subtree -> prunes after reading 2
]
result = alpha_beta(tree, depth=2, alpha=-math.inf, beta=math.inf, maximizing_player=True)
print(result) # 3
Running this prints 3, matching the minimax value computed in the walkthrough above. For a real game, replace the nested-list tree with a function that generates legal moves from a game state and an evaluation function for non-terminal positions at the cutoff depth.
Conclusion
The minimax algorithm alpha-beta pruning preserves correctness while eliminating branches that cannot affect the final decision, often letting a search skip large portions of the game tree. In the example above, the algorithm reached the correct minimax value of 3 without evaluating every leaf, which is the core efficiency benefit that makes alpha-beta pruning a standard optimization in adversarial game-tree search.
That said, alpha-beta pruning's efficiency depends heavily on move ordering. With optimal move ordering and even search depths, alpha-beta pruning reduces the effective branching factor from b to approximately sqrt(b) — a result due to Knuth, D.E. and Moore, R.W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4), 293–326 — roughly doubling the depth searchable in the same time. Practical engines approach optimal ordering with heuristics such as killer moves, the history heuristic, and MVV-LVA (most valuable victim, least valuable attacker) for captures. With worst-case (pessimal) move ordering, however, it degenerates to plain minimax and delivers no savings. For very deep trees, additional heuristics — such as iterative deepening or evaluation functions applied at a cutoff depth — are still required to keep the search tractable.
QA note: the pseudocode block uses a
textlanguage specifier; the Python block usespython. Both require a visual QA pass in the CMS before publish to confirm clean rendering of indentation and symbols.
