Battlecode: MIT's longest-running hardcore programming competition

As MIT’s Independent Activities Period draws near, I’ve received quite a volume of inquiries from underclassmen about “what should I take?” or “which of these competitions is better?”

It would be nice if I could point all future questions to a single place. So here are my thoughts on (read: pitch for) Battlecode – MIT’s longest-running and most badass programming competition.

What is it?

On a cold Boston January night on a dark stage in front of hundreds of cheering students, two teams will command massive armies and engage in deadly warfare – all within virtual reality. By this point, both teams will have worked tirelessly for four whole weeks to program and polish the best possible AI.

The battlefield itself is rendered in 3D on the center screen of MIT’s main auditorium, with two side screens providing a map overview as well as match statistics. The crowd cheers as the AIs are initialized and the two sides begin constructing robots, capturing objectives, and annihilating each other to the sound of lasers and explosions.

Eventually one team will be violently eliminated in a display of tactical genius on the part of the other – the eliminated team was unable to design an effective counter in the last week leading up to the finals. Sadly, they walk off the stage, a little disheartened, but happy to have made it so far in the finals for their first time. For the remaining team, however, the dream of glory and thousands of dollars in cash prizes lives on.

Overview

Battlecode is a programming competition (course number: 6.370), in which groups of up to four students program AIs to wage war in a Real-Time-Strategy game-like simulator. For those of you who are unfamiliar with the competition, here’s a small collection of matches from previous years:

For a brief overview:

• Teams of MIT students submit code that will run on their team’s robots within the simulator.
• The AIs are decentralized, meaning that robots do not share global information, and each robot must make its own decision based on the local environment and information nearby robots have radioed in.
• The game ends when one side captures the objective (changes from year to year), or eliminates the opposing enemy team.

The finals are held in MIT’s largest auditorium where hundreds of students gather to watch and cheer on as the two AIs duke it out live on stage, while the teams provide a running commentary on their design and strategy. Winners have the chance to dip their toes in prize pools of $40k+, there’s usually a ton of free food, and the whole spectacle is a ton of fun.

(If that doesn’t give you nerd chills, I don’t know what will.)

Why should I care about Battlecode?

If you’re a coder, then no doubt there is some confusion as to the merits of the various competitions on campus as the number increases every single year. Understandably, the web and mobile tracks have seen increased uptake, both due to the general startup craze, and in paraphrased words of fellow alumnuis @cyen, working with web/mobile technologies represents “real-world” vocational training that some students feel they lack.

While it’s true that the AI you write for Battlecode is not going to be the next big webapp or the cool new business entered into MIT’s $100k competition, the experience of hacking on a difficult problem with short deadlines will definitely improve your technical chops – more-so probably than building a pretty CRUD app to win the web-app competition.

From past winner Albert Ni:

Battlecode is such a valuable experience because it’s basically the one software engineering experience you have at MIT where you’re forced to make a ton of tradeoff decisions, but the wrong choice in the wrong place can literally be the difference between victory and defeat. Surprisingly, to me Battlecode turned out to be excellent preparation for the startup world because there you also don’t have enough time to get every last detail right and thus have to decide where to focus your limited energy, but focusing on the wrong things can doom your company.

Ironically you don’t actually get this engineering experience as much in the webapp or mobile app competitions. In both, contestants are expected to quickly cobble together a simple 30-day prototype, but the “rubber never really meets the road” as teams aren’t judged on relevant tangible metrics (and therefore not under pressure to make do-or-die decisions) such as week-over-week growth rate or profits.

As an example, in our team’s bot, I can point to a single commit that was literally the difference between winning the whole competition and being a runner-up: this untested 35 line hack was made one hour before the submission deadline as a last ditch effort to counter the one team we knew we would lose to in the finals (on the last day we consistently lost to them in unranked scrimmage matches). There’s nothing quite like standing on stage in front of hundreds of people hoping that your untested hack deploys correctly.

No one writes bug-free (or even pretty) code in Battlecode, but contestants quickly learn how to avoid the catastrophic bugs that singlehandledly lose games. They learn to allocate time efficiently, quickly prototype new strategies, and test often (you can sit and theorycraft all you want, but at the end of the day, only wins on the scrimmage server and tournaments count). And all this is done working closely with two or three other classmates under immense time pressures – a recipe for long nights, heated arguments, and massive merge conflicts.

These experiences and skills learned through Battlecode are hugely relevant in software engineering, startups, and life in general.

We have awesome alumni too!

If you’re still not convinced that Battlecode is the best IAP competition, allow me to point you to its rich history of alumni who later went on to do some amazing things:

• David Greenspan and Aaron Iba, two of the original directors of battlecode cofound a AppJet together (acq. by Google for $10MM), which launched etherpad, still one of the downright most useful web apps I have ever used. Aaron later went on to become a partner at the well-known startup incubator Y Combinator.
• Drew Houston (top 8 battlecode finalist) and Arash Ferdowski (battlecode director) cofounded Dropbox together. A significant percentage of Dropbox’s core engineering team are all Battlecode alumns too including Albert Ni, KMod, Zviad M., and Steve Bartel.

