0x80Lesson 9 of 18

Search: how AI finds its way

Race breadth-first, depth-first, greedy and A* search through a maze, and see why a good guess saves a lot of work.

24 min 7-question quiz 2 code exercises

By the end of this lesson you can

Describe a problem as states, moves and a goal
Explain how breadth-first and depth-first search differ
Explain how A* uses a heuristic to search less and still find the cheapest route

Before machine learning took over the headlines, AI was mostly about search. Your maps app finding a route, a video game character chasing you around walls, a robot vacuum planning its way home, even a puzzle solver for a Rubik’s cube - all of them search.

Search problems have three ingredients:

States - every situation you could be in (each square of a maze).
Moves - how you get from one state to another (step up, down, left or right), sometimes with a cost.
A goal test - how you know you’ve arrived.

The search algorithm keeps a frontier: the places it has discovered but not yet explored. The whole personality of an algorithm comes down to one question: which frontier spot do I explore next?

The same tree explored two ways. Numbers show the order each spot is visited.

Breadth-first search (BFS) explores the oldest spot first, like ripples in a pond. It always finds the route with the fewest steps.
Depth-first search (DFS) explores the newest spot first: it dives down one corridor until it hits a dead end, then backtracks. It uses little memory but can wander and finds a route, not the best one.

bfs_maze.py

1from collections import deque
2
3maze = [
4    "S.#.....",
5    ".##.###.",
6    "....#...",
7    ".##...#G",
8]
9rows, cols = len(maze), len(maze[0])
10start, goal = (0, 0), (3, 7)
11
12queue = deque([start])
13came_from = {start: None}
14explored = 0
15while queue:
16    cell = queue.popleft()          # oldest first: breadth-first
17    explored += 1
18    if cell == goal:
19        break
20    r, c = cell
21    for nr, nc in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
22        if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] != "#" and (nr, nc) not in came_from:
23            came_from[(nr, nc)] = cell
24            queue.append((nr, nc))
25
26path = []
27cell = goal
28while cell is not None:
29    path.append(cell)
30    cell = came_from[cell]
31print("explored", explored, "cells; path has", len(path) - 1, "steps")
32grid = [list(row) for row in maze]
33for r, c in path[1:-1]:
34    grid[r][c] = "*"
35for row in grid:
36    print("".join(row))

Output

explored 22 cells; path has 12 steps
S.#.....
*##.###.
****#***
.##***#G

Costs and clever guesses: A*

Real maps aren’t that simple: a muddy track takes longer than a paved road. Once moves have different costs, the fewest steps isn’t always the cheapest trip.

Uniform-cost search (also called Dijkstra’s algorithm) fixes that by always exploring the spot with the lowest cost so far. It finds the cheapest route, but it spreads out in every direction - including directly away from the goal.

A* (“A-star”) adds a heuristic: an educated guess $h$ of the remaining cost. It explores the spot with the smallest

$f = g + h$

where $g$ is the cost so far. On a grid, a great guess is the Manhattan distance - how many blocks away the goal is, ignoring walls. As long as the guess never overestimates, A* still finds the cheapest route, but it leans toward the goal and wastes far less effort. Greedy best-first search uses only $h$ : very fast, but easily fooled into wading through mud.

Try it

The great maze race

Pick an algorithm and watch it explore - darker cells were explored earlier. Mud (the brown dots) costs 5 to step into instead of 1. Run all four to fill the scoreboard: which one does the least work, which one finds the cheapest route, and which one gets tricked?

Explores in rings: every cell 1 step away, then 2, then 3… Finds the fewest steps, ignores mud.

wallmud (costs 5 to enter)explored (darker = earlier)route found

explored 0 cells

Scoreboard - run each algorithm to reveal its bars

Cells explored (effort) - lower is better

Breadth-first?
Depth-first?
Greedy best-first?
A*?

Route cost (quality) - lower is better

