Battlecode 2019 – An Autopsy

Posted by

Battlecode is MIT’s longest running programming competition which attracts thousands of contestants every year. Teams of 1-4 students spend their January to code up their bots to battle in a unique swarm-like game. They fight for Karbonite. They fight for domination. They fight for the glory of being Battlecode champion. While each year has its own unique game, the ideas of resource gathering, swarm teamwork and combat are staples of the game strategy.

I wasn’t new to competitive programming, but this was my first Battlecode ever. I started out solo and didn’t really know what to expect going in, but as the games turned in my favour I quickly took it more seriously and now I’m quite content with my experience competing in Battlecode.

My result: 5th place overall with the bot “Justice Of The War“.

Battlecode: Crusade – A Martian Holy War

In this year’s Battlecode, teams each start with 1-3 armed castles on a symmetrical map, which both players initially have info about. The map is a grid containing karbonite and fuel resources scattered in tight clusters, as well as passable and impassable squares. Karbonite is spent to build units, while fuel is used in every action – attack, movement, communication, and also building.

Both team’s goal is to eliminate the opponent’s castles. If no annihilation occurs, the tie is broken by #castles remaining, followed by total unit health, and finally a coin flip if those are also equal (rare).

Castles can build 4 types of mobile units. Pilgrims are miners and long vision scouts, Crusaders are cheap but mobile warriors, Prophets are long range glass cannons, and Preachers are high damage but low range tanks. Pilgrims can also build churches, which like castles are immobile, can build units and can receive resources from miners, but have half the HP and are unarmed.

In the game, each bot has its own process, time limit, and limited vision of the game. Robots communicate via signals – 16 bit messages that take fuel to broadcast. The higher the radius, the more the fuel cost. There is also a free 8-bit channel directly to all the team’s castles which all robots can use each turn.

My Battlecode Journey – Make Your own luck

I started Battlecode quite late. I missed the sprint tournament entirely, and just wanted to submit something for the seeding tournament to see how I would go. Somehow, the tournamet RNG gods were on my side and I did quite well. As the games went in my favour, I decided to take it very seriously and made it to the finals.

Seeding Tournament – An Unexpected Result

For this seeding tournament I did what I thought were the absolute basics – an AI that was capable (but not efficient) of mining and expansion via castles sending out pilgrims, and capable of amassing units and ordering an attack on the enemy castles at some point in the game. I didn’t do any scrimmages or work to test the effectiveness of the strategy, I just wanted those concepts in code as a coding exercise. I didn’t expect to place above other highly talented teams.

As it turns out, it was a great idea to get a basic bot going early in the competition. My bot with the mere un-tuned basics managed to place 12th, which was a great seed. If sustained, I would enter the finals.  Perhaps this is a lesson to future teams, that it’s very useful to get something in that covers the basics to get the engine running, rather than implementing the “ultimate” AI right away and miss the seeding tournament / get hit hard by a spec change.

With such a good seed, I decided to give Battlecode 2019 a proper go and disregarded life for the next 2 weeks.

The Road to Qualification

After gaining an understanding of the mechanics and strategy, it was clear that my code was terrible and I needed a new framework. Time for a rewrite, and I would seriously consider my strategy in the process.

Expansion

I had a feeling that quick and reliable expansion was a key factor that decided games. Expansion needed to be centrally coordinated, since churches sending pilgrims on an expedition could not tell which resources were occupied and which were not. 

I implemented effective castle-talk communication which included friendly unit locations and enemy unit sightings to help castles deduce which clusters were occupied, and which ones were available. Commands from the castle to churches now allow “pilgrimages” to start from the nearest structure to the expansion target, which allowed rapid expansion.

Later, I realised that central resources are often in hot contention and were the game deciders. It wasn’t good just to go for the closest resource, leaving the central ones to be nabbed by the opponent. I fixed this by adding weight to resource chunks near the center when deciding which ones to go to. Choosing the next resource to go to given weights was also an interesting problem. You don’t want to just go to the closest resource, it might be low value compared to a slightly further one. You don’t want to go to the highest weight one either, since it might be very far and you’ll miss everything along the way. I decided to go halfway. I invented my own metric and went to resources that minimised the “potential” of my position – the sum of (distance * weight) to remaining unclaimed resources. This meant that, for example, given a choice of equally far and valuable clusters, my bot would choose to expand to one that was also close to other valuable resources. The result was quite nice, but it was already at the point of diminishing returns:

 

Defense Lattice

