Saturday, December 19, 2015

Battlecode 2015 post-mortem: the other team

Just like last year I am writing up a post-mortem of Battlecode eleven months after the fact, because I can't wait for next year's competition and so I turn to reliving last year's.

I competed in Battlecode 2015 as "the other team" and took first place in the final tournament. There is a long history of winning teams writing detailed post-mortems and strategy reports; check out my links page to find them.

Here I'll talk about the game itself, how strategies evolved over the competition, what differentiated the top teams from the rest, and my prize-winning distributed pathfinding algorithm.


The 2015 game

Battlecode 2015 was very much in the style of classic real-time strategy games like Starcraft and Age of Empires. You had to build miners to gather ore to build buildings to make military units to kill the enemy's buildings. There was a tech tree and a whole slew of different unit types. There was a dash of MOBA flavor too: both teams started with some powerful defensive towers and could build a unique hero unit that gained abilities with experience.

If you want you can read the full game specs here, but I'll give you a quick overview.

The tech tree, showing which units built from which buildings, and which buildings were required in order to build other buildings.

Here's a brief rundown of the unit types:

Economy units:
  • Beaver: for constructing buildings, very weak in combat
  • Miner: for mining ore, very weak in combat
  • Computer: for running extra computations, useless in combat
Military units:
  • Soldier: weak and short-ranged, but cheap
  • Basher: melee unit that dealt area-of-effect damage
  • Tank: powerful and long-ranged, but expensive and slow
  • Drone: fast, able to fly over obstacles, but somewhat weak and somewhat expensive
  • Launcher: very slow and expensive, but capable of firing powerful autonomous missiles with very long range
  • Missile: programmable flying missile which could explode to deal large area-of-effect damage, but could be shot down by enemies.
  • Commander: unique expensive powerful unit; gained "experience" when nearby enemy units died and got special powers as it gained experience. You could only build one commander at a time.
There was a single resource, ore. Both buildings and units cost ore to construct. Ore was originally distributed across the map and had to be gathered by miners. So, as in any RTS, you needed a good economy to afford a good army.

The goal was to destroy the enemy's HQ. But the HQ was a ridiculously powerful defensive structure, so it was advisable to first weaken it by destroying the enemy's towers. Towers were formidable in their own right, with lots of health and a powerful attack, so you needed a big army to do this (and you had to get past the enemy army first!). With each tower destroyed, the enemy HQ would become weaker until it was eventually feasible to attack it directly.


Shifting strategies

The variety of unit types led to a lot of strategic experimentation and an evolving metagame.

My first working bot built soldiers and used them to attack enemy towers. I quickly discovered that this was a terrible idea, because soldiers were so weak that they suffered horrific casualties against towers even if the enemy had no other defenders. Next I tried tanks, which fared much better. I put a tank bot on the scrimmage server and quickly got stomped by a team that was building launchers. Launchers were very powerful: their missiles had much longer range than any other unit and did a large amount of area damage on detonation. Plus launchers were the only unit that could destroy towers without taking damage, because they could launch missiles from beyond the towers' range. Tanks didn't really stand a chance. So I spent some time writing launcher code and started doing well in scrimmages with a pure launcher bot.

The metagame shifted when people got around to implementing harassment. You needed to mine ore to build a big army, so if you could kill the enemy team's miners, or at least prevent them from getting to the ore out on the map, you could get a big advantage. TeamK started crushing everyone on the scrimmage server with a bot that would just build lots of drones and surround the enemy HQ. And it turned out that drones strictly dominated every other unit type: they were the fastest unit, and could shoot while moving, and could always stay out of range of enemies. They could even outrun missiles fired by launchers. So the only way to compete was to build your own drones. TeamK's strategy was to build huge quantities of drones, suffocate the enemy with them until the round limit was almost reached, and then use the drones to the destroy the enemy towers at the last second.

