(This is the second and final part in the University Of Waterloo CS Club Tron Challenge post series. You can find the first part here.)

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.

The first game starts of like this. My bot is red.

The board after a few moves. Our bot senses it can reach a wall to block our opponent of by going east…

Which is what happens here. It’s easy to see we’ve won now.

Our opponent makes optimal use of the remaining space, but loses.

The second game. We’re red again.

We’ve been chasing blue for a bit.

To close in on blue, we need to go the other way around. But due to our aggressive manoeuvres, we’ve made a mistake.

Blue exploits our mistakes and blocks us off. Well done.

A new game, we’re red again.

The first moves start of pretty symmetric.

We’re chasing our opponent for a bit. Since we cannot reach him by going north anymore, we’ll go down now…

Which is what happens here. Our bot quickly senses that we can close blue off. It’s pretty hard to eyeball here that we’ll end up with more room then blue, but our bot seems to be confident.

Indeed, a few seconds later the situation looks like this. It’s clear we’ve won.

Another game. Now we’re in blue. I’m picking this round because my bot had a lot of problems with this setup.

By chasing our opponent, we’re getting ourselves in a lot of trouble.

And indeed, a few moves later, red can easily corner us.

This game was played against the contest winner, a1k0n, we’re blue again.

Both players start of pretty aggressive.

Red makes a slight detour, so we go north to reach him.

Then red turns around, an obvious mistake would be to follow him by going south. In the first part we’ve mentioned this problem and included a fix to avoid these dead-ends.

…and thus we turn around as well.

Alas, red is still able to close us off before we reach him. I actually consider this a well-played game.

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_

Articulation points

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.

Worth reading

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.