Search and Optimization

Problems as search

Your phone finds a route across a city in a fraction of a second. A chess engine picks a move better than any human alive. A warehouse robot threads between shelves. Under the hood, all three are doing the same thing: exploring a space of possibilities in a clever order.

What is a search problem?

Before any learning happened in AI, there was search. The idea is to describe a problem so precisely that a computer can explore it without understanding it. The standard formulation has five parts:

• States: every configuration the world can be in, such as a board position or a location on a map.
• An initial state where you start.
• Actions available in each state, and a transition model saying which state each action leads to.
• A goal test that recognises success.
• Action costs, so that some solutions are cheaper than others.

A solution is a sequence of actions from the start to a goal, and an optimal solution is one with the lowest total cost.

How big do these spaces get?

The 8-puzzle has 181,440 reachable states, small enough to search exhaustively in milliseconds. The 15-puzzle has about 10¹³. Rubik's cube has about 4.3 x 10¹⁹ positions, and it took decades of work and a large amount of donated computer time to prove that every one of them can be solved in 20 moves or fewer. Growth like this is why the order in which you explore matters so much: if each state has b successors and the goal is d steps away, a blind search can face b^d paths.

Why does it matter?

Search is how AI systems act rather than just predict. Route planners, game engines, logistics optimisers, compilers, chip-layout tools and, increasingly, language-model agents that plan several steps ahead all reduce to exploring a space of states. Learning often supplies the judgement, such as a value estimate or a heuristic, and search supplies the lookahead.

Key takeaways

• A search problem is states, a start, actions with a transition model, a goal test and action costs.
• State spaces grow exponentially with depth, so the order of exploration decides what is feasible.
• Modern systems pair learned judgement with search: the network estimates, the search looks ahead.

Uninformed search

Uninformed search knows nothing about where the goal is. All it can do is decide which unexplored state to look at next. That single choice separates the classic algorithms.

How does it work?

Every graph search keeps a frontier: states it has discovered but not yet expanded. It repeatedly takes one state from the frontier, checks whether it is the goal, and adds its unvisited neighbours. A closed set remembers expanded states so none is explored twice. The only difference between the algorithms is which state leaves the frontier first:

On the mud field, breadth-first search charges straight through the mud because it counts steps, not cost, and returns a path more than twice as expensive as it needs to be. Uniform-cost search expands a similar number of cells but in cost order, so it walks around the mud. Depth-first search wanders: it finds a path, but often an absurd one. None of them has any sense of direction; that is what the next section adds.

Guarantees

Breadth-first search is complete (it finds a solution if one exists) and optimal when every action costs the same. Uniform-cost search is complete and optimal for any positive costs. Depth-first search is neither on infinite spaces, but it only stores the current path and its siblings, which is why variants such as iterative deepening, which runs depth-first search with a growing depth limit, remain useful when memory is tight.

Why does it matter?

The frontier-and-expand loop is the skeleton of nearly every search algorithm in AI, including the ones inside game engines and planners. Change the rule for picking from the frontier and you change the algorithm. The Pathfinding Visualizer lab lets you race these on bigger mazes.

Key takeaways

• All graph searches expand states from a frontier; the order of removal defines the algorithm.
• BFS minimises the number of steps, UCS minimises total cost, DFS guarantees neither.
• Uninformed searches spread out in every direction because they have no idea where the goal is.

Heuristics and A*

A heuristic is an educated guess of how far a state is from the goal. Add a good guess to uniform-cost search and it stops exploring in circles and heads for the goal, while still guaranteeing the best answer.

What is A*?

A*, published in 1968, orders the frontier by

g(n) is the cost already paid to reach n; h(n) is the estimated cost still to go.

On a grid with four-way moves, a natural heuristic is Manhattan distance: the number of horizontal plus vertical steps to the goal, ignoring walls. If h is always zero, A* is exactly uniform-cost search. The better h approximates the true remaining cost, the fewer states A* expands.

When is A* guaranteed to be optimal?

A heuristic is admissible if it never overestimates the true cost to the goal. Manhattan distance is admissible here: walls can only make the real route longer, and every step costs at least 1. With an admissible heuristic, A* never returns a suboptimal path, because a cheaper path would always have a lower f and be expanded first.

A heuristic is consistent if for every step from n to n' with cost c, h(n) ≤ c + h(n'): the estimate never drops by more than the step costs. Consistency implies admissibility, and it means that the first time A* expands a state it has already found the cheapest way to it, so no state needs reopening. Most heuristics built by relaxing the problem, such as ignoring walls, are consistent.

Trading optimality for speed

In practice you often want a good path fast rather than the perfect path slowly. Weighted A* multiplies the heuristic by a weight w ≥ 1, making the search greedier. The payoff comes with a guarantee: if h is admissible, the path found costs at most w times the optimum.

On the walls map, A* with w = 1 expands well under half the cells uniform-cost search does and still finds a cost-23 path. At w = 2 it expands fewer again but returns a path costing 27: within the promised factor of 2, and not optimal. Now switch to the Mud field map and push w to 5: the search becomes nearly greedy and ploughs through the mud, because it trusts the straight-line estimate more than the real costs it is paying.

Key takeaways

• A* expands states in order of g + h: cost so far plus estimated cost to go.
• Admissible heuristics never overestimate and guarantee optimal paths; consistent ones also avoid reopening states.
• Weighted A* inflates h by w for speed and returns a path at most w times the optimal cost.

Game search: minimax and alpha-beta

In a game, some of the moves in your search tree are chosen by someone trying to beat you. Search has to account for the opponent's best reply, and the reply to that, all the way down.

What is minimax?

Label the two players MAX and MIN. At the end of the game, score the position: win, lose or draw. Working backwards up the tree, a position where MAX is to move is worth the maximum of its children; a position where MIN is to move is worth the minimum. The value at the root is what MAX can guarantee against a perfect opponent, and the best move is the child that achieves it.

Real games are far too deep to search to the end, so engines stop at a depth limit and score positions with an evaluation function, a heuristic judgement of who is ahead. Tic-tac-toe is small enough to search completely, so the demo below plays perfectly.

How does alpha-beta pruning help?

Alpha-beta keeps two numbers during the search: alpha, the best score MAX is already guaranteed elsewhere, and beta, the best MIN is guaranteed. The moment a branch is proven worse than an option already available higher up, the rest of it is skipped, because a rational player would never enter it. The answer is identical to minimax. The savings depend on move order: with perfect ordering alpha-beta examines about b^d/2 nodes instead of b^d, which in the same time means searching about twice as deep.

A full minimax search from the empty board visits 549,946 positions; alpha-beta, even with the naive move order used here (squares in reading order), gets the same answer after about 21,000. Try to beat it: you cannot, because tic-tac-toe is a draw under perfect play. The best you can do is make it prove that again every turn.

From tic-tac-toe to chess and Go

Chess has a branching factor of about 35 and games of about 80 plies; Go has about 250 legal moves per position and games of about 150, numbers the AlphaGo paper uses to explain why exhaustive search is hopeless. In 1997, Deep Blue beat world champion Garry Kasparov with alpha-beta search on custom hardware and a hand-tuned evaluation function. Go resisted that approach for another two decades, until the combination of learned evaluation and a different kind of search that we meet at the end of this lesson.

Key takeaways

• Minimax assumes the opponent plays their best reply and backs values up the game tree.
• Alpha-beta skips branches that cannot affect the decision and returns exactly the minimax value.
• With good move ordering, alpha-beta searches about twice as deep as minimax in the same time.

Local search and annealing

Sometimes you do not need a path at all, only a good final state: a timetable with no clashes, a chip layout with short wires, a set of model hyperparameters. Local search forgets the path and just tries to improve the current solution.

What is hill climbing?

Start somewhere. Look at the neighbouring solutions. Move to the best one if it is better; otherwise stop. It uses almost no memory and often works well, but it has an obvious flaw: it stops at the first peak it reaches, which may be a minor local maximum far below the best solution. Plateaus and ridges cause similar trouble.

How does simulated annealing escape?

Simulated annealing borrows an idea from metallurgy: metal cooled slowly settles into a low-energy crystal, cooled quickly it freezes in defects. The algorithm proposes a random nearby move. Uphill moves are always accepted. Downhill moves of size Δ are accepted with probability

T is the temperature. When T is high almost anything is accepted; as T approaches zero only improvements are.

