Search: uninformed, informed and adversarial

Problems as search

Definition. A search problem has an initial state, actions that move between states, a goal test, and a step cost for every action. A solution is a sequence of actions from the initial state to a goal; an optimal solution has the least total cost.

Search algorithms differ in which node of the frontier (the set of generated but unexpanded nodes) they expand next. We compare them on four properties:

• Complete: does it always find a solution if one exists?
• Optimal: does it find the cheapest solution?
• Time and space complexity, in terms of the branching factor $b$, the depth $d$ of the shallowest goal and the maximum depth $m$.

Uninformed search

These use only the problem definition, no estimate of distance to the goal.

Breadth-first search (BFS) expands the shallowest node first, using a FIFO queue. It is complete (for finite $b$) and optimal when every step costs the same. Time and space $O(b^{d})$: memory is the real problem.

Uniform-cost search (UCS) expands the node with the smallest path cost $g(n)$, using a priority queue. It is complete and optimal for positive step costs; with equal costs it behaves like BFS. (It is Dijkstra's algorithm with an explicit goal.)

Depth-first search (DFS) expands the deepest node first, using a LIFO stack. Space is only $O(bm)$, but it is not optimal and not complete on infinite or cyclic spaces without a visited check. Time $O(b^{m})$.

Depth-limited search is DFS that stops at a depth limit $\ell$. Iterative deepening (IDS) runs depth-limited search with $\ell = 0, 1, 2, \dots$. It combines BFS's completeness and optimality (for unit costs) with DFS's $O(bd)$ memory. Re-expanding the upper levels costs little, because most nodes are at the deepest level; time stays $O(b^{d})$.

Bidirectional search runs two searches, from the start and from the goal, until they meet: about $2b^{d/2}$ nodes instead of $b^{d}$.

Algorithm	Complete	Optimal	Time	Space
BFS	yes	yes (unit costs)	$O(b^d)$	$O(b^d)$
UCS	yes	yes	$O(b^{1+\lfloor C^*/\varepsilon\rfloor})$	same
DFS	no (infinite depth)	no	$O(b^m)$	$O(bm)$
IDS	yes	yes (unit costs)	$O(b^d)$	$O(bd)$

Solved example

Example 1: BFS order. Graph: S → A, S → B; A → C, A → D; B → E; D → G (goal). Children are added in alphabetical order.

1. Queue [S]. Expand S: queue [A, B].
2. Expand A: queue [B, C, D].
3. Expand B: queue [C, D, E].
4. Expand C (no children), then D: G is generated.

BFS expands S, A, B, C, D and finds the path S → A → D → G. DFS (stack, alphabetical) expands S, A, C, D and then reaches G: it finds the same path here by luck, after fewer expansions.

Informed (heuristic) search

A heuristic $h(n)$ estimates the cost from $n$ to the nearest goal.

Greedy best-first search expands the node with the smallest $h(n)$. It is fast but neither complete nor optimal: it ignores the cost already paid.

A* search expands the node with the smallest

$f(n) = g(n) + h(n),$

the cost so far plus the estimated cost to go.

Admissible heuristic: $h(n) \le h^*(n)$ for every $n$, where $h^*$ is the true cheapest cost to a goal; it never overestimates. With an admissible heuristic, A* tree search is optimal.

Consistent (monotone) heuristic: $h(n) \le c(n, n') + h(n')$ for every edge $n \to n'$, and $h(\text{goal}) = 0$. Consistency implies admissibility, makes $f$ non-decreasing along every path, and makes A* graph search optimal (a node never needs reopening).

Exam points.

• $h(n) = 0$ for all $n$ is admissible and consistent; A* then becomes uniform-cost search.
• Of two admissible heuristics, the larger one (it dominates) expands no more nodes.
• For the 8-puzzle, "number of misplaced tiles" and "sum of Manhattan distances" are both admissible; Manhattan dominates.
• The maximum of admissible heuristics is admissible.

Solved example

Example 2: A*. Edges: S–A cost 1, S–B cost 4, A–B cost 2, A–G cost 12, B–G cost 3. Heuristic: $h(S) = 6$, $h(A) = 5$, $h(B) = 2$, $h(G) = 0$.

1. Expand S. Frontier: A with $f = 1 + 5 = 6$; B with $f = 4 + 2 = 6$.
2. Expand A (tie, broken alphabetically). New paths: B via A with $g = 3$, $f = 3 + 2 = 5$ (better than 6); G via A with $g = 13$, $f = 13$.
3. Expand B ($f = 5$). G via B: $g = 3 + 3 = 6$, $f = 6$.
4. Expand G ($f = 6$): goal.

A* returns S → A → B → G with cost 6. The heuristic is admissible here: the true costs to go are $h^*(S) = 6$, $h^*(A) = 5$, $h^*(B) = 3$.

Adversarial search (games)

In a two-player, zero-sum game with perfect information, MAX tries to maximise the score and MIN to minimise it.

Minimax computes the value of every node: at a leaf, its utility; at a MAX node, the maximum of its children; at a MIN node, the minimum. Searching the whole tree costs $O(b^{m})$ time.

Alpha–beta pruning returns the same value as minimax but skips branches that cannot affect the decision.

• $\alpha$ = best value MAX can guarantee so far on the path; $\beta$ = best value MIN can guarantee so far.
• At a MIN node, stop exploring children as soon as its value $\le \alpha$. At a MAX node, stop as soon as its value $\ge \beta$.
• With the best move ordering it examines about $O(b^{m/2})$ nodes, so it can search roughly twice as deep in the same time. With the worst ordering it prunes nothing.

Solved example

Example 3. MAX at the root has two MIN children. The left MIN node has leaves 3, 5; the right MIN node has leaves 2, 9.

1. Left MIN node $= \min(3, 5) = 3$, so $\alpha = 3$ at the root.
2. Right MIN node: the first leaf is 2. Its value can only go down from here, so it is at most $2 < \alpha = 3$. Prune the leaf 9.
3. Root value $= \max(3, 2) = 3$: MAX plays the left move.

Formulating problems in more depth

8-puzzle. The state is the arrangement of eight tiles and the blank on a 3×3 board. The actions move the blank Up, Down, Left or Right. Each step costs 1, and the goal is a fixed arrangement. There are $9! = 362{,}880$ arrangements, but only $9!/2 = 181{,}440$ can be reached from any given start, because a move never changes a parity invariant. A corner blank has 2 moves, an edge blank 3, and the centre 4, so the average branching factor is about 2.67.

Route finding. The states are cities, the actions are roads, and the step cost is the road length.