Search Algorithm
Systematically exploring possibilities to find a good one — AI's oldest technique, its most complete success, and nobody calls it AI anymore.
When not to use it
- When you don't have a model of the problem. Search needs rules. If you only have examples, learn.
- On exponential spaces without a good heuristic. Branching^depth doesn't yield to hardware.
- With an inadmissible heuristic, expecting optimality. Overestimate and A*'s guarantee is gone.
- When good-enough is fine and the space is huge. Local search is the right tool.
Reach for something else instead
- Learning — when you have examples and no model.
- MCTS with learned heuristics — when the space is too big and you have data. The AlphaGo answer.
- Constraint solvers — for scheduling and allocation, extraordinary and underused.
- Local search / annealing — huge spaces, approximate answers.
Sources & further reading
- Hart, Nilsson & Raphael (1968), A Formal Basis for the Heuristic Determination of Minimum Cost Paths — A*, and the optimality proof.
- Campbell, Hoane & Hsu (2002), Deep Blue — search plus hand-tuned evaluation; a hardware triumph that taught the field little.
- Silver et al. (2016), Mastering the game of Go with deep neural networks and tree search — MCTS with learned heuristics. Both halves needed.
Primary sources, listed so you can check the claims on this page rather than take them on trust.
Where people go wrong
- Reaching for ML when you have a model of the problem. Search is cheaper, exact and explainable.
- Expecting hardware to beat exponential branching. It doesn't. That's Lighthill's point.
- Reading Deep Blue as an AI achievement. It was search plus a hand-tuned evaluation on custom chips, and it taught the field very little.
- Missing that AlphaZero kept the search and threw out the hand-authored knowledge. That's the Bitter Lesson precisely.
At a glance
FieldFoundations
AI's oldest technique, and it won
Why nobody calls it AIthe AI effect; once it works reliably it's just software
Where the intelligence livesthe heuristic
A*'s guaranteeoptimal, if the heuristic never overestimates
The renaissancetest-time compute is search returning as "thinking"
DifficultyBeginner
Flashcards for this concept
Question
—
Answer
—
1 / 4
Often compared with
Search vs. learning — one needs a model of the problem and gives you guarantees; the other needs examples and gives you a heuristic. AlphaGo needed both, and reasoning models are rediscovering that.