Heuristic

A heuristic is a rule of thumb: a practical shortcut that guides a problem solver toward a good answer without guaranteeing the best one, or even guaranteeing an answer at all. The word comes from the Greek heuriskein, to find or discover, and it names the opposite temperament from an algorithm. An algorithm promises a correct result if followed to the end; a heuristic trades that promise for speed, trying the promising moves first, discarding the unpromising ones early, and accepting that some problems will defeat it. In artificial intelligence the term acquired a second, sharper meaning as well: a heuristic function, a quick estimate of how close a given situation is to the goal, which a search procedure uses to decide what to explore next.

The mathematician George Polya made heuristics a subject of study in How to Solve It, first published in 1945, which turned the tacit habits of good problem solvers into explicit advice. Polya described four phases (understand the problem, devise a plan, carry out the plan, look back) and a catalogue of questions to ask along the way: Can the problem be restated? Is there a related problem already solved? Can a simpler special case be tried first? Can one work backward from the desired result? None of these questions guarantees a solution, and that was precisely his point: they are the moves that experienced mathematicians actually make, and they steer attention without dictating an outcome. Early AI researchers read Polya closely, and his vocabulary of analogy, subgoals and working backward reappears almost unchanged in the 1950s programs that tried to mechanize reasoning.

Herbert Simon and Allen Newell carried the idea into computing by arguing that intelligence is largely the skillful use of heuristics against combinatorial explosion. Their Logic Theorist, demonstrated in 1956, proved theorems from Whitehead and Russell's Principia Mathematica not by enumerating every possible proof, which is hopeless, but by selective search guided by rules of thumb about which inferences were likely to help. Simon's broader theory of bounded rationality, for which he later received the Nobel memorial prize in economics, held that real decision makers have limited information, time and computing power, and therefore satisfice: they search until they find an option that is good enough rather than optimizing over every option. Heuristics, on this view, are not a degraded form of reasoning but the rational response to finite resources.

In heuristic search the crucial distinction is between a heuristic that is merely informative and one that is admissible. A heuristic h(n) is admissible if it never overestimates the true cost of reaching the goal from state n; it may be optimistic but never pessimistic. A stronger property, consistency (or monotonicity), requires that the estimate not drop by more than the actual cost of any single step. Hart, Nilsson and Raphael showed in 1968 that A-star search with an admissible heuristic returns a cheapest path. For the sliding-tile 8-puzzle, counting misplaced tiles and summing each tile's Manhattan distance to its goal square are both admissible, because every move shifts one tile one square, and the second dominates the first, so it prunes more. Good heuristics are often found by relaxation: solve a simplified version of the problem (tiles allowed to pass through one another, say) and use its exact cost as the estimate. Judea Pearl's 1984 book Heuristics gave this subject its standard treatment, and pattern databases, precomputed costs for sub-problems, later made optimal solving of the 15-puzzle and Rubik's Cube practical.

A common misconception is that a heuristic is the same thing as a guess, or that using one means accepting wrong answers. An admissible heuristic keeps the result optimal; what it changes is the effort. Even inadmissible heuristics are deliberately used when speed matters more than optimality, as in the greedy and weighted variants of best-first search, and the loss in solution quality can be bounded. The word also has a separate career in psychology: Amos Tversky and Daniel Kahneman's 1974 paper in Science, Judgment under Uncertainty: Heuristics and Biases, argued that people estimate probabilities using shortcuts such as availability and representativeness, which are usually serviceable yet produce systematic errors. Gerd Gigerenzer and colleagues replied that such shortcuts can be ecologically rational. The human sense and the search sense share a root idea, cheap guidance under limited resources, but they are different objects: one describes how minds behave, the other is an engineered estimate inside an algorithm.

Modern AI still runs on heuristics, now often learned rather than hand-written. Route planners, game-playing engines, robot motion planners and automated planning systems all depend on cost estimates to avoid blind enumeration. Chess engines combine alpha-beta pruning with evaluation functions, which are heuristics for the worth of a position; AlphaGo and its successors replaced handcrafted evaluation with neural networks trained to judge positions and propose moves, which is still heuristic guidance of search, just learned from data. Local-search methods, SAT solvers and the branching rules inside integer-programming software are likewise collections of tuned heuristics, and the learned policies in large language model reasoning pipelines can be seen as heuristics for which line of thought to try next. The pitfall is overconfidence: a heuristic that works well on typical inputs can fail badly on adversarial or unusual ones, and a learned estimate carries no admissibility guarantee unless one is separately proved.

Read heuristic as a bet placed on structure: a cheap judgment about where the answer is likely to lie, which turns an impossibly large search into a feasible one at the price of a guarantee that only careful design, as with admissibility, can win back.