Thursday, December 4, 2014

Battlecode 2014 recollections: that one team

Here are my recollections of Battlecode 2014, in which I took first place as "that one team." The goal is to convince you that Battlecode is cool and fun and you should compete in it.

The 2014 game

The 2014 Battlecode game was based around cow herding. The object of the game was to get 10 million milk before the other team. You got milk by building soldiers at your HQ, having your soldiers construct pastrs (pronounced “pastures,” short for Projected Animal Security and Treatment Region), and then herding cows into your pastrs. Each cow in a pastr would produce 1 milk per round. Cows were spontaneously generated on the map each round; some regions of the map generated cows faster than others. To herd cows into pastrs you could build noise towers, magical devices which could create noise at any location within a certain radius. Cows were scared away from noise, so you could use this noise to push cows into your pastrs. Building either a pastr or a noise tower required sacrificing a single soldier, which transformed into the desired building.

Meanwhile you could also get milk by sending your soldiers to destroy the opposing team's pastrs—if you could fight your way past the enemy team's soldiers. Destroying an enemy pastr rewarded you with 1 million milk, 10% of the total needed to win. Soldiers fought with laser guns which had a range of a few map squares. Soldiers could also self-destruct, sacrificing themselves to deal massive damage to all adjacent robots, but using this ability was tricky because it required charging forward under enemy laser fire to get adjacent to the enemy first.

As usual, there was a “fog of war”: your robots could only see nearby enemy robots. One exception was that you could always sense the location of the enemy's pastrs, no matter how far away they were, making it possible to play aggressively without having to scout out the enemy first. Furthermore robots could sense all obstacles on the map without having to explore it first. All robots were equipped with radios that let them talk to their teammates. Unlike in previous years, these radios were secure from enemy eavesdropping or jamming and had infinite range.

The strategic metagame

Throughout the competition there was a rapidly-evolving metagame. Strategies rose and fell as people discovered new ideas and new counters, and as they figured out how to implement more complicated strategies.

Some of the first successful bots on the scrimmage server were pure rush bots that would rally their soldiers in a group and wait to attack any pastrs foolishly built by the other team. They wouldn't milk any cows, but they would get milk by destroying opponents' pastrs. But you could beat these bots if you built a single pastr and defended it well.  Building multiple pastrs was dangerous because it spread your defenses thin and made you easy prey to a rush. I had some early success with a bot that would build a single pastr and defend it, but would abandon it and rush the enemy if they built more than one pastr.

Soon it became apparent that you really needed to build a noise tower next to your pastr if you wanted to herd effectively: a noise tower could pull in cows from a huge area and let you milk many times faster. This required sacrificing an extra soldier, however, and made you even more vulnerable to a rush. Team Pusheen realized that there was a clever way to get around this: build your pastr and noise tower next to your HQ, which was outfitted with a powerful defensive weapon. This "turtle" strategy made your pastr essentially invulerable and let you herd in peace. Pusheen captured the top of the ranked ladder by being the first to exploit this idea.

I thought this was a really annoying strategy, but it was hard to beat, so I copied it. All the top teams on the ladder did the same. But interestingly, in the days just before the sprint tournament the turtle strategy started to get countered. On maps where there weren't many cows near the HQ, you could beat the turtle by building a pastr in a more cow-rich area of the map. I and some other teams also developed a counter where you sent some of your solders to shoot and kill cows near the enemy HQ, stifling their milk production.
A scrimmage match with both teams using the turtle strategy. Neither team's soldiers can approach the enemy pastr without getting blown up by the enemy HQ. So both are just trying to shoot any cows in sight.
People also correctly anticipated that the devs would nerf the turtle strategy through map design. In the sprint tournament, turtling was completely unviable on many maps because there were no cows close to your HQ. Strategy started to become more subtle. Build timing became important: building early let you start milking first, but sacrificed a soldier that might be needed to defend against a rush. Once you had built a pastr, you needed to decide whether to defend it or to attack the enemy's pastr. Proxy 2 Gate won the sprint tournament, beating my bot in the final match on the strength of their better strategic decisions and more efficient noise tower herding.

After the sprint tournament strategies continued to evolve. I experimented with building two pastrs instead of one on large maps, with the idea being that it would be hard for the opponent to destroy both of them fast enough to keep me from winning. Some teams had started using offensive noise towers that would scare cows away from enemy pastrs and I tried that too. Others implemented a "contain" strategy where they would attempt to surround the opponent's HQ, gaining complete map control and gunning down any enemy soldier that tried to break the blockade.

One team, The Vegan Police, had a secret strategy that they didn't show on the scrimmage server and which they only busted out in the final tournament. They would send all their robots around the map to simultaneously build four or five noise tower + pastr pairs. When all these buildings completed at once, they would begin gaining milk at an incredible rate and it would be very difficult to rush around the map and kill all their pastrs in time to keep them from winning.

The combat micro arms race

Parallel to the strategic metagame was a ferocious arms race in soldier combat micro code. Perhaps this was even more important than the strategic back-and-forth. "Combat micro" refers to the round-by-round decision making your soldiers make while in combat with the enemy, and it wins games. You can win with pretty much any strategy if you outclass your opponent in combat, and you can lose with any strategy if you can't hold your own in combat.

The basic mechanics of combat were pretty simple: robots had a laser gun with a certain range that dealt a fixed amount of damage and could also self-destruct to deal damage to adjacent enemies. Yet it was anything but simple to write good combat micro code. The contest to develop good combat micro started on the first day of scrimmages and didn't let up in intensity until the final deadline.

