General Problem Solver
The General Problem Solver, or GPS, was a program developed from 1957 by Allen Newell, J. Clifford Shaw and Herbert Simon, reported in the 1959 paper Report on a general problem-solving program, which tried to solve many kinds of problems with one reasoning procedure by keeping the description of a task separate from the method used to work on it. It was the successor to the Logic Theorist, which had been built around a single domain, and it was the first major attempt to make a program whose generality was part of the design rather than an afterthought.
The key design decision was a clean split between task knowledge and problem-solving strategy. A user supplied a description of the task: the kinds of objects, a set of operators that could change one object into another, a table linking kinds of difference between objects to operators that tend to reduce them, and the initial and goal situations. The solver contained none of this domain content; it contained only the general method, which was means-ends analysis (the separate entry covers the technique in detail). Compare the current object with the goal, identify the most important difference, select an operator relevant to that difference, and if the operator cannot be applied immediately, make the removal of the obstacle a new subgoal. This recursive structure of goals and subgoals is what let the same program tackle logic proofs, symbolic integration, puzzles such as the Tower of Hanoi and missionaries-and-cannibals, and other tasks.
GPS was also a psychological theory, and this was as important to its authors as the engineering. Newell and Simon asked subjects to think aloud while solving logic problems and compared the sequences of goals in those protocols with the program's traces. They reported close correspondence on parts of the behavior, notably the habit of working by reducing differences, and they used the results to claim that programs of this kind could model human thinking. This work was developed through the early 1960s and into Human Problem Solving (1972), and the 1969 report by George Ernst and Newell, GPS: A Case Study in Generality and Problem Solving, assessed what the program could actually do across a collection of task environments.
Its limits were clear to its builders, and they explain why it was eventually set aside. The word general referred to the separation of method from task, not to ability to solve any problem. Humans still had to formalize each problem, writing the operators and building the difference table, and that was where much of the intelligence lay. Differences could trap the program in local dead ends, where reducing the obvious difference blocks a needed detour; the representation of each task was fixed in advance, so it could not reformulate a problem; and for realistic domains the search tree grew faster than heuristics could prune it. Ernst and Newell's assessment concluded that its generality came at the cost of power on any one task, and work shifted towards programs that held much more domain knowledge, a move that led to expert systems in the 1970s.
The idea has survived under other names, which is the best measure of its influence. Fikes and Nilsson's STRIPS planner (1971) formalized operators with preconditions and effects in the same manner, and modern automated planning, with languages such as PDDL, still describes actions that way. Newell's Soar architecture treats impasses as occasions to create subgoals, and so inherits the structure directly. The general split of reusable engine from declared task is also familiar in constraint solvers, SAT solvers and the planners in current agent software, where a language model may propose steps while a separate component tracks preconditions and goals.
A frequent misconception is that GPS failed because the dream of general intelligence was refuted. The more accurate reading is that it measured the cost of generality: a universal method gives little leverage without knowledge, a lesson the 1970s turned into the slogan that knowledge is power. Another pitfall is to equate GPS with the term means-ends analysis; the technique is older than the program and has been used outside it, and GPS is better seen as the first complete program organized around it.
Read the General Problem Solver as a bold experiment in separating how to search from what to search about: it showed that one engine could drive many tasks, and its limits showed that the task description, not the engine, carries most of the intelligence.