Wednesday, December 08, 2010

Google AI Challenge

For the past month or so I've been participating in the Google AI Challenge. The contest itself is quite interesting; you're supposed to write an AI to play a game similar to Galcon, and your bot will be pitted against other bots.

Now, the game is not quite as abstract, because what you're doing is moving ships around and attacking or defending; you can sort of explain or rationalize each move, or imagine some flavor or dramatic backstory to it. I find this to be good because you can actually do pretty well with heuristics or relatively simple decision rules.

Let me spend some time crowing about my bot, which I think did pretty well (446/4617 entries, or 90th percentile). To be honest, it's not all that elegant, being cobbled together from many generations of bots. The core algorithm is simple to describe: For each turn, each planet sends all (all!) its ships to attack a suitable target, which is determined by its distance, growth rate, owner, and number of defenders. There's also a simple defence algorithm in place to assist planets that are under siege, and a routine to expand optimally during the first turn. Surprisingly it did quite well, though I don't forsee it evolving further due to its limiting framework.

You can review some of the final matches at the bot's history page. Just click on "View Game" to view a game.

No comments: