Battlecode 2014

Battlecode is a worldwide programming contest organized by the MIT.

The 6.370 Battlecode programming competition is a unique challenge that combines battle strategy, software engineering and artificial intelligence. In short, the objective is to write the best player program for the computer game Battlecode.

In the contest a 2-player game written in Java is given. Each contestant has to write an AI for one of the players. After 3 weeks a preliminary tournament is held, where you can qualify for the finals, which is held in front of a live audience, commentated by the organizers.

In 2013 I came across Battlecode, but it was too late for participating in the tournament. One year later me and a friend of mine entered the tournament with the very Austrian name "schnitzel".

2014 Specifications

In the game of 2014 you could win by sending more GigaGallons milk to space than your opponent. The gamefield is discretized into a grid, where every cell in the grid contains a number of cows. A cell can only be traversable if it isn't water and there is no other robottype on this cell.

All teams started out with a fixed positioned HQ that could spawn SOLDIERS (aka space cowboys). Each of these soldiers could move (orthogonally and diagonally), shoot, suicide or transform into a PASTR or NOISETOWER .

A PASTR was the essential building which sends milk generated from nearby cows into space. A special mechanic of this year's game was that the cows where sensitive to noise. If a SOLDIER shoots or runs it generates noise and nearby cows run away from the noise source. This allowed some basic herding of cows, by generating noise in a smart pattern.

Some more details of the game:

• each robot can't share information to the other robots. The only way to communicate is a radio (int[]) where we can store one int per channel`
• the execution of the robots actions is turn based
• you have 2000 bytecodes per round per robot. If you need more bytecodes, your execution is split into several turns and you gain "action delay". Action delay slows down your ability to spawn, move, shoot or transform. These constraints boil down to that the player who uses less bytecodes (=efficient code) wins the battles.
• you don't know the map beforehand (so watch out for edge cases!)
• if you kill enemy PASTR you gain 1 GG milk
• a SOLDIER can also milk the cows on the cells it stands on
• the more soldiers you have, the slower they can respawn

To get a better idea of the game, you can watch one of our games in the sprint tournament (the tournament of the first week, that had no impact on the qualifiers) down here:

So we won the first map, and lost the second and third one. Our strategy was to build a "farm" (a NOISETOWER + PASTR) and wait at the farm until the opponent build a PASTR. Then we would simply attack that enemy PASTR with all of our soldiers. After some time we begin with building a new farm and repeat the process.
As you might have noticed there are several issues with this strategy. First of all we attack the enemy one by one, which is always a disadvantage versus many enemies. Second we used a diagonal pattern for our NOISETOWER, which was inferior to our final pattern. Third, we played against the winner of the whole competition :D. But what was already working really good, was our pathing.

Pathing

Pathing was one of the first things we implemented. Normally pathing on a 2D grid is a well known and solved problem in AI. What we wanted to use was the classical A* algorithm, but the problem lies in performance. In the worst case we have a complexity of \(\mathcal{O}(2^n)\), where \(n\) is the number of cells in the grid. So what we needed was a radical optimization of the number of nodes that A* has to consider. We did this by expanding rectangles onto the grid until they hit water and repeating this process until we filled the whole map (except water) with rectangles. Then we find which rectangles connect to one another and create portals (edges) between them.

This calculation was performed on the HQ after the first SOLDIER was spawned. The HQ was now able to calculate the shortest path between two points, by finding out in which rectangle they reside, using A* star to get a path of rectangles and finally calculating a path that consists of visiting the portals.
You can find our implementation here and here

Micro

Micromanagement was one of the most important factors of this year's game. Micro (the opposite of macro) are all actions that the soldiers make autonomously. The input of the micro are the sensor readings (stats of friendly/enemy soldiers/buildings nearby, hp, walls, ...) and the output are the actions (attack, retreat, shoot, sneak) the soldier should perform.

In the example above the blue soldier decided to shoot the enemy, because it knew that there were more friendly, than enemy soldiers nearby.
Our macro computed waypoints, which our soldiers tried to follow. There where several conditions in which the soldier decided to leave the waypoints. For instance, if the robot was outnumbered it retreated, if it saw that a friendly soldier was attacked, it tried to help him, etc.
The main logic of our micro was:

private void run() throws GameActionException {
    ......
    senseRobots();
    if (enemyRobotsCount == 0) {
        if (!attackBuilding())
            hold();
    } else if (!outnumbering()) {
        retreat();
        // kamikaze();
    } else if (isSafe()) {
        MapLocation friendToHelp = canHelpFriend();
        if (friendToHelp != null) {
            helpFriend(friendToHelp);
        } else {
            if (!attackBuilding())
                attack();
        }
    } else {
        if (!attackBuilding())
            shoot();
    }
}

