state-space search
/ STAYT-spays surch /
State-space search is a foundational way AI solves problems by treating them as finding a path through a giant maze of possibilities. Every situation you could be in is a 'state'; every move you could make takes you from one state to another; and solving the problem means finding a sequence of moves from where you start to where you want to be. Think of a sliding-tile puzzle: each arrangement of tiles is a state, each slide is a move, and the search is the hunt for the moves that reach the solved picture.
Laid out plainly, a search problem has four parts: a start state, a set of actions that move between states, a goal test that tells you when you've arrived, and (often) a cost on each move so you can prefer cheaper paths. The whole web of reachable states is the 'state space.' A search algorithm systematically explores this space — fanning out from the start, keeping track of where it's been, and building toward a goal. Different strategies explore in different orders: some go broad, some go deep, some follow a heuristic toward the most promising states first.
Its importance is twofold. Historically, framing intelligence as search was one of AI's first big ideas — game-playing, route-finding, planning, and puzzle-solving all fit the mold, and it powered classic systems through the symbolic era. Practically, it still runs underneath route planners, logistics schedulers, and game AIs today. Its hard limit is size: the number of states often explodes combinatorially (a chess game has more positions than atoms in the observable universe), so pure brute-force search is hopeless on big problems. That explosion is exactly why heuristics — smart guesses about which states to explore first — are essential rather than optional.
Solving a Rubik's cube as search: each scramble of the cube is a state; each face-turn is an action; the goal test is 'all sides one color.' From any state there are 18 possible turns, so the reachable states balloon astronomically. A blind search would never finish — which is why solvers lean on heuristics and structure to home in on the solution.
States, actions, and a goal test — and the combinatorial explosion that makes heuristics necessary.
The fatal enemy of state-space search is combinatorial explosion: realistic problems have astronomically many states, so exhaustive search is impossible. That's why heuristics, which prune the search toward promising states, aren't a luxury — they're what makes search usable at all.