As an example, soon after the sprint tournament I experimented with the self-destruct mechanic and quickly found that it was much more useful than I had thought (it didn't hurt that the devs had buffed its damage because they wanted more people to try using it). My new bot with self-destructs would convincingly beat older versions. It did well on the scrimmage server, too--but almost immediately I started seeing teams implementing anti-self-destruct code where they would run away from enemy suicide bombers. So I worked to make my self-destruct code cleverer and harder to flee from. This just caused others to refine their anti-self-destruct code. Soon I found it necessary to start copying their anti-self-destruct tactics as more teams started to employ self-destructs against me. And so on. This sort of thing was happening continually throughout the competition.

A battle in a scrimmage match. On the left flank of the battle, one of my blue robots charges forward over three turns to self-destruct and deal damage to three red enemy robots. It takes a lot of enemy laser fire in the process: one of the features of my self-destruct code was the ability to accurately estimate how much laser fire a suicide bomber would take while charging and whether it would be able to make it to the target before being killed.

Other challenges

Grand strategy and combat micro aren't the only challenges you have to solve in Battlecode. You need a good pathfinding algorithm so that your robots can find their way to the fight (and the devs are heartless and make some maps maze-like just to try to confuse your bots). Each of your robots runs its code separately, so you need to figure out how to use the inter-robot communications to keep your all your robots coordinated. You need to code your bots to act with imperfect information in the fog of war. And you need to do all of this in a clever and computationally efficient way, because each of your robots can only execute 10,000 instructions ("bytecodes") per turn on the Java Virtual Machine. This is not very much, and means that teams generally have to throw out well-known algorithms that they might have learned about in class and instead invent new heuristics from scratch. (In fact, in 2014 your robots' actions would be slowed down by computation, so that to some extent you had to choose between thinking and firing your laser gun.)

I think one of the strengths of my bot was good pathfinding. My soldiers had a fairly dumb bug nav pathfinding algorithm, but I used my HQ's spare bytecodes to do near-optimal pathfinding to my soldiers' rally point using a breadth-first search. The HQ would broadcast the results to the soldiers and when the soldiers reached a point from which an optimal path was known, they would start following the HQ's instructions. This pathfinding was very reliable, which was a crucial factor in doing well in the tournaments. Furthermore I got it implemented quite early, and it made a solid foundation on which to build the rest of my bot.

The tournaments

Battlecode has four tournaments. After the first week, there's the sprint tournament; after the second, the seeding tournament; and after the third, the qualifying tournament. The top 16 teams from the qualifying tournament go to the final tournament (and you can't change your code between the qualifying and final tournaments).

In the first week I implemented the nice navigation scheme described above, some mediocre combat micro, and a really cool herding algorithm for my noise towers. It used pathfinding to herd cows around obstacles and into my pastrs. Only after the sprint tournament did I realize that it actually sucked because it herded cows too slowly to compete with dumber herding strategies. I took second in the sprint tournament, losing to Proxy 2 Gate in part because of this and in part because of their superior strategy.

After this loss I spent the next week thinking really hard about strategies and trying lots of different ones on the scrimmage server. I eventually settled on a rush strategy on small maps, a one-pastr strategy on medium-sized maps, and a two-pastr strategy on large maps.

Meanwhile I also had to work on combat micro because I was getting massacred whenever I scrimmaged against the one-man team PaddleGoats. I tried to patch the weaknesses in my micro that his bot exploited and I also tried implementing self-destructs in some simple cases.

I ended up winning the seeding tournament, but I ran up against an unexpected strong opponent in team losingreallybadly. He was a one-man team who I had never scrimmaged against and who in fact played very few scrimmages against anyone during the entire competition. I played three matches against losingreallybadly in the seeding tournament: one in the winner's bracket where I won 2-1, and then two matches in the finals where I first lost 2-0 and then won 2-0. I was a bit lucky to win; losingreallybadly and I were quite closely matched. I feel I should also mention team Ten Hour Challenge, a one-man team who started working on his bot about ten hours before the seeding submission deadline and who took third in the seeding tournament with an impressively solid submission.

In the final week I focused almost entirely on combat micro, making a lot of effort to use self-destructs more effectively. In fact I think all the top teams made huge improvements in combat micro in the last week. The arms race continued unabated. Finally the submission deadline ended it.

I made it through the qualifying tournament without losing a game, but I had a close call in my match against team 6pool, who punished my bot for building pastrs too quickly. My bot only just managed to claw back from initial disadvantages in both games of the match.

This made me think that my bot's strategic decision-making wasn't very good, and I spent the whole week before the finals worrying about this but unable to change my code. Strategic mistakes did indeed cost me some games in the final tournament, but for the most part my bot's strengths in other areas ended up compensating. I won some close matches against anim0rphs and Armada before I ran into my old nemesis losingreallybadly, who knocked me down to the losers' bracket. But soon I faced him again in the finals and won two matches straight to take 1st place.

The decisive battle of the final game of the final tournament. My robots (in blue) gained the upper hand with some well-timed self-destructs, allowing them to safely build a pastr and win. 
I think I should mention all the awesome teams I met on IRC and at the finals during Battlecode 2014--PaddleGoats, Proxy 2 Gate, Armada, and anim0rphs were mentioned above, but also 0xgquotes, jalmad, and lots of others. I hope I see you all again in future years!