Breadth-first?
Depth-first?
Greedy best-first?
A*?

a_star.py

1import heapq
2
3maze = [
4    "..........~~.....",
5    "..........~~.....",
6    "S.........~~....G",
7    "..........~~.....",
8    ".................",
9]
10rows, cols = len(maze), len(maze[0])
11start, goal = (2, 0), (2, 16)
12
13def cost_to_enter(cell):
14    return 5 if maze[cell[0]][cell[1]] == "~" else 1
15
16def guess(cell):                    # Manhattan distance: never overestimates
17    return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])
18
19def search(use_guess):
20    frontier = [(0, 0, 0, start)]   # (priority, guess, cost so far, cell)
21    best = {start: 0}
22    explored = 0
23    while frontier:
24        _, _, cost, cell = heapq.heappop(frontier)
25        if cost > best[cell]:
26            continue                # stale entry: a cheaper route was found
27        explored += 1
28        if cell == goal:
29            return cost, explored
30        r, c = cell
31        for nxt in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
32            if 0 <= nxt[0] < rows and 0 <= nxt[1] < cols and maze[nxt[0]][nxt[1]] != "#":
33                new_cost = cost + cost_to_enter(nxt)
34                if new_cost < best.get(nxt, float("inf")):
35                    best[nxt] = new_cost
36                    priority = new_cost + (guess(nxt) if use_guess else 0)
37                    heapq.heappush(frontier, (priority, guess(nxt), new_cost, nxt))
38
39print("uniform cost: cost %d, explored %d" % search(False))
40print("A*:           cost %d, explored %d" % search(True))

Output

uniform cost: cost 20, explored 78
A*:           cost 20, explored 42

Same cheapest route (around the bottom of the mud, cost 20), but A* explored about half as many cells. On a real road map with millions of junctions, that difference is the gap between instant and unusable - which is why A* and its descendants power game AI and route planners.

Try it

Which search would you use?

Sort each situation by the algorithm that fits best.

0 of 6 sortedScore 0/0

“Fewest moves to solve a sliding-tile puzzle where every move counts the same”
“A sat-nav finding the fastest drive across a country”
“Generating a random maze by tunnelling as far as possible before backtracking”
“A strategy-game unit walking around forests (slow) and roads (fast) to reach the enemy base”
“Finding everyone within two friendships of you on a social network”
“Checking whether a maze has any way out at all, using as little memory as possible”

Key takeaways

Search problems = states, moves (with costs) and a goal test; algorithms differ in which frontier spot they explore next.
BFS (oldest first) finds the fewest steps; DFS (newest first) dives deep and uses little memory but finds a route, not the best.
Uniform-cost search finds the cheapest route when moves cost different amounts.
A* explores by $f = g + h$ : with a heuristic that never overestimates, it finds the cheapest route while exploring far less.

Lesson quiz

7 questions · pass with 5 correct · up to 50 XP

Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.

Practice: write Python

Write Python in the editor and run it against sample inputs. Python runs locally in your browser using a WebAssembly runtime.

Exercise 1

Solve a maze with BFS

+25 XP

The input is a maze, one row per line, until the end of input: S is the start, G the goal, # a wall and . open floor. You can move up, down, left or right.

Print steps: N with the fewest steps from S to G, or no path if G can’t be reached. Then print reachable: K - how many cells (including S) can be reached from S.

The lesson maze
Walled off
A straight corridor
A detour

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Exercise 2

The cheapest route through mud

+25 XP

The input is a maze like before, but ~ is mud: stepping into a mud cell costs 5, stepping into any other open cell (including G) costs 1.

Print cheapest cost: C - the lowest total cost from S to G (the goal is always reachable) - and manhattan guess: H, the Manhattan distance from S to G that A* would use as its first guess.

Go around the mud
A wide mud patch
Mud either way
Mud is the shortcut

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Questions about this lesson

Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.

Loading posts…