Search algorithms in AI

Search algorithms in AI are general procedures that solve a problem by systematically exploring a space of states: starting from an initial state, applying actions to generate successors, and stopping when a goal state is found. They differ in the order in which states are explored, which decides whether a solution is found, whether it is optimal, and at what cost.

1. Search as problem solving: the state space

State-space search

What it is. State-space search turns a problem into a graph. The nodes are states (a board position, a city, a partial proof), the edges are actions, and the task is to find a path from the initial state to a state that passes the goal test. Newell and Simon’s heuristic search hypothesis made it the core of early AI, and Russell and Norvig’s textbook still organises the subject around it [1].

How it works. Every algorithm below is the same loop with a different rule for choosing which frontier node to expand next: keep a frontier of generated but unexpanded nodes, take one out, test it, generate its successors, add them. A first-in-first-out queue gives breadth-first search, a stack gives depth-first search, a priority queue ordered by path cost gives uniform-cost search, and one ordered by path cost plus a heuristic gives A*. Algorithms are compared on four properties: completeness (finds a solution if one exists), optimality, time and space, measured with the branching factor $b$, the depth of the shallowest solution $d$ and the maximum depth $m$.

Limits. The graph is almost never written out; it is generated on demand, and its size is usually astronomical. A tree of branching factor $b$ has $b^d$ nodes at depth $d$. That single fact, combinatorial explosion, drives everything that follows.

2. Uninformed search: BFS, DFS, iterative deepening, uniform-cost

Uninformed (or blind) algorithms know nothing about where the goal is; they differ only in the order of exploration.

Breadth-first search (BFS)

Who and when. Konrad Zuse described breadth-first search in 1945, in his rejected doctoral thesis on the Plankalkül language, unpublished until 1972; Edward F. Moore published it in 1959 in “The shortest path through a maze” [2]. C. Y. Lee rediscovered it in 1961 for routing wires on circuit boards.

How it works. BFS expands all nodes at depth 1, then all at depth 2, and so on, using a first-in-first-out queue. It is complete when $b$ is finite, and it finds the shallowest goal, which is optimal when every action costs the same. Its weakness is memory: it must hold the whole frontier, $O\left(b^d\right)$ nodes. Used today for shortest paths in unweighted graphs, social-network distances, web crawling and as a building block in network-flow algorithms.

Depth-first search (DFS)

Who and when. Depth-first exploration of mazes goes back to Charles Pierre Trémaux in the nineteenth century; Robert Tarjan’s 1972 paper made it the basis of linear-time graph algorithms [3]. Backtracking in Prolog and in constraint solvers is depth-first search.

How it works. DFS always expands the deepest frontier node, using a stack, and backtracks when a branch is exhausted. It needs only $O\left(bm\right)$ memory, but it is not optimal and, in infinite or cyclic spaces without a visited set, not complete: it can walk down an endless branch while the goal sits one step from the root.

Iterative deepening depth-first search

Who and when. Already used in chess programs, and analysed by Richard Korf in 1985, who showed it is asymptotically optimal in time, space and solution cost among brute-force tree searches [4].

How it works. Run depth-limited DFS with limit 0, then 1, then 2, until a goal appears. Repeating the shallow levels looks wasteful but is not: most nodes of an exponential tree are in the deepest level, so the total work is

For $b=10$ the overhead is about 11 percent. Iterative deepening combines BFS’s completeness and shallowest-solution guarantee with DFS’s linear memory, and is the preferred blind search when the depth of the solution is unknown.

Uniform-cost search

Who and when. Uniform-cost search is Edsger Dijkstra’s 1959 shortest-path algorithm [5] run from a start state until a goal is removed from the queue, rather than over a whole graph given in advance.

How it works. Expand the frontier node with the lowest path cost $g\left(n\right)$. With strictly positive step costs, the first goal taken off the queue is optimal, because every cheaper path has already been expanded. It is A* with $h=0$. Used today inside routing software and network protocols (Dijkstra’s algorithm is the core of link-state routing such as OSPF).

3. Heuristic search: best-first, A*, IDA*, means–ends analysis, local search

A heuristic $h\left(n\right)$ estimates the cost of the cheapest path from node $n$ to a goal: straight-line distance on a map, the number of misplaced tiles in a sliding puzzle. It is where domain knowledge enters a general algorithm.