My sprint bot took a slightly different approach: it built drones for a while and tried to surround the enemy HQ. After a while it started building some launchers too, and used launchers to destroy the enemy towers one by one. This worked well until I reached the finals and came up against TeamK. Here I learned two things. First, building launchers was a mistake: the correct strategy was to build only drones (because slackening drone production meant you lost the drone vs. drone dogfights). Second, TeamK's drone micro ("micromanagement," i.e., round-by-round decisions in combat) was way better than mine. TeamK crushed me as they had crushed everyone else and won the sprint tournament.

After the sprint tournament the devs nerfed drones; they had never intended them to be so dominant and now they tried to rebalance all the units. There was a period of experimentation where everyone had to figure out the new best unit composition. At first I worked on improvements to my drone+launcher strategy. Then I tried out soldiers. Soldiers were quite weak units, but I found that they countered drone harassment because they were so cheap that you could churn out a bunch of them and easily kill any drones that came for your miners. Soldiers could also harass, though they were not as good at it as drones because they had to path around obstacles.

I eventually ended up with three strategies with a sort of rock-paper scissors relationship. The simplest strategy was to build pure launchers. This strategy would often lose to a drone+launcher strategy. That strategy was countered in turn by a soldier+launcher strategy. But soldier+launcher would lose to pure launchers, because soldiers were really bad against launchers. I got really stressed out because I couldn't decide which strategy to run in the seeding tournament.

I eventually went with the soldier+launcher strategy. This was a little odd; not many other top teams used soldiers. And most of them had also stopped using drones, which is what my soldiers were supposed to counter, so my choice wasn't the best. A pure launcher strategy might have been better. I also realized that I had neglected the commander. It had been buffed after the sprint tournament and was now monstrously powerful, but I didn't realize that fact until after the seeding deadline. A few teams showed off the power of the commander in the seeding tournament: Skillorcz, MiracleRogue, and Simple Soldier are the ones I remember.

I won the seeding tournament even though my strategy wasn't necessarily optimal. At that point most teams didn't have very polished bots and lots of matches were decided by who had fewer bugs. I faced Skillorcz in the final round, and that match was quite close.

After the seeding tournament I worked quite a bit on the commander. The devs had always imagined the commander as a support unit. It had an ability that would increase the damage dealt by nearby allies. However the commander was never used this way, because the units it would work best with--soldiers and tanks--were always too weak compared to launchers. The teams that did build a commander used it as a lone harasser. The commander excelled in this role because it had high damage for quickly killing miners and high mobility for escaping enemies (every few turns it could teleport a short distance). Furthermore it would gradually heal up if it took any damage, and if it got enough experience its attacks would paralyze targets so they couldn't run away. Together these abilities made the commander extremely powerful and it received significant nerfs after the seeding tournament, though it remained quite strong.

After the seeding tournament I settled on a strategy where I initially built a commander as quickly as possible and then pumped out pure launchers. The commander would try to kill any enemy harassers it ran across, but its main job was to go to the enemy HQ and kill their miners. Meanwhile the launchers would work as quickly as possible to destroy the enemy towers.

In the end launchers formed the core of every top team's army. I don't think any team who didn't build launchers made it through the qualifying tournament. Instead the strategic choices were questions like: did you harass with drones, soldiers, commander, or not at all? Did you send your launchers out as one group or split them up to attack multiple towers at once? Did you attack quickly or did you wait for the enemy to attack first? Even though all top teams built launchers, there was still a lot of strategic variation along these lines.


What separated the top teams from the rest?


1. Building the strongest unit. The devs did their best to balance the power of the various units so that different strategies were viable, but generally one unit was the strongest. At first that unit was the drone. The top sprint teams all built massive drone armies. Team K won the sprint tournament by building nothing but drones and writing very good drone micro.

After the sprint tournament drones were nerfed. From then until the end of the tournament, launchers were king. There were two reasons: (a) a large enough mass of launchers could annihilate an army composed of any other unit type, and (b) launchers were the only units that could kill towers without taking any damage, because missiles outranged towers. Launchers received some nerfs after the seeding tournament but they were still the best. All the teams that qualified for the finals used launchers as the core of their army. Frequently they also built some other units to harass enemy miners, but goal of harassment was to deprive of the opponent of ore so that they couldn't build as many launchers. And you could do quite well by forgoing harassment entirely and just building pure launchers from the start (Team2 did this and placed 4th overall). People joked that to tell which team was ahead you just counted the number of launchers on each side--and it was true.

