Now that the contest is finished, congratulations go out to the first place winner: a1k0n, well done!
I also wanted to pass on a few remaining interesting links and concepts I haven't yet included or explained in my first post.
How did I do? 144th place. Not bad for a heuristic, but next year I'll be using minimax as well.
A small selection of rounds
I'm including some final rounds to show where my bot did well, and where it performed poorly.
An easier (and better) minimax evaluation function: Voronoi territories
In the previous post I've already mentioned that the most important part of a good minimax strategy is the evaluation (the score) you give to each game state. A lot of players have been using a Voronoi Territory based system to evaluate their positions.
The name comes from Voronoi diagrams, a decomposition of space determined by distances to objects in that space (like points for example). When applied to the game of Tron, we could start with this simple board:
To define our territory, we figure out the quickest way to reach each free square, both for us, and for our opponent:
Our territory is defined by the squares we can reach quicker than our opponent, and vice verso. E.g. red's space is colored in light red, blue's space in light blue:
If we apply this method to each board in our minimax tree, we can assign a score. For example:
score = size of our territory - size of their territory
To expand on this idea, a lot of players also searched for articulation points on the board to see if it would make sense to block those off. Remember: an articulation point is a point such that removal (filling) that point would increase the number of disconnected "chambers". For example, the articulation points in the board above are:
A good strategy checks whether we can reach those articulation points first, if it separates us from our opponent, and if doing so would result in more territory for us than our opponent.
Now that the contest is over, a lot of players have posted their source code in this thread. The git repository of the contest winner is especially worth taking a look at.
Addendum: a1k0n has posted a post-mortem on his blog, which manages to explain things very well. It's a wonderful read.