The overall meta this year seemed to be “turtling”, which was to surround your castles with long range prophets. It is difficult to counter once established – enemy units must step into range first and get annihilated by many prophets before being able to make its first shot. This is because attack and movement cannot happen on the same turn. The endgame was that if we preserved our units better than the opponent then we can win by tiebreaker on unit health without needing to attack.

Days before the Qualifiers, I made a few adjustments to my lattice which proved to be very effective. Firstly, the lattice is built forwards to form an “umbrella”. Not only does this put my prophets in the most useful defense position, ie. between the enemy and the castle and not behind the castle, it also steals some early space so that the opponent needs to walk into my range to expand later, leading them to get picked off. Secondly, high HP crusaders were added to the lattice to boost unit health near the end of the game to win on tiebreakers. They were thrown to the back since they weren’t used in defense. This was the result, in the midgame where crusaders started showing up: 

Rush Defense

It wasn’t until a few days before the Qualifiers that I realised my bot was horribly vulnerable to a simple 3-preacher attack. My expansion was way too greedy, and my tower couldn’t build an effective defense quickly enough, even with its built in cannon. Scrimmaging against team “Volatile”, who was a classic rush bot, showed many preventable losses.

I realized that I would need to test my defense regularly, and decided to write my own 3-preacher rush to test quickly against. This was a good idea, the 20-minute investment saved countless hours of scrimmaging.

What resulted from my experimentation and trial and error was a very nice rush defense tactic. It included a good choice of defense units as a reaction to seeing an enemy rush, micro-optimization of valuable initial karbonite, and attack order which tried to get my units to attack the same target.

I also re-implemented my enemy-sighting castle-talk. Originally, it took 4 turns for a unit to report an enemy with full location, type and id. When I got it down to 1 with some compression and incomplete information, my castles actually found the info useful in defense. Now, if a rush came into view of a friendly unit close to the castle, the castle can prepare a defense before the rush even enters the castle’s vision. This dramatically reduced the damage my castles took during a rush, since it could order a halt in expansion to save resources for the emergency, and send out a few prophets that had time to get into position. 

This was the result, notice how the castle starts building before the rush comes into view:

 

Resource Management

A common cause of losses for lattices I saw in the seeding tournament was running out of fuel. After the fuel was gone, the prophets could not shoot, allowing the enemy to get right up close and slaughter everything. So, I made sure to implement some kind of resource management. For the qualifier tournament, global messages were sent from my castle periodically to inform all builders of the global fuel reserve target. This target was the result of a formula that tried to guess the potential strength of the enemy’s army, assuming both sides were equal.

Results

I didn’t get to see many games, but I was happy to see my bot make it’s way up the rankings. I’m glad most of the things I did helped me win games. For example resource management was crucial in winning against team “Chicken” to secure the Winner’s 8. They threw a constant bombardment of crusaders that tried to drain a lattice’s fuel, but my resource management allowed me to barely hold up. In the end, my bot got 4th seed, which was amazing.

The Final Scramble

There were only 50 hours between end of seeding tournament and end of finals submission. So far, my strategy has been purely defensive, and I didn’t think there could be much left to change in terms of the overall meta. I was very exhausted, ready to take it easy for 2 days. I was also very wrong.

I myself added a new twist to my strategy. I decided that my bot wasn’t just going to tolerate having fewer resources anymore and passively lose a turtle war. Instead, it was going to “rage war”, whenever it realizes that it’s lost the resource race. So I made my bot attack central resources controlled by the enemy with a wave of prophets and preachers, whenever my castles determined that it’s lost the resource race. It was the only real attacking behavior in my bot, and it seemed to convert many games which it would have otherwise lost. 

Discussions about “church lightning” started to come out of the closet. Many people (including me) thought they were the only ones to think of this exploit – to build pilgrims and churches in alternation in a single turn of the turn queue. Some teams started to implement it and created frightening attacks against what used to look like impenetrable lattices. Some already had it. I tried, and spent more than a dozen hours before realising that it’s just too risky in terms of development and strategy and decided to just improve what I had.

Many teams also came out with aggressive tactics. Team “smite” were one of the first to use harassing units to disrupt the enemy’s expansion efforts and killed innocent pilgrims. Just a day before the finals submission, the High School tournament revealed new metas – dropping “offensive churches” right into the enemy position and spawning warrior units from them with first hit. This was one of those things which you brush off early in the contest without realizing how effective it really was. Some teams like “Gisthekey”, “chicken” and “smite” employed that in the finals. My scrim history against those tactics were horrifyingly bad.