Teams that didn't build launchers fared poorly against teams that did. To do well, you had to build the right units. 

The lesson here is that you should frequently scrim against the top teams and copy their strategies. To do well in Battlecode you don't need to invent clever strategies yourself. It's enough to copy the strategies that are doing well on the scrimmage server. But you do have to be able to write the code to execute these strategies, which brings me to the next point.

2. Top teams' bots had a quality I would call "reliable execution." Whatever their strategy was, they executed it reliably. This meant a bunch of things. It meant that at any point in time, every robot was doing something useful. It meant that their units didn't get stuck while pathfinding. It meant that they didn't sit around waiting forever for some attack signal that never came. It meant that if they lost some units, they rebuilt them as quickly as they could and kept trying.

This sort of reliability was hard to achieve because executing a strategy required doing a lot of individual things right in a hostile environment. I'd say there were five main sub-tasks in 2015: you had to gather ore, you had to build production buildings, you had to produce units, you had to rally them to wherever you wanted to attack, and you had to kill the enemy units in combat. Each of these steps was nontrivial to code, especially since you didn't know the maps in advance and there were enemies actively opposing you. If even one step failed, you lost the game, no matter how clever your high-level strategy was.

So the top teams were the ones who had spent enough effort on each of these sub-goals that they could execute each one, and thus their overall strategy, reliably, no matter what the map was or what the enemy did.

One lesson to draw from this is that simple strategies are better than complicated ones, because simpler strategies are easier to execute reliably. For example, here is the logic my launchers followed:
  • Step 1: Shoot missiles at any nearby enemy units.
  • Step 2: If there are no nearby enemy units, head for the nearest enemy tower.
At a high level, that was all my launchers did. It worked well because it meant I was always attacking. You could imagine a more complicated strategy like "wait until you have 5 launchers, then move as a group to the nearest enemy tower, but come back to defend if the enemy attacks." But such a strategy has more failure modes. What if I never get to build 5 launchers because there isn't enough ore? What if I bring back all my army to defend but it turns out there was only one puny enemy unit attacking? What if I get stuck in a cycle of constantly moving back to defend, then forward to attack, then back, then forward, never getting anywhere? 

I think the reason I won the final tournament was that I had better reliable execution than other teams. My pathfinding was solid: my army essentially never got stuck behind obstacles. Some teams had good harassment and killed a lot of my miners, but my bot rebuilt the miners and kept going (while punishing the enemy for spending money on harassers instead of launchers). In every game, I attacked as quickly as possible and I never stopped attacking. So if the opposing team ever slipped at all, I won. 

Combat micro? 

In previous years, good combat micro was the single most important thing to focus on in your bot. I think that this year it was actually less important than overall reliable execution. There were a few teams whose launcher combat micro was distinctly superior to mine, and I lost a few games in the final tournament because of this. But the game was rich enough that you could make up for inferior micro in other areas. If a game came down to an even launcher-vs-launcher battle I would lose to these teams. But if I had mined better so that I had 50% more launchers, I would win. Or if our armies passed by each other without meeting I would often win by attacking their base faster. Or if their army got stuck behind obstacles I would win with superior pathfinding. 

In the grand final match I faced Skillorcz and won mainly because we played on two maps with tricky obstacles and my pathfinding was better. But in previous matches Skillorcz had demonstrated that their launchers were far superior to mine in a direct engagement.

Distributed pathfinding

I think the most unique thing in my bot was my pathfinding. Pathfinding was tricky in 2015 because most of the map was initially obscured by the fog of war, so you didn't know the locations of obstacles until you explored. Teams didn't need good pathfinding at first because drones were strong and they could just fly over obstacles. Furthermore in the sprint tournament the maps were pretty easy to navigate even for ground units. In later tournaments the maps became more complicated, and good pathfinding became more important.

A standard Battlecode pathfinding algorithm is the "bug" algorithm. Bug moves directly toward the destination until it runs into an obstacle. Then it follows the edge of the obstacle until it gets to the other side, after which it goes back to moving directly toward the destination. This is a nice and simple algorithm and it usually works well. However there are a number of pitfalls. How do you tell when you have gotten around the obstacle? This is easy if the obstacle is convex, but what if the obstacle is very convoluted? What do you do when the obstacle is another robot, which can move around?

I implemented bug, but I didn't want to rely on it. So my main pathfinding algorithm was breadth-first search. In this algorithm you work backward from the destination, finding optimal routes to that destination from every square on the map. Once you work backward to your current location, you start following the computed route.

This has two problems. First, it takes a lot of bytecodes. It can take hundreds of rounds to run. I dealt with this by writing a distributed version of breadth-first search that ran on all my miner robots, using whatever spare bytecodes the miners had left after mining. So I had a sort of "pathfinding supercomputer" made of miners. The supercomputer would broadcast the pathfinding results to the launchers. I always built 30 miner robots, so this would give a 30x speedup (minus some overhead from inter-miner communication), meaning I could do complete pathfinding in just a few rounds even for large maps.

The second problem was that you didn't know where all the obstacles were until you moved near them. So a launcher might follow a precomputed path and run into an obstacle that no one knew about when the path was being computed. I solved this with brute force: when a launcher ran into a hitherto-unknown obstacle, it would signal the miners and they would do the whole pathfinding calculation over again. With the power of the miner supercomputer this only took a few rounds and the launcher was soon on its way again.

This pathfinding was extremely robust and could handle arbitrarily complicated maps. At the final tournament I won a prize for best pathfinding because my bot was the only one that could navigate the really nasty maze-like map below. And as I mentioned above, superior pathfinding also won me a few maps in the final tournament, especially in the grand finals against Skillorcz.


The map for the pathfinding prize competition (sponsored by Bloomberg, who snuck in some advertising). Your robots started inside the right-hand B and had to destroy the enemy HQ inside the left-hand B. There were no enemy units: your opponent was the map.



Things I could have done better

Other teams had better micro than me. Skillorcz debuted some very impressive commander micro in the seeding tournament and their commander was probably still the best in the finals. A few other teams also implemented a clever trick in their launcher micro. Launchers could shoot missiles significantly farther than they could see. So a day or two before the deadline a few teams started shooting "scouting missiles" ahead of their launchers. If the scouting missiles saw an enemy they would trigger a barrage of follow-up missiles. To the enemy these missiles would seem to be appearing by magic out of the fog of war; there would be nothing to fire back at. This was a great advantage in launcher vs launcher engagements. I heard about this only after I had finalized my code and I couldn't motivate myself to try to implement it myself in the little time left. As a result I often got the worse end of launcher vs launcher fights against top teams in the final tournament.

I never optimized my mining very much. There were all sorts of complicated questions you could ask about mining. How many miners should you build? Building more takes more ore but increases your ore collection rate later. How long should you mine each square of terrain? Mining efficiency decreased gradually as you mined out each square. Should you mine the nearest ore or should you go to the richest known ore deposit? Should you send out explorers in the hope of finding particularly rich ore deposits? 

Given all this it might seem that to be competitive you would need to work out some fancy strategy for mining. Instead I had a really stupid strategy: always build 30 miners, and always mine the ore closest to my base. This was surely suboptimal in some cases: for example, on a map with little ore 30 miners might be way too many. I never noticed any big improvements by deviating from this simple economic strategy, so I kept it throughout all the tournaments. But I think some other teams did better; for example they could detect when they were on a low-ore map and would then build fewer miners.


Awesome people

Battlecode isn't just about the thrill of competition. If you participate, be sure to hang out in the #battlecode IRC channel on irc.freenode.net. I got to meet a bunch of cool people there and at the finals. Shout outs to the teams Skillorcz and TeamK (two finalist teams who flew from Europe to the live finals!), PaddleGoats, Designed by Committee, MiracleRogue, ayyyyyyyylmao, 10 pool, MunichSquad, and other teams I met whose names I don't remember because I'm writing this almost a year late. Hope to see you guys in 2016!



More on Battlecode 2015