Climbing Keokradong in thick fog
You are on a hill in Bandarban, in fog so thick you can only feel the slope under your feet. Goal: the highest point.
Rule: always take the step that goes up the most. Stop when every step goes down.
No map, no memory of where you have been, one position at a time. That is local search.
Squid Game's glass bridge is the opposite problem: one wrong step and you are out, so there is no "try and step back". Local search lives on landscapes where you can always take another step.
When the path doesn't matter
In 8-queens the answer is the final board, not the moves that led to it. Same for timetables, chip layouts and delivery routes. So:
- Complete-state formulation: every state is a full candidate solution (all 8 queens on the board).
- Objective function: a number to maximise (or a cost such as h = attacking pairs to minimise).
- Neighbours: states one small change away (move one queen in its column).
- Keep one current state: O(1) memory, works on spaces far too big to search systematically.
Landscape vocabulary
Global maximum: the best state anywhere.
Local maximum: better than all its neighbours, but not the best.
Plateau: a flat area; a shoulder is a plateau that still leads up.
Ridge: a sequence of local maxima that is easy to walk along in one direction but every single move goes down.
Live lab: a climber that only sees its feet
Hill climbing and its variants
function HILL-CLIMBING(problem) current β problem.INITIAL loop neighbour β highest-valued successor of current if VALUE(neighbour) β€ VALUE(current): return current # a peak (maybe local) current β neighbour
Steepest ascent, adapted from Russell & Norvig. Greedy: it never looks more than one step ahead.
| Variant | Change |
|---|---|
| Sideways moves | allow equal-valued moves (with a limit) to cross shoulders |
| Stochastic | pick a random uphill move, more likely the steeper ones |
| First-choice | try random neighbours, take the first that is better: good when there are thousands of neighbours |
| Random restart | if stuck, start again from a random state; keep the best result |
Random-restart hill climbing is complete with probability approaching 1: eventually a start lands in the global hill's basin.
Worked example: h for an 8-queens board
Given
An 8-queens board in the complete-state formulation, one queen per column. Columns 1β8 from left to right, rows 1β8 from bottom to top. The queens are on rows (5, 6, 7, 4, 5, 6, 7, 6).
Find
h (number of attacking pairs, counted once) and the best move for steepest-ascent hill climbing.
Method: Russell & Norvig's 8-queens hill-climbing example
Solution
Predict the answer first. Then reveal one step at a time.
Live lab: 8-queens, one move at a time
The textbook board: h = 17. Every number is the h you would get by moving that columnβs queen there.
Your turn Β· 1: how many restarts?
Steepest-ascent hill climbing solves a random 8-queens board with probability p = 0.14, taking 4 steps when it succeeds and 3 when it gets stuck.
(a) With random restarts, how many runs do you expect? (b) How many steps in total? (c) Redo (b) with sideways moves: p = 0.94, 21 steps when it succeeds, 64 when it fails.
Work it out first.
Press Solve when the class has an answer.
Simulated annealing: sometimes step down
function SIMULATED-ANNEALING(problem, schedule) current β problem.INITIAL for t = 1, 2, 3, β¦ T β schedule(t) if T = 0: return current next β a random successor of current ΞE β VALUE(next) β VALUE(current) if ΞE > 0: current β next else current β next with probability eΞE/T
The idea
Early on (T high) accept many bad moves: explore, jump out of small hills. Later (T low) accept almost none: settle on a peak.
If T is lowered slowly enough, SA finds the global optimum with probability approaching 1.
Named after annealing in metallurgy: heat a metal, then cool it slowly so its atoms settle into a low-energy crystal. A village kamar (blacksmith) quenching a da does the opposite: fast cooling makes it hard but brittle.
Worked example: how likely is a step down?
Given
Simulated annealing, acceptance probability eΞE/T for a worse move (ΞE < 0).
Find
The acceptance probability for ΞE = β2 and ΞE = β10 at T = 10, 2 and 0.5. What do the numbers say?
Method: Metropolis acceptance rule, as in Russell & Norvig's simulated annealing
Solution
Predict the answer first. Then reveal one step at a time.
Live lab: annealing on the landscape
Critical thinking Β· tuning the temperature
A classmate runs SA with Tβ = 0.1 and Ξ± = 0.5 (T halves every step) on the landscape and says: "Annealing is no better than hill climbing, it got stuck on the first hill."
What happened? What does SA become when T is very large, and when T is very small? How would you choose Tβ?
Work it out first.
Press Solve when the class has an answer.
Local beam search: k climbers that talk
- Start with k random states.
- Each step: generate all successors of all k; if one is a goal, stop.
- Otherwise keep the best k from the whole pool and repeat.
Unlike k independent restarts, information flows: if one state finds a great hill, its successors take over the beam and the climbers on poor hills are dropped.
The same feature is the weakness: all k can crowd onto one hill and lose diversity. Stochastic beam search picks the k successors at random, weighted by value. Add "parents combine" and you get genetic algorithms (Week 5).
Try it
In the landscape lab, choose Local beam (k = 4) and press New random start a few times. Four climbers start; within a few steps the beam usually sits on one hill.
| Memory | Shares information? | |
|---|---|---|
| Hill climbing | 1 state | β |
| k random restarts | 1 at a time | No |
| Local beam (k) | k states | Yes |
Real world: routes, timetables and chips
Pop quiz
Question 1 / 5
Local search keeps in memoryβ¦
Three things to remember
Local search keeps one complete state and moves to neighbours: O(1) memory, no path, no guarantee. Problems: local maxima, plateaus, ridges.
Hill climbing takes the best neighbour until none is better. Fixes: sideways moves, random restarts (8-queens: 14 % β 94 % β β 100 %).
Simulated annealing accepts bad moves with eΞE/T, cooling T slowly. Local beam keeps the best k of all successors.
Before next class: Assignment 1 is due Week 4, Class 1. Next week: informed search. Heuristics, greedy best-first and A*.
Class Test 1
Covers
Problem formulation Β· BFS and DFS Β· UCS Β· DLS and IDS (traces and the comparison table) Β· local search basics (hill climbing, annealing acceptance, beam search).
Rules
Closed book, written, answer all questions on the paper. Calculators allowed, phones away. Write your tie-breaking and goal-test convention at the top of every trace.
Questions are handed out on paper. The practice set is on the course page under Assessments.