Showdown at the Finals

The final tournament is a double elimination with each match consisting of a best of 3.

A Rough Start My first match against “CitricSky” was a good match but a bit unlucky. The first game went to CitricSky who had superior expansion and just took over the whole map. In the second game, CitricSky took the lead in development again, however my prophets successfully flushed them out of some key central resources in the midgame with the “rage war” attack, and narrowly took the game. In the third game however, a very unfortunate bug I left in my crusader lattice let CitricSky win the unit health race as I lost on the tiebreaker. I was knocked down to losers in the first game. 

Long Road Ahead
Being knocked down so early also meant you had to fade many more matches to stay in in the double elimination format, so it’s a double whammy 🙁

I unfortunately had to face my fellow Aussies NP-cgw very soon in the 1st match of the losers bracket. They are a brilliant team and had some amazing tactics, like their spectacular calculus attack and church lazers, but it was very unfortunate that they never had a chance to show that in the finals. You need a bit of luck in these tournaments, and they didn’t get any. The map selections were not in their favour and I won the match and advanced.

From then on I had some good bracket luck. I saw that my selective “rage-war” strategy really stole some crucial games against passive enemies as I advanced. 

A Unexpected Victory
It was time to face “Gisthekey” who had frighteningly good aggression against my greedy expansion. Our scrimmage record was not good for me, which I only had a score of 3/10. 

In the first game, they completely annihilated me on a large map using agressive churches in very few turns. I was nervous going to the second, but my bot remained emotionless and determin(istic)ed. The second game featured a smaller drier map which favoured me. Without any expansion, my defense grew quickly and rendered their aggressive church ineffective. I went on to win that second game. In the third game, their attack was initially on fire. There were two central resource clusters, and they were doing damage to the closer one which I barely controlled. However my expansion was not distracted by the fight and took the cluster far away, while Gisthekey failed to send any pilgrims there. Now with more resources than Gisthekey, my bot was able to put up a defense, and won the match. I was very lucky to survive this matchup.

Elimination

Next was Standard Technology, who won the #1 seed in the qualifiers without losing a single match. But the meta has changed dramatically since then, and now I face them in the losers bracket.

They had a crusader harass opening which I somehow avoided in the first game, but in the second they established territory that I couldn’t take back. It’s now 1-1, and we went to the final game of the match.

At the start, they harassed their way into controlling some key central resources. But soon, prophets started amassing from my church near them. In one foul swoop my prophets took them back – the “rage war” tactic. It drew audible gasps from the crowd. However, the victory was short lived. The attack lead to my churches being completely undefended, and in that short window Standard Technology took one of them down along with a huge resource cluster. My castles, with information received from units, recognized that they were at the rough end of a pretty close imbalance. It ultimately decided that retaking that cluster was needed, otherwise it would lose the unit health tiebreaker.

Unfortunately, it initiated many attacks that simply ran out of fuel, and didn’t amount to a successful retake. It was not a well tuned strategy because I only had a few hours to work on it, however it did carry me quite far into the tournament. The cost of the war on my side allowed Standard Technology to take the match on tiebreaks, and I was eliminated in 5th place.

“Smite”, an experienced and determined team, would go on to win the tournament with the High School phenomenon “Knights of Cowmelot” in 2nd place.

What I have learnt & Final thoughts

Firstly, thanks to all the devs who work countless hours on battlecode with no pay and have to put up with everyone’s nagging and complaining on discord. I can’t imagine how stressful it was when things started to go wrong. Thanks also to all the sponsors who made Battlecode possible.

In games like Battlecode, optimal strategies can be very complex and unexpected even if they arise from simple rules, so it’s not much use to review the results of individual strategy choices like “Oh I should have used a dense lattice”. The quality of a strategy is only apparent after a process of testing, not reflection. Rather, it’s more useful to review my decision making and problem solving process.

My Mistakes

1. I should have worked in a team. Thinking back, I would value the experience of working in a team higher than getting a good Battlecode rank. There were teamwork skills that I could have further developed that would allow me to be part of something greater than what I could do alone. Sure, working alone has its short term benefits like lack of team politics overhead and instant decision making, but it doesn’t teach me anything new in my workflow, and ultimately capped the potential of what I could produce.