The temperature falls over time, here geometrically: T is multiplied by a cooling factor slightly below 1 at every step. Early on the search roams across valleys; late on it behaves like hill climbing and settles on a peak. Cool slowly enough and, in theory, it finds the global optimum with probability approaching one; in practice the schedule is a tuning knob.

From most starts hill climbing stops on whichever peak is nearest; over many random starts it reaches the global peak only about one time in five. Annealing with the default schedule reaches it a clear majority of the time. Cool fast and its success rate falls back towards hill climbing, because the temperature drops before it has had a chance to cross the valleys.

Genetic algorithms

Genetic algorithms, developed by John Holland, keep a whole population of solutions instead of one. Each generation, fitter solutions are more likely to be selected as parents; pairs are combined by crossover, and random mutation keeps diversity. Crossover is the distinctive part: it can join a good first half from one parent to a good second half from another. Genetic and other evolutionary methods are used where solutions are easy to score but hard to differentiate, such as antenna shapes, schedules and neural architecture search.

Key takeaways

• Local search improves a single current solution and ignores the path; hill climbing stops at local optima.
• Simulated annealing accepts downhill moves with probability e^(Δ/T) and cools T so it can escape early and settle late.
• Genetic algorithms search with a population, using selection, crossover and mutation.

The travelling salesman

Visit every city once and return home by the shortest route. It sounds like a puzzle for a rainy afternoon. It is one of the most studied hard problems in computer science, and it sits underneath delivery routing, drilling circuit boards and sequencing genomes.

Why is it hard?

With n cities there are (n - 1)!/2 distinct round trips: fix the starting city, order the rest, and halve because each tour can be driven in either direction. Factorials grow faster than any exponential. The problem is NP-hard, meaning no known algorithm solves every instance in polynomial time, and finding one would settle the most famous open question in computer science.

Twenty cities already take about two years of brute force. The Held-Karp dynamic programme brings 20 cities down to under a second by reusing the best path through each subset of cities, but it is still exponential: 60 cities would take it over 100,000 years, and by 80 cities it would outlast the age of the universe.

How is it solved in practice?

Two ways. Exact solvers such as Concorde use branch and bound with linear-programming relaxations to prove a tour optimal without enumerating tours; they have solved an instance with 85,900 cities, a triumph of pruning rather than speed. Everyday systems use heuristics instead: build a tour greedily, then improve it with local search such as 2-opt, which reverses a segment whenever that shortens the tour, or the stronger Lin-Kernighan moves. These typically land within a few percent of optimal in a fraction of a second, which is what route-planning apps actually need.

Key takeaways

• n cities have (n - 1)!/2 tours, so brute force fails beyond about 15 cities.
• The best exact worst-case algorithm, Held-Karp, is still exponential; exact solvers win by pruning, not enumeration.
• Practical systems use local search such as 2-opt for near-optimal tours in milliseconds.

Search in modern AI

Deep learning did not replace search. The most striking results of the past decade come from combining the two: a network provides intuition, and search checks that intuition by looking ahead.

How did AlphaGo search?

AlphaGo used Monte Carlo tree search (MCTS). Instead of expanding every move to a fixed depth, MCTS grows the tree unevenly, spending its budget on promising lines. Each simulation walks down the tree, adds a node, evaluates it and sends the result back up. AlphaGo used a policy network to suggest which moves were worth trying and a value network (mixed with fast rollouts) to judge positions, and beat the European champion Fan Hui 5-0 before defeating Lee Sedol 4-1 in 2016. AlphaZero then learned chess, shogi and Go from self-play alone with the same recipe.

Beam search in language models

A language model generates text one token at a time, and choosing the most likely token at each step (greedy decoding) does not give the most likely sentence. Beam search keeps the k best partial sentences at each step instead of one. It is standard in machine translation and speech recognition. Open-ended chat models usually sample instead, because the single most likely text tends to be bland and repetitive; the Next-Token Sampling Lab explores that side.

Greedy decoding grabs "A" because it is the likeliest first word, then is stuck with a sentence of probability 0.100. A beam of two keeps "The" alive long enough to discover that "The sun rose" is almost three times as likely.

Planning in agents and reasoning

