Concept · Chapter 1: What Is Artificial Intelligence?
Search
Search solves a problem by exploring sequences of possible actions from a start state until one reaches the goal — and a good heuristic decides which possibilities to explore first.
The problem
Many tasks — puzzles, routes, games, plans, proofs — have an astronomical number of possible action sequences; we need a systematic way to find one that works.
The solution
Model the problem as states and actions, then explore the space: blindly (breadth-first, depth-first) or guided by a heuristic estimate of how close each state is to the goal (A*).
The consequence
Search powered route planners, puzzle solvers and chess engines — and it returns in modern AI as tree search guided by learned networks (AlphaGo) and as the exploration of reasoning paths in language models.
You should understand first
Intuition
You're in a maze. You could try every corridor in order of distance (breadth-first), follow one corridor as far as it goes before backing up (depth-first), or — if you can see roughly where the exit is — prefer corridors heading that way (heuristic search). All three are search; they differ in which possibility they try next.
Try it
Try it
Draw walls on a grid and watch breadth-first, depth-first and A* search find their way — and count how much each has to explore.
The numbers that make search hard
If each state offers possible actions and a solution needs steps, blind search may face on the order of possibilities. Chess has roughly 35 legal moves per position; looking just 10 moves ahead is already about positions.
Where it appears in AI
- Classical AI: puzzle solving, planning (Shakey, STRIPS), theorem proving, and game playing — Deep Blue searched on the order of 200 million chess positions per second.
- Learning meets search: AlphaGo (2016) used neural networks to supply the "intuition" — which moves are promising, who is winning — that guided its tree search Established.
- Language models: beam search in decoding, and search over multiple reasoning paths with a verifier choosing among them Active research (Chapter 14).
Why should I care?
As a researcher
Search is making a comeback in reasoning research: sampling many reasoning paths, tree search over thoughts, verifier-guided search. Its classic trade-offs — breadth vs depth, heuristics, exploding branching factors — are the same.
As an engineer
Pathfinding, scheduling, query planning, and beam search in text generation are all search. Choosing and tuning the heuristic is often most of the work.
Modern systems that depend on it
- Route planning and games
- AlphaGo-style tree search
- Beam search in sequence generation
- Search over reasoning paths in LLMs
Historical context
Before
Exhaustive trial and error; early theorem provers such as the Logic Theorist framed reasoning as search.
After
Heuristic search (A*, 1968); game-tree search (Deep Blue, 1997); learned heuristics guiding tree search (AlphaGo, 2016).
Used today
Maps and navigation, logistics, game AI, compilers and databases — and inside AI systems that generate or check many candidate solutions.
What to remember
- Problem = states + actions + start + goal test.
- BFS: explores level by level; finds shortest paths but explores widely.
- DFS: dives deep first; little memory, but paths can be long.
- A*: expands by (cost so far + heuristic estimate); optimal if the heuristic never overestimates.
- Branching factor b and depth d → roughly b^d states: why good heuristics matter.
Key papers
Some Studies in Machine Learning Using the Game of Checkers
A. L. Samuel · 1959 · IBM Journal of Research and Development
One of the first programs that improved by learning from play — an early demonstration that learning can beat hand-tuning.
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Peter Hart, Nils Nilsson, Bertram Raphael · 1968 · IEEE Transactions on Systems Science and Cybernetics
Introduced A*, the heuristic search algorithm still used in route planning, games and robotics.
Computer science as empirical inquiry
Allen Newell, Herbert A. Simon · 1976 · Communications of the ACM
The classic statement of the symbolic-AI worldview: the physical symbol system hypothesis and heuristic search as the heart of intelligence.
How to read it: Their 1975 Turing Award lecture. Read it as the best case for the approach this chapter shows running into limits.
Mastering the game of Go with deep neural networks and tree search
David Silver, Aja Huang et al. · 2016 · Nature
AlphaGo combined learned intuition (neural networks) with classical search — and beat top professionals at a game long thought decades away.
How to read it: A perfect bridge between this chapter's two halves: symbolic search, guided by learned networks.