battlecode

I spent six years in grad school at MIT. Every year, the thing I looked forward to most was 6.370 "Battlecode" — a programming competition held in January during IAP (independent activities period).

I never won. I never placed in the top 8. I'm pretty sure I always placed in the top 16. I talked to some of the winners, and I think I played Battlecode wrong. The way to win was refinement — lots of tests and tweaks. But I just wanted to find some simple elegant hack that could win without too much code.

I failed. But here are some hacks I was proud of:

*

2006: The Drop

Robots mined energy by sitting on a green square. Each player started by a green square, and most maps didn't have any other green squares available. It was very difficult to attack the opponents green square, since they could regenerate units, and the attacking force couldn't, so the battle was generally waged over some hills in the middle of the map — whoever controlled the hills the most after some time limit would win.

But I figured the opponent's green square could be killed, with a StarCraft "drop". I built a bunch of mortars (very slow long range tank type things), loaded them into two transports, flew around the edge of the map, one going left, and the other right, arriving simultaneously, unloading just in range of their green square, and firing continuously. The mortars couldn't even see the green square — the transports had to tell them where it was before being shot down.

I didn't test this trick in the scrimmage matches — I uploaded it at the last possible moment. The next day, before the tournament matches started, someone told me they were impressed and scared of my drop. I asked how they saw it, and apparently one of our scrimmage matches was delayed in the queue, and when it finally ran, it ran with my latest code, but the deadline for the other team had already passed to upload new code.

Anyway, it did well, but it didn't win. I seem to recall in my final match killing the opponent's green square, but that map had alternate green squares, and their team managed to take one.

Still, I was flattered to win the vote for best strategy, which was a prize of a PSP.

2007: Regular Expression Pathfinding

This year had upgrades scattered around the map. Navigating to the upgrades required path finding, and although everyone knew about A*, the issue was implementing it efficiently. The world of Battlecode provides relatively few bytecodes per time-step — so few, in fact, that most people didn't use A*, and those that did faced a tradeoff between thinking time and moving time.

To make things easier on people, the Battlecode engine would discount the bytecodes involved with various standard library methods, counting them as a predetermined fixed number of bytecodes regardless of what happened inside the function. For instance, Arrays.hashCode would count as maybe 100 bytecodes, regardless of the length of the array being hashed.

Battlecode excluded certain standard libraries, including java.util.regex. However, they didn't exclude String, and String has a couple regular expression methods build into it: matches and replaceAll. And these functions could be called for a fixed bytecode cost, regardless of the size of the string being matched against.

This gave me an idea about how to do path finding — a method that would be extremely inefficient in terms of actual computation time, but counted as fast by the Battlecode engine:

Step 1: Encode the entire map as a giant string. Mark traversable squares with a ' ', mark myself with an 'x', mark upgrades with a 'u'.

Step 2: To find the shortest step toward a 'u' from 'x', replace blanks next to u's with u's, until there's a u next to an x. If the u is north of the x, go north, etc.

Here's an excerpt of the code (full code here) with highlighted regular expressions:

for (int t = 0; t < 40; t++) {
if (s.matches(regex(".*(x(?=.{A,C}u)|(?<=u.{A})x|(?<=u.{B})x|(?<=u.{C})x|x(?=u)|(?<=u)x).*"))) {
...
if (s.matches(regex(".*x(?=.{B}u).*"))) {
... = SOUTH;
} else if (s.matches(regex(".*(?<=u.{B})x.*"))) {
... = NORTH;
} else if (s.matches(regex(".*x(?=u).*"))) {
... = EAST;
} else if (s.matches(regex(".*(?<=u)x.*"))) {
... = WEST;
}
...
return ...;
}

String ss = s.replaceAll(regex(" (?=.{A,C}u)|(?<=u.{A}) |(?<=u.{B}) |(?<=u.{C}) | (?=u)|(?<=u) "), "u");
if (s.equals(ss)) break;
s = ss;
}

Note that the regex function is replacing the A's, B's and C's with numbers having to do with the size of the map.

Now normally a robot wouldn't have enough time to iterate over a small portion of the map within a single time-step, which made even A* difficult, but my robots would iterate over every square of the entire map 40 times within a single time-step and have computation to spare.

Of course, this strategy was so inefficient that it slowed down the Battlecode engine itself, and for fear of triggering some red flags amongst the dev team hosting the competition, I restricted this path finding to only certain robots (the other robots would just follow them).

