Why AM and Eurisko Appear to Work (1983) [pdf]

https://www.aaai.org/Papers/AAAI/1983/AAAI83-059.pdf

by zetalyrae • 5 years ago

36 17 5 years ago

zetalyrae6• 5 years ago

Context: AM (Automated Mathematician) is a program that starts with a knowledge base of set theory and heuristics and builds its way up to natural numbers, Goldbach's conjecture (depending on how you interpret the print-outs), etc. Eurisko takes AM one step further by having heuristics to guide the development of new heuristics.

I read this because I'm working on a history/review of AM and Eurisko. It's one of the most fascinating episodes in the history of AI: a good old fashioned symbolist AI program that has all these impressive success stories, and defines the SOTA. Source code was never published and it was never reproduced. Eliezer Yudkowsky said[0] of Eurisko that it "may still be the most sophisticated self-improving AI ever built". Like something out of a Borges story!

Further reading for those interested:

  AM: An artificial intelligence approach to discovery in mathematics as heuristic search.
    Douglas B. Lenat. 1976.
    https://stacks.stanford.edu/file/druid:sb448rj9905/sb448rj9905.pdf

  The Nature of Heuristics I
    Douglas B. Lenat. 1982.
    http://blog.funcall.org/docs/am-eurisko/Heuristics_I.pdf

  The Nature of Heuristics II
    Douglas B. Lenat. 1983.
    http://blog.funcall.org/docs/am-eurisko/Heuristics_II.pdf

  The Nature of Heuristics III
    Douglas B. Lenat. 1983.
    http://blog.funcall.org/docs/am-eurisko/Eurisko_Heuristics_III.pdf

  On the thresholds of knowledge.
    Douglas B. Lenat, Edward A. Feigenbaum. 1991.
    http://blog.funcall.org/docs/am-eurisko/On_the_thresholds_of_knowledge.pdf

  AM: A Case Study in AI Methodology
    G.D. Ritchie, F.K. Hanna. 1984.
    https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.4342&rep=rep1&type=pdf

AM has been reimplemented[1] in Prolog.

[0] https://www.lesswrong.com/posts/rJLviHqJMTy8WQkow/recursion-...

[1] https://github.com/akkartik/am-utexas/tree/master

jsnell2• 5 years ago

Did Eurisko ever have any replicable success stories?

The only success story of any kind I've heard, repeatedly, were the two Traveller tournaments. But Lenat's telling of that story is disputed by the people who were involved in that community, and doesn't make much sense in some ways. And obviously it wasn't replicable either.

So honestly my assumption for the last couple of decades has been that Eurisko was all smoke and mirrors.

akkartik• 5 years ago

Yeah that's the word on the street. However, I think Eurisko is worth study even if we reframe it as a work of IA (Intelligence Augmentation) rather than AI. It seems extremely unlikely that Lenat could win the Travellers tournaments unaided.

zetalyrae6• 5 years ago

disputed by the people who were involved in that community

Can you link me to a source? I'm gathering the sources for the TCS tournament.

I think the success at TCS was real. Lenat wrote at length about this case. From my working-progress notes:

The winning fleet is describe here: http://members.pcug.org.au/~davidjw/tavspecs/best_tml/Starsh...

The results of the match were apparently published in the Journal of the Travellers Aid Society, issue #10, from 1981. There isn't an archived copy anywhere, sadly. Google's News Archive search turns up nothing for "Eurisko" or "Lenat".

