Heuristics & Search in AI

Intelligence as search

Long before neural networks dominated AI, the field's founding insight was simpler: many problems that look like "intelligence" — playing chess, planning a route, proving a theorem, solving a puzzle — can be reframed as searching through a space of possible states to find one that satisfies a goal. This is the state space model: a starting state, a set of actions that transform one state into another, and a goal test.

Chess becomes a search through board positions. Route planning becomes a search through map locations. Even logical deduction becomes a search through which rules to apply next. Once a problem is expressed this way, generic search algorithms can solve it — the hard part shifts from "how do I solve this specific problem" to "how do I search this space efficiently."

Blind search and why it fails to scale

The simplest search strategies — breadth-first search (explore all states at distance 1, then 2, then 3...) and depth-first search (dive down one path as far as possible before backtracking) — are called uninformed or blind search because they use no knowledge about which direction looks promising. They just enumerate.

The problem is combinatorial explosion. A state space can grow exponentially with problem size: a 15-puzzle has about 10^13 reachable states, and chess has roughly 10^47. Blind search exploring even a tiny fraction of that space is computationally hopeless. This is exactly the gap heuristics were invented to close.

Greedy best-first search

The simplest way to use a heuristic is greedy best-first search: at every step, expand whichever state has the lowest h(n) value — the one that looks closest to the goal. This is fast and often finds a solution quickly, but it has a serious flaw: it can be fooled. A path that looks promising early on can lead into a dead end or a much longer route overall, because greedy search never reconsiders the cost already paid to get where it is — it only looks forward.

This is the same failure mode as always taking the most tempting local decision without accounting for sunk cost: it finds a path, but rarely the best path.

A*: combining past cost and future estimate

A* search fixes greedy search's blind spot by scoring each state with f(n) = g(n) + h(n), where g(n) is the actual, known cost to reach state n from the start, and h(n) is the estimated cost remaining to the goal. A* always expands the state with the lowest f(n) — effectively balancing "how much have I already spent" against "how much do I think is left."

This combination is what makes A* both efficient (guided by h, it avoids blind search's explosion) and capable of finding the truly optimal path (guided by g, it won't abandon a cheaper path for one that merely looks closer on a bad heuristic). It is the default algorithm behind GPS routing, game AI pathfinding, and robotics motion planning.

Admissibility: the condition that guarantees optimality

A* only guarantees it finds the optimal solution if the heuristic is admissible — meaning h(n) never overestimates the true remaining cost. An admissible heuristic can be wrong in the optimistic direction (think the goal is closer than it really is) but never wrong in the pessimistic direction.

For grid pathfinding, straight-line (Euclidean) distance is admissible because no real path can be shorter than a straight line. Manhattan distance is admissible on a grid where only horizontal and vertical moves are allowed. If a heuristic overestimates, A* can be tricked into skipping the actual optimal path in favor of one that merely looks cheaper — trading correctness for speed, which is sometimes an acceptable tradeoff and is exactly what weighted A* variants do deliberately.

Search strategy comparison

Why this still matters next to modern AI

Heuristic search is "classical" or "symbolic" AI, and it is easy to assume deep learning made it obsolete. It didn't. Search and learning are complementary: AlphaZero combines a learned evaluation function with a search procedure (Monte Carlo Tree Search, A*'s probabilistic cousin); modern robotics motion planners still run A* or its variants under the hood; and route-planning software, build systems, and compilers all lean on heuristic search daily. Learning is often what produces the heuristic function itself — a neural network can learn h(n) instead of a human hand-deriving it, which is precisely the bridge between classical and modern AI.

What's next

A* handles single-agent pathfinding, but many real problems are defined by constraints between many variables at once rather than a path to a goal. The next module, Constraint Satisfaction Problems, covers backtracking and arc consistency — the search techniques behind scheduling, Sudoku solvers, and resource allocation.