Greedy best-first search

Expand the node that looks closest to the goal, ordering the frontier by $h\left(n\right)$ alone. It is often fast, but it ignores the cost already paid, so it is not optimal, and without a visited set it can loop.

A* search

Who and when. Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute published A* in 1968, in work connected with the Shakey robot project [6]. The same paper proved the optimality result below.

How it works. A* orders the frontier by an estimate of the total cost of the best solution through $n$:

where $g\left(n\right)$ is the cost of the path found so far from the start to $n$ and $h\left(n\right)$ the heuristic estimate of the rest. Write $h^{*}\left(n\right)$ for the true remaining cost. Two conditions matter:

Every consistent heuristic is admissible. Straight-line distance is admissible for road routing because no road is shorter than a straight line.

Worked example. Four states: start $S$, goal $G$, and $A$, $B$. Edges $S\to A$ cost 1, $S\to B$ cost 4, $A\to B$ cost 2, $A\to G$ cost 6, $B\to G$ cost 3. The heuristic is $h\left(S\right)=5$, $h\left(A\right)=4$, $h\left(B\right)=2$, $h\left(G\right)=0$. The true remaining costs are 6, 5, 3 and 0, so $h$ is admissible, and checking each edge shows it is consistent.

Greedy best-first search would have gone S → B → G (cost 7), because B has the smallest $h$. A* does not stop when G is first generated at cost 7; it stops when G is selected, and by then the cheaper route has been found.

A stronger result also holds: with a consistent heuristic, no algorithm that is guaranteed optimal and uses the same heuristic expands fewer nodes than A*, apart from ties. Used today in route planning, robot motion planning, video-game pathfinding and, with heuristics computed from the problem description, in automated AI planning. Limits. A* keeps every generated node in memory, which is usually what stops it; and its speed depends entirely on how close $h$ is to $h^{*}$. With a weak heuristic it degrades toward uniform-cost search.

IDA* (iterative deepening A*)

Who and when. Richard Korf, 1985, in the same paper as the analysis of iterative deepening [4].

How it works. Run depth-first search, cutting off any branch whose $f=g+h$ exceeds a threshold. The first threshold is $h\left(s_0\right)$; each new iteration raises it to the smallest $f$ value that exceeded the old one. With an admissible heuristic the first goal found is optimal, and memory is only linear in the solution depth. Korf reported it as the only algorithm then known to find optimal solutions to random instances of the Fifteen Puzzle within practical limits, and in 1997 used it with pattern-database heuristics to find optimal solutions to random Rubik’s Cube states [7]. Limit: without memory it re-expands the same nodes many times, badly so when there are many distinct $f$ values.

Means–ends analysis (GPS)

Who and when. Allen Newell, J. C. Shaw and Herbert Simon, in the General Problem Solver, created in 1957 and reported in 1959 [8]. The history of symbolic AI covers its place in the field.

How it works. Compare the current state with the goal and name the most important difference. Look up an operator known to reduce that difference (a table of differences and operators supplies the domain knowledge). If the operator cannot be applied yet, make satisfying its preconditions a subgoal and recurse; then apply it and repeat on the remaining differences. Example: the difference between home and a distant meeting is distance, which a plane reduces; the plane’s precondition, being at the airport, is a smaller difference that a taxi reduces.

Legacy and limits. GPS separated a general reasoning engine from the domain knowledge it runs on, a design that returned in STRIPS and in the goal-directed search of every later planner. It solved only small, well-formalised problems; the difference table had to be written by hand, and working on one difference could undo another, the problem that later planners called goal interaction.

Local search: hill climbing and simulated annealing

When only the final state matters, not the path (placing eight queens, laying out a chip, building a timetable), local search keeps a single current state and moves to a neighbour. Hill climbing always moves to the best neighbour and stops at a peak, which may only be a local maximum. Simulated annealing, introduced for combinatorial optimisation by Kirkpatrick, Gelatt and Vecchi in 1983 by analogy with cooling metal [9], sometimes accepts a worse neighbour, with probability $e^{-\Delta /T}$ for a loss $\Delta$ at temperature $T$, and lowers $T$ over time, so it can escape local optima early and settle late. Local search uses almost no memory and scales to huge problems; it is incomplete, and cannot prove that no solution exists. Stochastic local search for satisfiability, such as WalkSAT, is covered on the constraint satisfaction, SAT and SMT page.