As it turned out, our micro was too offensive. The optimal strategy for the micro was a defensive one, because the player who makes the first move to the enemy, is the one who has to wait one round to shoot.
We also didn't have time to implement the kamikaze feature, the top teams had. It would choose one brave soldier, who would run towards the enemy and explode him/herself to cause massive damage. Next year we definitely have to focus more on the micro part.

Macro

The main idea of our macro was to use squads. A squad is a number of soldiers (in our case we start with 5) who always stick together in a swarm-like behaviour. Every squad listens to the radio for a new path (computed by the HQ) to follow. Squads can be merged when needed, but can't split. Our first squad followed this simple strategy:

HOLD was a special state in the beginning of each game. We wanted to group our soldiers in the base, without blocking our spawn area (see for instance the famous "Troll"-map). Imagine for instance a maze map with cell-width 1. With spawning one bot we would already block the other end of the maze. To circumvent this, we used a "pressure" system where each bot, leaves one empty space behind him and as soon as the cell gets filled we advance one step. This would ensure that we would fill the maze without blocking.

MEET was our "silent farm". We noticed that building a PASTR had its costs: The enemy can now find us on his map and we lose one soldier that transforms into the PASTR. So we introduced the idea of silent farms, which just use a NOISETOWER and the soldiers themselves for farming. That's why some of our games are boring to watch, because the enemies didn't handle the case of silent farms and we would win by this slow farming method.

As soon as the enemy build a PASTR we would attack it in our RAGEMODE, because this meant that they had 2 soldiers less than us (1 for the NOISETOWER and 1 for their PASTR). In the RAGEMODE we calculate routes from our "silent farm" to the nearest enemy PASTR and distribute the path with the radio. If our soldiers destroy the enemy PASTR we calculate a new route in the HQ, to the next PASTR and so on, until all PASTRS are destroyed.

While the current squad is in RAGE, we spawn a new squad, where all soldiers start in the MILK state. This means that they go to our previous "silent farm" and the first who arrives, builds a PASTR, the rest circles around our new farm. This had the advantage that we already collected a lot of cows nearby, and the NOISETOWER was already build there. If the last squad succeeded in destroying all enemy PASTR, it would join the current squad and go into the MILK state.

Farm spot

The last thing I want to talk about our implementation, was our way of finding the perfect farm spot. There were three metrics we considered:

1. stay away from our HQ
2. maximize the distance to the midline (explanation below)
3. maximize the cow growth nearby

The midline divided the map into two parts, where one part contained our HQ and the other the enemies HQ. When we maximise the distance to the midline, we ensure that our farm location is closer to our HQ than theirs. So if we spawn new soldiers, they should reach the spot sooner than the enemy. The third metric had to take into account that nearby water made herding impossible. We fixed this by emitting 8 lines with different directions from the cell and stopping if we hit water.
In a perfect world we would now compute the score of our metrics in every cell and take the cell with the highest score. But this was too slow to compute, so we sampled the grid in every \(n\)'th cell.

Tools

In battlecode it is important to test the impact of all the changes you make. For testing we implemented a short python script, which executed a game against all our previous bots, on all maps. We also cloned all the code of teams, which were on a public github repository (use private repos, next time ;D) and played on all maps against them. The script would then output a *.csv which would contain statistics, about our weakest map and the strongest team.

Tournament

The results of the tournament can be seen here. They even implemented a webviewer (implemented in flash), so you can rewatch the matches in all their glory. Here is the list of our matches (i recommend the one against The Vegan Police ):

• Sprint Tournament
  • that one team vs. schnitzel
  • schnitzel vs. Cyber Mob
  • Dragonfly vs. schnitzel
  • Jimmy Wu vs. schnitzel
• Seeding Tournament
  • schnitzel vs. caddar
  • schnitzel vs. Team Legendairy
  • that one team vs. schnitzel
  • schnitzel vs. 1260/3
• Qualifying Tournament
  • schnitzel vs. Jimmy Wu
  • The Vegan Police vs. schnitzel
  • schnitzel vs. Ace of Spades

Conclusion

So we didn't get into the finals, but the whole competition was a lot of fun. We saw a lot of interesting strategies and awesome micro (props to The Vegan Police, Paddlegoats and That one team). Thanks to the organizers, who did a great job, with the game specs and the tournament.

Schnitzel will be back!