Problem Solving By Search
Adversarial Search & Game Playing
Every algorithm in Chapters 2-4 assumed a single agent, alone, in an environment that doesn't fight back (Module 1, Chapter 4's "single-agent" environment prope
Jr Codex AI Notes
Level: Intermediate–Advanced Prerequisites: Chapter 4 Time to complete: ~30 minutes
Table of Contents
- Search Against an Opponent
- Game Trees
- The Minimax Algorithm
- Alpha-Beta Pruning
- Depth-Limited Search & Evaluation Functions
- Handling Chance — Expectimax
- Why Chess/Go Engines Still Matter Today
- Summary & Next Steps
1. Search Against an Opponent
Every algorithm in Chapters 2-4 assumed a single agent, alone, in an environment that doesn't fight back (Module 1, Chapter 4's "single-agent" environment property). Adversarial search handles the multi-agent, competitive case — a game where another agent is actively trying to make you lose.
Path-Based Search (Ch.2-3) Adversarial Search (this chapter)
───────────────────────────── ─────────────────────────────
"Find MY best path to the goal" "Find MY best move, given that
my OPPONENT will respond with
Single-agent, no opposition THEIR best move to hurt me"
Two (or more) agents, WITH
directly opposing goals
───────────────────────────── ─────────────────────────────
This chapter focuses on zero-sum, two-player, perfect-information games (like chess or tic-tac-toe) — one player's gain is exactly the other's loss, and both players can see the entire board.
2. Game Trees
A game tree extends Chapter 1's state-space graph with one crucial addition: alternating levels represent alternating players' turns.
Tic-Tac-Toe Game Tree (partial)
─────────────────────────────────────────
[Empty board] ← MAX's turn (X)
/ | \
[X.. ] [.X.] [..X] ← MIN's turn (O)
/ \ ... ...
[XO.] [X.O] ← MAX's turn again
... ...
─────────────────────────────────────────
The Two Roles
─────────────────────────────────────────
MAX: the player we're building the AI FOR — wants to
maximize the final score/outcome
MIN: the opponent — assumed to play OPTIMALLY against
us, trying to minimize our score (i.e., maximize
their own, since it's zero-sum)
─────────────────────────────────────────
A critical assumption: adversarial search assumes the opponent plays optimally — this is a deliberately pessimistic, worst-case assumption (a weak opponent only makes the outcome better than predicted, never worse), which is what makes the resulting strategy robust.
3. The Minimax Algorithm
Minimax computes the best move by assuming both players play perfectly — MAX always picks the move leading to the highest value, MIN always picks the move leading to the lowest.
def minimax(state, depth, is_maximizing_player, get_children, evaluate, is_terminal):
if is_terminal(state) or depth == 0:
return evaluate(state)
if is_maximizing_player:
best_value = float("-inf")
for child in get_children(state):
value = minimax(child, depth - 1, False, get_children, evaluate, is_terminal)
best_value = max(best_value, value)
return best_value
else:
best_value = float("inf")
for child in get_children(state):
value = minimax(child, depth - 1, True, get_children, evaluate, is_terminal)
best_value = min(best_value, value)
return best_valueMinimax Value Propagation
─────────────────────────────────────────
[Root] MAX picks the HIGHEST child value
/ | \
3 12 8 MIN picks the LOWEST child value
/|\ /|\ /|\ at each of ITS turns
3 5 6 12 8 2 8 4 6
(leaf values — final outcomes at the bottom of the tree)
MIN's node under "3": min(3, 5, 6) = 3
MIN's node under "12": min(12, 8, 2) = 2
MIN's node under "8": min(8, 4, 6) = 4
MAX's root: max(3, 2, 4) = 4 ← MAX's best guaranteed outcome
─────────────────────────────────────────
# A tiny, complete tic-tac-toe move selector using minimax
def get_best_move(board, player):
best_score = float("-inf")
best_move = None
for move in available_moves(board):
new_board = apply_move(board, move, player)
score = minimax(new_board, depth=9, is_maximizing_player=False,
get_children=lambda b: [apply_move(b, m, opponent(player))
for m in available_moves(b)],
evaluate=evaluate_board,
is_terminal=is_game_over)
if score > best_score:
best_score, best_move = score, move
return best_moveMinimax is complete and optimal against an optimal opponent — for small games (tic-tac-toe) it can even solve the entire game tree exhaustively. For large games (chess), the tree is astronomically large, motivating Sections 4-5.
4. Alpha-Beta Pruning
Alpha-beta pruning produces the exact same result as plain minimax, but skips exploring branches that can't possibly affect the final decision — often dramatically reducing the number of nodes examined.
def alpha_beta(state, depth, alpha, beta, is_maximizing_player, get_children, evaluate, is_terminal):
if is_terminal(state) or depth == 0:
return evaluate(state)
if is_maximizing_player:
value = float("-inf")
for child in get_children(state):
value = max(value, alpha_beta(child, depth - 1, alpha, beta, False, get_children, evaluate, is_terminal))
alpha = max(alpha, value)
if alpha >= beta:
break # BETA CUTOFF — MIN would never let us reach this branch anyway
return value
else:
value = float("inf")
for child in get_children(state):
value = min(value, alpha_beta(child, depth - 1, alpha, beta, True, get_children, evaluate, is_terminal))
beta = min(beta, value)
if alpha >= beta:
break # ALPHA CUTOFF — MAX would never let us reach this branch anyway
return valueAlpha & Beta, Intuitively
─────────────────────────────────────────
alpha: the BEST value MAX can guarantee SO FAR (a lower bound)
beta: the BEST value MIN can guarantee SO FAR (an upper bound)
If, while exploring, we find a value that's WORSE for the
current player than a guarantee already available from a
DIFFERENT branch — there's no point continuing to explore
this branch. The opponent would simply never let play reach
a bad-for-them outcome from a branch that's already knowably
worse than an alternative.
─────────────────────────────────────────
Example — a Cutoff in Action
─────────────────────────────────────────
[MAX]
/ \
[MIN] [MIN]
/ \ \
3 ??? ...
MIN's LEFT subtree: explores 3, sees the SECOND child is <= 3
(since MIN wants the minimum) — MIN's left result will be AT
MOST 3.
If MAX has ALREADY found a guarantee of 5 from a DIFFERENT
branch, MAX will NEVER choose this left branch (max(5, <=3) = 5
regardless) — so alpha-beta STOPS exploring the "???" child
entirely. It literally cannot change the final decision.
─────────────────────────────────────────
With a good move-ordering (checking likely-best moves first), alpha-beta pruning can effectively double the search depth achievable in the same time — this is why real chess engines rely on it (plus Section 5's techniques) rather than plain minimax.
5. Depth-Limited Search & Evaluation Functions
Real games like chess have game trees far too large to search to the end (a "terminal" win/loss/draw state) — so engines search only a limited number of moves ahead, then use an evaluation function to estimate how good a non-terminal position is.
def evaluate_chess_position(board):
"""
A simplified chess evaluation function — estimates how favorable
a position is for the CURRENT player, without knowing the actual outcome.
"""
piece_values = {"pawn": 1, "knight": 3, "bishop": 3, "rook": 5, "queen": 9}
my_material = sum(piece_values[p] for p in board.my_pieces)
opponent_material = sum(piece_values[p] for p in board.opponent_pieces)
material_score = my_material - opponent_material
mobility_score = len(board.legal_moves) * 0.1 # more available moves = more flexible position
return material_score + mobility_scoreDepth-Limited Minimax/Alpha-Beta
─────────────────────────────────────────
Instead of recursing all the way to a TERMINAL state
(checkmate/stalemate — potentially dozens of moves away),
stop after a fixed DEPTH and call evaluate() on whatever
position is reached — treating that estimate AS IF it were
the true outcome.
The quality of PLAY depends heavily on:
1. How DEEP the search can go (more compute = deeper)
2. How ACCURATE the evaluation function is
─────────────────────────────────────────
This is exactly why chess engine strength has historically tracked computing power so closely — Deep Blue's 1997 win over Kasparov (Module 1, Chapter 2's history) came substantially from raw search depth enabled by specialized hardware, evaluating far more positions per second than any competitor at the time.
6. Handling Chance — Expectimax
Minimax assumes a deterministic, adversarial opponent. Games involving randomness (dice, card draws) need a variant that accounts for probability — directly connecting to Module 4's probabilistic reasoning, applied here to game-tree search.
def expectimax(state, depth, node_type, get_children, evaluate, is_terminal, probabilities=None):
"""
node_type: "max", "min", or "chance"
probabilities: for chance nodes, a dict mapping each child to its probability
"""
if is_terminal(state) or depth == 0:
return evaluate(state)
children = get_children(state)
if node_type == "max":
return max(expectimax(c, depth - 1, "min", get_children, evaluate, is_terminal) for c in children)
elif node_type == "min":
return min(expectimax(c, depth - 1, "max", get_children, evaluate, is_terminal) for c in children)
elif node_type == "chance":
# EXPECTED value — weighted average over all random outcomes
return sum(
probabilities[c] * expectimax(c, depth - 1, "max", get_children, evaluate, is_terminal)
for c in children
)Minimax vs Expectimax
─────────────────────────────────────────
Minimax: assumes the opponent ALWAYS plays optimally
against you — worst-case reasoning
Expectimax: for CHANCE nodes (dice rolls, card draws),
takes a PROBABILITY-WEIGHTED AVERAGE across
outcomes instead of a min/max — appropriate
for backgammon, or the random tile draws
in a game like 2048
─────────────────────────────────────────
7. Why Chess/Go Engines Still Matter Today
The Legacy of Adversarial Search
─────────────────────────────────────────
Deep Blue (1997) Pure alpha-beta pruning + massive
specialized search hardware — no
machine learning involved at all
AlphaGo (2016) COMBINED classical adversarial search
(Monte Carlo Tree Search, a more
advanced relative of minimax) WITH
deep learning (evaluating positions
via a trained neural network instead
of hand-coded rules like Section 5)
Modern engines Nearly all top chess/Go engines today
(Stockfish, AlphaZero) still use SOME form of adversarial
tree search at their core, now
enhanced by learned evaluation
functions — the classical
technique from this chapter never
went away, it got COMBINED with
deep learning (full depth in the
DL notes)
─────────────────────────────────────────
This is a clean, concrete example of Module 1, Chapter 3's point that symbolic and sub-symbolic AI aren't mutually exclusive — modern game-playing AI is a genuine fusion of this chapter's classical search with the learning-based techniques covered in the Deep Learning notes.
8. Summary & Next Steps
Key Takeaways
- Adversarial search handles competitive, multi-agent games by assuming the opponent plays optimally against you — a deliberately pessimistic, robust assumption.
- Minimax computes the best guaranteed outcome by alternating max/min at each level of the game tree; alpha-beta pruning produces the identical result while skipping provably irrelevant branches.
- Real games use depth-limited search plus an evaluation function to estimate non-terminal positions, since full game trees (chess, Go) are far too large to search exhaustively.
- Expectimax replaces min nodes with probability-weighted averages for games involving genuine chance (dice, card draws).
- Modern game-playing AI (AlphaGo and beyond) combines this chapter's classical tree search with deep-learning-based evaluation functions — the two paradigms are complementary, not competing.
Concept Check
- Why does minimax assume the opponent plays optimally, even if a real opponent might not?
- What guarantee does alpha-beta pruning provide relative to plain minimax, despite exploring fewer nodes?
- Why does chess require a depth-limited search with an evaluation function, while tic-tac-toe doesn't?
Next Chapter
→ Chapter 6: Constraint Satisfaction Problems
Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index