Alpha-Beta Pruning
Discover the clever shortcut that lets game AIs search twice as deep by ignoring branches that can never change the outcome.
It's 1997. Deep Blue is about to beat Garry Kasparov — the reigning world chess champion — in a six-game match. The machine is evaluating 200 million positions per second. But here's the dirty secret: it isn't actually checking all of them. A huge fraction of the tree gets thrown away before it's even evaluated, because a clever algorithm proved those branches could never matter.
That algorithm is alpha-beta pruning. It's a turbocharge for minimax — the classic game-tree search — that produces the exact same answer while skipping branches that a rational opponent would never let you reach. Master it and you can search roughly twice as deep for the same compute budget. That's the difference between a decent move and a brilliant one.
#Quick Recap: How Minimax Works
Minimax treats a two-player zero-sum game as a tree. Each level alternates between the maximizing player (MAX, usually you) trying to get the highest score, and the minimizing player (MIN, your opponent) trying to get the lowest score.
- At leaf nodes (the bottom of the tree), a scoring function assigns a number: positive means good for MAX, negative means good for MIN.
- At MAX nodes, the parent takes the highest child score — MAX picks the best move.
- At MIN nodes, the parent takes the lowest child score — MIN picks the worst move for you.
The algorithm backs values up from leaves to root. It's correct but slow — every leaf gets visited, even ones a rational player would never reach.
Negotiating With a Stubborn Opponent
Imagine you're negotiating a deal. You've already found a supplier who'll sell you widgets for $10. Now you're listening to a new supplier list their prices. The moment they quote $12 for the first item, you can hang up — you're never taking a deal worse than $10 overall, and this supplier has already proved they can't beat it.
Alpha-beta pruning is exactly this: keep a running record of the best deal you've already secured (alpha for MAX, beta for MIN), and the moment you see the current branch can't beat it, stop listening and move on.
#Meet Alpha and Beta
Alpha-beta adds two numbers that travel down the tree as the search unfolds.
- Alpha (α) — the best score MAX has guaranteed so far on the path from the root. MAX will never accept anything below this. Starts at -infinity.
- Beta (β) — the best score MIN has guaranteed so far on the path from the root. MIN will never allow anything above this. Starts at +infinity.
As the search progresses, alpha rises and beta falls. The pruning rule is simple:
> If α ≥ β at any node, stop exploring its remaining children. The branch is pruned.
Why? Because whatever value this node returns will fall outside the window [α, β] that the ancestor cares about — so no matter what the remaining children say, the ancestor will never choose this path. And here's the crucial point: no approximation is happening. You get the exact minimax answer, just faster.
# Alpha-beta pruning — complete from-scratch implementation
# Tree stored as nested lists; leaves are plain numbers.
def alpha_beta(node, alpha, beta, maximizing):
if not isinstance(node, list): # leaf node
return node
if maximizing:
value = float('-inf')
for child in node:
value = max(value, alpha_beta(child, alpha, beta, False))
alpha = max(alpha, value)
if alpha >= beta:
break # MIN won't allow this; prune remaining siblings
return value
else:
value = float('inf')
for child in node:
value = min(value, alpha_beta(child, alpha, beta, True))
beta = min(beta, value)
if alpha >= beta:
break # MAX already has a better guarantee elsewhere
return value
# Tree: root=MAX, depth-1=MIN, leaves
# [[3,5], [2,8], [9,1]] -> MIN picks min of each pair: 3, 2, 1
# -> MAX picks max of those: 3
tree = [[3, 5], [2, 8], [9, 1]]
result = alpha_beta(tree, float('-inf'), float('inf'), maximizing=True)
print("Best score for MAX:", result)Move Ordering: The Secret Multiplier
Alpha-beta prunes more when good moves are examined first. If MAX sees its best move early, alpha rises quickly and cuts off more MIN branches. With random move ordering you get modest savings; with perfect ordering, the effective branching factor drops from b to roughly sqrt(b), letting you search to double the depth for the same time budget.
Real engines use iterative deepening (search to depth 1, then 2, then 3 — each pass informs move ordering for the next) combined with a killer heuristic (try moves that caused cutoffs at sibling nodes first).
nodes_visited = 0
nodes_pruned = 0
def alpha_beta_traced(node, alpha, beta, maximizing):
global nodes_visited, nodes_pruned
if not isinstance(node, list):
nodes_visited += 1
return node
if maximizing:
value = float('-inf')
for i, child in enumerate(node):
value = max(value, alpha_beta_traced(child, alpha, beta, False))
alpha = max(alpha, value)
if alpha >= beta:
nodes_pruned += len(node) - i - 1 # count skipped siblings
break
return value
else:
value = float('inf')
for i, child in enumerate(node):
value = min(value, alpha_beta_traced(child, alpha, beta, True))
beta = min(beta, value)
if alpha >= beta:
nodes_pruned += len(node) - i - 1
break
return value
# 3 levels, branching factor 3 = 27 leaves total
big_tree = [[[1,4,2],[6,3,5],[8,2,7]],
[[4,1,3],[9,2,6],[3,5,1]],
[[7,4,3],[2,8,5],[6,1,4]]]
result = alpha_beta_traced(big_tree, float('-inf'), float('inf'), True)
print(f"Result: {result}")
print(f"Leaves evaluated: {nodes_visited}")
print(f"Leaves pruned: {nodes_pruned}")Pruned Does Not Mean Bad
A common misconception: pruned branches are bad moves. They're not — they're irrelevant moves. A rational opponent will never allow the game to reach those positions, so evaluating them would not change which move the root chooses. Pruning is a logical proof of irrelevance, not a value judgment.
Also note: alpha-beta gives the exact minimax result only when both players play optimally. If your opponent sometimes makes suboptimal moves, the pruned branches are still safe to ignore for the purposes of finding your best response to optimal play.
# Complete alpha-beta AI for tic-tac-toe
def check_winner(board):
wins = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
for a,b,c in wins:
if board[a] == board[b] == board[c] and board[a] != '.':
return board[a]
return 'draw' if '.' not in board else None
def ab_ttt(board, alpha, beta, is_max):
result = check_winner(board)
if result == 'X': return 10
if result == 'O': return -10
if result == 'draw': return 0
if is_max:
best = float('-inf')
for i in range(9):
if board[i] == '.':
board[i] = 'X'
best = max(best, ab_ttt(board, alpha, beta, False))
board[i] = '.'
alpha = max(alpha, best)
if alpha >= beta: break
return best
else:
best = float('inf')
for i in range(9):
if board[i] == '.':
board[i] = 'O'
best = min(best, ab_ttt(board, alpha, beta, True))
board[i] = '.'
beta = min(beta, best)
if alpha >= beta: break
return best
def best_move(board):
best_score, move = float('-inf'), -1
for i in range(9):
if board[i] == '.':
board[i] = 'X'
score = ab_ttt(board, float('-inf'), float('inf'), False)
board[i] = '.'
if score > best_score:
best_score, move = score, i
return move
# X has two in the left column (squares 0, 3). Winning move is square 6.
# Board: X O . squares: 0 1 2
# X O . 3 4 5
# . . . 6 7 8
board = ['X','O','.', 'X','O','.', '.','.','.']
print("AI plays square:", best_move(board))During an alpha-beta search, you're at a MIN node with α = 5 and β = +∞. The first child returns 3. You update β = 3. Should you evaluate the remaining children?
#Why This Matters Beyond Games
Alpha-beta is the engine behind decades of game-playing AI. Stockfish (world-class chess engine) still uses it at its core. The core insight — track the best guarantee on each side and stop the moment a branch can't beat it — generalizes far beyond games.
In modern systems, alpha-beta is combined with: - Transposition tables — cache evaluated positions, since the same board is reachable by many move orders. - Quiescence search — at the depth limit, keep going until the position is "quiet" (no captures pending) to avoid misjudging tactical positions. - Learned evaluators — AlphaZero replaced the hand-crafted scoring function with a neural net, but still uses tree search guided by the same pruning logic.
Even outside games, the mindset — prove a branch is irrelevant and skip it — appears in branch-and-bound optimization, constraint propagation, and database query planning. You've just learned a fundamental idea in computer science.
Key takeaways
- Alpha-beta pruning is minimax with two running bounds: alpha (best MAX can guarantee) and beta (best MIN can guarantee). When α ≥ β, prune.
- Pruned branches are not approximations — they genuinely cannot change the result a rational player would choose.
- With perfect move ordering, alpha-beta roughly halves the tree depth needed, letting an AI search twice as far ahead for the same compute.
- Move ordering techniques like iterative deepening and the killer heuristic are critical for maximizing how much gets pruned.
- The same bound-and-prune idea appears in optimization, constraint solving, and query planning — it's a fundamental CS pattern.
Start with the scores of each final position (the leaves).
This is the lesson's alpha-beta function run on a small MAX-root tree. What does it print?
def alpha_beta(node, alpha, beta, maximizing):
if not isinstance(node, list):
return node
if maximizing:
value = float('-inf')
for child in node:
value = max(value, alpha_beta(child, alpha, beta, False))
alpha = max(alpha, value)
if alpha >= beta:
break
return value
else:
value = float('inf')
for child in node:
value = min(value, alpha_beta(child, alpha, beta, True))
beta = min(beta, value)
if alpha >= beta:
break
return value
tree = [[3, 5], [2, 8], [9, 1]]
print(alpha_beta(tree, float('-inf'), float('inf'), True))Alpha starts at -infinity and beta at +infinity at the root. What is printed for this MIN node's returned value?
def alpha_beta(node, alpha, beta, maximizing):
if not isinstance(node, list):
return node
value = float('inf')
for child in node:
value = min(value, alpha_beta(child, alpha, beta, True))
beta = min(beta, value)
if alpha >= beta:
break
return value
# MIN node reached with alpha already = 5 from an ancestor
node = [7, 3, 9, 1]
print(alpha_beta(node, 5, float('inf'), False))Complete the pruning check inside a MAX node. The lesson's rule: stop exploring remaining children the moment alpha is at least beta.
if maximizing: value = float('-inf') for child in node: value = max(value, alpha_beta(child, alpha, beta, False)) alpha = max(alpha, value) if alpha beta: break # MIN won't allow this; prune remaining siblings return value
Put the body of a MIN node's child loop in the correct order for alpha-beta pruning, matching the lesson's implementation.
for child in node:
beta = min(beta, value)
value = float('inf')if alpha >= beta:
value = min(value, alpha_beta(child, alpha, beta, True))
break
This code has a bug — what's wrong?
def alpha_beta(node, alpha, beta, maximizing):
if not isinstance(node, list):
return node
if maximizing:
value = float('-inf')
for child in node:
value = max(value, alpha_beta(child, alpha, beta, False))
beta = max(beta, value) # update on maximizing branch
if alpha >= beta:
break
return value
# ... (MIN branch omitted)Below is a plain minimax function. Your job is to upgrade it into alpha-beta pruning.
The game tree is a nested list of integers (leaves are numbers, interior nodes are lists). The function alternates between MAX (maximizing=True) and MIN (maximizing=False).
Add alpha and beta parameters, update them correctly after each child, and break out of the loop when α ≥ β.
Both test trees should print [OK] — the alpha-beta answer must match minimax exactly.
Try it live — edit the code and hit Run to execute real Python: