Friday, September 14, 2007

2003 Gladiator-style 'wars' select out weak programs

Gladiator-style 'wars' select out weak programs

  • 10:00 12 July 2003
  • Exclusive from New Scientist Print Edition. Subscribe and get 4 free issues
  • Will

Computer scientists have found the ultimate way to debug their programs - let them compete against other programs in a gladiator-style tournament.

Dubbed Grid Wars II, the contest held at the ClusterWorld conference in San Jose, California, last month was like a software version of television's Robot Wars and Battle Bots. In each battle, programs fought to gain control of processing power in a huge parallel computer.

Besides giving computer scientists an excuse to tear themselves away from their terminals the contest also has scientific merit, according to some contestants. "Grid Wars gave me the opportunity to test my algorithm," says Mark Wenig, one of the finalists from NASA's Goddard Space Flight Center in Greenbelt, Maryland. "It is a perfect environment to test and compare different approaches."

The contest began with 236 different programs, submitted by universities, government research departments and software companies from around the world. The objective of each entrant was to fight for control of 2500 computer processors.

Attack or defence

A program can take over a neighbouring processor by firing virtual "bullets" at the program already occupying it. When a processor is hit three times the defending program loses control and is replaced by its aggressor. By communicating between occupied processors allied programs are able to coordinate an attack or defence.

Onlookers watched the algorithms on a screen that displayed each match. Each processor was represented by a square in a giant grid and each program by a different colour. To start off, programs fought it out in small groups. The winners of each group contest were then paired off in a 32-program knock-out contest.

When this was whittled down to the final two the atmosphere was nail-biting, says Matt Oberforger of Engineered Intelligence in Colorado, who organised the event. The final battle saw Wenig's program - created using genetic algorithms - take on a program designed by a computing student from Moscow State University.

Rogue and Cobra

NASA used a process that mimics natural selection to "evolve" the best fighting code, while the Russian chose to write his program by hand. "It was the US versus Russia, man against machine," says Oberforger.

For the first 400 out of 500 cycles the NASA program, "Rogue" was clearly dominating and had control of 1500 of the 2500 processors. But in the final moments the Russian contender, called Cobra, quickly defeated Rogue. "In the last hundred cycles the Russian program broke out and slowly ate up the genetic algorithm," says Oberforger. "Nobody really believed it would." The key to its success may have been its ability to communicate efficiently and hence spread quickly, he says.

No comments: