Tron AI

I have spent much of the past few days competing in a AI contest hosted by the University of Waterloo and sponsored by google. I have been having tons of fun with the contest and figured others would be interested in participating or reading how the contest has been going. I encourage anyone who finds this interesting to participate as it takes less than 5 minutes to get started and your first bot competing.

Here is a play of me beating the #1 ranked bot. I got lucky here, but be sure to watch other matches of mybot against others

The contest is to write an AI to play the game of Tron. It is played on a grid with each player moving one spacer per turn and each space moved from leaves an impassible wall. If you are not familiar with the classic film tron, it is easiest to think of the game as two player snake, where each players snake continues to grow every move. The goal of the game is to outlast your opponent before crashing into a wall.

On the day the contest launched I was already able to jump up to the top 20 in the rankings. I started off with something very basic. Every turn there are only three possible moves (the first turn there are 4) and so I just tried to narrow it down from there. I would decide which direction to move by looking in all three directions (forward left right) and choose the direction farthest from a well. This end up having the bot move to the center of the space and then run around in the middle. After watching a few rounds I decided this would work best if I first cut off some options to the enemy. So I would first run to the nearest edge and then follow the above strategy hoping to first block off their path. Lastly I would avoid draws by preferring not to move to squares the enemy could move to. This worked surprisingly well for being so simple and just avoiding walls,and I was ranked pretty well.

This did not last long, as more and more people submitted or improved their bots I had to get smarter. My first major improvement was to mark the open space in continuous regions. So my bot would scan the map, and color in every continuous space, each group a different color, and then count the number of squares of each color there were. This was a huge advantage, first it allowed me to not move into dead ends. If the head of my snake bordered two different colors, move into the one with more space available. Worked great. Now my bot would not do stupid things like move down obvious dead ends. If there was ever a choice between two regions I would end up in the larger one. This alone coupled with my old strategy bumped me up back into the top 20.

The way I stored my colors gave me an added benefit, if there was a color that bordered both me and the enemy I knew that there was some path between us. So I could use this and if there was no possible path between us, go into space saving mode. This meant to not do anything fancy just follow the wall since all that was needed now was to out last him, and hope we have more space than them. My space saving ideas still could use a lot of work since this situation comes up all the time once the board has been divided.

Next I added an attack routine. I just based this off of common cases I saw while watching my bot. Since my bot would race to the middle I could then move towards and edge and hopefully cut them off. I did this based on quadrants. I divided the map like so:

|1|2|
|3|4|

Then if I started in 1 and the enemy started in 4 the game would proceed as fallows. I would find a wall, then move to the middle. I would check what quadrant the enemy was in, if they were in 2 or 3 make a dash for the wall. If they are not in 2 or 3, just stick with evasive maneuvers. Works really well against certain bots like this


My bot still has a long way to go before beating some of the top ranked bots. I have some ideas in the works still though. This contest has been tons of fun and goes till the end of the month so check it out!