2. I should have tested the strategies that I kept in the back of my mind. Perhaps I just didn’t have time for this, but once I’ve got my eco and turtle strategy implemented, I didn’t do the basic thing of trying other strategies like aggressive churches or harassers which I had in the back of my mind. They turned out to be very effective and rather trivial to implement, but I spent my time tuning what I had instead. In a team this would have been more plausible, but even with my limited hours, an effective experimentation workflow could lead me to discover other effective strategies. There was also an aspect of “I don’t want to copy what other teams figured out first”, which is nonsense.

3. I should have scrimmaged more. I was foolish in being stingy with my scrimmages, fearful that others will take advantage of it. But each scrimmage is a mutual benefit to the scrimmag-ees, and each scrimmage gives you two teams an advantage over everyone else in the entire tournament who didn’t scrimmage.

4. I should have at least test the big changes at the end, or avoid them entirely. What kicked me down maybe a rank or two in EV in the final tournament was my crusader lattice bug. After an “improvement” on my crusader behavior my crusaders didn’t lattice properly, which was the most trivial low hanging fruit in this strategy. They blocked my castles from building anything near the end, forcing me to lose on tiebreaks unless I had a massive lead earlier. Without the bug, I would have won the first elimination and entered the winners bracket against CitricSky. A simple test or two would have found the problem, but I was too confident that it would be fine. On the other hand not all late changes were bad. My war behavior certainly converted its fair share of games, and that was implemented in the last 8 hours. Still, in the future I would plan to spend the last few hours on bugfixes only, never to add new features that will risk breaking what’s already working. Features like the war behavior should have been implemented earlier with better planning.

What I did right

1. Got a “proof of all concepts” bot early. Submit something that works rather than nothing. Get your machine oiled early and just submit something that does a little bit of every concept, rather than going stealth mode trying to complete your megabot. What you learn with that first quick bot will help you write that 2nd good one a lot better and faster. Plus, a good early seed will have real cascading effects on your results later.

2.  Participated in discussions (Discord). This wasn’t easy for me since I was a shy person. I’m not saying my contributions were any good, but at least being in the forum meant you could share (steal) ideas with everyone else and be kept up to date with what everyone else is thinking. Battlecode games are very complex and it’s impossible for you to come up with the perfect strategy. So it’s important to keep up to date with the latest strategy trends. And if you contribute, you’ll get feedback about your ideas.

3. Worked in short “sprints”. I managed to work much more effectively when I worked in short 2-3 day sprints and really planned out my hours. Before each sprint, I would spend a couple of hours to write the list of features and bug fixes I want to realistically accomplish. These couple of planning hours payed dividends. I then assign my estimated hours for each task, multiply the hours by 3, since everything takes me 3x longer than I think it does, and I removed anything that is not as important when it does overflow the 2-3 day limit. This kept me focused and on schedule, and the hour time limits helped beat procrastination. I ended up completing things that I would have otherwise forgotten without a proper workflow. Any extra hours at the end of the sprint were dedicated to testing.

4. Fixed known weaknesses in my strategy early instead of brushing them off. In the seeding tournament I witnessed the defeat of lattices through running out of fuel. In some testing I saw the defeat of my own bot to rushes. Sometimes you are tempted to brush them off and think “Oh that’ll never actually happen, I’ld rather work on something else”. Resource management and rush protection were actually not trivial to implement, but I took them seriously and protected my lattice against it. In the seeding tournament, both of those techniques helped my bot to win games it would have otherwise lost and I was happy my work paid off as it placed 4th.

Final Thoughts

All in all, Battlecode wasn’t as tech-heavy as I expected. I thought it was going to be a battle of AI technologies like reinforcement learning and neural nets, but instead it’s a month of rather human discovery of game strategies and the implementation of those strategies. Nothing wrong with that, it’s just that I didn’t know what to expect. It calls for more real-life heuristic problem solving and project management than fancy cute algorithms or techniques, and gives a better representation of real world problem solving than traditional algorithm competitions like the informatics olympiads. It was interesting to see the problem and goals evolve as the meta and fashion changed, even though the spec itself stayed exactly the same (after the sprint). It was like I was working at a startup in a rapidly rising market.

My results were quite lucky. My general decisions to stick with the tested lattice strategy didn’t backfire as the meta evolved, and my investment into good eco paid off as it stayed very relevant by the time finals came. I wasted a lot of time trying to get Church Lightning working which I eventually abandoned due to how easy it was to counter, but on the other hand my “rage war” tactic luckily turned out to be effective, and with these things you never really know until you have tried so no regrets there. In the finals, I had more good luck than bad and placed 5th. GG.

 

Leave a Reply

Your email address will not be published. Required fields are marked *