4. Game-tree search: minimax, alpha–beta, Deep Blue, MCTS, AlphaGo

In a two-player, zero-sum game with perfect information, the opponent chooses half the moves. The state space becomes a game tree whose levels alternate between MAX (the program) and MIN (the opponent).

Minimax

Who and when. John von Neumann proved the minimax theorem for two-person zero-sum games in 1928. Claude Shannon’s 1950 paper “Programming a Computer for Playing Chess” proposed searching the chess tree with minimax to a limited depth and scoring the frontier positions with an evaluation function [10]. Every chess program since has followed that outline.

How it works. The minimax value of a state is defined recursively:

MAX plays the move with the highest value, on the assumption that MIN answers with the move that is worst for MAX. Computing $V$ exactly by depth-first search costs $O\left(b^d\right)$. For chess, with roughly 35 legal moves per position, that is why programs search to a fixed depth and rely on the evaluation function below it.

Alpha–beta pruning

Who and when. Alpha–beta was discovered several times. John McCarthy proposed the idea around the 1956 Dartmouth workshop; others arrived at it independently in the late 1950s and early 1960s, including Alexander Brudno, who published in 1963. Donald Knuth and Ronald Moore gave the definitive analysis and correctness proof in 1975 [11].

How it works. Search depth-first while carrying two bounds: $\alpha$, the best value MAX is already guaranteed elsewhere on the path, and $\beta$, the best value MIN is already guaranteed. As soon as a node’s value is known to fall outside $(\alpha ,\beta )$, the rest of its children cannot change the decision at the root, and are skipped. The value returned at the root is exactly the minimax value; pruning changes the cost, never the answer.

Worked example. MAX chooses among three moves leading to MIN nodes B, C and D, each with three leaves (Figure 1).

1. B: leaves 5, 9, 6. MIN takes the smallest, so $V\left(B\right)=5$, and now $\alpha =5$ at the root: MAX can get at least 5.
2. C: the first leaf is 3, so $V\left(C\right)\le 3<\alpha$. Whatever the other two leaves are, MAX will not choose C. Both are pruned.
3. D: leaf 10 gives $V\left(D\right)\le 10$, which does not settle it; leaf 4 gives $V\left(D\right)\le 4<\alpha$, so the third leaf is pruned.

How much pruning helps depends on move order. Knuth and Moore showed that with the best move always searched first, alpha–beta examines

leaf positions instead of $b^d$: in the same time it can search roughly twice as deep [11]. With the worst ordering it prunes nothing. Chess programs therefore spend much of their effort on ordering moves well, using iterative deepening, transposition tables and heuristics. Limits: the evaluation function is still hand-written or learned, and anything beyond the search horizon is invisible (the horizon effect).

Deep Blue (1997)

IBM’s Deep Blue, built by Murray Campbell, A. Joseph Hoane Jr. and Feng-hsiung Hsu, beat world champion Garry Kasparov 3½–2½ in May 1997, after losing their first match 4–2 in February 1996 [12]. It was a massively parallel alpha–beta searcher with custom chess chips, able to evaluate about 200 million positions per second, with extensive search extensions and an evaluation function whose parameters were tuned by its engineers with the help of a database of grandmaster games. It did not learn to play from self-play. Stockfish, the leading open-source engine, still searches with alpha–beta; since 2020 it has evaluated positions with a small neural network (NNUE), which makes it a hybrid of the kind described on the neuro-symbolic AI page.

Monte Carlo tree search (MCTS)

Who and when. Rémi Coulom named Monte Carlo tree search in 2006, in a paper presented at the Computers and Games conference in Turin, and used it in his Go program Crazy Stone [13]. The same year Levente Kocsis and Csaba Szepesvári published UCT (“Upper Confidence bounds applied to Trees”), which chooses moves in the tree with a bandit formula and comes with convergence guarantees [14]. The 2012 survey by Browne and colleagues covers the first years of variants [15].

How it works. MCTS builds a partial game tree, one simulated game at a time, in four steps:

