Introduction
Minimax looks at every position, but many of them cannot change the answer. Suppose you have already found a move that guarantees a draw, and you start looking at another move where the opponent's first reply already beats you. You do not need to see the opponent's other replies: you will not choose that move. Alpha-beta pruning turns this reasoning into an algorithm. It gives exactly the same result as minimax and is the core of every serious game engine.
How it works
The search carries two numbers down the tree:
- alpha: the best value MAX can already guarantee on the way to this node (starts at −∞);
- beta: the best value MIN can already guarantee (starts at +∞).
At a MAX node, each child's value can raise alpha; at a MIN node, it can lower beta. As soon as alpha ≥ beta, the node's remaining children are pruned: whichever player is choosing above will never let the game reach this node, because they already have something at least as good elsewhere.
In the classic tree ((3 12 8) (2 4 6) (14 5 2)), the first MIN node is worth 3, so alpha = 3 at the root. In the second MIN node, the first leaf is 2: this MIN node is worth at most 2, which is worse for MAX than 3, so its leaves 4 and 6 are never examined.
How much is pruned depends on move ordering. If the best move is always tried first, alpha-beta examines about b^(m/2) positions instead of b^m, so it can search twice as deep in the same time. Engines order moves with cheap guesses: captures first, the best move from a previous shallower search first, and so on.
Some games include chance, such as dice. Expectimax adds chance nodes whose value is the probability-weighted average of their children. With equally likely outcomes it is simply the mean. Pruning is harder there, because one child cannot bound an average.
Syntax
def alphabeta(node, alpha, beta, is_max):
if is_leaf(node): return value(node)
for child in children(node):
v = alphabeta(child, alpha, beta, not is_max)
if is_max: alpha = max(alpha, v)
else: beta = min(beta, v)
if alpha >= beta: break # prune the remaining children
return alpha if is_max else beta
Example
LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
count = {"minimax": 0, "alpha-beta": 0}
def winner(board):
for a, b, c in LINES:
if board[a] != "." and board[a] == board[b] == board[c]:
return board[a]
return None
def minimax(board, player):
count["minimax"] += 1
won = winner(board)
if won:
return 1 if won == "X" else -1
if "." not in board:
return 0
values = []
for i in range(9):
if board[i] == ".":
board[i] = player
values.append(minimax(board, "O" if player == "X" else "X"))
board[i] = "."
return max(values) if player == "X" else min(values)
def alphabeta(board, player, alpha, beta):
count["alpha-beta"] += 1
won = winner(board)
if won:
return 1 if won == "X" else -1
if "." not in board:
return 0
best = -2 if player == "X" else 2
for i in range(9):
if board[i] == ".":
board[i] = player
value = alphabeta(board, "O" if player == "X" else "X", alpha, beta)
board[i] = "."
if player == "X":
best = max(best, value)
alpha = max(alpha, value)
else:
best = min(best, value)
beta = min(beta, value)
if alpha >= beta:
break
return best
for start in ["X...O....", ".X..O...."]:
count = {"minimax": 0, "alpha-beta": 0}
plain = minimax(list(start), "X")
pruned = alphabeta(list(start), "X", -2, 2)
print(f"X at square {start.index('X') + 1}, O in the centre, X to move:")
print(f" minimax value {plain}, positions {count['minimax']}")
print(f" alpha-beta value {pruned}, positions {count['alpha-beta']}")Line by line
minimaxis unchanged from the last lesson;alphabetais the same search with alpha and beta passed down and abreakwhen they cross.- Both functions count every position they visit.
- Both positions have O in the centre; X is in a corner in the first and on an edge in the second, and X is to move.
- Both searches give the same value, a draw, as they must.
- Alpha-beta visits a small fraction of the positions that plain minimax visits.
Expected result
X at square 1, O in the centre, X to move:
minimax value 0, positions 7332
alpha-beta value 0, positions 844
X at square 2, O in the centre, X to move:
minimax value 0, positions 8104
alpha-beta value 0, positions 616
In the real world
Chess engines combine alpha-beta with iterative deepening, move ordering, transposition tables (memoizing positions reached by different move orders) and evaluation functions learned from data. Backgammon programs use expectimax-style search over dice rolls. AlphaZero and its successors replaced alpha-beta with Monte Carlo tree search guided by a neural network, but alpha-beta engines remain among the strongest chess players.
Common mistakes
- Pruning on alpha > beta instead of alpha ≥ beta, which is still correct but prunes less.
- Sharing alpha and beta between sibling subtrees incorrectly, instead of passing them down.
- Expecting alpha-beta to change the answer: if it does, there is a bug.
- Averaging with expectimax at nodes where a player chooses, or choosing at chance nodes.
Best practices
- Test alpha-beta against plain minimax on many small positions: the values must always agree.
- Order moves with a cheap estimate before searching them.
- Count leaves or positions visited to measure the effect of every improvement.
Summary
Alpha-beta pruning keeps the best guaranteed values for MAX (alpha) and MIN (beta) and stops exploring a node when alpha ≥ beta. It returns the minimax value while visiting far fewer positions, especially with good move ordering. Expectimax handles games of chance by averaging over outcomes.
Quick check
Key takeaways
- Alpha-beta returns exactly the minimax value, often after examining far fewer positions.
- When alpha ≥ beta at a node, its remaining children can be skipped.
- With perfect ordering, alpha-beta can search about twice as deep as minimax in the same time.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.