Hacker News new | past | comments | ask | show | jobs | submit login
Why AM and Eurisko Appear to Work (1983) [pdf] (aaai.org)
36 points by zetalyrae 20 days ago | hide | past | favorite | 17 comments



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


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.


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.


That’s a good subtitle for my PhD thesis. “Novel but disappointing”.


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.


>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...


I can't link to the exact sources, it's probably almost 10 years since I looked into this last thinking of writing an article on it :) What I remember is that there were discussions on Usenet and the Steve Jackson Games forums with contributions from people who were involved at the time.

It's definitely true that Lenat won those two tournaments, and that the fleet design was computer-assisted. But optimizing a fleet would have been a relatively simple search problem, and he was the only competitor with a minicomputer. When the problem could have been solved by any number of simple algorithms, it's hard to take those solutions as evidence of a one-of-a-kind self-improving AI.

But Lenat isn't just saying that Eurisko searched the space effectivelyl. Instead there are all these stories about amazingly clever strategies that Eurisko found. But most of those stories appear to be incompatible with the actual rules of the game. And the stories aren't even self-consistent, but seem to change on every telling.

Here's some examples, mostly from tracking down the original Traveller High Guard and Trillion Credit Squadron supplements, and trying to map the stories to the actual game concepts:

Eurisko's design for ships that supposedly fired on themselves if damaged, to self-destruct and ensure that the minimum agility of the fleet did not drop? The rules only allow firing on the enemy. Could not have happened. Total fabrication.

The story about the "fuel tenders", that Eurisko made into warships? A minimum reserve was not actually a requirement in the rules. But if it were, there is just no chance that you'd need computer optimization would figure that out.

The story about the Eurisko's unhittable, unarmed, super-fast lifeboat that always guaranteed a draw? By the tournament rules a fleet that had no weapons left to fire was deemed to have lost. (In the link you posted with the fleet, I assume that this is the point of the Bee by abusing the Emergency Agility rule. But it should work out to a -8 DRM and thus hittable.)

The claim that he was told to quit the tournament or it'd be shut down? Disputed by the people who ran the tournament. Why would they need to threaten the cancelation of the tournament? They could just ban Lenat, or ban computer aid, with no repercussions. It's just pure embellishment.

The story about how all the opponents resigned after one round, one even before the first round, because it was so obvious that they'd lost? That's just absurd. Nobody goes to board game tournaments to resign without playing, and this is totally incompatible with the legend that Eurisko's designs looked strange and inefficient.

In terms of inconsistencies, when Lenat told the story in the '80s, his fleets were supposed to be slow and heavily armored. When he told the story to Malcom Gladwell 20 years later, he instead had an uncountable number of tiny, defenseless ships with big guns, and that the enemy could just not kill all of those tiny ships in time. A diametrically opposite story (and the latter one, as one should be used to by now, not possible by the rules since the rules capped the number of pilots for the fleet at 200, and even a small ship required at least one pilot).

Basically, when Lenat says something trivial but verifiable about Eurisko and these tournaments, it's highly likely to be obviously untrue. Just completely made up for a punchier just-so story. Why would we believe his unverifiable claims on non-trivialities, like the nature of his super-AI?


Good points. All this could be solved if the system was reproducible. Given that Cyc is meant to be the successor to Eurisko, I'm surprised they never tried a public, reproducible demo with OpenCyc designing a winning fleet, or playing a game after being taught the rules of it.

But I think the broader point is that even if it could self modify, Eurisko was incapable of learning. Like every other GOFAI program, it exists in its own carefully programmed universe of logic. And it's usefulness as a stepping stone to AGI is limited.

GOFAI research continues today under the label "cognitive architecture".


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!



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...


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.


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)

Related:

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)


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?


Is it possible to find Eurisko source?


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


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: