Search & Problem Solving

A surprising number of classic AI problems reduce to the same shape: you have a starting situation, a set of moves you're allowed to make, and a goal — and solving the problem means searching through the possibilities to find a path from start to goal.

State spaces

Picture a maze. Each position in the maze is a state. From any state, a small number of moves (up, down, left, right) lead to other states. The full set of every state reachable this way is the state space, and solving the maze means finding a sequence of moves — a path through that space — from the start state to the goal state. This same shape describes far more than mazes: a sliding tile puzzle, a route-planning app finding a route between two addresses, and a chess engine considering possible move sequences are all searching a state space, just a much larger and more complex one.

Breadth-first search: finding the shortest path

One straightforward way to search a state space is breadth-first search: explore all states one step away from the start, then all states two steps away, and so on, until the goal turns up. Because it explores in order of distance from the start, the first path it finds to the goal is guaranteed to be a shortest one:

Python bfs.py

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

def bfs(start, goal):
    visited = {start}
    queue = deque([[start]])
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(path + [neighbor])
    return None

print(bfs("A", "E"))

Output

['A', 'B', 'D', 'E']

The search explores every neighbor of A first (B and C), then every unvisited neighbor of those, and so on outward — which is exactly why the first path it finds to E is guaranteed to be the shortest one, without ever needing to check every possible path.

Why brute-force search doesn't scale

Breadth-first search works well when the state space is small. The problem is that most interesting state spaces are enormous: a Rubik's Cube has over 43 quintillion possible states, and a chess position has, on average, roughly 35 legal moves available, compounding with every additional move considered. Exploring every possibility exhaustively — a combinatorial explosion — becomes computationally impossible almost immediately as the space grows.

Heuristics: searching smarter, not exhaustively

The practical fix is a heuristic: a rule of thumb that estimates how promising a state is, so the search can prioritize exploring the most promising branches first instead of blindly exploring everything. A well-known algorithm called A* (pronounced "A-star") combines this idea with breadth-first search's shortest-path guarantee, and is the basis of most real-world pathfinding, including the route-planning behind mapping apps.

Why chess and Go needed a different approach: a full game of chess has more possible move sequences than there are atoms in the observable universe — no heuristic search, however clever, can explore that space directly within a reasonable time. This is exactly the gap that machine learning fills: instead of exhaustively searching, a system like a modern chess or Go engine learns to evaluate positions from experience, then searches only the small, promising slice of the space that evaluation points toward. That's the bridge into the next lesson.

PreviousA Brief History of AI NextMachine Learning Basics