Hacker News Reader

Comment by aaroniba | Hacker News Reader

BattleCode was the best thing I did while at MIT, and one of the most unique and rewarding experiences of my life.

The way David and I were able to win it in 2003: at that time, robot positions were stored as two doubles (x,y). You could move yourself by a precise amount or read the precise x,y position of another robot, each in only 1 bytecode. So instead of using broadcastMessage(String), checking that no other team was trying to screw with our messages, all of which took lots of bytecodes to get right. Instead of that, our robots communicated through the low bits of double values in their positions. Kind of like bees dancing for each other. This gave us enough of an edge to beat out all the other players. This was 100% David Greenspan's idea, by the way. I just worked hard to help code it up.

MIT classes are supposedly a lot of hard work, but at that point I had never worked as hard on anything as I did on our BattleCode player.

View on HN

Working on Battlecode was the same way for me, most intense time I've ever spent at MIT. Lots of teams were really into it which made it all the more competitive and fun.

In 2009 one of our rivals was a solo coder who was in the top 8 of the previous year (we became friends through the competition and still hang out to this day). He relayed to me a story of how one of the other teams had tried to sabotage his efforts. They sent a female member of their team over to his room to convince him to drink with her. It didn't work, although that was mostly because he already liked to drink and code.

Awesome story!! What an amazing guy.

Drunkasaurus! Oh man, 2009 was a good year :)

I'll echo what skates and iba said -- battlecode was probably one of the most productive things I did in school. when everyone else is trying to teach you how to properly to document your preconditions, battlecode is purely about GSD (get s* done) - an extremely valuable lesson for an aspiring young entrepreneur.

my favorite battlecode hack: we used to assign a fixed "cost" to certain methods, namely Arrays.hashCode(). one of the more experienced players figured out that everyone was using this to checksum their radio broadcasts. he then proceeded to reverse engineer the hash code algorithm and spam teams with enormous messages that had legitimate checksums but were actually just megabytes of trash! the poor opponents would just sit there chewing cpu until the engine finally killed them for using too much heap :)

edit: actually read through cory's post - glad to see he already mentioned this one!

Hey Aaron.

Communication via entity position is genius. Awesome! I wish my team had thought of that.

I have to say that being a contestant in 6.370 (robocraft/battlecode/etc) was easily the most fun, and the best practical experience I had while attending MIT. So, hats off to you and your partners for turning it from fun into excellent.

What I especially enjoyed about the 6.370 experience was the instructions constraint. With it being as low as it was, you really had to get smart about stuff like pathfinding - you could write a respectable AI using more normal approaches, but I suspect most contestants throw away traditional algorithms pretty quickly.

Less loved was that Java's compiler appears to hate (or maybe hated, at the time) efficiency. My teams usually wound up disassembling in order to find places where java was being stupid at compile time, and finding ways to get it to be less so. It makes a pretty big difference when every instruction counts. But, if it hadn't been for that, I might not have taken Compilers subsequently, so...

In any case. Thank you for your contribution to an enduring and truly excellent tradition in the MIT lexicon.

Yeah navigation via A* / other traditional algorithms is almost always a no-go in Battlecode because of the way the bytecode limitation works. You almost always have to create some extremely custom pathfinding algorithm tuned to the constraints of the engine.

The simple algorithms are stuff like bugnav (walk in your desired direction until you see a wall then attempt to trace around it), but you'll find that even in something as simple as bugnav, there are a _ton_ of edgecases you have to account for in a discrete implementation that results in robots tracing around each other / stuck in infinite loops, etc.

Our 2012 bot uses a special implementation of the discrete tangentbug algorithm that allows us to precompute squares during rounds which we have extra bytecodes to spare[1]

It's probably _the_ most complex part of our codebase, and the person who wrote it doesn't even really understand how it works anymore.

[1] https://bitbucket.org/Cixelyn/bcode2012-bot/src/default/team...

I think the last time we played, one of my teammates came up with 'detractors'; i.e. 'stay away from here, it's bad news', once a bot was sure that a place was not good for pathing, they would drop one and it would make its way around to the other bots.

That actually worked surprisingly well. Our implementation had briefly stupid behavior in a few scenarios, but after a lot of testing it was clearly our winner.

It looks like this year isn't as big on the pathing, as 'every square on the map is traversable, and there is no longer any distinction between ground and air units.'

That's mighty unfortunate. I thought that was one of the more interesting challenges.

At first, I was a bit "meh" about this article, right about until I read about the bytecode hacking, very awesome, the ex-demoscener in me rejoiced :)

Reply on news.ycombinator.com