Problem Solving as Search

Intelligence as exploring possibilities

A huge class of problems shares one shape: an initial state, available actions, a goal test, and costs. Solving = finding an action sequence from start to goal. A maze, a Rubik's cube, airline scheduling, chess, route planning: all search problems over a (usually astronomically large) tree of states. Classical AI's first great insight: thinking can be modeled as systematic exploration of alternatives.

Uninformed search

Knowing nothing about which direction is promising:

• Breadth-first search (BFS) — explore all states 1 step away, then 2, then 3… Finds the shortest solution; memory-hungry (the frontier explodes).
• Depth-first search (DFS) — plunge down one branch, backtrack on dead ends. Tiny memory; no shortest-path guarantee; can wander.
• Uniform-cost search (Dijkstra) — BFS generalized to weighted steps: always expand the cheapest known path so far.

All hit the same wall: combinatorial explosion. Chess has ~$10^{120}$ possible games (the number that killed 1970s optimism). Brute force is hopeless; intelligence must prioritize.

Informed search: A*

A heuristic $h(n)$ estimates the remaining distance from state $n$ to the goal — e.g. straight-line distance in route planning. A* expands the node minimizing

$f(n) = g(n) + h(n)$

(cost already paid + estimated cost remaining). The elegant theorem: if $h$ never overestimates (an admissible heuristic), A* is guaranteed to find an optimal path — while exploring a tiny fraction of the space. Optimism steers, honesty guarantees. A* runs your GPS, videogame pathfinding, robot motion planning and puzzle solvers; heuristic design (often via relaxing the problem's rules) is the craft.

Adversarial search: games

Chess adds an opponent who picks against you. Minimax reasons down the game tree: I choose the move maximizing my worst-case outcome, assuming the opponent minimizes it. Alpha-beta pruning skips branches that provably can't change the decision (a good move ordering doubles searchable depth). Since trees end long before checkmate, a hand-crafted evaluation function scores frontier positions — Deep Blue's was tuned by grandmasters, searching ~200 million positions/second.

The modern synthesis: AlphaGo/AlphaZero replaced hand-crafted evaluation with a deep network (trained by self-play RL) and brute-force minimax with Monte Carlo tree search guided by that network — learning which branches deserve exploration. Search provides deliberate planning; learning provides intuition. Neither alone beat Go; together they did. Remember this hybrid — "neural intuition + symbolic planning" is a template you'll see again in LLM agents.

Key takeaways

• Framing problems as state-space search is classical AI's foundational move.
• A*: expand by cost-so-far + admissible estimate-to-go → optimal paths, tiny explored fraction.
• Games: minimax + pruning + evaluation; AlphaGo = learned evaluation + guided search — the enduring hybrid recipe.