1. Selection: from the root, repeatedly pick the child that maximises the UCT score below, until reaching a node with unexplored moves.
2. Expansion: add one new child node.
3. Simulation: play the game to the end from there, with random or cheap policy moves (a “playout” or “rollout”).
4. Backpropagation: update the win count and visit count of every node on the path.

where $w_j$ is the number of wins through child $j$, $n_j$ its visits, $N$ the parent’s visits and $c$ an exploration constant ($\sqrt{2}$ in the UCB1 bandit rule of Auer, Cesa-Bianchi and Fischer [16]). The first term exploits moves that have won; the second explores moves that have been tried rarely. After the time budget runs out, the program plays the most-visited move.

Why it mattered. Alpha–beta needs an evaluation function, and in Go nobody could write a good one. MCTS needs only the rules: the average result of many playouts is the evaluation. From 2006 on, the strongest Go programs were built on it. Used today in game engines for Go, general game playing and some planning under uncertainty. Limits: random playouts can badly misjudge positions where one precise line matters, as in tactical chess, and the method is statistical: it estimates a value rather than proving one.

AlphaGo and AlphaZero: search plus learned evaluation

DeepMind’s AlphaGo beat Lee Sedol 4–1 in March 2016. Its Nature paper describes MCTS guided by two deep networks: a policy network that proposes promising moves and a value network that judges positions, combined with rollouts [17]. AlphaZero (Science, 2018) dropped the rollouts and the human game data, learned both networks by self-play, and reached superhuman level in chess, shogi and Go with the same algorithm [18]. In chess it searched far fewer positions per second than alpha–beta engines, relying on the network to be selective. These systems are hybrids: the tree search is exact bookkeeping over legal moves, the part that says which moves exist and what follows from them; the networks supply the judgement that nobody could write down.

5. Timeline

6. Where search breaks

• Combinatorial explosion. Every technique here fights exponential growth; none defeats it in general. Finding optimal solutions to the generalised sliding-tile puzzle is NP-hard, and planning, a form of search, is PSPACE-complete in general (see STRIPS). The 1973 Lighthill report named combinatorial explosion as a central obstacle to AI, as the history of symbolic AI recounts.
• The heuristic is knowledge, and someone has to supply it. A* is only as fast as $h$ is informative. Heuristics derived automatically from a problem description, and learned heuristics, are the modern answers.
• The model must be right. Search is exact with respect to its model: states, actions, costs, rules of the game. If the model omits something, the optimal path in the model can be wrong in the world. Search guarantees nothing about the fidelity of the model it searches.
• Uncertainty. Classical search assumes deterministic actions and a fully observable state; hidden information and noisy sensors need probabilistic extensions.

7. Search and fail-safe models

A fail-safe model is an AI model built so that when it fails, it fails toward a controlled, safe state instead of a confident error. The positive one is admissibility. The A* theorem is a guarantee that holds whatever the heuristic’s quality, as long as the heuristic is never allowed to overestimate: a bad heuristic makes A* slow, never wrong. That is the shape of a fail-safe property: the component that supplies judgement can be weak, and a structural constraint on it keeps the answer correct. AlphaGo shows the same division from the other side: networks propose moves, and the rules of the game, applied exactly by the tree search, decide which moves exist.

The cautionary lesson is that search is only as good as its model, and a search that returns “no solution found” within a budget has not proved that none exists. An honest system reports those as different outcomes. We apply the same discipline to knowledge: a model may propose; only the floor admits a fact. Peel, by Perslis Research, is built that way: there is no neural network in the loop that decides, knowledge is typed, sourced cards, and learning is readable counts. To our knowledge it is the first fail-safe model; the exact claim and the closest earlier work are on What is a fail-safe model? Peel is a research prototype. For how search fits with the other methods, see the guide to symbolic AI techniques and What is symbolic AI?

8. Questions

What are search algorithms in AI?

They are general procedures that solve a problem by exploring a space of states: start from an initial state, apply actions to generate new states, and stop when a goal state is reached. Breadth-first search, depth-first search, uniform-cost search, A*, minimax, alpha–beta pruning and Monte Carlo tree search are the standard examples.

What is the difference between uninformed and informed search?

Uninformed, or blind, search uses only the problem definition, so it explores states in a fixed order such as level by level or deepest first. Informed, or heuristic, search also uses an estimate of the remaining cost to the goal, which lets it explore promising states first and usually find solutions far faster.

Why is A* optimal?

