Light Cycles

I've been spending a bit of my free time recently on an internal programming competition being held at work (there's a top prize of $250, but it's really more of a pride thing). The goal of the competition is to create the artificial intelligence for a computer to play a game that resembles the Light Cycles in Tron. We were allowed to compete as a team, but as it turned out, my partner and I are the only team. The other five entries are competing as individuals.

The game is pretty simple. You have a square grid (N x N). Your computer player and the opponent's computer player will start in random squares, but it will be symmetric to ensure fairness. Every turn, both players move to an adjacent square. Squares previously occupied become walls. Your goal is to survive longer than your opponent.

The game itself is turn-based, but simultaneous moves are made on each turn. That is, each player is given a board state submits its move (Up, Down, Left, Right). Both submitted moves are then issued simultaneously resulting in a new game state.

If two players decide to move to the same square, it is a draw. Similarly, if two players crash on the same turn, it is a draw. If one player crashes (presumably having no possible safe moves) and the other does not, then the crashing player loses and the survivor wins.

Anyway, we've made a lot of great progress, and the computer player is highly competent (on larger boards, we lose to it almost always and once in a while we are able to draw). It's been a fun experience so far, and we've definitely learned a lot from it. The official competition is going to be held next Friday at work, and we're hoping to see some good stuff coming from the other competing entries.

The winning entry will be determined by a round-robin tournament. I think each pair of teams will battle on several boards, and the set of boards will be identical so everything is fair. Scoring is going to be the sum of results, where you get 1 for a win, 0 for a loss, and 0.5 for a draw.

If anyone wants to give our program a whirl, let me know. We really do want some help spotting obvious exploitable patterns by our computer player. I can only provide an executable to be run in a Windows environment, so if you're on a different OS, sorry.