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.

  • Winning team gtg ice skating lessons' strategy report. (I'm hosting this myself; the original here seems to be down.)
  • Winning team My Archon Died BellmanFording the Stream's strategy report. (I'm hosting this myself; the original here seems to be down.)
  • 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

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!