In The Nature of Heuristics I, Lenat shares details of the TCS tournament (please excuse typos, the PDFs have bad OCR):

  EURISKO was given the rules of the game, and the constraints on the design process, and spent a great amount of time (roughly 500cpu hours on a Xerox Dolphin) managing a heuristically-guided evolution process. Fleets would fight, and the simulated battle would be analyzed (by some of EURISKO'S heuristics) to determine which design policies were winning, and--occasionally--what fortuitous circumstances could be abstracted into new design heuristics. An example of the former was when the Agility of ships gradually decreased, in favor of heavier and heavier Armor plating of the hulls. An example of the latter was when a purely defensive ship was included in an otherwise-awful fleet, and that fleet could never be fully defeated because that defensive ship, being very small, unarmored, and super agile, could not be hit by any of the weapons of the larger nearly-victorious fleet. The author culled through the runs of the program every 12 hours or so of machine time (i.e., each morning, after letting it run all night), weeding out heuristics he deemed invalid or undesirable, rewarding those he understood and liked, etc. Thus the final crediting of the win should be about 60/40% Lenat/EURISKO, though the significant point here is that neither Lenat nor EURISKO could have won alone. Most of the battles are tactically trivial, the contest being almost decided by the designs of the two fleets; that--and the thickness of the tulebooks--were the reason this appeared to be a valid domain for EUR1SKO.

  [...]

  Almost all the other entrants in the final tournament had fleets that consisted of about 20 ships, each with a huge spinal mount weapon, low armor, and fairly high agility, and a large number of secondary energy weapons (laser-type weapons). This contrasted with Eurisko's fleet, and such an enemy was rapidly decimated, at a loss of about a third of Eurisko's line ships, and no risk to its specialty ships.

  [...]

  The tournament directors were chagrined that a bizarre fleet-such as this one captured the day, and a similar fleet (though not so extreme) took second place. As a result, the rules for future years' TCS tournaments have been changed, to dramatically reduce the design singularities which EURISKO (work- ing with the author) found.

In The Nature of Heuristics II, Lenat writes about how Euriko's heuristics affected fleet design:

  A second use of R7 in tile naval design task, one which also inspired a rules change, was in regard to the fuel tenders for the fleet. The constraints specified a minimum fractional tonnage which had to be held back, away from battle, in ships serving as fuel tenders. R7 caused us to consider using warships for that purpose, and indeed that proved a useful decision: whenever some front-line ships were moderately (but not totally) damaged, they traded places with the tenders in the rear lines. This maneuver was explicitly permitted in the rules, but no one had ever employed it except in desparation near the end of a nearly-stalemated battle, when little besides tenders were left intact. Due to the unintuitive and undesirable power of this design, the tournament directors altered the rules so that in 1982 and succeeding years the act of 'trading places' is not so instantaneous. The rules modifications introduced more new synergies (loopholes) than they eliminated, and one of those involved having a ship which, when damaged, fired on (and sunk) itself so as not to reduce the overall fleet agility.

Here, R7 refers to the heuristic:

  R7: if f is an interesting function which takes a pair of A's as inputs,
      then define and study the coalesced function g(a) = ~f(a, a).

A frustrating thing about the papers on Eurisko is that the heuristics are only ever described in abstract, qualitative prose, and we never see the implementation details. "Interestingness" might be loosely defined somewhere. I think the heuristics were frames with hacky Lisp fragments as their slots.

My conclusion is: a lot of games are broken by "extreme" strategies that humans wouldn't think of but machines easily find. Sometimes, ignoring the labels and treating the game as a glass bead game, disconnected from the real world, helps. A lot of games that are hard for humans are easy for machines, because humans care about the "conceptual integrity" of the game, while machines just care about optimizing some metric. Humans may not think to try a strategy that makes sense within the formalism of the game but is incoherent with the concepts the game is supposed to represent, e.g., having foot soldiers attack aircraft.

So, for example, a machine might easily land on a strategy of having the fleet be a swarm of lightly armored ships, while a human player is thinking in terms of grand naval battles and crossing the line. See swarm tactics[0] and the Millennium Challenge 2002 wargame[1].

LessWrong user ChrisHallquist concluded[2] the same thing:

  My suspicion is that Lenat's TCS win tells us more about TCS than about EURISKO, that TCS is likely a game that's inherently vulnerable to the "find winning strategies by simulating a lots of games on a computer" meta-strategy. I've heard, for example, that battles are often tactically trivial, with the outcome of battles effectively determined by the composition of the two fleets (and fleet composition is what Lenat used EURISKO for). If that hypothesis is correct, though, it suggests it shouldn't be necessary to reimplement EURISKO specifically to get a program that's good at designing TCS fleets. If that turns out not to be the case, it would be evidence that there really is something special about EURISKO after all.

[0]: https://en.wikipedia.org/wiki/Swarming_(military)

[1] https://en.wikipedia.org/wiki/Millennium_Challenge_2002

[2] https://www.lesswrong.com/posts/Myr7PLikhzYgPFhuy/replicatin...

theamk• 5 years ago

Can you tell more about this?

Back when I first heard about the Eurisco story, I tried to find the other accounts but all I saw were the same story re-told multiple times.

Any links would be greatly appreciated!

blihp• 5 years ago

I thought Lenat was pretty up front about what Eurisko did and why it was nearly a one-trick pony. What I gathered from his writings was that he essentially used a Genetic Algorithm (which was novel at the time as it would have been a very early, possibly the first, implementation) to modify the Lisp code. So it was essentially randomly swapping out tiny snippets (i.e. Lisp atoms) of the code and managed to achieve good results because of the impedance match between the Lisp code and the problem domain.

So while I wouldn't say it was smoke and mirrors, Eurisko was both novel (for the GA approach) and disappointing (it had nothing resembling understanding of the problem) at the same time.

janzer• 5 years ago

There was a brief discussion/effort to reimplement Eurisko on LessWrong about a decade ago[0], of course it rapidly devolved into whether such effort would promote the end of the human race.

[0] https://www.lesswrong.com/posts/t47TeAbBYxYgqDGQT/let-s-reim...

zetalyrae6• 5 years ago

The hardest part of this is there just aren't enough implementation details to reverse engineer Eurisko.

Especially the heuristics are only ever described very abstractly.

dang• 5 years ago

A few small past threads:

Some documents on AM and EURISKO - https://news.ycombinator.com/item?id=18443607 - Nov 2018 (10 comments)

Why AM and Eurisko Appear to Work (1983) [pdf] - https://news.ycombinator.com/item?id=9750349 - June 2015 (5 comments)

Why AM and Eurisko Appear to Work (1984) [pdf] - https://news.ycombinator.com/item?id=8219681 - Aug 2014 (2 comments)

Early AI: “Eurisko, the Computer with a Mind of Its Own” (1984) - https://news.ycombinator.com/item?id=27298167 - May 2021 (1 comment)

Eurisko, The Computer With A Mind Of Its Own - https://news.ycombinator.com/item?id=2111826 - Jan 2011 (8 comments)

Let's reimplement Eurisko - https://news.ycombinator.com/item?id=656380 - June 2009 (25 comments)

Eurisko, The Computer With A Mind Of Its Own - https://news.ycombinator.com/item?id=396796 - Dec 2008 (12 comments)

also

https://news.ycombinator.com/item?id=1856635 - Nov 2010 (8 comments)

listic• 5 years ago

Is it possible to find Eurisko source?

zetalyrae6• 5 years ago

It was never published and IIRC Lenat claims it was lost. Which is not incredible. A lot from that era is lost.

Cybiote• 5 years ago

Here is a 1984 article on Eurisko: https://aliciapatterson.org/stories/eurisko-computer-mind-it...

From the article we learn Eurisko is more of an example of human machine symbiosis than of AI.

"Thus the final crediting of the win should be about 60/40% Lenat/Eurisko," he wrote, "though the significant point here is that neither party could have won alone. The program came up with all the innovative designs and design rules and recognized the significance of most of these. It was a human observer, however, (the author) who appreciated the rest, and who occasionally noticed errors or flaws in the synthesized design rules which would have wasted inordinate amounts of time before being corrected by Eurisko."

Lenat did not know much about the game and its search space was intractable for the AI. The combination of both was able to come up with unique solutions counter-intuitive to humans.

From a certain perspective, Eurisko could also be viewed as on the path to some next iteration of programming that never quite arrived. That is, programming languages stalled in the 70s, as Alan Kay notes in: http://worrydream.com/EarlyHistoryOfSmalltalk/

A look beyond OOP as we know it today can also be done by thinking about late-binding. Prolog's great idea is that it doesn't need binding to values in order to carry out computations [Col *]. The variable is an object and a web of partial results can be built to be filled in when a binding is finally found. Eurisko [Lenat *] constructs its methods—and modifies its basic strategies—as it tries to solve a problem. Instead of a problem looking for methods, the methods look for problems—and Eurisko looks for the methods of the methods. This has been called "opportunistic programming"—I think of it as a drive for more enlightenment, in which problems get resolved as part of the process.

This higher computational finesse will be needed as the next paradigm shift—that of pervasive networking—takes place over the next five years. Objects will gradually become active agents and will travel the networks in search of useful information and tools for their managers. Objects brought back into a computational environment from halfway around the world will not be able to configure themselves by direct protocol matching as do objects today. Instead, the objects will carry much more information about themselves in a form that permits inferential docking. Some of the ongoing work in specification can be turned to this task [Guttag ][Goguen].

Tongue in cheek, I once characterized progress in programming languages as kind of "sunspot" theory, in which major advances took place about every 11 years. We started with machine code in 1950, then in 1956 FORTRAN came along as a "better old thing" which if looked at as "almost a new thing" became the precursor of ALGOL-60 in 1961. In 1966, SIMULA was the "better old thing," which if looked at as "almost a new thing" became the precursor of Smalltalk in 1972.

Everything seemed set up to confirm the "theory" once more: in 1978 Eurisko was in place as the "better old thing" that was "almost a new thing". But 1983—and the whole decade—came and went without the "new thing". Of course, such a theory is silly anyway—and yet, I think the enormous commercialization of personal computing has smothered much of the kind of work that used to go on in universities and research labs, by sucking the talented kids towards practical applications.

I believe Eurisko operates on very similar principles as PI, which is detailed here:http://bactra.org/reviews/hhnt-induction/ in a fascinating review by Shalizi.

Unlike the classifier system, which acts on raw binary strings, PI rules and representations are Lisp expressions, and there are more structured representations of concepts, which are however still basically rule clusters. Again unlike the classifier system, which gets new rules by using a genetic algorithm on existing ones, PI has a number of specific inductive mechanisms --- specialization, generalization, abduction, and concept formation --- which are intended to be reminiscent of conscious experience, unlike the GA.

PI was invented by Holland, who is more famously known for his contributions to genetic algorithms and evolutionary computation. Those algorithms were meant to be used in a system like PI and not in the stand alone manner typical of today. Learning Classifier Systems being simplified versions of PI, are probably the closest concept to Eurisko in semi-active use. DreamCoder: https://arxiv.org/abs/2006.08381 is the latest development along this investigatory and very much underexplored path to Machine intelligence.

perl4ever• 5 years ago

I had to look up which came first the "Automated Mathematician" or the "Allied Mastercomputer".

I've had an eerie feeling every time Lenat's name came up because I read about Cyc in some popsci magazine decades ago, and then it remained in obscurity, but the last I heard of it, it was still being worked on.

It's the sort of thing you think - is there no publicity because it was a dead end, or because it worked too well to let just anybody mess with it?

Why AM and Eurisko Appear to Work (1983) [pdf]

Related Stories