AI AI-01.06
Adversarial search: minimax and alpha-beta
Game trees, minimax, alpha-beta pruning, evaluation functions and depth limits, with a tic-tac-toe agent you can play against.
The big idea
Route planning has one decision maker. A game has two, and the second one is trying to beat you. When you plan a chess move you cannot simply search for a path to checkmate, because after every move of yours the opponent picks the reply that is worst for you. A plan that only works if the opponent cooperates is not a plan.
Adversarial searchSearch in a setting with an opponent whose choices work against yours, as in two-player games. handles this by assuming the opponent is as smart as you. Think of it as playing devil's advocate against yourself: for each move you consider, imagine the strongest answer, then your best answer to that, and so on. You pick the move whose worst case is best. That rule is called minimax, and with one clever shortcut, alpha-beta pruning, it powered the game-playing programs that beat human champions at checkers and chess.
How it works
Step 1: The game tree
A two-player, turn-taking, perfect-information game (tic-tac-toe, chess, checkers) defines a game treeA tree whose nodes are game positions and whose edges are moves, alternating between the players, with final scores at the leaves.. The root is the current position. Its children are the positions after each legal move, their children the positions after each reply, and so on, down to the end of the game. Each finished game, a leaf, has a score called its utility: for example +1 if the first player wins, -1 if they lose, 0 for a draw.
Name the players MAX, who wants the score high, and MIN, who wants it low. Levels of the tree alternate between them. Each level is called a ply: one move by one player.
Step 2: Minimax
MinimaxThe value of a game position assuming both players play optimally: leaves have their utility, MAX nodes take the maximum of their children, MIN nodes the minimum. computes the value of every position from the bottom up:
- A finished position is worth its utility.
- A position where MAX moves is worth the maximum of its children's values.
- A position where MIN moves is worth the minimum of its children's values.
MAX then plays the move leading to the child with the highest value. Done with depth-first search, this needs memory only for one path, but it visits every position in the tree. With a branching factor and a game that lasts plies that is positions. Tic-tac-toe is small: the full tree from the empty board has 549,946 nodes, which a computer searches in well under a second. Chess has around 35 legal moves per position and games of 80 plies or more, so is out of the question.
Read Figure 1 bottom up. The left MIN node takes the smallest of 4, 9 and 6: 4. The middle one would take the smallest of 3, 7 and 8: 3. The right one: 2. MAX takes the largest of 4, 3 and 2, so the position is worth 4 and MAX plays left. Notice what that means: the 9 and 10 are tempting, but MIN would never let MAX have them.
Step 3: Alpha-beta pruning
Look again at the middle branch. After its first leaf, 3, MIN can already hold MAX to at most 3. MAX has a guaranteed 4 on the left. Whatever the remaining leaves are, the middle branch cannot beat 4, so there is no point looking at them. The same happens on the right as soon as the 2 appears.
Alpha-beta pruningA version of minimax that skips branches which cannot affect the final decision, using two bounds: alpha (the best MAX can guarantee so far) and beta (the best MIN can guarantee so far). makes this systematic. It carries two numbers down the depth-first search:
- : the best value MAX can already guarantee on the path so far (starts at ).
- : the best value MIN can already guarantee (starts at ).
Whenever a node's value is known to fall outside the window, that is , the remaining children are skipped. The answer is exactly the same as minimax. Only the work changes.
Try it
Wins are scored , so the agent prefers quick wins and slow losses; a value of 0 means best play leads to a draw. Try this:
- Set who starts to the AI and press New game. To choose its first move, plain minimax searches 549,945 positions; alpha-beta reaches the same choice with about 21,000, roughly 96 percent fewer. Every first move is worth 0: tic-tac-toe is a draw with perfect play.
- Start yourself and take a corner. The table shows that every reply except the centre is a loss for the AI (a negative value), and it plays the centre. Pink rows are moves alpha-beta cut short once it knew they could not beat the best move found.
- Try to win, for example by setting up a fork (two threats at once). You cannot: the agent sees the fork coming and never enters a position that allows one.
Step 4: The same idea in code
Minimax and alpha-beta are one function with one extra line:
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)]
def winner(b):
for i, j, k in LINES:
if b[i] != "." and b[i] == b[j] == b[k]:
return b[i]
return None
def score(b):
"""+1 if X won, -1 if O won, 0 for a draw, None if not over."""
w = winner(b)
if w:
return 1 if w == "X" else -1
return 0 if "." not in b else None
visited = 0
def minimax(b, player, alpha=-2, beta=2, prune=False):
global visited
visited += 1
s = score(b)
if s is not None:
return s
best = -2 if player == "X" else 2 # X maximizes, O minimizes
for i in (i for i, c in enumerate(b) if c == "."):
child = b[:i] + player + b[i + 1:]
other = "O" if player == "X" else "X"
v = minimax(child, other, alpha, beta, prune)
if player == "X":
best, alpha = max(best, v), max(alpha, v)
else:
best, beta = min(best, v), min(beta, v)
if prune and alpha >= beta: # opponent never allows this line
break
return best
for prune in (False, True):
visited = 0
value = minimax("." * 9, "X", prune=prune)
name = "alpha-beta" if prune else "minimax "
print(f"{name}: empty board value {value}, visited {visited:,}")Output
minimax : empty board value 0, visited 549,946
alpha-beta: empty board value 0, visited 18,297 Both report the same value for the empty board, 0, a draw. Alpha-beta visits 18,297 positions instead of 549,946, about 30 times fewer, by adding if prune and alpha >= beta: break. (The lab's counts differ slightly because it scores wins by depth.)
Going deeper
Move ordering decides how much alpha-beta saves
Pruning happens when a good move has already been seen. If the best move is always searched first, alpha-beta examines about positions instead of : effectively the square root, which lets a program search twice as deep in the same time. With random order it is closer to , and with the worst order it prunes nothing. Real engines try the most promising moves first: captures, moves that were best in a shallower search, and "killer" moves that caused cut-offs in sibling positions.
Depth limits and evaluation functions
Even with pruning, chess cannot be searched to the end. So programs stop at a fixed depth (a cutoff) and score the position there with an evaluation functionA function that estimates the value of a non-final game position, such as a weighted sum of material and positional features., an estimate of how good it is for MAX. A classic chess evaluation is a weighted sum of features:
where might be material (pawn 1, knight and bishop 3, rook 5, queen 9) and the others king safety, mobility or pawn structure. Today the evaluation is often a neural network learned from games instead.
Two pitfalls come with cutting off. The horizon effect: a program can push an unavoidable loss just past its search depth with delaying moves and believe it has escaped. And cutting off in the middle of a capture sequence gives a wildly wrong score, so engines keep searching quiescence moves (captures and checks) until the position is calm. Iterative deepening (depth 1, then 2, then 3) lets the engine stop when its time runs out and still have the best move from the deepest finished search, and the shallow searches give it the move ordering for the deeper ones.
Beyond two-player, deterministic games
Games of chance, such as backgammon, add chance nodes whose value is the probability-weighted average of their children (expectiminimax). Games with hidden information, such as poker, need reasoning about what the opponent might hold. And games with enormous branching factors, such as Go with about 250 moves per position, defeated alpha-beta altogether; the next lesson, Monte Carlo Tree Search and AlphaGo , covers the method that cracked them.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Full minimax | Tiny games such as tic-tac-toe, where the whole tree fits in the time budget | Anything larger: it visits every position |
| Alpha-beta with good move ordering | Two-player, deterministic games with moderate branching, such as chess and checkers | Very large branching factors, and positions that are hard to evaluate |
| Depth-limited search plus evaluation | Real-time play where some error is acceptable | Accuracy depends on the evaluation; horizon effect |
| Monte Carlo tree search | Huge branching factors and no good handcrafted evaluation | Needs many simulations; weaker on sharp tactical lines |
Common mistakes
- Assuming the opponent will make the move you would like. Minimax assumes their best reply, and its worst case is a guarantee.
- Thinking alpha-beta can change the chosen move. It returns exactly the minimax value; it only skips work.
- Searching moves in a fixed, naive order. The same alpha-beta can be thousands of times faster with good ordering.
- Stopping a search in the middle of an exchange of pieces and trusting the evaluation.
- Treating a 0 from minimax as "nothing is happening". It means best play by both sides leads to a draw.
In the wild
Where you will see this: classic chess and checkers programs, including the systems that beat world champions in the 1990s, were built on alpha-beta search with handcrafted evaluation functions and careful move ordering. Modern open-source chess engines still use alpha-beta at their core, often with a neural network as the evaluation function. The same minimax reasoning appears in security as worst-case analysis: choose the defence whose outcome is best against the strongest attacker.
Check yourself
-
A MIN node has children worth 6, 2 and 9. What is its minimax value?
Show answer
C. 2 MIN picks the smallest value among its children: 2.
-
MAX has already found a move worth 5. Exploring another move, the MIN node below sees a child worth 3. What can alpha-beta do?
Show answer
B. Skip MIN's remaining children: this move is worth at most 3 to MAX MIN can hold MAX to 3 or less here, and MAX already has 5 elsewhere, so the rest of this branch cannot matter.
-
With perfect move ordering, roughly how much deeper can alpha-beta search than minimax in the same time?
Show answer
C. About twice as deep Perfect ordering reduces b^m to about b^(m/2) positions, so the same budget reaches about twice the depth.
-
A chess program stops searching at depth 6 and scores positions by material. What is the horizon effect?
Show answer
B. It pushes an unavoidable loss beyond depth 6 with delaying moves and thinks it escaped Beyond the cutoff the program sees nothing, so delaying a loss by a few plies can look like avoiding it.
-
Why did alpha-beta search struggle on Go?
Show answer
C. Go has a huge branching factor and positions are hard to evaluate With about 250 legal moves per position and no simple, accurate evaluation, even pruned search cannot see far enough.
Recap
- A game tree alternates MAX and MIN levels; minimax backs values up by taking the max or the min of the children.
- Minimax plays the move with the best worst case, assuming an optimal opponent.
- Alpha-beta pruning skips branches that cannot change the decision and returns the same answer.
- Good move ordering lets alpha-beta search about twice as deep.
- Real games cut off at a depth limit and score positions with an evaluation function, watching for the horizon effect.