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!

Monday, December 21, 2015

Battlecode idioms

In this post I talk about Battlecode-specific coding idioms I've used. Battlecode can encourage some weird constructions, usually because you want to save bytecodes. Before reading this post you should probably read Cory Li on bytecode optimization. Also check out Steve Arcangeli's code snippets.

Static everything

It turns out that accessing a static field or method of a class is cheaper (in bytecodes) than accessing a regular field or method. The reason is that normally to access a field or method you first have to push the "this" reference onto the stack, which costs an extra bytecode. So if you have a class for which you only ever make one instance, it's better to just make everything static and not make any instances.

Wait, but won't all your different robots interfere with each other by setting the same static fields? No: each robot has its own Java Virtual Machine. This means that static fields for one robot are not shared with other robots. (It has to be this way, otherwise you'd get free inter-robot communication).

In my code, everything is static unless there's a reason it can't be. One annoying case is that if you want to use virtual functions (that is, if you want to override a base class method or interface method) these have to be non-static.

Maps inside the broadcast array

This may change in the future, but in 2014 and 2015 each team had 65536 broadcast channels for communication between robots. This is a lot. It's enough that you can fit the entire map inside the broadcast channels, using one channel per square. Actually you can fit several maps, so I used this idea in several ways in 2015.

First, I used it to tell missiles what their targets were. When a launcher spawned a missile, it would write the robot ID of the missile's target to a broadcast channel corresponding to the missile's starting location. When the missile spawned, it would look at its location, calculate the corresponding broadcast channel, and read its target from that channel.

Second, pathfinding results were written to the broadcast array. I used a breadth-first search (BFS) algorithm to calculate, for each square on the map, which direction to move if you wanted to reach the current destination. So I had one channel for each map tile, writing to that channel the direction that a robot standing on that square should move next.

Third, the intermediate state of the BFS algorithm was stored in the broadcast array. This meant that many different robots could all participate in running the algorithm. So in my 2015 player, a miner with spare bytecodes would read the current state of the algorithm from the array and run the algorithm for a bit, writing results to the results channels. Then at the end of its turn the miner would write the new state of the algorithm to the broadcast array, letting another miner pick up where it had left off.

Instead of thinking of broadcasts in terms of little robots talking to each other via radio, you should think of the broadcast array as a region of memory shared by all your bots. Whatever you could do with shared memory, you can do with the broadcast array.


Precomputation

In some cases you can precompute things and store them in hardcoded static arrays. Then during play you can simply access the array instead of computing the thing. For example in 2014 robots could self-destruct, damaging all adjacent robots. I precomputed an array to answer the question, "Given that there is an enemy robot at position (dx,dy) relative to me, what directions can I move to bring myself adjacent to it?" The array gave a list of such directions for all small (dx,dy).

Be aware that initializing a static array does cost bytecodes. The compiler automatically writes a "static initializer" for your class, which is invoked when the class is loaded (which happens the first time each robot uses the class, so probably on its first round of life). If your static array is very large you may go over the bytecode limit on the first round of the robot's life. This may be fine, but be aware of it.

I heard Dan Gulotta suggest that hardcoded strings carry no such initialization penalty, so if you need to you can get around this initialization penalty by encoding your precomputed info in strings.

Here are some examples of this string trick that I might try using in 2016. Often you find yourself needing to take a square root when you compute a distance. In 2015 the devs set
Math.sqrt
to cost 20 bytecodes. But you can define a string containing the square roots of all numbers up to 32000 or so and then look up the square roots by indexing into the string:

Here we are using Java's octal escape codes in the definition of
lookup
. This can be used to specify
char
values between 0 and 255 decimal, which is 377 octal. The
integerSquareRoot
function above costs only 5 bytecodes per call, and you can save another bytecode by manually inlining it. This technique could be useful if you are computing square roots in a tight loop (and is probably a terrible idea otherwise). One limitation is that you are limited to about 32000 characters in string literals. Another limitation is that your text editor may balk at lines a hundred thousand characters long.

Another thing this technique might be useful for is precomputing random numbers.
Math.random
costs something like 75 bytecodes, so you could instead precompute random numbers, store them in a string, and pull them out at a cost of 5 bytecodes each.

Data structures

As Steve Arcangeli writes here, you should probably avoid java.util. Any data structures you need--lists, queues, sets, etc.--are best implemented as arrays if you want to be bytecode-efficient. Check out his example of a bytecode-efficient HashSet. I often find myself needing a queue, which I implement like this:

The array should be chosen to be large enough that you will never run over the end. It might seem wasteful to allocate a big array up front when you might not end up pushing many things onto the queue. However in Battlecode memory efficiency is not a concern. You are only charged for bytecodes, and you can use as much memory as you want as long as you stay under the limit, which is around 8 MB per bot. Java has a single bytecode to allocate an arbitrarily large array (even a multidimensional one!), so you may as well just allocate a really big one. The array is automatically initialized for free (to zero for integers, to false for booleans, etc.) which is often useful.


Debugging

I find it convenient to be able to quickly switch which indicator strings I am printing. For example maybe I want to take a break from working on combat micro to fix a pathfinding bug. I have some convenient debugging functions that allow me to do this:

Here is the Debug class that enables this. It also includes convenient functions for appending to an indicator string or clearing all indicator strings.

My Debug class also contained some utility functions for counting bytecodes, but I won't bore you by writing them out here.


