How far is this puzzle from solved?
The 8-puzzle from Week 2, scrambled. Before you touch it: how many moves will it take?
You cannot know without solving it. But you can estimate, and A* only needs an estimate that never says too much.
Worked example: h₁ and h₂ by hand
Given
Start: 7 2 4 / 5 _ 6 / 8 3 1. Goal: _ 1 2 / 3 4 5 / 6 7 8 (Russell & Norvig's example).
Find
h₁ (misplaced tiles) and h₂ (sum of Manhattan distances). Are they admissible? Which is better?
Method: 8-puzzle heuristics (Russell & Norvig)
Solution
Predict the answer first. Then reveal one step at a time.
Live lab: h₀ vs h₁ vs h₂ on the 8-puzzle
| A* with | nodes generated | depth d | b* |
|---|---|---|---|
| h = 0 (UCS) | — | — | — |
| h₁ misplaced | — | — | — |
| h₂ Manhattan | — | — | — |
Bars are on a log scale. All three find the same optimal depth (both heuristics are admissible); the better-informed h₂ generates far fewer nodes.
Measuring a heuristic: the effective branching factor
If A* generates N nodes and finds a solution at depth d, b* is the branching factor of a uniform tree of depth d with N + 1 nodes:
| d | IDS | A*(h₁) | A*(h₂) |
|---|---|---|---|
| 12 | 3,644,035 · b* 2.78 | 227 · 1.42 | 73 · 1.24 |
| 24 | too many | 39,135 · 1.48 | 1,641 · 1.26 |
Nodes generated, averaged over 100 random 8-puzzles per depth (Russell & Norvig).
Dominance
If h₂(n) ≥ h₁(n) for every n (both admissible), A* with h₂ never expands more nodes than with h₁. Reason: A* surely expands every node with f(n) < C*, i.e. h(n) < C* − g(n); a larger h makes that condition true for fewer nodes.
A b* close to 1 means the search walks almost straight to the goal. A well-designed heuristic keeps b* roughly constant as problems get harder.
Inventing heuristics: relax the rules
The 8-puzzle rule: a tile can move from square A to square B if A is adjacent to B and B is blank. Drop conditions and the problem gets easier:
| Relaxed rule | Exact cost of the relaxed problem |
|---|---|
| A tile can move to B if A is adjacent to B | h₂: Manhattan distance |
| A tile can move to B if B is blank | Gaschnig's heuristic |
| A tile can move from A to B (teleport) | h₁: misplaced tiles |
The optimal cost of a relaxed problem is an admissible (and consistent) heuristic for the original: the real problem has fewer moves available, so it can only cost more.
Three more sources of h
Max of several: h = max(h₁, h₂, …) is admissible and dominates each one.
Pattern databases: solve a subproblem exactly (e.g. tiles 1–4 only, others as blanks) for every configuration, store the costs, look them up during search.
Learning: fit h(n) = c₁x₁(n) + c₂x₂(n) to solved examples (x₁ = misplaced tiles, x₂ = adjacent pairs that are not adjacent in the goal). Fast, but not guaranteed admissible.
Your turn · 1: heuristics for a robot that moves like a king
A hospital delivery robot moves on a grid in 8 directions. Straight steps cost 1. Candidate heuristics to the target at (Δx, Δy): Manhattan Δx + Δy, Euclidean √(Δx² + Δy²), Chebyshev max(Δx, Δy).
(a) If a diagonal step costs 1, which are admissible? (b) If it costs √2? Use Δx = 3, Δy = 2 as a test. (c) Why are the good ones admissible even with walls in the way?
Work it out first.
Press Solve when the class has an answer.
Critical thinking · is the perfect heuristic worth it?
h = h* (the exact remaining cost) makes A* walk straight to the goal. Why not always use it?
Argue it in pairs for two minutes. There may be more than one defensible answer.
h₁ is admissible and so is h₂. Is h₁ + h₂ admissible? Is (h₁ + h₂)/2?
Argue it in pairs for two minutes. There may be more than one defensible answer.
Games: search when someone fights back
Until now the environment did what we asked. In a game, a second agent chooses half of the moves, against us. We study the simplest kind: two players, turn-taking, deterministic, fully observable, zero-sum (one's win is the other's loss).
| A game as a search problem | |
|---|---|
| S₀ | initial state (empty board) |
| TO-MOVE(s) | whose turn: MAX or MIN |
| ACTIONS(s), RESULT(s, a) | legal moves and their effect |
| IS-TERMINAL(s) | is the game over? |
| UTILITY(s, p) | final score for player p (+1 / 0 / −1) |
Why ordinary search fails
A* finds a path to a goal. But we do not control MIN's moves, so no path is guaranteed. We need a strategy: a move for every reply the opponent might make.
| Game | b | game tree |
|---|---|---|
| Tic-tac-toe | ≤ 9 | 549,946 nodes |
| Chess | ≈ 35 | ≈ 10154 (1040 positions) |
| Go | ≈ 250 | ≈ 10360 |
Minimax: assume the opponent is perfect
- A depth-first walk to the leaves, then values are backed up: MAX takes the largest child, MIN the smallest.
- The minimax value is what MAX can guarantee against a perfect opponent.
- Complete (finite tree), optimal against an optimal opponent. Time O(bm), space O(bm).
Values are always from MAX's point of view. A MIN node does not "want" a high number: it picks the smallest, because small is bad for MAX.
John von Neumann proved the minimax theorem in 1928, two decades before the first computer: every finite two-player zero-sum game has a value both players can guarantee.
Worked example: backing up values
Given
MAX moves, then MIN. Leaves are utilities for MAX (Russell & Norvig's example).
Find
The minimax value of every node and MAX's best move.
Method: MINIMAX: MIN takes the smallest, MAX the largest (Russell & Norvig)
Solution
Predict the answer first. Then reveal one step at a time.
Live lab: tic-tac-toe against minimax
Your move.
From the empty board the full game tree has 549,946 nodes (only 5,478 distinct positions: many move orders reach the same one). Tiny for a computer. Chess has about 1040 legal positions and Go about 10170: full minimax is hopeless there.
Your turn · 2: a three-ply tree
Find the minimax value of every internal node and MAX's best first move. Which leaf is reached if both play perfectly?
Work it out first.
Press Solve when the class has an answer.
Critical thinking · what if MIN is not perfect?
Minimax assumes MIN plays perfectly. Your opponent is a beginner who often blunders. Is minimax still a good strategy? Can MAX do worse than the minimax value? Could it do better?
Argue it in pairs for two minutes. There may be more than one defensible answer.
Real games are too deep: cut off and evaluate
- Stop the search at a depth limit d (IDS from Week 3: deepen until time runs out) and replace UTILITY by an evaluation function EVAL(s): an estimate of the utility.
- EVAL is the game version of a heuristic h. The usual form is a weighted sum of features:
Chess material: pawn 1, knight 3, bishop 3, rook 5, queen 9; fi = (my pieces − yours) of each kind, plus terms for king safety, mobility, pawn structure.
A position can look great at depth d and lose the queen at depth d + 1. Engines extend the search on "noisy" moves (captures, checks) until the position is quiet: quiescence search.
Same lesson as today's first half: a better evaluation (heuristic) lets a shallower search play stronger.
Real world: from Sholo Guti to AlphaGo
Bangladesh's village board game: 16 beads each, capture by jumping, two players, no dice, full information. Exactly the kind of game minimax with an evaluation function plays well: a good class project (b is small enough for depth 6–8).
Dice make it stochastic: minimax needs chance nodes that average over the dice (expectiminimax). Same recursion, one more node type.
Deep Blue beat world champion Garry Kasparov in 1997 with alpha–beta minimax, custom chips and about 200 million positions per second. AlphaGo beat Lee Sedol 4–1 at Go in 2016: tree search guided by neural networks that had learned the evaluation function, because Go's b ≈ 250 defeated hand-written heuristics.
Why could a hand-written EVAL work for chess but not for Go?
Argue it in pairs for two minutes. There may be more than one defensible answer.
Pop quiz
Question 1 / 5
For the 8-puzzle, h₂ (Manhattan) dominates h₁ (misplaced tiles). This means…
Three things to remember
Relax the rules, solve exactly, use the cost: an admissible, consistent h. 8-puzzle: h₁ misplaced, h₂ Manhattan; h₂ dominates.
Judge a heuristic by b* (N + 1 = 1 + b* + … + b*d) and by its cost per node. Combine admissible heuristics with max.
Games: MAX and MIN alternate; minimax backs up max/min values: O(bm) time, O(bm) space. Deep games: cut off and use EVAL.
State 3 5 _ / 6 1 4 / 7 2 8, same goal as today. (a) Find h₁ and h₂. (b) A* with h₂ finds the 12-move solution after generating 39 nodes; with h₁, 156 nodes. Find b* for each. Check (a) in the lab by sliding tiles into this state.
Work it out first.
Press Solve when the class has an answer.