NOA Labs

Search & Planning

State-space search, A* pathfinding, and minimax/game trees for adversarial games, with worked examples.

Search as a problem-solving strategy

Long before machine learning, one of AI's oldest and still most reliable tools is search: systematically exploring possible sequences of actions to find one that reaches a goal. A huge range of problems reduce to this shape — solving a puzzle, planning a route, choosing a move in a game — even though none of them require learning from data at all. This is the part of "classical AI" (see this track's introduction and history pages) that never went away; it runs quietly inside route planners, logistics software, robotics, and game engines today.

A state-space search problem is defined by:

  • An initial state — where you start.
  • A set of actions, each of which transforms one state into another.
  • A goal test — a way to check whether a given state counts as "done."
  • Usually, a cost for each action, so some solutions can be better than others.

Take a simple sliding-puzzle example: getting from a starting arrangement of tiles to a target arrangement, one legal slide at a time. Each arrangement of tiles is a state; each legal slide is an action; the goal test is "does this arrangement match the target." Solving the puzzle means finding some sequence of actions from the initial state to a goal state — and, ideally, a short or cheap one, not just any sequence.

Plaintext
Initial state:      Goal state:
1 2 3                1 2 3
4 _ 6                4 5 6
7 5 8                7 8 _

Action: slide the tile below the blank ("5") up into the blank
Result: one step closer to the goal state

The search space is the (often enormous) set of all reachable states, connected by actions — visualized as a graph or tree where nodes are states and edges are actions. Solving the problem means finding a path through that graph from the start node to a goal node.

Uninformed (blind) search explores the state space with no knowledge of which direction is actually promising. Breadth-first search expands every state at the current depth before going deeper (guaranteed to find the shortest path, but can explore huge numbers of irrelevant states). Depth-first search dives down one path before backtracking (uses less memory, but can waste time on a bad path with no way to know it's bad).

Informed (heuristic) search uses a heuristic function — an estimate of "how close is this state to the goal" — to guide exploration toward promising states first, instead of blindly expanding everything. This is the difference between wandering a maze in the dark and having a rough sense of which turns lead toward the exit.

A* (pronounced "A-star") is the best-known informed search algorithm, and it's still the standard choice behind many real pathfinding systems (video game NPC movement, robotics motion planning, some routing engines). For each candidate state n, A* tracks:

  • g(n) — the actual cost to reach n from the start (known exactly, since it's the path already taken).
  • h(n) — a heuristic estimate of the remaining cost from n to the goal (a guess, not a known value).
  • f(n) = g(n) + h(n) — the estimated total cost of a path through n.

A* always expands the state with the lowest f(n) next, from a priority queue of candidates. Provided the heuristic never overestimates the true remaining cost (called being "admissible"), A* is guaranteed to find the optimal (cheapest) path — not just any path.

Worked example: finding a path on a small grid

Plaintext
S . . #
. # . .
. # . G

S is the start, G is the goal, # is a wall, . is open ground, and each step (up/down/left/right) costs 1. A common heuristic for a grid like this is Manhattan distance — |x1 - x2| + |y1 - y2| — the minimum possible number of steps ignoring walls, which never overestimates the true cost since walls can only make the real path longer, never shorter.

Python
def manhattan_distance(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

# From (0, 1) -- one step right of S -- to G at (2, 3):
manhattan_distance((0, 1), (2, 3))  # -> 4

A* expands states roughly in order of "how promising the total estimated path looks," so it explores far fewer irrelevant states than blind search would on any grid of meaningful size — the search fans out toward the goal instead of spreading evenly in every direction.

Minimax and game trees

Search also drives classical game-playing AI, but with a twist: in a two-player adversarial game (tic-tac-toe, chess, checkers), the opponent is also choosing moves — and choosing them to work against you. Minimax handles this by assuming your opponent always plays optimally against you, then picks the move that's best for you given that assumption.

A game tree represents every possible sequence of moves as a tree: the root is the current board, each node's children are the board states one move later, and leaves are game-ending positions scored from one player's perspective (say, +1 for a win, 0 for a draw, -1 for a loss).

Plaintext
                Current board (your move, "MAX" player)
                /              \
        Move A                  Move B
        (opponent's move,       (opponent's move,
         "MIN" player)           "MIN" player)
        /        \                /        \
   +1 (win)   -1 (loss)      0 (draw)    0 (draw)

Minimax evaluates the tree from the leaves up: at a "MIN" (opponent) node, it assumes the opponent picks whichever child is worst for you; at a "MAX" (your) node, it picks whichever child is best for you, given the opponent will respond optimally below it. In the tree above: under Move A, the opponent (MIN) would pick the -1 leaf rather than the +1 one, so Move A is effectively worth -1 to you. Under Move B, both children are 0, so Move B is worth 0. Minimax therefore picks Move B — not because it leads to a win, but because it's the best outcome you can guarantee against an opponent playing to defeat you.

Real games have far too many positions to fully expand this tree (chess has more legal positions than atoms in the observable universe, by most estimates), so practical implementations cut the tree off at a fixed depth and use a heuristic evaluation function to score non-terminal positions, and use alpha-beta pruning to skip entire branches that can be proven irrelevant — if you've already found a move guaranteeing at least a certain score, and a branch currently being explored can be proven to do worse than that no matter how it plays out, there's no need to finish exploring it.

Where this still matters

Search and planning didn't get replaced by machine learning — they got combined with it. AlphaGo (see this track's history page) paired deep neural networks with tree search rather than using either alone; modern LLM-based agents that plan multi-step tool use (covered in this site's LangChain tutorials) are, at a conceptual level, doing a much fuzzier version of the same "explore possible next actions, prefer the ones that look closer to the goal" idea A* formalizes precisely. Route planners, warehouse robots, and puzzle solvers still run exactly the classical algorithms described here, largely unmodified, because the problems they solve have well-defined states, actions, and goals — exactly the shape search-based algorithms are built for.

Common mistakes

  • Using a heuristic that can overestimate the true remaining cost with A* — this breaks the optimality guarantee, and the algorithm can return a path that isn't actually the cheapest one.
  • Assuming minimax requires the opponent to actually play "the worst move for me" out of malice — it assumes the opponent plays optimally for themselves, which happens to be the worst case for you, not spite.
  • Trying to fully expand a game tree for any non-trivial game — the number of positions grows so explosively that even fast modern hardware needs depth cutoffs, heuristic evaluation, and pruning to make real games tractable at all.