Google & University of Waterloo AI Challenge - Java Tron Bot

When the University of Waterloo announced a Google sponsored AI challenge I was intrigued and decided to enter. The contest goal is to program a bot which plays a simplified version of Tron. For those of you who may not be familiar with the details of Tron I will briefly explain. The game involves two players who start out on a board that is bounded by walls. On each turn both players must move one grid square, and every time they move they leave behind a wall in the place where they last were. As a result, as a player moves across the game board they leave behind a solid wall. If you crash into a wall at any time you lose.

The goal of the game is to outlive your opponent, or even better, crash your opponent by boxing them into a small area while your bot can roam the rest of the board.

So far my bot has been doing pretty well, staying in the top 5-10% of the bots entered. As of the writing of this post my bot was in third place out of 300 bots participating. So far it has had 168 wins, 13 losses, and 22 draws in which both bots lost because they tried to move onto the same square.

The dynamic graph below shows my latest rank. The sudden drops coincide with me recompiling and submitting a new version of the bot which starts out at the bottom and has to fight its way back up.

More details available at my contest profile.

It will be interesting to see how this turns out. I really have no expectation of winning, but I do think that it shouldn't be unreasonable to expect to be able to stay somewhere near the top of the scoreboard.

Tips

Since my bot is doing pretty well I think I can give a few tips to other participants. This will probably be injurious to my bot's ranking, but I'm in this more for the intellectual challenge than the winning, so I don't really mind helping the competition.

My basic strategy is to use a modified version of flood fill to count the number of clear squares in each direction which the bot can move. Since the bot leaves a wall behind it there are only three effective squares that have to be tested. By counting the number of empty squares that can be flooded in each direction I can ensure that I don't enter a blind corner, but rather stay out in the open as much as possible.

At each step the bot also checks to see if it is possible to reach the opponent. If my bot detects that it is walled in, or that the opponent is walled in and it is impossible to reach it then my bot goes into a space saving mode which tries to make effective use of the available grid squares in its room.

Otherwise my bot tries to move toward the opponent, while maintaining a certain amount of weight on traveling in a fairly straight direction. When the bot nears its opponent it begins following a set of rules that I have developed to try to block the opponent off while avoiding a draw in which the two bots crash together.  This is the most difficult part of the algorithm, but it essentially involves staying close, but not too close while trying to travel parallel to the opponent so as to block it off.

Possible Improvements

Of course my bot isn't perfect, and there is definitely some room for improvement. I plan to improve the space saving mode, which is currently not as effective as it ought to be. I also plan to add some basic prediction to better judge the opponent's heading so that the bot can avoid being blocked off itself.

Recommended Testing Procedure

I started out testing my bot against the simple sample bots provided. After I was able to beat those bots easily I duplicated my bot and began working on a second version, trying to beat my first version. I repeated this process of forking my bot and fighting the old version until I could beat it consistently.

One quick tip is that the map engine outputs maps which can also be input as valid starter maps. So if at any point your bot crashes or does something stupid that you don't like you can take one of the last map outputs, copy it out of the terminal, paste it into a text file, and use it as input to retest your bot. Then make changes to the code until it responds to that specific condition in a way that you approve of.

In this way you can take a snapshot, so to speak, of a game moment and tweak your bot until it responds properly.

Conclusion

I am really quite excited about this AI competition. Although I doubt I will win, it has certainly been a learning experience so far, and I'm sure that it will continue to teach me more. After the contest has concluded I will share my bot's source code with you. In the meantime, for the sake of competition, I'll just explain how my bot works.

Update

I have written a follow up article containing some code snippets to help you implement the techniques I discussed in this article.

4 comments:

  1. I'm also doing the challenge, best of luck!

    ReplyDelete
  2. Hey Nathan,

    This is Jeff, the organizer of the Google AI Challenge. I love the article, and these are some great tips for the other competitors. It had never occurred to me that you could copy the test engine's output into a new map file to restart a game from a saved state. Great idea!

    Do you mind if I link people to this post from the main site? I'm trying to throw up some more content, like tutorials, strategy guides, algorithm examples, etc. Also, if you want to write some more about anything related to the Tron contest, we would love you forever.

    ReplyDelete
  3. Certainly. I will continue sharing more tips and ideas as I develop my bot. I'll probably share some source code snippets too at some point.

    ReplyDelete