And if you’re not a programmer at all, you should still come to watch the matches and listen to the teams discuss strategy. It’s definitely a ton more exciting than watching an animated excel graph of numbers.

But… JAVA (whine)

There seems to be an increasingly allergic reaction to Java in the hacker community for its verbosity, ceremony, and corporate stooginess (see this poem). The JVM-based nature of Battlecode has certainly drawn much criticism in this regard - especially when MIT’s entire computer science curriculum is Python-based. Java’s certainly not the coolest language these days.

You quickly find, however, that the Java necessary to perform well in competition is nothing like anything you’ve ever written before. The AI of every individual robot is encapsulated within it’s own virtual execution environment, and the computational currency is not execution time, or even memory, but rather JVM Bytecodes.

What? Bytecodes? I can already hear some of you say. Hear me out – this strange limitation has some wonderful merits. Within these confines, contestants are forced to throw away everything they know about computer science and build their own data structures, their own architecture, and their own algorithms from scratch to deal with such constraints. It forces code to be lean; it forces contestants to be creative and continually innovate new heuristics that run in linear or sublinear time; most of all, these things all have to be self-discovered or invented, as there’s no immediate book or guide to turn to.

Being creative and arbitraging the bytecode counters is well within the spirit of the game, leading to some of the most remarkable hacks I’ve ever seen. A small oversight in the specs counted java.util.regex as a fixed-cost. Team Little’s 2007 entry exploited this with an impressive regular-expression encoding of dijkstra’s algorithm, allowing them to perform an O(nlogn) algorithm in just O(1) time. The hole was patched the following year after Little won recognition for the clever hack. Never-the-less, the existing cat and mouse game between the constestants and the devs has lead to an ever-evolving game. For more examples, Steve Arcangeli has a very detailed post explaining some of the clever data structures they were able to exploit during the 2011 competition.

Despite being severely bytecode-limited, you still have to program an AI for a game that is insanely complex. Consider that not only do you have to write good heuristics for pathfinding and attack code, but you also need to share information between robots by broadcasting data packets (as each robot is its own autonomous entity). Thus, in addition to the actual attacking / firing of lasers, there is a second unseen battleground of information warfare. This leads to all sorts of shenanigans. In 2009, teams thought they were being clever by exploiting the fixed cost of Arrays.hashCode() to hash messages cheaply in O(1) time. But Greg Little went even one step further, looked up the OpenJDK hashCode implementation, and designed a messaging attack that mutated the contents of the array without changing the resulting hash. His bot was able to completely disrupt enemy communication, and in some cases, cause them to overload and stop moving via erroneous messages. Badass.

So, despite the Java heritage, Battlecode still offers something for everyone – the hacker dreams up neat ways of executing computations within the confines of the engine; the computer scientist drafts the algorithm to compute on the platform; and the low-level performance engineer optimizes it to make it bytecode efficient. All the past winners of battlecodes have been amazingly talented hackers that I seriously look up to and respect for their ability.

To conclude

Having participated 3 consecutive years in Battlecode, I can definitely say that, at least for me, it was the best use of my time during IAP. There’s really nothing like four friends moving together into a single dorm room for one month with a bunch of monitors, a ton of ramen, and a battleplan for victory (In that sense, it’s probably more “startup-y” than doing 6.470/6.570). And despite being a competition, the top teams have always been amazingly generous, offering to share code secrets, tips, and techniques even when I was first a beginner just getting off the ground. Learning from and interacting with some of the best hackers MIT has to offer is quite a humbling experience.

To any MIT students or prospectives considering Battlecode: find a few friends and dive in! You definitely won’t regret it.

To read further

The brand new 2013 game spec will be released January 7th late afternoon. Meanwhile you can check out the old 2012 spec to get a feel for the game details.

In the spirit of Steve Arcangeli’s postmortem on the 2011 winning bot, my next few posts wil be on our 2012 experiences as well as tips, tricks, and techniques relevant to the current battlecode engine. We were fortunate enough to utilize a few of Team Gunface’s tricks in the design of our own bot and would love to continue the tradition by writing up a few of our own. (By the way, if you’re interested in participating in Battlecode, both of Steve’s posts are required reading. One of the only resources out there that really details the thought process behind some of the design while also swapping old war stories).

I’m also going to kick the generousity up a notch and in addition to just writing up code snippets, with the permission of my teams, I’ve also open sourced all of my previous battlecode bots. In order, they are:

Feel free to browse through the code, though the commenting density is somewhat inconsistent, and a lot of last-minute changes are undocumented and/or inconsistent with the provided documentation. Also, don’t read through the commit log if you’re easily offended.

Lastly, if you’re interested in sponsoring future battlecode competitions, check out their sponsorship info.

Edit: Check out comments from past competitors and devs on the Hacker News thread