Archive: Google AI Challenge! (C#)

Note:  This used to be on my old blog.  That went down, but I still had the file, so here it is!

The (February 2010) Google AI Challenge was a programming contest held from 2/4/2010 - 2/26/2010.
I finished 28th out of 708 entrants. I wrote it in C#, because my most likely next job will have me working at Microsoft. Plus I wanted to try to win, so I didn't want to experiment with a language I've never studied (Python) or a language I've never been particularly good with (Lisp). I toyed with doing it in C++, but I'm more comfortable with C# right now.

My code is available (zipped up) here:

The Game

The challenge was to create an AI that would play the Tron Lightcycles game, also known as Snakes or Worms or Snafu.
In it, the two players begin in a rectangular board (sometimes with obstacles within the board). Simultaneously, each player moves one square in an available direction (N,E,S, or W), and the position the player vacates is replaced with a wall. The first player to hit a wall loses, but if both players hit a wall (or each other) at the same time, the game is a tie.

The Algorithm

My algorithm seemed to me to be pretty much straightforward and basic, right out of my college AI class. In fact, I had some known issues with my algorithm. And there were places where I figured it could be rewritten to be more efficient, whether it was just a code cleanup or a wasteful algorithm. Still, 680 participants ended up finishing behind me, so I guess I did enough.

Evaluation

My algorithm began with the evaluation code. Basically, this took the "current" state of the board, and gave an integer score based on how well my AI was doing.
In what I later learned was called using a Voronoi heuristic, I went through each square of the board, giving my AI 100 points if it was closer the square than the opponent, and subtracting 100 points if the opponent was closer. Positions that were walls went unscored.
This was not the best evaluation function. I knew early on there was an issue on certain boards where a bottleneck could easily separate some available positions with others.

#########
#   #   #
# 1##   #
#       #
#   #   #
#   #   #
#   #   #
#   #   #
#   #   #
#   #2  #
#   #   #
#   #   #
#########

In this example, player 2 isn't really in a particularly bad position. But my AI evaluates this board as being a great position for player 1. Player 1 is closer to all of the spots on the left side of the board, and some of the spots on the right side of the board (the upper ones), so player 1 is judged to have an advantage. Unfortunately for my AI, player 1's position isn't that strong - it's much closer to a tie. Not knowing that this board is evenly scored for players 1 and 2 was my AI's biggest issue.

Here's an example of a game that was lost because of this issue: http://csclub.uwaterloo.ca/contest/visualizer.php?game_id=4073327

I never got around to solving this problem before the contest ended, but apparently the #1 finisher, Andy Sloane, came up with an idea at 3am on the final day of the contest.

Lookahead

For my lookahead, I used a recursive algorithm, a variant of Negamax with alpha-beta pruning.

Basically this meant that for each possible move my AI could make, it would call my NegamaxAB function (sending the function a board that included the move made) , and whichever move returned the best score would be the move to make.
The NegamaxAB function would first check to see if the board it was given was a cutoff node (time ran out, or someone crashed, or the maximum depth to search had been reached). If so, it would evaluate that board and return it.
If it wasn't a cutoff node, the Negamax would generate all possible moves for the player to move, and then send those to the NegamaxAB function, looking for the best move (highest score). Because I was also performing alpha-beta pruning on the algorithm, I kept track of values for alpha (the minimum score for the maximizing player) and beta (the maximum score for the minimizing player). In each call to NegaMax, the positions of alpha and beta are switched, and the evaluation score is negated, allowing for the single Negamax function to put itself in the shoes of each player when it is being run for that player.

Because Negamax was designed for turn-based two player games, I made the design decision to evaluate board like a turn-based two player game. My player would go first, and the opponent would go second. So my algorithm's calculated my opponent's turn using my move as data. Basically I assumed my opponent knew exactly what I would do. This made it a little easier to port the Negamax algorithm to my code, and also made my AI's decision a bit more difficult than it actually was.

The Time Limit

Under the contest rules, each move had a one second time limit. I handled this using an iterative deepening search.

I started by performing a search 2 moves ahead (one for me, one for my opponent). That search ended with a "best move".
If there was still time, I performed a brand new search 4 moves ahead. If I didn't run out of time in the middle of this new search, the move returned would become the new "best move"
I continued doing this, adding 2 levels of lookahead at each iteration, until I ran out of time. I added two levels of lookahead to simulate both players making a move.
The best move returned from the most recent completed search was the move I made.

Filling a Separated Board

Often, my AI would find itself in a situation where it was separated from the opponent, where the two bots were in separated zones.

#########
#   #   #
#   #   #
#  1#   #
#   #   #
#   #   #
#   #2  #
#   #   #
#   #   #
#########

In this case, my AI would switch to fill mode.
My intent was to make this a breadth first search, where each node was evaluated by the number of positions accessible to it.
I ended up wastefully reusing my iterative deepening code instead, and didn't get to fixing it before I ran out of time.
I did make one improvement. Sometimes my AI would find itself staying away from small sections it couldn't fill. If there were more than one of these sections it would put all of them of until it only had the option of even partially filling one of them.

Illustrated in this game: http://csclub.uwaterloo.ca/contest/visualizer.php?game_id=4041576
In this game, my AI finds itself staying away from the two dead ends, until it finds itself forced to go to one of them. By this time, though, trying to stay away from the one-square dead ends made my AI create two multiple-square dead ends. It chose one, leaving many squares open on the board. If the fill had been better, my AI would have won that game.

So to try to fix it, I modified the evaluation to not include dead ends beyond the first. That way, my AI would allow itself to block off a dead end rather than postpone that section of the board until later, which could be deadly if there were multiple dead ends on the board. It was a definite improvement.

The Competition

I don't know how talented the field was. I assume it was pretty good. Granted, not all of the 708 entrants were particularly good or tried very hard, but I'm still assuming they were pretty good. First off, 302 of the participants submitted their code more than twenty times. That means that 302 participants actually uploaded code to the server more than twenty times. Usually, a code upload only comes after making modifications to the AI, so 302 participants seemed really motiviated to participate. Secondly, and I'm just guessing on this, but it takes a certain type of motivated individual to participate in a contest like this. I would guess that the majority of participants were above average, especially the 302. Why join otherwise.
I'm sure there were plenty of participants who didn't have the time to invest in trying to win, but the 302 made a good effort. I estimate I submitted about 30 times. I had 14 different distinct versions of my AI, and 24 unique submissions. Sometimes I resubmitted old code to get a better view of how my AI was doing.

Summary

This was one fun challenge. I enjoyed the time I put into coding up my AI, and it was icing on the cake that I managed to perform pretty well (28th out of 708, in case you don't remember). It was exciting to see how my AI fared on the leaderboard, and how my improvements were reflected on the preliminary rankings. I coded late into the night sometimes, and I sometimes woke up early to get in some coding before work. I did it because I loved it. Next time, maybe I'll win.