If Frank was a computer program...

[virgil]

The entire article can be read HERE, but I'll quote the pertinent part, since it mainly talks about basketball.

In 1981, a computer scientist from Stanford University named Doug Lenat entered the Traveller Trillion Credit Squadron tournament, in San Mateo, California. It was a war game. The contestants had been given several volumes of rules, well beforehand, and had been asked to design their own fleet of warships with a mythical budget of a trillion dollars. The fleets then squared off against one another in the course of a weekend. “Imagine this enormous auditorium area with tables, and at each table people are paired off,” Lenat said. “The winners go on and advance. The losers get eliminated, and the field gets smaller and smaller, and the audience gets larger and larger.”

Lenat had developed an artificial-intelligence program that he called Eurisko, and he decided to feed his program the rules of the tournament. Lenat did not give Eurisko any advice or steer the program in any particular strategic direction. He was not a war-gamer. He simply let Eurisko figure things out for itself. For about a month, for ten hours every night on a hundred computers at Xerox PARC, in Palo Alto, Eurisko ground away at the problem, until it came out with an answer. Most teams fielded some version of a traditional naval fleet—an array of ships of various sizes, each well defended against enemy attack. Eurisko thought differently. “The program came up with a strategy of spending the trillion on an astronomical number of small ships like P.T. boats, with powerful weapons but absolutely no defense and no mobility,” Lenat said. “They just sat there. Basically, if they were hit once they would sink. And what happened is that the enemy would take its shots, and every one of those shots would sink our ships. But it didn’t matter, because we had so many.” Lenat won the tournament in a runaway.

The next year, Lenat entered once more, only this time the rules had changed. Fleets could no longer just sit there. Now one of the criteria of success in battle was fleet “agility.” Eurisko went back to work. “What Eurisko did was say that if any of our ships got damaged it would sink itself—and that would raise fleet agility back up again,” Lenat said. Eurisko won again.

Eurisko was an underdog. The other gamers were people steeped in military strategy and history. They were the sort who could tell you how Wellington had outfoxed Napoleon at Waterloo, or what exactly happened at Antietam. They had been raised on Dungeons and Dragons. They were insiders. Eurisko, on the other hand, knew nothing but the rule book. It had no common sense. As Lenat points out, a human being understands the meaning of the sentences “Johnny robbed a bank. He is now serving twenty years in prison,” but Eurisko could not, because as a computer it was perfectly literal; it could not fill in the missing step—“Johnny was caught, tried, and convicted.” Eurisko was an outsider. But it was precisely that outsiderness that led to Eurisko’s victory: not knowing the conventions of the game turned out to be an advantage.

“Eurisko was exposing the fact that any finite set of rules is going to be a very incomplete approximation of reality,” Lenat explained. “What the other entrants were doing was filling in the holes in the rules with real-world, realistic answers. But Eurisko didn’t have that kind of preconception, partly because it didn’t know enough about the world.” So it found solutions that were, as Lenat freely admits, “socially horrifying”: send a thousand defenseless and immobile ships into battle; sink your own ships the moment they get damaged.

...

“In the beginning, everyone laughed at our fleet,” Lenat said. “It was really embarrassing. People felt sorry for us. But somewhere around the third round they stopped laughing, and some time around the fourth round they started complaining to the judges. When we won again, some people got very angry, and the tournament directors basically said that it was not really in the spirit of the tournament to have these weird computer-designed fleets winning. They said that if we entered again they would stop having the tournament. I decided the best thing to do was to graciously bow out.”
It isn’t surprising that the tournament directors found Eurisko’s strategies beyond the pale. It’s wrong to sink your own ships, they believed. And they were right. But let’s remember who made that rule: Goliath. And let’s remember why Goliath made that rule: when the world has to play on Goliath’s terms, Goliath wins.

[angelfromanotherpin]

Good playtesting of historical war games always includes some people who don't know or care about the conventions of the day. That's how you find out about the bug where charging uphill into phalanxes is a mysteriously good idea. Sensibly informed people probably won't try that.

[Heath Robinson]

Good old genetic algorithms. Cold, merciless, antisocial, ignorant, and stridently literal. Ridiculously inefficient compared to any sort of design process, thiough. Ten hours a night on a hundred machine cluster is a hilarious amount of processing power.

[Neeeek]