A* expands nodes in order of f(n) = g(n) + h(n), the cost so far plus a heuristic estimate of the rest. If the heuristic never overestimates the true remaining cost, then any node on an optimal path always has an f value no larger than the optimal cost, so A* expands it before it could select a worse goal. That property is called admissibility.

What is an admissible heuristic?

An admissible heuristic never overestimates the true cost of reaching the goal from a node. Straight-line distance on a road map is the classic example, because no road between two points is shorter than the straight line. A consistent heuristic, which also obeys a triangle inequality along every edge, is always admissible.

How does alpha–beta pruning work?

Alpha–beta pruning runs minimax depth-first while tracking alpha, the value the maximising player is already guaranteed, and beta, the value the minimising player is already guaranteed. When a branch is shown to be worse than an option already available, its remaining children are skipped. The result is exactly the minimax value, often with far fewer positions examined.

What is Monte Carlo tree search?

Monte Carlo tree search, named by Rémi Coulom in 2006, estimates the value of moves by playing many simulated games. It grows a search tree by repeating four steps: selection with a formula such as UCT, expansion, a simulated playout and backpropagation of the result. It needs no hand-written evaluation function, which made it the breakthrough method for computer Go.

Is A* search artificial intelligence?

Yes. A* was developed in 1968 at the Stanford Research Institute as part of AI research on the Shakey robot, and heuristic search is one of the founding techniques of symbolic AI. It is now so widely used in routing and games that it is often thought of simply as an algorithm, a common fate for symbolic AI methods that work.

Did Deep Blue use machine learning?

Not in the modern sense. Deep Blue, which beat Garry Kasparov in 1997, was a massively parallel alpha–beta search engine with custom chess chips and an evaluation function designed and tuned by its engineers using grandmaster games. Later systems such as AlphaZero learned their evaluation from self-play.

9. References

1. S. Russell, P. Norvig. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2020.
2. E. F. Moore. The Shortest Path Through a Maze. Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, 1959.
3. R. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing 1(2):146–160, 1972. doi:10.1137/0201010
4. R. E. Korf. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence 27(1):97–109, 1985. doi:10.1016/0004-3702(85)90084-0
5. E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1:269–271, 1959. doi:10.1007/BF01386390
6. P. E. Hart, N. J. Nilsson, B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics 4(2):100–107, 1968. doi:10.1109/TSSC.1968.300136
7. R. E. Korf. Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases. Proceedings of AAAI-97, 1997.
8. A. Newell, J. C. Shaw, H. A. Simon. Report on a General Problem-Solving Program. Proceedings of the International Conference on Information Processing (Paris), pp. 256–264, UNESCO, 1959.
9. S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi. Optimization by Simulated Annealing. Science 220(4598):671–680, 1983. doi:10.1126/science.220.4598.671
10. C. E. Shannon. Programming a Computer for Playing Chess. Philosophical Magazine 41(314):256–275, 1950. doi:10.1080/14786445008521796
11. D. E. Knuth, R. W. Moore. An Analysis of Alpha-Beta Pruning. Artificial Intelligence 6(4):293–326, 1975. doi:10.1016/0004-3702(75)90019-3
12. M. Campbell, A. J. Hoane Jr., F.-h. Hsu. Deep Blue. Artificial Intelligence 134(1–2):57–83, 2002. doi:10.1016/S0004-3702(01)00129-1
13. R. Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Computers and Games (CG 2006, Turin), LNCS 4630, pp. 72–83. Springer, 2007. doi:10.1007/978-3-540-75538-8_7
14. L. Kocsis, C. Szepesvári. Bandit Based Monte-Carlo Planning. Machine Learning: ECML 2006, LNCS 4212, pp. 282–293. Springer, 2006. doi:10.1007/11871842_29
15. C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, S. Colton. A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games 4(1):1–43, 2012. doi:10.1109/TCIAIG.2012.2186810
16. P. Auer, N. Cesa-Bianchi, P. Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47(2–3):235–256, 2002. doi:10.1023/A:1013689704352
17. D. Silver, A. Huang, C. J. Maddison, A. Guez, et al. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature 529(7587):484–489, 2016.
18. D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, et al. A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go through Self-Play. Science 362(6419):1140–1144, 2018. doi:10.1126/science.aar6404