AI Tested on 'Super Mario Brothers' Game

AI Tested on 'Super Mario Brothers' Game
Eric Bland, Discovery News

http://dsc.discovery.com/news/2009/08/17/super-mario-brothers.html

Aug. 17, 2009 -- Human players might have defeated Bowser decades ago in the original Super Mario Brothers video game, but a new competition is pitting computers against Koopa Troopas to save Princess Toadstool.



The contest is designed to evaluate the effectiveness of artificial intelligence programs.

"Basically we need a good way to compare different artificial intelligent techniques," said Julian Togelius, an assistant professor at IT University of Copenhagen and who, along with his colleague Sergey Karakovskiy, is organizing the competition.

"Computer games have a design that is relevant to humans, are fast paced and well defined. And besides, everyone loves games."

The computer programs will pit Mario and his brother, Luigi, against the same Goombas, Piranha Plants and Bullet Bills that human players have confronted for decades.

The specific levels, however, will be new to human and computer players alike.

Togelius has developed a random level generator that will create dozens of new, never-before-seen levels. To the possible chagrin of frustrated human players, the original Super Mario Brothers levels would likely be too easy for a computer, said Togelius.



Togelius will keep the exact number of levels a secret to both man and machine until shortly before the conference, when he plans to play every computer-generated level himself to test its difficulty.

For humans, with our enormous amount of cultural information acquired over a lifetime, learning how to defeat Bowser and rescue the Toadstool Princess can be a relatively easy proposition. "It's actually really unfair to the computer in one sense," said Togelius.

There are two broad approaches that Togelius expects programmers will use to keep Mario safe.

The first is artificial evolution. Computer programmers create many different controllers, let them loose on the game, evaluate their effectiveness, eliminate the worst controllers and reproduce the best controllers. Artificial evolution is effective, but time-consuming.

Another technique is called temporal difference learning. Say Mario is next to a short pipe with a mushroom shaped Goomba approaching from behind. Mario can can squish the Goomba or jump over the wall. With temporal difference learning, the AI plays out both scenarios, finds the best one and then applies that to the next scenario. The computer learns from each situation as the game progresses.

Robert Baumgarten is a Ph.D. student at Imperial College London developing his own Mario AI with another approach.

"I gave it all the basic instructions, but I don't really know what the AI would do," said Baumgarten. This technique is called pathfinding, since the computer finds its own way once these instructions are programmed.

At first Baumgarten's AI liked to run fast and constantly jump over enemies, and occasionally into pits. A few tweaks to his program corrected the program, and the computer stopped jumping into holes.

Baumgarten's AI also had some pleasant surprises. Without programming, the AI learned to grab the shells from defeated enemies and use them to destroy other enemies.

"This nice behavior sometimes just appears," said Baumgarten. "We try to optimize the behaviors that will lead to success."

The competition will be decided by the AI that can complete the most levels. The winner will be revealed at two upcoming conferences: the Games Innovation Conference at the end of August and the IEEE Symposium on computational Intelligence and Games in early September.