Thursday, February 25, 2016

Battlecode 2016 post-mortem: future perfect

This year I did Battlecode with Luchang Jin, a fellow member of my research group at Columbia. We competed as team future perfect and won first place in the final tournament. In keeping with ancient tradition, here are my thoughts on this year's Battlecode.

We've open sourced our bot on Github if you want to check out our code.

Us (Red) vs. what thesis (Blue) in the first game of the Battlecode 2016 final tournament


The 2016 game

This year the game was a zombie invasion. The goal was to destroy or outlast the enemy team.

Zombies
Zombies periodically spawned from "dens" scattered around the map and would move toward and attack the nearest player-controlled unit. More and stronger zombies spawned as the game went on. Units that were killed by zombies came back to life as zombies and turned on their former friends.
There were four kinds of zombie units. Here I won't worry about the differences between them; if you want you can read about the details in the game specs.

Player unit types

Archons: In a return to Battlecode's roots, each team started with a number of archons, a leader unit which could construct other units. Whichever team lost all their archons first lost the game. All the other units were built by archons.
Soldiers: cheap but mediocre combat unit
Guards: melee unit with a lot of health
Turrets: expensive and stationary units with a long-ranged powerful attack. Turrets could transform into a mobile TTM (Turret Transport Mode), which could move around but couldn't attack until it transformed back into a turret. Transforming took some turns.
Scouts: couldn't attack, long vision range, could fly over obstacles
Vipers: could infect other units, dealing damage over time and turning them into zombies

