Saturday, December 13, 2008

AI vs TCS: Old School Lispers vs Traveller Grognards

I remember reading about Trillion Credit Squadron in the Journal of the Traveller's Aid Society back when I was a kid, playing Traveller (well, mostly rolling up characters and subsectors and buildng and mapping ships, but still). The idea is: you get a trillion credits to create a naval squadron using the rules in Traveller Book 6: High Guard. Then the squadrons beat on each other till one is left standing, in an apocalyptic battle. People from all over could submit their squadrons. I guess it was play-by-mail or something?

Anyway, Artificial Intelligence researcher Douglas B. Lenat decided to use TCS as a way to work on artificial intelligence in a "real" domain, that is, the computer had to compete with humans. He was working with heuristics, ways to take shortcuts to solutions across the immense and unnavigable search space of possible answers to questions. Humans use heuristics; up until that point computer AI work had mostly focused on brute force travels through search space, but the limitations of that approach had become very apparent. But brute force is conceptually easy and heuristics are hard to understand and optimize.

Anyway, he had the computer run a gazillion simulations of the TCS, starting with ideas about how to win that *he* provided, but with those ideas gradually supplanted by experience in simulated combats. Eventually the computer had evolved its own ideas about how to win, and they were... unorthodox. The computer had learned how to break the system: make a large number of tiny but very heavily armored ships, and count on outlasting the enemy -- be able to lose dozens and dozens of ships and still have enough left, when the last enemy ship is worn to the ground, to win.

He crushed the competition in 1981. In 1982 they changed the rules at the last minute, hoping to throw off the computer, but it still dominated the game. Finally they asked him not to compete in 1983, saying if he did they would shut down the game after that, I suppose because they were frankly sick of watching this highly effective but boring and annoying strategy keep on winning.

The whole story is well worth reading.

Little did I expect to find a story about original edition Traveller on the Programming Reddit. (Note: some of the Redditors find the story dubious, on the grounds that if that shit worked we'd still be using it today, and that hype-filled stories about AI were the order of the day back in the early-to-mid 80s, and the hype seldom panned out. So... grain of salt. But it's still a great story.)

2 comments:

Anonymous said...

Hey Ed. Book 6 was Scouts. Book 5 was High Guard.

I don't get many moments to let my geek flag fly... I figure that was just one of them.

Ed

Ed H said...

Damn! A little bit of synaesthesia getting the better of me. 6 is a light-blue number in my mind, and High Guard's lettering was light blue. 5 is red-orange, which associates with Mercenary in my mind. Despite the fact that each of those books is numbered one less than that.

Your geek flag flies high indeed!