LLM agents face search problems too: which tool to call, in what order, and when to back up. Methods such as Tree of Thoughts make this explicit, running breadth-first or depth-first search over partial solutions with the model proposing steps and scoring them as a heuristic; on the Game of 24 puzzle it lifted GPT-4's success rate from 4% with chain-of-thought prompting to 74%. The same pattern of generate, evaluate and keep the best runs through modern reasoning systems and agent frameworks. And when the value of states must be learned from reward rather than given, search meets reinforcement learning.

Key takeaways

• Monte Carlo tree search focuses simulations on promising lines; AlphaGo guided it with policy and value networks.
• Beam search keeps the k best partial sequences and finds likelier outputs than greedy decoding.
• LLM agents and reasoning methods reuse classic search: propose steps, evaluate them, expand the best.

Check your understanding

Six scenarios from robots, games and routing. Pick the answer you would defend to a colleague.

A delivery robot moves on a warehouse grid. Aisles cost 1 per cell but crossing the loading bay costs 4 per cell because of traffic. You want the cheapest route. Which search is guaranteed to find it?

References

Sources for this lesson. Russell and Norvig is the place to go deeper on everything here; the 1968 A* paper is short and still rewarding.

References

1. [1]

   Artificial Intelligence: A Modern Approach (4th edition)(opens in a new tab)

   Russell, Norvig, 2020

   The standard AI textbook. Chapters 3 to 6 cover problem solving by search, local search, adversarial search and constraint satisfaction.

2. [2]

   The Diameter of the Rubik’s Cube Group Is Twenty(opens in a new tab)

   Rokicki, Kociemba, Davidson, Dethridge, 2014

   Every one of the 43 quintillion positions of Rubik’s cube can be solved in 20 moves or fewer.

3. [3]

   A note on two problems in connexion with graphs(opens in a new tab)

   Dijkstra, 1959

   The shortest-path algorithm that uniform-cost search is a version of.

4. [4]

   A Formal Basis for the Heuristic Determination of Minimum Cost Paths(opens in a new tab)

   Hart, Nilsson, Raphael, 1968

   Introduced A* and proved it finds an optimal path when the heuristic never overestimates.

5. [5]

   Heuristic search viewed as path finding in a graph(opens in a new tab)

   Pohl, 1970

   Weighted heuristic search: trading solution quality for speed by scaling the heuristic.

6. [6]

   An analysis of alpha-beta pruning(opens in a new tab)

   Knuth, Moore, 1975

   Showed that with perfect move ordering alpha-beta examines roughly the square root of the nodes minimax does.

7. [7]

   Mastering the game of Go with deep neural networks and tree search(opens in a new tab)

   Silver et al., 2016

   AlphaGo: Monte Carlo tree search guided by policy and value networks. Beat European champion Fan Hui 5-0.

8. [8]

   Deep Blue(opens in a new tab)

   Campbell, Hoane, Hsu, 2002

   The architecture of the chess machine that beat Garry Kasparov in 1997: massively parallel alpha-beta search on custom chips.

9. [9]

   Optimization by Simulated Annealing(opens in a new tab)

   Kirkpatrick, Gelatt, Vecchi, 1983

   Borrowed the physics of slowly cooling metals to escape local optima, applied to chip layout and the travelling salesman problem.

10. [10]

    Adaptation in Natural and Artificial Systems

    Holland, 1975

    The book that founded genetic algorithms.

11. [11]

    A Dynamic Programming Approach to Sequencing Problems(opens in a new tab)

    Held, Karp, 1962

    Exact TSP in about n squared times 2 to the n steps, still the best known worst-case bound for exact solution.

12. [12]

    The Traveling Salesman Problem: A Computational Study

    Applegate, Bixby, Chvatal, Cook, 2006

    Describes the Concorde solver and the optimal solution of an 85,900-city instance.

13. [13]

    A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play(opens in a new tab)

    Silver et al., 2018

14. [14]

    Tree of Thoughts: Deliberate Problem Solving with Large Language Models(opens in a new tab)

    Yao, Yu, Zhao, Shafran, Griffiths, Cao, Narasimhan, 2023

    Runs breadth-first and depth-first search over intermediate reasoning steps, with the language model proposing and evaluating them.