Coding for the Win - How I Built a Tower Defence Bot

While you might have heard people speaking about how fun programming is, I find it much less common that people treat it as a game. In "competitive programming", however, communities do just that - program against each other in order to win.

A South African example is the annual Entelect Challenge where the competitors write programs to play a game for them. At 2018's Tower Defence Challenge, my entry did really well. Here is how I went about it.

What is this game we're playing?

The first step in any competitive programming challenge is to make sure you understand the problem that you're trying to solve.

Each match has two player-written programs. The programs take turns and have two seconds to read in the state of the board, come up with a good move, and shut down again.

So, what is the game my program needed to play? This year, the game is a lane based tower defence game. Each player has an 8x8 grid to build towers on:

There are three towers that you can build:

Energy towers produce energy for you to build other buildings,
Attack towers shoot missiles at your opponent and
Defence towers block opponent missiles.

The short description on how to win is that you need to shoot your opponent with enough missiles! Specifically, shooting missiles that pass completely over your opponent's side of the board without hitting any of their towers.

At the beginning of the game, players build their energy towers. This helps them to build up energy, so that they can keep building other towers. Then, they build attack towers, which will shoot missiles at their opponent. If a missile hits an opponent's tower, the tower is damaged. The defence tower can stop up to four missiles. The other towers are destroyed after a single missile hits them. If a missile makes it all the way across the opponent's board without hitting their towers, then the opponent is hit by the missile themselves. The winner is the first player to hit their opponent with twenty missiles. Your opponent, of course, isn't going to make this easy. They will build their own attack towers that are shooting back at you.

What is the best way to play?

On a high level, all of the programs entered into the competition need to do the same thing: read the current state of the game and choose a move. It's useful to have an idea for how many moves the program has available to choose from, so I did some quick maths to get an idea for the number of possible moves. This isn't the most accurate mathematics, but it was enough to give me a feeling for the order of magnitude that I was dealing with.

Say that you and your opponent both have enough energy to build any of the three towers, anywhere on the board:

The 8x8 grid means that you have 64 spots to build in.
The 3 different building types that could go in each spot lead to you having 192 different moves that you could make.
Your opponent also has 192 different moves that they can make.
If you look just one move into the future, considering every combination of your moves and your opponent's moves, that's 36 864 different states that the game could be in just one move into the future.

Something important to realise for this game is that many of the towers only really have an impact a few moves into the future. Energy towers, for example, don't have any immediate effects but impact your ability to build for the rest of the game. Even with the attack towers, you need to look a few moves into the future to see the
missiles being created and flying at your opponent.

If you look two moves into the future, then there are 967 458 816 different states to consider!

I've found that a typical game lasts somewhere between 50 and 100 turns. Clearly, the number of different paths that you can take through this game is massive.

Based on this, it didn't seem to be possible to find a BEST
move. That’s why I decided to focus on finding a GOOD ENOUGH move.

This decision helped to focus the direction I took when researching possible alternatives. I went looking for algorithms applied to problems where it wasn't possible to do an exhaustive search of all possible moves.

The Monte Carlo Tree Search

When you're faced with a difficult problem, it is usually a good idea to see what similar problems people have solved before.

In this case, I was inspired by AlphaGo, a program that Google wrote to play Go. In an average Go turn, there are 250 possible moves, making it even worse than the 192 that we need to deal with. AlphaGo manages the large number of possible moves by using a technique called a Monte Carlo Tree Search.

I've written before about Monto Carlo algorithms generally, and so I felt I was in a good position to give it a stab. The high level idea is actually fairly simple:

Make a list of the possible moves you can make now.
For each of those moves simulate a game that starts with that move.
Choose all other moves in the game at random, and simulate with random moves until somebody wins.
Record if you won or not at the end of the simulation.

If you do one simulation of the game using random moves, then the outcome doesn't tell you much. If you do a thousand simulations using the same starting move, then it can tell you statistically if the starting move was any good.

Now, the challenge this posed to me was: How do I simulate enough games in the available two seconds to get a statistically significant result? I wrote my program in the Rust programming language, which gave me a good balance between low level control over my program and the convenience of modern high level languages. I'm going to go into more detail on exactly what I did to have a fast simulation in a future article, but it involved many evenings of staring at profiler outputs trying to figure out how to do things just a little bit more efficiently. Rust's excellent support for parallel programming also helped me to get a large speedup by making full use of the multi-processor computers that the tournament was being run on.

In the end, thanks to rewriting my bot to make heavy use of bitwise set operations, I was able to run in the region of 400 000 games to completion in two seconds.

The power of friendship

One of the most valuable things I did for this project was to spend time talking to my friends. Towards the end of the competition, we even ran our programs against each other to get some feedback on how we were doing. Talking to others about the issues I was hitting helped me because I was:

Finding out about approaches that I wouldn't otherwise have considered,
Thinking through my problems by verbalising them (the rubber duck approach), and
Keeping myself motivated when things took longer than I thought they would.

In competitions, it's always tempting to try to keep all of your ideas to yourself. Resist that temptation and talk with your friends.

As an example, one of the secrets of my program's success is that I have a highly performant implementation of the game rules. I did that by making heavy use of bitfields to represent the game board, and bitwise operations to handle the transitions between states.

When I implemented this, I got stuck on a tricky problem: how do you randomly and efficiently choose an unset bit in a bitfield? After discussing the problem with a friend, he pointed my towards an article called Bit Twiddling Hacks, which happened to have exactly the bitwise trick I needed.

Sharing ideas helps to create more ideas.

Upcoming articles

That's all from me for right now, but I'm planning on writing several more posts on this topic, delving deeper into the issues I mentioned:

Resources

Codingame hosts regular competitions, and has a really slick player portal for writing bots.
In December, join me for the Advent of Code, a programming challenge advent calendar.
I'm going to be keeping an eye on the Entelect Challenge website around April next year to see what interesting new game they come up with next.

Justin Worthe is a software engineer with an interest in music, games, good coffee, and using programming to get stuff done. He can often be found trying to find ways to play with all of these interests simultaneously. In the meantime, you can catch him on Twitter or Github.