This team did extremely well, and was at the top of the scrimmage server for most of the time leading up to the final tournament, but near the end, another team rose above me with a team making efficient use of a robot type that I wasn't using — they were using a weak-fast unit, while I was using a strong-slow unit.

So, wanting to win first place, and knowing I would lose to this particular team with my current strategy, I made a last-minute change, which turned out to be bad. I started using the weak-fast unit myself, which required making more of them, but they were harder to navigate through narrow passages (since they were all crowded around the special path-finding unit), and in my final match, my robots literally got stuck trying to navigate through a small hole in a wall.

Still, the devs were impressed with my regular expression path-finding hack, and I got some sort of prize for it :)

2008: Attempted Genetic Algorithm

I had a teammate this year, and he had access to a 16-core machine which we tried to use to genetically evolve the parameters for a robot player. We actually did get all the infrastructure set up to do it, and ran a few generations, but we ended up thinking of strategies that existed outside the parameter space of the player we were evolving. I was sad that the genetic algorithm strategy didn't work out. I was so hopeful.

I do feel proud of our team logo though. I had been calling my team "little" from previous years, and that name had earned some cred in the community, so I wanted to keep it. My teammate was fine with that, but I felt bad anyway. So, since his name was "yang", I made this our logo:

2009: Communication Warfare

Battlecode robots can't talk to each other directly. They need to send messages. The thing is, the enemy team can hear the messages too, if they are in range. Not only that, but there's no way to know for sure who sent a message. So there's some possibility of communication warfare, by trying to send fraudulent message to the other team, usually by re-broadcasting messages received from them earlier, after corrupting them with random modifications.

Most teams don't worry about this since communication warfare is hard (it's hard enough to get the robots to do anything at all), meaning that most teams don't bother to do it, meaning that defending against it is usually worthless. However, the top teams generally do worry about it, since they don't want to lose against a team that actually does modify and re-broadcasts their own messages.

So how does one protect against someone modifying a string? Usually by hashing it, and sending the hash as well. Of course, the bytecode restrictions are pretty severe, so hashing the message can be costly, but it's cheap to use the Arrays.hashCode function, since that one is discounted (as mentioned above).

However, it turns out that Arrays.hashCode is not cryptographically secure. I took at look at the sourcecode for it, and devised a way to modify an array, without affecting the hash of the array. Here's the way Java hashes an array of ints from Arrays.hashCode:

public static int hashCode(int a[]) {
    if (a == null)
        return 0;
    int result = 1;
    for (int element : a)
        result = 31 * result + element;
    return result;
}

Here's a snippet from my robot's code:

public static void corruptMessage(Message m) {
    ...
    int i = r.nextInt(m.ints.length - 1);
    int x = r.nextInt();
    m.ints[i] += x;
    m.ints[i + 1] -= 31 * x;
    ...
}

It would pick two sequential elements of the array to corrupt. It would then add a random value x to the first element, and to preserve the previous hash value, it would then subtract 31*x from the next element.

One of the top teams was in fact affected by this, and told me about it. As I understood it, they were sending map coordinates, and they would resize an array to hold coordinates that fell outside their current map data structure (since the robots don't know the extents of the map when the game starts). However, when they received corrupted coordinates from me, they would often resize the array to be gigantic, and throw an out-of-memory exception and die.

I believe they fixed this before the final tournament — I think I included the message corruption in my scrimmage player and they noticed their robots mysteriously exploding in some scrimmage matches. However, I recall getting some sort of "message warfare" award.

2010: Teleportation

It wasn't much, but I did get a prize for some teleportation code. There was a teleportation tower unit that could teleport units near it to other teleportation towers. And I had a bit of path planning code that factored in the possibility of teleportation — though not with regular expressions.

2011: 6.470-staff

While competing in 6.370, I was helping run 6.470, a web programming competition. In fact, four of the 6.470 organizers were interested in competing in 6.370, and so we pooled our resources under the Battlecode team 6.470-staff. This year was perhaps the most complicated Battlecode environment to date, with robots that could be customized with components, and I spent some time writing code to simulate duels between robots with various components in order to know what configurations to use in response to enemy configurations.

Appendix

* Note that the 2006 shirt says RoboCraft. This was the original name, but to avoid angering Blizzard, it was changed to Battlecode, and in fact Blizzard became a sponsor of Battlecode in 2008.

Here are the fronts and backs of all my Battlecode shirts.

Here's all my Battlecode sourcecode.. well, most of it. I don't know where my code is from 2006.