The devs did a great job of balancing the unit types, and all of them were useful (well, if we're a bit generous to guards).

Resources
Units were built by archons from a resource called "parts." Each team received a passive income of parts, and there were also parts scattered about on the ground that archons could collect. There were also "neutral" units sitting on the map that you could recruit to your team by touching them with an archon.

Blind and mute
In the previous few years, robots had shared vision and could freely communicate with each other over a high-bandwidth message channel. That changed this year. This year, your robots did not share vision: each robot could only see a small radius around itself. Most robots could not send data to each other. Only scouts and archons could broadcast data (any robot could receive), and these messages had only 64 bits each. Broadcasting a message cost time, and the cost increased for longer range broadcasts. Sending a message across the whole map might freeze your scout or archon for several turns.

So most robots were essentially blind and mute. This made it much harder than in previous years to gather information, to coordinate your army, and to make intelligent decisions.

The game was easier in one respect: there were no permanent obstacles, only "rubble" which you could clear out of your way if you spent enough turns digging through it. This meant that there was no need for sophisticated pathfinding.

Week one: turtles and cows

We got right to work when the game was released. As quickly as we could we hacked together a bot that would spawn a swarm of soldiers.  The swarm just kind of jiggled aimlessly around the map, hoping to find and kill the enemy. 

We woke up the next day to a bunch of scrimmage losses against teams with a much simpler strategy: sit in one place and build a bunch of turrets. Turrets were very strong, especially in groups. The idea of this "turtle" strategy was just to sit inside an impenetrable fortress while waiting for the other team to be devoured by the zombies. 

This seemed very strong to us, so we set to work on a turtle bot. Turtles soon evolved to build scouts alongside turrets. The reason was that turrets could shoot farther than they could see, so it was useful to have a scout nearby which could use its long-range vision to call out targets for the turrets to attack.

Us (Red) vs. #trump2016 (Blue, off-screen), a scrimmage match showing an early example of a turtle formation. We defend against the attacking zombies with turrets. Our scouts broadcast (emitting purple circles) to tell the turrets where to shoot. Off-screen, #trump2016's army is eaten by a ravening zombie horde.

Over the course of the week teams figured out ways of building stronger and stronger turtles; some leading turtle teams were Polar Vortex and NP-Compete. (Polar Vortex's actual name was F=<-sin(theta)/r , cos(theta)/r>. Please mentally replace "Polar Vortex" with that equation in what follows.)

We didn't see how anything could possibly beat the strong defensive formation of a turtle bot, but then we played some educational scrimmages against team Super Cow Powers. He had a much more active strategy: he would build soldiers and turrets and move out onto the map, taking all the resources, killing all the zombie dens, and building a very strong army. He would destroy turtles very simply: his turrets would pack up into TTMs, move into range of the enemy turrets, transform back into a turrets, and start shooting. This attack was a bloody business that cost him a lot of casualties, but he had resources to spare because he controlled the whole map. His turrets were especially effective because he built scouts and paired them with turrets to form a powerful two-man group, making sure the turret always knew about all the enemies that were in range to shoot. 

We were very surprised to see how well this worked against us. Soon we came to believe that the Super Cow Powers strategy was the future. Turtling was a very passive strategy and could only be made so good, but the Super Cow Powers strategy could be made better and better. Our goal for the last few days before the sprint tournament was to replicate this strategy. By the sprint tournament we had a passable Super Cow Powers imitation and were doing very well with it on the scrimmage server.

Team 1064CBread got quite high on the scrimmage ladder during the first week with an amusing trick that let them beat a bunch of teams, including us. They built a turtle formation, but they also built a bunch of robots whose only job was to broadcast as many messages as possible. The point was that robots could receive messages from enemies as well as from allies, and all messages went into the same signal queue. So any enemy robot that tried to read messages would have to chew through hundreds of 1064CBread's messages every turn. This would use up all their computation time and so the enemy robots would just sit there doing nothing, and would quickly die to the zombies. Meanwhile 1064CBread's robots ignored all the messages and just defended against the zombies until the enemy died.
The fearsome broadcast spam attack.
Sadly for 1064CBread, the devs quickly patched this because the message spam was making the match replay files gigantic. Robots were limited to sending only a few messages each every turn.

The sprint tournament: zombies everywhere

Team DenReapers won the sprint tournament. The zombies were honorary co-winners. The sprint tournament maps turned out to have many more zombies than the practice maps we had been scrimmaging on. So in a large fraction of games, both teams were quickly overwhelmed by zombies and the winner was determined by whoever's archons could run away better. We hadn't spent much time on archon retreat code, since we could handle the zombies easily on the practice maps. So we got knocked out in the round of 8.

We (Red) get owned by zombies and get knocked out of the sprint tournament. Turing It Up (Blue) advances because of their nimbler archons.

The devs had intentionally made the zombies strong as an experiment, but they actually went farther than they intended. On a few maps there was a bug where a powerful wave of zombies that was supposed to spawn on round 2,700 actually spawned on round 270. This wave was essentially impossible to survive, so both teams died very quickly on those maps.

Week two: biological warfare

After the sprint tournament, the devs learned their lesson and reduced the number of zombies. They also made the zombie units weaker and easier to deal with. I think this was healthy for the game: the zombies became manageable enough that teams could actually fight each other instead of just trying to flee as fast as possible.

One lesson we learned from watching other teams in the sprint tournament and from scrimmaging afterwards was that the viper unit was very powerful. Vipers had an attack that infected their target with a disease that did a huge amount of damage over time. A unit that died while infected would revive as a zombie and potentially turn on their allies, doing even more damage. A single viper could keep many enemy units infected, so in the right circumstances a single viper could destroy, say, 10 enemy soldiers. 

So we started using vipers in addition to soldiers and turrets. We also wrote some code to make terminally infected robots do a suicide charge. If one of our robots determined that it was going to die to a viper infection, it would charge headlong at the nearest enemy. The idea was that when our robot turned into a zombie we wanted the zombie to attack the enemy unit and not our own.

The seeding tournament

By the seeding tournament, I think the top teams were roughly evenly split between a soldier+turret+viper strategy, like us, and a turtle strategy. The grand final of the seeding tournament was us against Polar Vortex, who were probably the best turtle team. We won in a close match.

Us (Red) vs. Polar Vortex (Blue) in the final match of the seeding tournament. We set up offensive turrets to attack their defensive turtle position. Once their turrets are eliminated we collapse on their archons with our soldiers.

Week three: the final push

The metagame shifted somewhat in the last week. Turtles fell rapidly out of fashion--even Polar Vortex stopped turtling--perhaps because turrets had been nerfed a bit. Our soldier+turret+viper strategy also fell out of fashion. Most top teams ended up with a soldier+viper strategy, maybe building a few turrets late in the game.

We were confused by this shift, because we thought turrets were still really strong, so we kept building lots of them. We kept using the same strategy and just made incremental improvements to our bot. In retrospect, I think that with perfect play soldier+viper was stronger than soldier+turret+viper, because turrets were weak against intelligent aggressive micro. But that was hard to implement, so in practice we kept doing well with soldier+turret+viper.

We had seen some impressive games by team mid high diamonds against turtle teams in the seeding tournament. They would surround the turtle with soldiers and vipers just outside of the enemy turrets' range. Then at a certain round the soldiers and vipers would rush in as one and massacre the turtle. After seeing this we implemented it ourselves, but this turned out to be a waste of time because turtles were going out of fashion fast.

The final tournament

Finally the deadline ended our three weeks of frantic coding. We made it through the qualifying tournament to the finals, where the top 16 teams gathered in person at MIT.

The final tournament showed how well the devs balanced the game this year to make multiple strategies viable. There was
  • Our strategy of soldiers+turrets+vipers, shared by a few other teams
  • Many teams doing a more aggressive soldiers+vipers strategy
  • A couple of teams turtling 
  • One team, foundation, with a very scary zombie-based strategy
Foundation was a pacifist: he only built scouts, which couldn't actually attack. His scouts would go out and find zombies and then lure the zombies to the enemy team. Once they found the enemy, foundation's scouts would allow themselves to be killed by the zombies, adding themselves to the zombie army. Now the enemy team had a huge horde of zombies attacking it, while foundation's archons sat on the other side of the map serenely churning out scouts:

foundation (Red) vs. bigswingingDKEs (Blue). Red's scouts lead a huge army of zombies to destroy Blue.
This strategy took down many very good teams. The games were spectacular, ending very quickly and decisively.

We managed to beat foundation, in part because we had seen The Simple Soldier using this very strategy on the scrimmage server during week two. We lost that scrimmage, got really scared by the strategy, and implemented it ourselves. Then we spent some time testing our main bot against the scout/zombie strategy and figuring out how to maximize our chances of surviving against it. We found that it was best to build soldiers when under heavy zombie attack, and that it was very important in that situation to avoid building vipers or turrets, which were both worse than useless against zombies. This code probably helped us hold off foundation's zombies in our match against them in the final tournament.

The most exciting game of the final tournament was definitely mid high diamonds vs. The Simple Soldier. The Simple Soldier turtled, and mid high diamonds couldn't break their defense. So toward the end of the game, mid high diamonds sent their entire army--except for one archon--to one corner of the map. Then they used their own vipers to turn their entire army into zombies. The resulting zombie horde utterly crushed The Simple Soldier:

mid high diamonds (Red) vs. The Simple Soldier (Blue). Red converts their entire army to zombies, which smash blue's defenses. Red wins because they have hidden a single archon in the lower-right corner of the map.

We had idly considered exactly this strategy, but thought it would be too hard to implement. So we were very impressed to see mid high diamonds execute it so cleanly. The ending of this game got the loudest applause of anything in the finals.

The grand final match again came down to us against Polar Vortex, and again it was a close match. During the last week Polar Vortex had transitioned from a turtle strategy to a soldier+viper strategy. In one game they beat us by rushing our army before we could build up a critical mass of turrets that could defend each other. But in the other two games we held them off long enough to build a powerful army and won the match.

Reflections on three years of Battlecode

I've done Battlecode for three years now and each time the competition has been the highlight of my year. I would spend all of December waiting for the game release and all of January Battlecoding.

The devs deserve a lot of credit for making Battlecode great. They not only make the game, they are active all month giving lectures, fixing bugs, carefully balancing the game, and hanging out on IRC answering questions. They've kept the tradition going 15 years, and I hope for many more.

But really what makes Battlecode great is the people competing in it. This January a bunch of people worked really hard for a month making virtual robots fight little pixelated zombies. That would be a silly and unrewarding thing to do it there weren't a community of other people working hard on the same challenge.

During this intense contest everyone is amazingly friendly. Lots of people are active and helping each other out on IRC. The finalist dinner is all smiles (maybe it helps that everyone's code is already finalized and that robots are immune to trash talk). We sat with some other teams for four hours at the dinner talking about strategies we had tried and laughing about bugs we had found in our bots.

I'm graduating this year, so I'll no longer be fully eligible to compete in Battlecode. But I'll definitely be back next year one way or another. See you all in 2017!