Good old genetic algorithms. Cold, merciless, antisocial, ignorant, and stridently literal. Ridiculously inefficient compared to any sort of design process, thiough. Ten hours a night on a hundred machine cluster is a hilarious amount of processing power.

I could do the same calculations on my laptop in about 5 minutes today, so it's not really all that much processing power.

[Juton]

Good old genetic algorithms. Cold, merciless, antisocial, ignorant, and stridently literal. Ridiculously inefficient compared to any sort of design process, thiough. Ten hours a night on a hundred machine cluster is a hilarious amount of processing power.

Not in 1981 it wasn't. Back in 81 that amount of processing power wouldn't have even equaled a little netbook, or a good desktop from the late 90s.

This algorithm sounds like it's superior to several design processes though, because it defeated how many fleets that where lovingly tailored by the human opponents.

[Heath Robinson]

There have been approximately 10 doublings since 1980. That means that computing speed has been multiplied by 1024. So 100 computers operating for 10 hours every night for 30 nights back then is still equivalent to about a day of continuous operation by equivalent machines today.

I'm pretty sure that the other people involved in the competition did not spend 24 hours deciding on their composition.

[Surgo]

There have been approximately 10 doublings since 1980.

Uh, source? A citation to a theoretical law (that doesn't even talk about computing speed) isn't exactly valid when we have actual historical data.

[Juton]

There have been approximately 10 doublings since 1980. That means that computing speed has been multiplied by 1024. So 100 computers operating for 10 hours every night for 30 nights back then is still equivalent to about a day of continuous operation by equivalent machines today.

I'm pretty sure that the other people involved in the competition did not spend 24 hours deciding on their composition.

Moore's law doesn't tell the whole story, especially with regards to parallel computation.

I think the point of the article still stands, a rational outsider was able to out perform experts. In this case it's because all the experts started with some ideal of what a fleet should look like and worked towards that, when it reality that wasn't the real ideal at all.

I'm sure some of those players spent 6-8 hours on their force design, most likely they spent more if they where allowed to make their own ships. So it wasn't a question of the computer doing more brute force calculations, it was player bias.

[Heath Robinson]

There have been approximately 10 doublings since 1980.

Uh, source? A citation to a theoretical law (that doesn't even talk about computing speed) isn't exactly valid when we have actual historical data.

I tried looking for the historical data. I didn't find any, so I had to use recourse to approximations from said hypothetical law. I'm not ignorant of the weakness of that citation.

Looking again, after a short break for tea, I can find the frequency of early IBM PCs stated as 4.77 MHz. Assuming that is a valid basis for an estimate of the computing power of each machine used (I don't recall seeing the kind of machine mentioned in the article, for all we know they could be mainframes, and MHz is not the sole decider of computing power) and comparable OS resource consumption between then and now, the 100 machine cluster running for 10 hours still compares quite reasonably to modern machine running for 1 hour.

Given that the original approach utilised 30 000 machinehours, it is still not a trivial amount of computation today.


GAs are still inefficient in a large number of ways because they are so wasteful and erratic. As a relation of beam search they can end up specialising in some portion of the search space, ignoring the existence of greater maxima elsewhere. The fact that the rules for this particular game create a single maxima is happenstance.

[Juton]

GAs are still inefficient in a large number of ways because they are so wasteful and erratic. As a relation of beam search they can end up specialising in some portion of the search space, ignoring the existence of greater maxima elsewhere. The fact that the rules for this particular game create a single maxima is happenstance.

The thing about GAs is that you can't be sure that the answer they return is actually the best answer, or only one of the best. We can be sure that the local maxima returned by the system in the article was better than what the humans where using.

I find it odd that you say that GAs are wasteful and erratic, sure they're not optimal if you have an actual algorithm and the processing power to use it. They work when you don't have an actual algorithm, and they can compute an answer, not always the best one, to an NP complex question in a reasonable amount of time.

[Koumei]

It's a good thing times have changed since then, and companies don't churn out shitty, unbalanced rule sets for their games, then blame the user when someone picks up on their mistakes and makes an awesome force with said shitty ruleset.

OH WAIT A MINUTE.

[CatharzGodfoot]

Now that algorithms can consistently beat grandmasters at chess, you don't need shitty unbalanced rules to be bested by a "rational outsider". Also, I'd like to think that Frank actually understands the semantics of D&D.

[Surgo]

Heath_Robinson, I do not really understand your critique. Yes, GAs and other AI random search approaches tend to converge on local maxima -- that does not make them useless (or no one would use them). For that matter, they aren't worse or less efficient than designed processes because, again, if they were, no one would use them.

The linked article is pretty interesting for the rest of it, by the way. Even though it seems to get a bit wrong in basketball (I think the constant full-court press is way common in youth basketball than the author wants you to believe), it strikes me as an awful lot of people (basketball parents and coaches, wargames people, whatever) qqing and falling back on that old "baaaawww, but playing to win is wrong" nonsense whenever someone comes along and beats them at their own game because they're playing to win.

[Manxome]

Genetic algorithms are a clever technology and useful for a lot of stuff. But, as prof. Bart Massey of PSU put it, "If there are two ways to do something, and one of them is a genetic algorithm, the genetic algorithm is the wrong way." Maybe not strictly accurate, but definitely a good rule-of-thumb.

Having some playtesters with no context is certainly useful, because they can discover that some strategy that "obviously wouldn't work" actually works quite well. On the other hand, you also want some playtesters with a ton of background knowledge and who understand how things are intended to be used, so that your testers don't blunder around in the dark using strategies that are genuinely bad, and never realize it because no one who knows what they're doing is there to crush them. I've certainly had playtest sessions for some of my games where a tester reports "X sucks", and then I tried playing with X and kicked their ass because I knew what all of the intended synergies and tactics were.

Now that algorithms can consistently beat grandmasters at chess, you don't need shitty unbalanced rules to be bested by a "rational outsider". Also, I'd like to think that Frank actually understands the semantics of D&D.

It's dangerous to generalize from chess. Back in the day, people thought that chess would be an impossible challenge for computers, that they'd never play at a grandmaster level, and they actually had fairly defensible reasons for thinking that--in my opinion, it is still quite possible that a computer will still never play chess "like" a human grandmaster. But it turns out there's a radically different approach to playing chess, one that humans suck at but that computers can do amazingly well, and it's a technique that does not extend gracefully to other games or applications.

In actuality, Chess turns out to be part of a very small class of games that is really easy for computers to play, because it has a very small move space and the difference between novice and grandmaster play is whether you look 3 or 7 moves ahead.

Look at something moderately complex, like a RTS game, and even with significant emphasis placed on areas where computers trivially outperform humans (like reaction time, and doing many things in parallel) and frequently cheating in the computer's favor (perfect knowledge, free resources, etc.) and you still end up with human players who fight like 5 AIs at once and win. Admittedly, those AIs aren't designed with hundreds of expert man-months or running on custom-designed supercomputers or anything, but their performance is downright embarrassing.

I listened to a talk about 5 years ago from someone who helped write a computer program that played general games whose rules were described in first-order logic. I believe the rules of the contest were that the computer program had a few hours after receiving the rules to "think" about them before the game started, and then would have several minutes per move for a game like othello or open-hand poker (the games weren't allowed to have hidden information). He made the point that if someone in the audience were given the rules to the game in first-order logic they probably wouldn't make a single legal move, but presenting the rules in that format is obviously designed to make things easier for the computers, and I don't think they could have competed with a third-grader who understood the rules.

[Crissa]

Didn't anyone point out that clock cycles aren't all that expanded? So did the breadth of each processor (we're using a 64-bit language while that was an incomplete 4-bit language) and even some netbooks have more than one processor.

Of course, we waste more cycles on niceties, but we have more co-processors than most systems at the time.

An AI still can't beat a trained Go player.

-Crissa

[CatharzGodfoot]

An AI still can't beat a trained Go player.

But can you honestly look at a finished Go board and say who won? Because I can't.

[Juton]

I've been learning how processor speed has been increasing in class and what the limitations are. Within 10 years we will have reduced transistors to the smallest possible, which is about 10 atoms long. That will leave us with computer chips that aren't as powerful as a human brain, but we can hook up a lot of them to work together. I wonder if there will still be types of problems that humans will still be better at than computers, it's not totally insane to think it's possible, as human brains have an architecture completely different than the computers we use.

[Crissa]

An AI still can't beat a trained Go player.

But can you honestly look at a finished Go board and say who won? Because I can't[/].

Any beginner can. It's one of the first things you learn.

The answer lies in how many spaces are surrounded by only one color, and who has the most of these, basically.

Now that I know how to play, it's endlessly fascinating to watch.

-Crissa

[Jilocasin]

Now that I know how to play, it's endlessly fascinating to watch.

True dat. I love go.