Heuristic Discovery in Lenat's AM and EURISKO Programs

Douglas Lenat's Automated Mathematician (AM) and EURISKO programs represent foundational milestones in symbolic artificial intelligence, demonstrating how machines can discover new concepts and strategies through heuristics. Developed in the late 1970s and early 1980s, AM used a set of predefined rules to explore mathematical set theory, successfully rediscovering fundamental concepts like prime numbers and Goldbach's conjecture. Recognizing AM's inability to generate new rules of discovery, Lenat created EURISKO, an advanced system capable of modifying its own heuristics to adapt to entirely new domains, ranging from circuit design to strategic naval warfare. Together, these programs illuminated both the immense potential and the structural limitations of automated heuristic discovery.

The Automated Mathematician (AM)

Created by Lenat for his 1976 Stanford PhD dissertation, the Automated Mathematician was designed to model mathematical discovery not by proving known theorems, but by proposing interesting new concepts. AM began with 115 basic concepts of set theory—such as sets, bags, equality, and operations like union and intersection—and 243 heuristic rules.

Heuristics in AM functioned as rules of thumb that guided the program toward "interesting" mathematical territory. For example, a heuristic might suggest that if a function is interesting, looking at its inverse might also be interesting. Another heuristic might evaluate a concept as more interesting if it accidentally coincides with another established concept.

AM operated using an agenda-driven control structure. It generated a queue of tasks, ranked them by an "interestingness" score calculated by its heuristics, and executed the top task. Through this method, AM autonomously progressed from basic set theory to arithmetic. It defined the concept of cardinality (numbers), discovered addition, multiplication, and eventually isolated prime numbers. It even formulated Goldbach’s conjecture (every even integer greater than 2 is the sum of two primes) and the fundamental theorem of arithmetic.

The Limitations of AM

Despite its early success, AM eventually hit a wall. As the program moved further away from its initial set-theory concepts into complex number theory, its progress slowed and eventually halted.

The core issue was that AM's 243 heuristics were static. While the program could discover new mathematical concepts, it could not discover new heuristics to help it navigate those new concepts. The rules that worked well for basic set theory were inadequate for advanced number theory. Furthermore, subsequent analysis by Lenat and other researchers revealed that much of AM's success was inadvertently aided by the properties of the LISP programming language. Small syntactic changes in LISP expressions often resulted in meaningful mathematical mutations, a quirk that could not be relied upon for broader scientific discovery.

EURISKO: Evolving the Heuristics

To overcome AM’s stagnation, Lenat developed EURISKO in the late 1970s. The primary objective of EURISKO was to apply heuristic discovery to the heuristics themselves. If AM discovered concepts, EURISKO was built to discover the rules of discovery.

To achieve this, Lenat changed how heuristics were represented. In AM, heuristics were rigid blocks of LISP code that the program could execute but could not easily read or alter. In EURISKO, heuristics were represented as "units" or frames—the exact same data structures used for standard concepts. A heuristic had slots for its conditions, its actions, and its overall worth.

Because heuristics were treated just like any other concept, EURISKO could apply its meta-heuristics to modify, combine, or delete existing heuristics based on their performance. If a heuristic consistently led to dead ends, its "interestingness" value dropped, and it was used less frequently. If a heuristic proved useful, EURISKO would attempt to specialize or generalize it to create new, potentially better rules.

Real-World Applications of EURISKO

Unlike AM, which was confined to mathematics, EURISKO was tested across various domains to prove the generality of self-modifying heuristics.

One of its most famous triumphs occurred in the Traveller Trillion Credit Squadron competition, a complex war game where players design fleets of futuristic warships within strict budget and engineering constraints. EURISKO was fed the rules of the game and tasked with evolving a winning fleet. By mutating fleet configurations and testing them against simulated opponents, EURISKO discovered a loophole in the game's rules: a massive fleet of tiny, unmoving, heavily armed ships paired with a single fast ship to force draws when losing. EURISKO won the national championship in 1981. After the game organizers changed the rules to ban its strategy, EURISKO found a new, entirely different loophole and won again in 1982.

EURISKO also made a significant contribution to Very Large-Scale Integration (VLSI) circuit design. Tasked with exploring three-dimensional microchips, EURISKO applied a heuristic favoring symmetry and discovered a high-density, three-dimensional NAND/OR gate structure that human engineers had not previously considered.

The Legacy of Heuristic Discovery

While EURISKO successfully demonstrated that a symbolic AI could modify its own rules and adapt to new environments, it eventually encountered its own bottleneck. Lenat realized that for EURISKO to make leaps in complex domains, it needed a massive amount of foundational knowledge. Without a broad understanding of how the world works, the program spent too much time rediscovering basic truths or exploring nonsensical paths.

This realization directly led Lenat to abandon pure heuristic discovery in 1984 to start the Cyc project. Cyc shifted the focus from discovering rules in a vacuum to manually encoding millions of pieces of human "common sense" knowledge, laying the groundwork for modern knowledge graphs and ontologies. Ultimately, AM and EURISKO proved that symbolic manipulation guided by heuristics could mimic human creativity, while simultaneously exposing the necessity of vast domain knowledge in artificial intelligence.