The state-space model [N, A, S, GD]

The four-tuple

Luger gives one definition that every example in the chapter instantiates. A state space is the four-tuple

$$[N,A,S,GD]$$

where:

• $N$ — the set of nodes (states): every legal configuration the problem can be in.
• $A$ — the set of arcs (operators): the legal moves that transform one state into another.
• $S$ — a nonempty subset of $N$, the start state(s).
• $GD$ — the goal description: a nonempty subset of $N$, the states you are trying to reach.

A solution path is any path from a node in $S$ to a node in $GD$. To model a problem is exactly to fill in these four slots — naming what a state is, what the legal moves are, where you begin, and what counts as done. Get the four-tuple right and the search algorithm is then mechanical.

Two kinds of goal

The goal description comes in two flavours, and confusing them leads to the wrong algorithm:

• Type 1 (state property). The goal is a measurable property of a single state — a winning tic-tac-toe board, the solved 8-puzzle configuration. You stop the instant you reach a node with that property; the path you took is incidental.
• Type 2 (path property). The goal is a measurable property of the whole path — most famously the travelling-salesperson minimum-cost tour. No single state tells you whether you have won; you must track cumulative cost across the entire path. Type-2 goals force you to carry path information that type-1 goals let you discard.

The combinatorial explosion

The branching factor $B$ is the average number of children each state generates. At depth $d$ the number of nodes is $B^d$ — exponential. This single fact is why naive search fails on hard problems and why Chapter 4's heuristics exist. Chess has $B\approx 35$ and games run ~80 ply deep, giving on the order of $10^{120}$ possible game paths — vastly more than the number of atoms in the observable universe. Even modest branching factors are hopeless at depth: $B=10$, $d=10$ already means $10^{10}$ leaf nodes.

Worked example — the 8-puzzle as [N, A, S, GD]

The 8-puzzle is a $3\times 3$ frame with eight numbered tiles and one blank.

• $N$ = every arrangement of the eight tiles plus the blank ($9!/2=181,440$ reachable configurations — the full $9!$ space splits into two disconnected halves of equal size, so exactly half of all arrangements are reachable from any given start).
• $A$ = the (up to) four operators slide the blank up / down / left / right — equivalently, slide an adjacent tile into the blank.
• $S$ = the given scrambled board.
• $GD$ = the single solved board $\{1,2,3/8,\_,4/7,6,5\}$ — a type-1 goal (a property of one state).

The blank has 2–4 legal moves depending on whether it sits in a corner, edge, or centre, so the branching factor averages roughly $B\approx 2.67$. At that rate the space is still huge at depth 20, which is exactly why the 8-puzzle becomes the running example for heuristic search in Module 4.