General Problem Solver

Imagine you are standing on one side of a wide, muddy river and want to reach the dry ground on the opposite bank. You observe the distance, realize you cannot leap across, and decide to find a fallen tree branch to act as a bridge. This natural way of thinking—noticing the gap between where you currently are and where you want to be, and searching for a specific tool or action to shrink that gap—is called "means-ends analysis." On June 15, 1959, in Pittsburgh, Pennsylvania, researchers introduced a computer program called the General Problem Solver (GPS) that was designed to tackle puzzles, logic theorems, and word problems by mimicking this intuitive human strategy.

How does General Problem Solver fit into the history of artificial intelligence?

In the late 1950s, the nascent field of artificial intelligence was highly fractured, divided between those exploring biological brain simulations and those building symbolic mathematical machines. Earlier work, such as the McCulloch-Pitts Neural Model and the SNARC Neural Simulator, attempted to replicate the physical architecture of animal brains. Meanwhile, early software pioneers sought to construct intelligent machines by focusing on high-level cognitive processes. The formal origin of this approach gained major momentum during the Dartmouth Workshop of 1956, where the AI Term Coined by John McCarthy set a shared path for researchers.

Prior to the General Problem Solver, Allen Newell and Herbert Simon had achieved significant acclaim with the Logic Theorist in 1956. While the Logic Theorist successfully proved complex theorems from Bertrand Russell’s Principia Mathematica, it was fundamentally limited to the domain of propositional logic. Newell and Simon, operating from the Carnegie Institute of Technology (now Carnegie Mellon University), realized that true intelligence required a machine capable of separating its core reasoning mechanics from the specific details of any individual task.

The introduction of the General Problem Solver on June 15, 1959, represented a crucial shift toward "generalism." It was the first software system built on the premise that any problem, whether playing chess, translating languages, or solving algebra, could be standardized into a uniform mathematical architecture. This development occurred alongside other major software innovations of the era, such as the creation of the LISP Programming Language, which together established the hegemony of symbolic "Good Old-Fashioned AI" (GOFAI) for the subsequent three decades.

What are the core technical achievements of General Problem Solver?

The technical brilliance of the General Problem Solver rested on its separation of task-specific knowledge from the general-purpose search engine. To solve a problem using GPS, a programmer had to define the problem using three distinct components:

1. Objects and States: The representation of the world at any given moment. This included the "Initial State" (where the program starts) and the "Goal State" (the desired target configuration).
2. Operators: Mathematical transitions or actions that can transform one state into another. Each operator had specific preconditions that had to be met before it could be applied.
3. A Difference Table: A matrix mapping specific differences (the gaps between states) to the operators best suited to eliminate or reduce those differences.

Once these components were declared, the GPS engine executed its primary algorithmic achievement: means-ends analysis (MEA). Unlike simple brute-force search routines that blindly tried every option, means-ends analysis was a recursive, goal-directed heuristic search. GPS would measure the "distance" between its current state and the goal state, identify the largest difference, and look up an operator to reduce it. If the operator's preconditions were not met, GPS would temporarily pause its primary objective, create a new "sub-goal" to alter the current state so the operator could be used, and recursively apply means-ends analysis to solve this sub-problem.

This recursive nesting allowed GPS to solve classical cognitive puzzles such as the "Towers of Hanoi" and the "Missionaries and Cannibals" problem. Rather than just writing code to solve a single puzzle, Newell and Simon had built an engine where the logic of problem-solving was decoupled from the problem itself. Additionally, the system was built using the Information Processing Language (IPL), which introduced list processing, nested subroutines, and dynamic memory allocation—concepts that would become standard in modern computer science.

Why is the legacy of General Problem Solver significant to modern computing?

The General Problem Solver was a landmark proof of concept, yet its real-world limitations ultimately defined the boundaries of early symbolic AI. While it succeeded spectacularly on well-formulated, closed-world puzzles, it struggled with real-world scenarios. In complex domains, the program suffered from a "combinatorial explosion"—the number of possible states and transitions grew exponentially, quickly exhausting the limited computer memory of the 1960s.

Furthermore, GPS lacked any concept of semantic meaning or common sense; it was entirely dependent on humans to translate the messiness of reality into clean, symbolic variables. These shortcomings invited rigorous philosophical objections, such as the Dreyfus Critique Published by philosopher Hubert Dreyfus, and later the Chinese Room Argument formulated by John Searle, both of which challenged the notion that symbolic manipulation equals genuine understanding.

Despite these limitations, the design philosophies of GPS directly paved the way for subsequent generations of intelligent software. The concept of means-ends analysis was integrated into Shakey the Robot through its STRIPS planning engine, allowing physical machines to navigate physical environments by breaking tasks into sub-goals. GPS also proved to be the grandfather of specialized expert systems, including the DENDRAL Expert System and the MYCIN Expert System, which dominated AI applications in the 1970s and 1980s by marrying symbolic heuristic search with deep, specialized knowledge bases.

Even in contemporary computing, where statistical approaches like neural networks and reinforcement learning are prominent, the foundational concepts of GPS persist. The transition-based formulations of states, actions, and rewards used in algorithms like the Q-Learning Algorithm and modern Deep Q-Networks (DQN) are direct mathematical descendants of the state-space graphs pioneered by Newell and Simon in 1959.