Search Space
A search space is the set of all candidate states, configurations or action sequences that a problem solver could in principle examine while looking for a solution. It is the landscape in which search happens: every legal arrangement of an 8-puzzle, every sequence of chess moves, every route between two cities, every assignment of values to the variables of a scheduling problem. The space is usually defined implicitly by rules for generating successors rather than stored as a list, which matters, because the spaces that arise in practice are far too large ever to be written down. What separates solvable problems from hopeless ones is often less the difficulty of recognizing an answer than the size of the space that has to be explored to find it.
The growth of a search space is governed by two numbers: the branching factor b, the number of options available at each step, and the depth d, the number of steps in a solution. A tree of depth d with b choices at every node contains on the order of b^d leaf paths, so the count grows exponentially with depth, not linearly. With b = 2 and d = 20 there are about a million paths; with b = 10 and d = 20 there are 10^20, far beyond what any computer can enumerate. This is the combinatorial explosion, a phrase that became a standard objection in the early 1970s: the 1973 Lighthill report on artificial intelligence, commissioned in Britain, argued that methods that worked on toy problems would collapse in the real world because of it, and the criticism contributed to cuts in research funding.
Chess shows the scale vividly, though the figures are estimates and should be quoted as such. Claude Shannon's 1950 paper, Programming a Computer for Playing Chess, in the Philosophical Magazine, observed that a typical position offers roughly thirty to forty legal moves and a game lasts on the order of eighty plies (one ply is a single move by one side). Allowing about a thousand possibilities for each pair of moves over forty moves gives roughly 10^120 possible games, the figure now known as the Shannon number. It is a rough order-of-magnitude estimate, not an exact count, and different assumptions give somewhat different exponents. The number of distinct legal positions is much smaller, widely cited as somewhere in the region of 10^43 to 10^47, but still astronomically beyond enumeration; the observable universe holds roughly 10^80 atoms. For comparison, Go has a branching factor near 250 and a space of legal positions commonly put at around 10^170, which is why Go resisted brute-force methods for decades after chess fell.
Pruning is the central defense: eliminating whole subtrees without examining them. In game playing, alpha-beta pruning stops exploring a branch as soon as it is provably no better than an option already in hand; with excellent move ordering it examines roughly the square root of the nodes plain minimax would, which in effect doubles the depth reachable in the same time, as Donald Knuth and Ronald Moore analyzed in 1975. In planning and constraint solving, pruning rules out partial assignments that already violate a constraint. Heuristic estimates prune indirectly by showing that a branch cannot lead to a cheap enough solution. The distinction worth keeping is between safe pruning, which never removes the optimal answer, and unsafe pruning, such as beam search or forward pruning in chess programs, which gains speed by risking the loss of a good line.
A frequent misconception is that faster hardware will eventually dissolve the problem. Exponential growth defeats constant-factor improvements: a computer a thousand times faster adds only a few levels of depth when b is large. Equally mistaken is the idea that a vast search space means a hard problem; a space can be astronomically large and still easy to navigate if the structure is helpful, as sorting a list or finding a shortest path in a graph shows, where clever algorithms avoid the space altogether. Hardness is a property of how much structure the solver can exploit, not of the raw count.
Today the same issue appears under new names. Neural network training explores a continuous parameter space far larger than any discrete game tree, yet gradient information makes the walk tractable. Reasoning systems built on large language models sample and score many possible chains of thought, which is again a search over a branching space with learned guidance and pruning. Program synthesis, drug design, chip layout, protein conformation and theorem proving all confront spaces of this kind, and progress usually comes from shrinking the effective branching factor with structure, learned priors or good representations rather than from more raw enumeration.
Read search space as the territory a problem defines, whose size is set by b^d and not by the difficulty of the answer, and treat every advance in heuristics, pruning and learning as a way of not having to visit most of it.