Uniform search, heuristic strategies, local optimisation, constraint satisfaction, and adversarial games — with full traces and worked examples
Imagine you are dropped in an unfamiliar city and asked to reach a hospital. You have no map — just the ability to see the roads directly around you. You could explore every street systematically (BFS), or dive down one road as far as it goes before backtracking (DFS). These two intuitions correspond precisely to the foundational uninformed (or uniform) search strategies — algorithms that explore the state space without any domain-specific hints about which direction is "closer" to the goal.
Before comparing strategies, we establish four universal evaluation criteria. Every search algorithm in this unit will be judged on: completeness (guaranteed to find a solution?), optimality (finds the best solution?), time complexity, and space complexity. These four properties appear on virtually every AI exam — learn them for every algorithm in this tutorial.
A problem-solving agent is a goal-based agent that plans ahead: it formulates a problem, searches for a solution sequence, and then executes that plan. Unlike a reflex agent (which reacts to each percept), it can consider multi-step futures.
Key assumption: the environment is static, fully observable, deterministic, and discrete. This makes planning tractable — the environment won't change while the agent thinks, and every action has a known, certain outcome.
Any problem to be solved by search is fully specified by five components. This is a commonly tested definition — memorise all five.
In(Arad).{Go(Sibiu), Go(Zerind), Go(Timisoara)}.In(Bucharest).The state space is the set of all reachable states. It forms a directed graph — each node is a state, each edge is an action. Search algorithms explore this graph to find a goal.
We use the classic Romania road problem (Russell & Norvig Ch. 3) as our running example. The agent starts in Arad and wants to reach Bucharest. Edge weights are road distances in km. The admissible heuristic h(n) = straight-line distance (SLD) to Bucharest.
| City (n) | Road Connections (km) | h(n) = SLD to Bucharest |
|---|---|---|
| Arad | Zerind 75 · Sibiu 140 · Timisoara 118 | 366 |
| Zerind | Arad 75 · Oradea 71 | 374 |
| Sibiu | Arad 140 · Oradea 151 · RimnicuVilcea 80 · Fagaras 99 | 253 |
| Timisoara | Arad 118 · Lugoj 111 | 329 |
| RimnicuVilcea | Sibiu 80 · Pitesti 97 · Craiova 146 | 193 |
| Fagaras | Sibiu 99 · Bucharest 211 | 178 |
| Pitesti | RimnicuVilcea 97 · Craiova 138 · Bucharest 101 | 98 |
| Bucharest (GOAL) | Fagaras 211 · Pitesti 101 · Giurgiu 90 · Urziceni 85 | 0 |
Optimal solution: Arad → Sibiu → RimnicuVilcea → Pitesti → Bucharest = 418 km. Every algorithm in this tutorial is benchmarked against this answer.
BFS expands the shallowest unexpanded node first by using a FIFO queue as the frontier. Think of the search as a wave that expands outward level by level — all nodes at depth d are explored before any node at depth d+1.
Create frontier = FIFO queue with the initial node. Create explored = empty set.
If frontier is empty → return failure.
Dequeue node n. Goal test: if Goal(n.state) → return solution path to n.
Add n.state to explored. For each action a: if Result(n,a) not in explored or frontier → enqueue child.
Go to Step 2.
DFS expands the deepest unexpanded node first using a LIFO stack. It plunges as far down one branch as possible before backtracking. The critical advantage over BFS is linear memory — DFS only needs to store the nodes on the current path plus their unexpanded siblings at each level.
DFS without cycle detection will loop forever on any cyclic state space. Even with an explored set, DFS is incomplete in infinite-depth spaces. Never state "DFS is complete" without these qualifications. The space advantage of DFS only matters when the solution exists and is reached before memory would fill anyway.
BFS finds the shallowest goal, but not the cheapest when step costs vary. Uniform-Cost Search (Dijkstra's algorithm) expands the node with the lowest path cost g(n) using a priority queue. It is optimal for any non-negative step costs.
Pure BFS exhausts memory on deep problems. Pure DFS wanders forever in infinite spaces. The ideal algorithm would combine BFS's completeness with DFS's memory efficiency. Three refinements move us toward that ideal: Depth-Limited Search caps DFS to prevent infinite loops, Iterative Deepening IDDFS achieves BFS completeness with DFS space, and Bidirectional Search halves the depth by searching from both ends simultaneously.
DLS is DFS with a preset depth limit ℓ. Nodes at depth ℓ are treated as if they have no successors. This prevents infinite descent but introduces a new failure: if the goal is deeper than ℓ, DLS returns cutoff — "goal exists but not within ℓ steps."
IDDFS elegantly resolves the depth-limit dilemma: try every possible depth limit from 0 upward. Run DLS(0), then DLS(1), then DLS(2), … stopping at the first depth that finds a solution. Yes, nodes are re-expanded — but the overhead is remarkably small.
Set depth limit ℓ = 0.
Run DLS(ℓ). If result = solution → return it. If result = failure (no solution anywhere) → return failure.
If result = cutoff (goal may exist deeper) → set ℓ = ℓ + 1 → go to Step 2.
Run two simultaneous searches: forward from the start, backward from the goal. Halt when the two frontiers intersect. Assemble the solution by joining the two half-paths at the meeting node.
This comparison table is among the most heavily tested in AI exams. Memorise the completeness, optimality, and complexity for every row.
| Strategy | Complete? | Optimal? | Time | Space | Frontier Structure |
|---|---|---|---|---|---|
| BFS | ✅ Yes¹ | ✅ Yes² | O(b^(d+1)) | O(b^(d+1)) | FIFO Queue |
| Uniform-Cost (UCS) | ✅ Yes³ | ✅ Yes | O(b^(C*/ε)) | O(b^(C*/ε)) | Priority Queue (g) |
| DFS | ❌ No | ❌ No | O(b^m) | O(b·m) | LIFO Stack |
| Depth-Limited | ❌ No⁴ | ❌ No | O(b^ℓ) | O(b·ℓ) | LIFO Stack + limit |
| IDDFS | ✅ Yes | ✅ Yes² | O(b^d) | O(b·d) | LIFO Stack |
| Bidirectional BFS | ✅ Yes | ✅ Yes² | O(b^(d/2)) | O(b^(d/2)) | Two FIFO Queues |
¹ if b finite; ² if all step costs equal; ³ if all costs ≥ ε>0; ⁴ complete if ℓ≥d
IDDFS is the recommended uninformed algorithm whenever the solution depth is unknown. It achieves BFS completeness and optimality using only DFS-level O(b·d) memory. If asked "which uninformed strategy is best in practice?" → answer IDDFS.
Uniform search strategies are reliable but blind — they treat every direction as equally promising. Knowing that Bucharest lies east of Arad should steer us away from roads heading west. Informed (heuristic) search uses a function h(n) — a cheap estimate of remaining cost — to guide the frontier toward the goal and avoid wasted exploration.
This section covers three informed strategies in order of sophistication: Greedy Best-First Search (fast but suboptimal), A* (optimal and complete), and memory-bounded variants (IDA*, SMA*) that scale A* to large state spaces.
h(n) = estimated cost of the cheapest path from state n to a goal. Two key properties govern its quality:
Admissible: h(n) ≤ h*(n) for all n — never overestimates the true cost. Required for A* optimality.
Consistent (monotone): h(n) ≤ c(n,a,n') + h(n') for every edge. This is the triangle inequality; consistency implies admissibility.
Best heuristics come from relaxed problems — remove one or more constraints. 8-puzzle: allow tiles to move anywhere (not just to the adjacent blank) → Manhattan distance h(n) = Σ(|Δrow| + |Δcol|). A tighter (higher) admissible heuristic always expands fewer nodes.
A* expands the node minimising f(n) = g(n) + h(n): actual cost already incurred g(n) plus admissible estimate of remaining cost h(n). The sum f(n) estimates total path cost through n.
Heuristic: h(n) = SLD to Bucharest (admissible because road ≥ straight-line always).
| Step | Expanded | g(n) | h(n) | f=g+h | Next frontier (by f) |
|---|---|---|---|---|---|
| 1 | Arad | 0 | 366 | 366 | Sibiu(393), Timisoara(447), Zerind(449) |
| 2 | Sibiu | 140 | 253 | 393 | RimnicuVilcea(413), Fagaras(415)… |
| 3 | RimnicuVilcea | 220 | 193 | 413 | Fagaras(415), Pitesti(417)… |
| 4 | Fagaras | 239 | 178 | 417 | Pitesti(417), Bucharest-via-Fagaras(450)… |
| 5 | Pitesti | 317 | 98 | 417 | Bucharest-via-Pitesti(418)!, … |
| 6 | Bucharest | 418 | 0 | 418 ✓ | Optimal path found! |
Optimal: Arad(0)→Sibiu(140)→RimnicuVilcea(220)→Pitesti(317)→Bucharest(418 km). A* rejects Fagaras→Bucharest (total 450 km) because it tracks g(n). Only 6 nodes expanded to find the global optimum.
State: [[7,2,4],[5,_,6],[8,3,1]], Goal: [[1,2,3],[4,5,6],[7,8,_]]
| Tile | Current (r,c) | Goal (r,c) | Misplaced? | Manhattan dist |
|---|---|---|---|---|
| 1 | (2,2) | (0,0) | ✗ | 4 |
| 2 | (0,1) | (0,1) | ✓ In place | 0 |
| 3 | (2,1) | (0,2) | ✗ | 3 |
| 4 | (0,2) | (1,0) | ✗ | 3 |
| 5 | (1,0) | (1,1) | ✗ | 1 |
| 6 | (1,2) | (1,2) | ✓ In place | 0 |
| 7 | (0,0) | (2,0) | ✗ | 2 |
| 8 | (2,0) | (2,1) | ✗ | 1 |
| Totals | h₁ = 6 | h₂ = 14 (dominates!) | ||
Manhattan distance h₂=14 provides a much tighter lower bound than h₁=6. A* with h₂ expands approximately 32× fewer nodes than A* with h₁ at depth 14.
All algorithms so far maintain a complete path from start to goal. But many real problems — factory scheduling, protein folding, microchip layout — only care about the final configuration. Their state spaces are too vast for systematic exploration. Local search keeps only the current state and moves to neighbouring states to improve an objective function, using almost no memory. The trade-off: most landscapes have many local peaks that are not the global optimum.
Set current = initial state.
Compute best_neighbour = highest-valued neighbour of current.
If VALUE(best_neighbour) ≤ VALUE(current) → return current (local maximum). Else set current = best_neighbour → go to Step 2.
Local maxima: Better than all neighbours but not global best — halts prematurely.
Ridges: Sequence of local maxima forming a ridge — diagonal moves needed to traverse.
Plateaus: All neighbours have equal value — random sideways moves needed to escape.
| Iteration | Move | h (attacking pairs) | Status |
|---|---|---|---|
| Start | Random placement | 17 | Initialise |
| 1 | Move col-3 queen: row 4 → row 1 | 12 | ↓ Improved |
| 2 | Move col-6 queen: row 7 → row 3 | 7 | ↓ Improved |
| 3 | Move col-2 queen: row 5 → row 2 | 4 | ↓ Improved |
| 4 | No single move reduces h below 4 | 4 | Local min — STUCK |
| Restart | New random start → hill climb | 0 | Goal found! ✓ |
86% of random starts reach a local min. Random-restart hill climbing succeeds after ≈ 7 restarts on average. Success after k restarts = 1 − 0.86^k → very reliable.
Set current = initial state; temperature T = T₀ (high).
Pick a random neighbour next. Compute ΔE = VALUE(next) − VALUE(current).
If ΔE > 0 → accept. If ΔE ≤ 0 → accept with probability P = e^(ΔE/T).
Cool: T = α·T (e.g. α=0.99). If T ≈ 0 → return current. Else go to Step 2.
Maintain k states simultaneously. Generate all successors of all k states; keep the k best. Unlike k independent hill climbs, beams share information — successful beams attract others. Stochastic beam search selects k survivors probabilistically (∝ VALUE) to avoid all k converging on the same local max.
Initialise: k random individuals (encoded strings). Evaluate fitness f(x).
Select: Pairs of parents proportional to fitness (roulette wheel). Higher fitness = higher reproduction chance.
Crossover: Swap tails at a random cut-point to produce two children. e.g. 11010|001 + 00110|111 → 11010|111 and 00110|001.
Mutate: Flip each bit with small probability p_m ≈ 0.01 — maintains diversity.
Replace & repeat until termination criterion (max generations or sufficient fitness).
| Algorithm | Memory | Escapes Local Optima? | Optimal? | Best Application |
|---|---|---|---|---|
| Hill Climbing | O(1) | ❌ No | ❌ No | Quick; use with random restarts |
| Simulated Annealing | O(1) | ✅ Yes (probabilistic) | ✅ Slow cooling | TSP, VLSI layout, scheduling |
| Local Beam Search | O(k·b) | ✅ Partially | ❌ No | k parallel searches sharing info |
| Genetic Algorithms | O(population) | ✅ Yes (crossover) | ❌ No (practice) | Design optimisation, feature selection |
Standard search treats states as black boxes with no internal structure. Constraint Satisfaction Problems (CSPs) exploit that structure: each state is an assignment of values to variables, and solutions must satisfy a set of constraints. This enables constraint propagation — reasoning that prunes impossible values before search even begins — making exponential problems tractable in practice.
CSPs arise everywhere: Sudoku (variables=cells, domains=1–9, constraints=no row/col/box repeats), map colouring, timetabling, circuit layout, frequency assignment, and crossword puzzles.
A CSP has three elements:
Solution = a complete (all variables assigned) and consistent (no constraint violated) assignment.
Colour 7 Australian regions so no two adjacent regions share a colour, using {Red, Green, Blue}.
| Variable | Domain | Neighbours (≠ constraints with) | Degree (# constraints) |
|---|---|---|---|
| WA | {R,G,B} | NT, SA | 2 |
| NT | {R,G,B} | WA, SA, Q | 3 |
| Q | {R,G,B} | NT, SA, NSW | 3 |
| SA | {R,G,B} | WA, NT, Q, NSW, V, T | 6 — assign FIRST (MRV) |
| NSW | {R,G,B} | Q, SA, V | 3 |
| V | {R,G,B} | SA, NSW | 2 |
| T | {R,G,B} | None (island) | 0 — assign anytime |
Valid solution: WA=Red, NT=Green, Q=Red, SA=Blue, NSW=Green, V=Red, T=Green. SA is assigned first (most constrained — 6 neighbours restrict its choices most).
If all variables assigned → return assignment (success).
Select unassigned variable X by MRV (fewest remaining legal values — "fail first").
Order values in DOMAIN(X) by LCV (least constraining value — rules out fewest neighbour values).
For each value v: if X=v is consistent → assign it. Apply forward checking: remove v from neighbours' domains. If any domain empties → undo, try next v.
Recurse. If success → return. Else remove X=v and try next. If all values fail → return failure (backtrack).
Start with a complete but possibly inconsistent assignment. Repeatedly select a conflicted variable and reassign it to the value minimising the number of violated constraints. Halt when no conflicts remain.
For N-Queens: solves N=1,000,000 in roughly the same number of steps as N=100 — essentially constant in N. This is one of the most striking results in local search for CSPs.
Until now the environment was benign — static or merely stochastic. Games introduce a rational adversary who actively minimises our utility. A move that looks excellent may be catastrophic if the opponent responds optimally. Adversarial search provides the mathematical framework for reasoning under strategic opposition.
Defined by: S₀ (initial state), PLAYER(s) (MAX or MIN), ACTIONS(s), RESULT(s,a), TERMINAL-TEST(s), UTILITY(s,p): +1 win / 0 draw / −1 loss for player p. Zero-sum: what MAX gains, MIN loses. Both play perfectly rational.
If TERMINAL-TEST(s) → return UTILITY(s).
If PLAYER(s) = MAX → return max over a of MINIMAX(RESULT(s,a)).
If PLAYER(s) = MIN → return min over a of MINIMAX(RESULT(s,a)).
α = best value MAX has guaranteed so far (init −∞). Updated at MAX nodes.
β = best value MIN has guaranteed so far (init +∞). Updated at MIN nodes.
Prune at MAX node: if value ≥ β → cut (MIN won't allow this).
Prune at MIN node: if value ≤ α → cut (MAX has better elsewhere).
Traditional engines (Deep Blue, Stockfish) use handcrafted EVAL + alpha-beta + iterative deepening. AlphaZero (2017) replaced EVAL with a deep neural network trained by self-play and replaced alpha-beta with Monte Carlo Tree Search (MCTS). It beat world-champion engines in chess, Go, and Shogi after hours of self-play. Yet the core principle — search guided by value estimates — is unchanged since Shannon 1950.
This section consolidates every algorithm, formula, and comparison from Unit II. Work through all tables and the final challenge quiz before your exam.
| Algorithm | Complete? | Optimal? | Time | Space | Key Idea |
|---|---|---|---|---|---|
| BFS | ✅ Yes¹ | ✅ Yes² | O(b^(d+1)) | O(b^(d+1)) | FIFO; shallowest first |
| Uniform-Cost | ✅ Yes³ | ✅ Yes | O(b^(C*/ε)) | O(b^(C*/ε)) | Priority queue by g; cheapest first |
| DFS | ❌ No | ❌ No | O(b^m) | O(b·m) | LIFO; deep first; low memory |
| Depth-Limited | ❌ No⁴ | ❌ No | O(b^ℓ) | O(b·ℓ) | DFS with cap ℓ |
| IDDFS ★ | ✅ Yes | ✅ Yes² | O(b^d) | O(b·d) | Best uninformed: BFS quality + DFS space |
| Bidirectional | ✅ Yes | ✅ Yes² | O(b^(d/2)) | O(b^(d/2)) | Two frontiers meet in middle |
| Greedy Best-First | ❌ No | ❌ No | O(b^m) | O(b^m) | Priority by h only; fast, suboptimal |
| A* ★ | ✅ Yes | ✅ Yes (adm. h) | O(b^d) | O(b^d) | f=g+h; best informed; complete + optimal |
| IDA* | ✅ Yes | ✅ Yes | O(b^d) | O(b·d) | A* with DFS-level memory |
| Hill Climbing | ❌ No | ❌ No | — | O(1) | Greedy local; stuck at local optima |
| Simulated Annealing | ✅ Yes⁵ | ✅ Yes⁵ | — | O(1) | P=e^(ΔE/T) acceptance; escapes optima |
| Local Beam | ❌ No | ❌ No | — | O(k·b) | k parallel states sharing info |
| Genetic Algorithm | ❌ No | ❌ No | — | O(pop) | Selection + crossover + mutation |
| Backtracking CSP | ✅ Yes | N/A | — | O(n·d) | DFS + constraint check + backtrack |
| Minimax | ✅ Yes | ✅ Yes | O(b^m) | O(b·m) | Max/min alternating; game trees |
| Alpha-Beta ★ | ✅ Yes | ✅ Yes | O(b^(m/2)) best | O(b·m) | Minimax + pruning; same result, fewer nodes |
¹ b finite; ² uniform cost; ³ costs≥ε>0; ⁴ yes if ℓ≥d; ⁵ logarithmic cooling schedule; ★ = recommended for each category
| Formula | Meaning | Used In |
|---|---|---|
f(n) = h(n) | Heuristic only; ignores g(n) | Greedy Best-First |
f(n) = g(n) + h(n) | Actual + estimated remaining cost | A*, IDA* |
h(n) ≤ h*(n) ∀n | Admissibility — never overestimate | A* optimality proof |
h(n) ≤ c(n,a,n') + h(n') | Consistency (triangle inequality) | A* no re-expansion |
P = e^(ΔE/T) | SA acceptance probability for worse state | Simulated Annealing |
V(MAX node) = max_a V(child) | MAX picks highest child | Minimax |
V(MIN node) = min_a V(child) | MIN picks lowest child | Minimax |
O(b^(d/2)) | Alpha-beta best case; doubles searchable depth | Alpha-Beta |
Mistake 1: Calling DFS "complete" — NOT complete in infinite-depth or cyclic spaces.
Mistake 2: Saying BFS is optimal for weighted graphs — only optimal for uniform step costs. Use UCS for varying costs.
Mistake 3: Confusing admissibility and consistency — consistency is stronger; consistent ⟹ admissible, not vice versa.
Mistake 4: Saying alpha-beta finds a better solution than minimax — it finds the same solution faster by pruning irrelevant branches.
Mistake 5: Confusing MRV (which variable next in CSP) with LCV (which value to try next) — different decisions, different heuristics.
Mistake 6: Saying SA is always globally optimal — only with a logarithmically slow cooling schedule (impractically slow). In practice it finds near-optimal solutions.