megalodonai

During last Friday’s lunch, a bunch of software engineers at Points.com competed to see who could create the best AI in a game called Tron, inspired by the original movie’s lightcycles. The code for the game can be found here.

The competition was scored by round robin and everyone got a chance to match up their bot against everyone else’s. Each match was a best 2 out of 3; bots got 1 point for winning a game, 1/2 a point for tying and another point for winning a match.

Thirty-six matches later, the LeslieBot (Leslie Barron) came out on top with 7 wins and a tie followed closely by the MichaelLossosInterceptorBot and the MegalodonAI (Kelvin Chan).

Overall, it was a lot of fun for our first AI competition. Hopefully, we can do more in the future.

Now for an explanation of the LeslieBot.

Every turn the bot would first calculate the possible directions it was allowed to go.

It did this by determining how much total space it had available in all directions, and removing the directions which didn’t equal to the maximum space possible. This would guarantee that it would never trap itself without the intervention of the other player.

After calculating the directions it could go, it determined if the player was within the same trapped area. If not, then it would always return the first direction of the possible directions, which was just a priority in the order of NESW. This was the simplest way to fill as much as the available space as possible. If the AI has not been trapped by the other player, then it know it has already chosen the larger area and was almost guaranteed victory at this point. If the player was still reachable then it would continue cutting the screen into chunks until it was all alone, in which case it would start filling.

So how did it calculate the space in each direction?

More or less, it used a slightly modified breadth-first-search. For each direction, it would keep a count of all spaces it had access to and mark them off with the direction it was attempting. This was stored in a global integer array representing the board. If it tried moving in a direction and the space in front of it had already been marked as some direction then it could use the same count as that direction, which meant each space on the board would be scanned at most once. Once it had the counts of each direction it would remove the non maximums to get the list of allowed directions.

With the global board it was easy to figure out if the enemy player was in the same trapped region. First it got the location of the player, and if the breadth-first-search had coincided with the enemy’s spot, then the other player was reachable.

In short:

  1. Cut board
  2. Go to bigger region
  3. If alone, fill space; otherwise go to step 1
Assuming the other player didn’t trap the bot themselves this strategy seems to almost always work.
Here are some screenshots:
megalodonai
spiralai
lesliebot