General Problem Solver
The General Problem Solver (GPS) is a pioneering computer program in the field of artificial intelligence, developed between 1957 and 1959 by Allen Newell, Herbert A. Simon, and J. C. Shaw at the RAND Corporation.[1] Intended as a universal system for tackling diverse intellectual tasks, GPS employed a general-purpose heuristic method called means-ends analysis to simulate human-like problem-solving by reducing differences between initial states and desired goals through recursive subgoal generation.[2] At its core, GPS represented problems using a formal structure consisting of objects (elements of the problem domain), operators (actions that modify objects), and goals (target states).[1] The means-ends analysis strategy operated by evaluating the discrepancies between the current problem state and the goal, selecting an appropriate operator to minimize those differences, and treating any resulting obstacles as new subgoals to be solved iteratively—a process that emphasized planning and divide-and-conquer tactics over exhaustive search.[3] This approach drew from observations of human cognition, aiming to model adaptive reasoning applicable across domains rather than relying on domain-specific rules alone.[4] Demonstrating practical utility, GPS successfully addressed a range of benchmark problems, including proving theorems in symbolic logic (such as those from Whitehead and Russell's Principia Mathematica), solving cryptarithmetic puzzles like SEND + MORE = MONEY, and navigating tasks in trigonometry and the Tower of Hanoi puzzle.[1] These achievements highlighted its ability to handle combinatorial challenges within structured "microworlds," though performance degraded in larger search spaces due to exponential growth in possibilities and the program's dependence on predefined representations.[4] GPS holds enduring significance as one of the earliest symbolic AI systems, establishing key paradigms in heuristic search, goal-directed reasoning, and computational modeling of cognition during the field's formative "golden age" of the 1950s and 1960s.[2] By bridging computer science and psychology, it influenced the development of later programs and theories, underscoring the potential—and initial limitations—of general intelligence simulation while inspiring ongoing research in automated problem-solving.[5]History and Development
Origins and Motivation
The field of artificial intelligence emerged in the early 1950s amid growing interest in simulating human intelligence using computers, with the 1956 Dartmouth Summer Research Project serving as a pivotal catalyst that formalized symbolic AI as a discipline. Organized by John McCarthy, Marvin Minsky, Nathaniel Rochester, and Claude Shannon, the conference proposed exploring how machines could form abstractions, solve problems reserved for humans, and improve themselves, conjecturing that "every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it."[6] Allen Newell and Herbert A. Simon, listed among the interested participants, were inspired by this vision to pursue computational models of cognition.[6] Newell and Simon's motivation for the General Problem Solver (GPS) stemmed from their studies in human cognition, building directly on their 1956 development of the Logic Theorist, the first AI program designed to prove mathematical theorems and mimic human reasoning processes.[7] At the RAND Corporation, where Newell worked as a researcher and Simon consulted, they sought to generalize these insights into a framework for simulating human problem-solving, drawing from psychological experiments that recorded subjects' thought protocols during tasks like logic puzzles.[8] This work reflected a broader ambition to bridge psychology and computing, treating programs as theories of human behavior to uncover the mechanisms of adaptive intelligence.[9] RAND's funding played a crucial role, supporting Newell, Simon, and collaborator J.C. Shaw in their efforts to develop general-purpose tools for complex decision-making, aligned with the organization's focus on defense-related strategic analysis during the Cold War era.[8] The specific goal of GPS was to create a program capable of solving any formal problem by systematically reducing differences between the current state and the goal state, inspired by observed human strategies in psychological protocols.[7] This approach, briefly referencing means-ends analysis as the core method, aimed to demonstrate how heuristic processes could enable computers to exhibit intelligent behavior across diverse domains.[7]Creation Process and Timeline
The development of the General Problem Solver (GPS) began in the summer of 1957 at the RAND Corporation, where Allen Newell, J.C. Shaw, and Herbert A. Simon initiated work on a program to simulate general human-like problem solving, building directly on the 1956 Logic Theorist, their earlier heuristic theorem-proving system.[10] Shaw's creation of the Information Processing Language (IPL), one of the first list-processing languages, was integral to this phase, enabling efficient symbolic manipulation and representation of problem states through linked lists, which addressed limitations in earlier machine-code implementations.[11] The collaborative effort involved cross-institutional coordination between RAND and Carnegie Institute of Technology, with protocol analysis of human subjects—using think-aloud techniques to capture problem-solving behaviors—guiding the design from the outset.[10] By late 1957, the first working version of GPS was operational, demonstrating basic means-ends analysis on formalized problems.[12] Iterative refinements followed through 1958, incorporating feedback from human protocol data to enhance subgoal formation and search mechanisms; this included testing on simple puzzles like the Tower of Hanoi and the missionaries-and-cannibals problem to validate generality across domains.[13] A key milestone was the 1958 publication of "Elements of a Theory of Human Problem Solving" in Psychological Review, which outlined the program's theoretical underpinnings and early empirical fits to human data. Public demonstration and broader dissemination occurred in 1959 with the presentation of "Report on a General Problem-Solving Program" at the International Conference on Information Processing in Paris, showcasing GPS's application to diverse tasks such as symbolic logic proofs and chess endgames.[14] The program's evolution continued into the early 1960s, culminating in a detailed exposition in the 1963 anthology Computers and Thought, where Newell and Simon's chapter "GPS, a Program that Simulates Human Thought" highlighted its simulation of cognitive processes and influence on artificial intelligence research.[15]Key Contributors
Allen Newell, a researcher with a background in mathematics and physics who transitioned into computer science at the RAND Corporation, played a central role in the development of the General Problem Solver (GPS) by leading the design of its programming architecture and overall structure.[8] Newell, along with colleagues, co-authored key reports on GPS, emphasizing its mechanisms for simulating human-like problem solving.[16] His contributions extended to broader AI research, earning him the A.M. Turing Award in 1975 shared with Herbert A. Simon for foundational work in artificial intelligence and information processing.[17] Herbert A. Simon, a psychologist and economist, provided the cognitive theoretical foundation for GPS, drawing on human decision-making models to inform its problem-solving strategies.[18] Simon contributed to GPS through analyses of human protocols in problem solving, which helped shape the program's heuristic approaches.[19] For his pioneering research into decision-making processes, including bounded rationality concepts influential in GPS's design, Simon received the Nobel Prize in Economic Sciences in 1978.[20] J.C. Shaw, a computer scientist at the RAND Corporation, was essential for the technical execution of GPS, implementing components of the Information Processing Language (IPL) used to code the program and handling early programming tasks.[11] Shaw's work on IPL, developed in collaboration with Newell and Simon, enabled the list-processing capabilities critical to GPS's operation on the JOHNNIAC computer.[21] Though less recognized than his co-developers, Shaw's contributions were integral to realizing the system's functionality.[22] The development of GPS also benefited from institutional support at RAND, where Shaw advanced IPL as a versatile programming tool, and the organization's computational resources, including access to the JOHNNIAC, facilitated the program's implementation and testing.[19][11]Theoretical Foundations
Means-Ends Analysis
Means-ends analysis serves as the core heuristic strategy in the General Problem Solver (GPS), a method that systematically identifies discrepancies between the current problem state and the desired goal state, then selects operators to diminish those differences.[1] This approach enables GPS to navigate complex problems by focusing on functional transformations rather than exhaustive enumeration, classifying objects according to their roles in achieving intermediate ends.[1] The process operates recursively: once a difference is detected, GPS generates a subgoal aimed at applying a suitable operator to reduce it, subsequently addressing any new differences that emerge from this application until base cases—such as no remaining differences or primitive operations—are reached.[1] This recursive decomposition creates a hierarchy of subgoals, allowing the system to break down intricate tasks into manageable steps while maintaining a directed path toward the overall objective.[1] Central to this strategy are components such as operator selection, which prioritizes transformations relevant to the specific difference identified, often through pattern matching against operator preconditions and effects.[1] Backtracking is incorporated to handle failures, wherein unsuccessful subgoals prompt GPS to abandon the current path and explore alternative operators or differences.[1] The theoretical foundation of means-ends analysis draws from empirical studies of human cognition, particularly think-aloud protocols collected from college students solving symbolic logic problems, which revealed patterns of discrepancy reduction and subgoal formation mirroring the GPS mechanism.[23] These protocols demonstrated that human problem solvers intuitively employ similar heuristics, oscillating between goal states and means to achieve them, thereby validating the model's psychological plausibility.[23] Formally, the means-ends analysis in GPS follows these structured steps:- Identify the difference: Compare the current state (object A) with the goal state (object B) to pinpoint the primary discrepancy (d).[1]
- Select an operator: Search the available operators for one whose effects can reduce d, based on relevance criteria such as partial matching.[1]
- Apply and test: Establish a subgoal to enable the operator's application if necessary, execute it to transform the state, and evaluate the outcome.[1]
- Recur on new differences: If the goal is not achieved, repeat the process on any residual or newly introduced differences arising from the transformation.[1]