Sharing my thoughts on software development

Sunday, February 28, 2010

Google AI Challenge

I have recently competed in Google AI Challenge, it was a lot of fun and I have learned quite a few things. Here is a quick explanation of the strategy I employ.

First it checks to see if two bots are seperated.
If two bots are connected, it will use Minimax/Alpha Beta Pruning to determine the best move it should take. The evaluation functions is as follows:
  1, if I win: +1000; opponent wins: -1000
  2, if disconnected, and I have more open spots: +800; opponent has more open spots: -800; same: 0; Open spots is determined by flood fill.
  3, if still connected,
    find articulation points and divide map into zones
    find the largest zones
    use breadth first algorithm to divide the zones into spots I can reach first and spots enemy can reach first
    return final score as spots I can reach first - spots enemy can reach first
The whole Alpha Beta Pruning process is wrapped using a Iterative Deepening loop.

When two bots are seperated, simply use a breadth first algorithm to determine how many open spots are left after each move using flood fill. Then choose the move that leaves the most spots open, in case two moves are equally good, hug the wall.

It is written in C#, and can be found here: http://github.com/analyst74/Tron-Bot

Update:  here is a great write up about the challenge and many related links http://www.benzedrine.cx/tron/