Reading Java bytecode

If you want to come up with your own bytecode-saving tricks, it's helpful to be able to look at the bytecode itself. To see the bytecode that the compiler generates from your source, you can open up the .class file in Eclipse (probably other IDE's have a similar feature?). To learn what each instruction is doing you can refer to Wikipedia's list of JVM instructions.


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

Thursday, December 4, 2014

Battlecode links

There are a number of essays and posts on Battlecode strewn across the internet. I'm trying to collect links to all of them here, and I update this post as I find more. This post also has links to the software and game specs from past years so you can download and play previous versions. 

In addition to this post you should check out Bovard Tiberi's archive of Battlecode history.


General Battlecode posts

I read a lot of these to motivate myself before my first Battlecode in 2014!


Posts from specific years

Here are links to post-mortems and code repositories from Battlecodes past.

2009
  • Winning team gtg ice skating lessons' strategy report. (I'm hosting this myself; the original here seems to be down.)
2010
  • Winning team My Archon Died BellmanFording the Stream's strategy report. (I'm hosting this myself; the original here seems to be down.)
2011
2012
2013
2014
  • A nice post on Battlecode 2014 by David Westreicher of team schnitzel
  • My recollections as 2014 winner that one team
  • My code repository, which contains links to other 2014 repositories
2015
2016


Battlecode software from previous years


You can still download the last few years' versions of Battlecode and try them out. There are even recorded lectures and example code to help you out. If you are planning on doing Battlecode for the first time, a little practice on a previous year's competition can help you get a running start when the new game is released. While the game changes from year to year, the API is fairly stable and many of the problems you need to solve are the same each year. 

Battlecode 2013


The OpenCourseWare site for Battlecode 2013 has everything you need to try your hand at the 2013 competition, including the game software and specs, an example player, and recordings of the course lectures.  

Battlecode 2014


In Battlecode 2014 the goal was to herd cows into pastures and get 10 million giga-gallons of milk before the other team, while sending soldiers to shoot the other team's cows and blow up their pastures. 


Battlecode 2015


The 2015 competition was a pretty standard RTS game: you had to go out on the map and mine ore to make units to attack and destroy the enemy HQ. 



Battlecode 2016


The 2016 competition was a zombie invasion, with the goal being to survive longer than the other team or to destroy them outright.


    Even older Battlecode gameplay specs

    Here are the gameplay specs for the Battlecode competitions all the way back to 2001, the first year of Battlecode. Before 2007 Battlecode was called Robocraft. Thanks to Alex Chen for these links.



    The Tech articles about Battlecode

    Here are some articles about Battlecode in The Tech, MIT's student newspaper. Thanks to Dan Gulotta for these links.

    How to win Battlecode

    Perhaps you would like to win Battlecode. Here is how to do it.

    Priorities for your bot

    In 2014, I think that the best bots were the best because they did three things well: combat micro, pathfinding, and strategy. 

    I list these in order of importance. To win, you absolutely need top tier combat micro. You can't afford to fall behind in this area, or a better team will wipe your robots off the map regardless of your strategy.

    Almost as important, you need robust pathfinding. Many games were lost because one team got some or all of their robots stuck behind a convoluted obstacle, allowing the other team to pick up a free win. Note that I say "robust" and not "optimal." It's much more important that you not get stuck than that you get to the destination as fast as possible. A well-implemented bug nav is much, much better than a buggy A*.

    Finally, you need good strategy. While you do need to keep up with the metagame, robust execution is again most important. My bots made some suboptimal strategic choices in the final tournament but managed to claw back many of those games because the other teams' bots got confused or distracted and stopped making progress toward the goal of collecting milk. Your robots always have to being doing something sensible even if you are losing or the enemy is doing something unexpected.

    At least, that's how it was in 2014! If the game doesn't change too much, I expect that these will continue to be important priorities in the future.

    How to write a winning bot

    So how can you write a bot that wins? The most important rule is: copy other teams! If you lose a scimmage match, don't be proud. Copy the technique that beat you, whether it's a new strategy or a combat micro refinement, and start using it. This will also let you start developing counters to that technique, using your implementation as a test opponent.

    Make it easy to write lots of code fast. You are going to have to write (and rewrite, and rewrite) a few thousand lines of code in just a few weeks. This is not a lot of time, so you need to make it as easy as possible to write code efficiently. Use a nice IDE. Wrap the API in easy-to-use interfaces. I found it particularly useful to wrap the communications functions and debugging functions in nicer interfaces.

    Don't do premature bytecode optimization. Try to have a sense of which parts of your code cost a lot of bytecodes, but don't work too hard on optimizing them early on when they are still likely to change.

    Test a lot. Keep a lot of versions of your bot around and play your current version against others to test your improvements. Implement other strategies and test your strategy against those. I probably spent similar amounts of time coding and watching test matches between different versions of my bots. By the end of Battlecode 2014 I had 46 different versions lying around that I had used for testing at various points. The most rigorous testing ground is the scrimmage server because other teams' bots will behave in unexpected ways and you get to see whether your code can handle it. Keep in mind that the goal of testing is to see your bot lose: losing tells you what you need to fix and improve. So prefer to play scrimmages on your weakest maps. Fix all the bugs and problems you find in your testing, unless you make a careful and considered decision that the bug is too rare or minor to matter. Unfixed bugs will come back to bite you in tournaments.

    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!