Occam's Coder

Brainstorm many possible algorithms - then pick the stupidest that works!

- Art of Programming Contest Ahmed Shamsul Arefin

First, an introduction. We're team E Doc Tablet! A trio of high school graduates with an enduring interest in programming...

We managed to hit Top 8 for the seeding tournament but failed to make it into Top 16 for the finals (overall ranked #21 on auto-matchmaking server). Also, we somehow managed to clinch the best strategy report prize o.O although it's slightly outdated (a lot changes in a couple of days).

Intro - We give a brief overview on the year's game for those not familiar with it.
Strategy - An in-depth breakdown of the challenges in this year's Battlecode as well as a verbose discussion of the various strategies we (and other teams) implemented.
Thoughts - Skip ahead for the post mortem proper.
TemplatePlayer - Improved examplefuncsplayer written in OOP style with basic functionality. Good for new players to extend upon! :D

As this really isn't an intro to Battlecode 2017, but a post mortem/strategy report on our team's experience, let me point you to >the actual game specs< this year. However, let's briefly set up the scene of this year's game to better place the following strategy discussion in context.

Story thus far...

The evil scourge that is Zombies have finally died off. In the aftermath, autonomous machines are left to revive the galaxy's ecosystem from the devastations of war. Unfortunately, the over-competitive nature of the different robot factions have led to them destroying other factions more altruistic then they are in donating to the Robotic Wildlife Fund. Thus sets up the scene for battles (and peaceful farming) of epic proportions in this year's Battlecode!

Game Elements

Bytecodes

  • Each robot has a set allocation of bytecodes per round.
  • Measure of computational resources taken up by a robot.
  • Sets an upper limit of how much computation a robot can make in a round.
  • Interactions by the robot with game engine (movement, sensing, broadcasting) all take up a set amount of bytecodes.
  • Writing efficient code that runs within this bytecode limit is a huge part of the challenge in Battlecode!

Bullet Trees

  • Produces resources - Bullets! per round scaled to its current health.
  • Health decays per round, maintained by Gardener robots 'watering' them.
  • Can only be planted by Gardener robots.

Victory Points!

  • A measure of your bot's altruism.
  • Donate bullets to gain Victory Points (VP).
  • Instant win upon accumulating 1000 VPs!

Robotic Species

The Archon

  • Hire Gardener robots.
  • Fat - it's twice the radius of other robots.
  • Slow, basically it's not that useful a unit other than spawning gardeners.
  • Excellent bullet sponge early game!
  • Has twice the bytecode allowance of other robots, possible offloading of computation to Archons.

Gardeners

  • Builds the other types of robots.
  • Plant bullet trees! (accrue resources)
  • The ability to hire multiple Gardeners means that this year, unit production is more distributed.
  • Even with the Archon destroyed, surviving Gardeners can continue the fight and eventually win!

Lumberjacks

  • Short range melee offensive units. (AOE attack)
  • Slow movement - alas not that effective as an offensive unit...
  • Fret not! Main purpose of chopping down nearby neutral trees. (clearing obstacles)
  • Makes space for Gardeners to plant bullet trees!

Scouts

  • The only 'Flying' unit! (able to traverse on top of trees)
  • Long sight radius, as its name suggests, good for scouting...
  • Weak attack, Low HP - Terrible front-line unit.
  • Good for getting behind enemy lines and disrupting economy. (harass)

Soldiers

  • Backbone of the army.
  • Able to fire multiple bullets in a single attack! (1/3/5)
  • Tough when amassed. (soldier ball)
  • Relatively high movement speed allows it to kite around the slower moving (though more powerful) tanks.

TANKS!

  • Extremely high velocity bullets!
  • Also able to fire multiple bullets in a single attack. (1/3/5)
  • Slow, lumbering TANKS! Able to run over trees. (destroys them after some time)
  • High upfront cost (3x cost of soldier), balanced with a much higher HP and attack damage.
  • Sadly, not that frequently seen in games... (easily kited by faster moving soldiers)

Battlecode is a competition where writing efficient hacks produce better results than tried and tested classical solutions. With the game engine already written, it's a whole lot like Robotics, more engineering than algorithmics. Given robust hardware and drivers pre-loaded, your task being filling up the software with AI magic :)

This year's game placed an emphasis on both aspects familiar to any RTS fan - Micro and Macro. A bot with good soldier dodging but bad economy will lose to one that prioritizes farming on large maps. A bot that picks the wrong time to invest in a strong economy will get swarmed early game by bots that rush on maps with a direct path between the two factions. Careful balancing and adaptation of the bot's behavior to the map was crucial for success against other teams.

Scene from a match played on the map Chess

As can be seen in the above frame, this year's game also introduced a 'bullet hell'-esque combat on continuous space (robots in prior years travelled on a discrete grid). This meant that there were a lot more variation for movement and combat micro between the teams. Attacking wasn't hitscan (immediately hitting enemy upon acquiring valid target) anymore, which meant a good micro-code could turn the battle to your favor even against a larger force.

Micro

Game between Oak's Disciples(red) and 5th/6th(blue) during the final tournament

That 1 red soldier took down 2 blue soldiers before sucumbing to the combined firepower of 5 blue soldiers. At the end of the competition, it was generally agreed that team Oak's Disciples had the best soldier micro code and could effortlessly win a 1v2 engagement against most other teams.

Movement

Most teams settled into using some implementation of bug pathing to traverse the map with limited vision. On maps with a direct path between teams' starting locations, the team that had a better pathing algorithm would have had a better chance at rushing the opponent and winning the game.

Soldiers from Waterloo Omega Ruby(red) navigating the paths on map Moba during the final tournament.

Dodging

Dodging was often the critical factor in determining the outcome of early game soldier 2v2 fights. Here, our team's soldiers scans 8+1 directions (not moving is an option too) and picks out the highest-scoring direction to travel in. Things like getting hit by a bullet or straying into a lumberjack's strike radius will impose a penalty to the score. This will reduce that location's score and prevent our soldiers from travelling in that particular direction.

Close quarters combat on Arena. Visualization: Yellow (good) <--> Red (bad)

Shooting

Shooting is more complicated than simply calling a method to attack a certain grid coordinate. Rather, there were some interesting strategies for shooting this year - Tree Squatting, Sniping and Flickering.

Red's scout rushes towards blue early game and kills the gardener from its perch on one of blue's bullet trees (Referenced Match).
Match between 4th Place(red) and potato(blue). Red's tanks are shooting at a target well outside their sight radius.
Soldiers offset their shooting direction, cycling left/center/right/center.

Tree Squatting by scouts was a popular strategy in the Sprint tournament (first week of competition), to the point that those teams which don't implement such a strategy would most definitely lose to a team that does. After tweaking the scouts' HP and attack damage, this strategy fell out of popular use. However, scouts were still effective sneaking past enemy lines to harass those hard-to-get gardeners sitting amidst their hextet of trees.

Sniping was another strategy made available through bullet hell combat. Due to the high velocity of a tank's bullets, some teams implemented a 'sniping' function to them. However, such a strategy was prone to friendly fire.

A strategy that we implemented towards the end of the tournament was to offset our shots towards the intended target. Such a strategy spread out the cone of bullets wider and made it harder for the enemy to dodge our bullets.

Macro

Although playing on a continuous space introduced many new micro challenges, it's teams' macro that decided most games. Even with the best micro, a single soldier cannot stand up to a mass of 10 soldiers or a trio of tanks. With resources this year shared between building units, planting trees, and attacking, the careful managing of bullets was crucial to a team's success.

Furthermore, the added win-condition of donating 1000VPs imposed added pressure on games. Teams had to decide whether they should go donate their bullets for VP or build offensive units to win by wiping out the enemy team. It's the ability to correctly discern the suitable strategy that attributed to top-teams' success.

In the closing rounds of an intense battle amidst a tight maze, team Arbitrary Graph fails to donate their cache of bullets, allowing us to clinch the round of 3 :D
Team Don't Panic keeps their cool even when they break the client by stockpiling too many bullets...

The tie-break condition of VPs also resulted in a number of hilarious situations in matches...One should always donate in the last few rounds of a match to avoid such embarrassing situations :P

Farming

Planting bullet trees was a critical component in this year's game (it's about reviving the ecosystem afterall). The layout to plant trees had a large impact on the bot's performance in matches. Main considerations teams had to take into account when choosing a farming layout were density, speed, and space.

Easiest to implement hexagonal 'flowers' spread out in a dispersed manner.

Naive 'flowers' scored high in the density metric - with a 1:6 gardener to tree ratio. However, they required a suitable clearing and if not implemented properly, could lead to congestion around the archon, preventing further spawning of gardeners and stalling economic growth. It also took some time for gardeners to find a suitable clearing before planting trees.

A popular strategy utilized by top teams during sprint tournament was the 'sparse-forest' layout.

'Sparse-forest' solved many of the problems faced by naive 'flowers', chiefly speed. The sparse layout was more flexible as it didn't require as much space as a flower. Such a strategy worked best on dense maps and offered an early game economic advantage as the team could plant trees even in tight corners where a flower design would fail. However, it fell out of use towards the seeding tournament as units moved slower and the early game advantage offered by such a layout didn't offset its vastly lower gardener to tree ratio.

Arranging 'flowers' in a bigger hexagonal grid offered an improvement in efficiency.

A layout that saw widespread use towards the end of the competition was the 'ordered flowers'. A grid was overlayed atop the map to provide gardeners coordinates to spread out individual 'flowers'. Such a system allowed for gardeners to speedily find their target location without congestion and preserved the density of a 'flowers' layout. Even though it took a while to get started (clearing sufficient space), by this time, unit speeds were cut in half so games moved a lot slower and such a strategy was favored.

Here, teams had the most visually obvious differences in their strategies. With the basic 3 layouts described above, many teams added their own flair to farming. Be it an expanded circle of trees, trees in a box around the gardener or a funky elipse, teams had varying implementations of planting trees.

In order to have sufficient space to build large tanks, some teams opted to expand the circle of trees around the gardener. For instance, team Yggdrasil fit a ring of 7 trees with a clearing for building tanks around their gardeners. Although such a strategy allowed teams to quickly build tanks, we found that early game tanks weren't as efficient as a bunch of more manoeuvrable soldiers (since early game usually meant lots of neutral trees lying around).

Team Yggdrasil had an enlarged circle of bullet trees, allowing space to spawn tanks!

Probably the signature of Team Rocket is their unique eliptical farming layout. It might be entirely for its aesthetic appeal, however, we believe there's some strategy involved here. Planting the lower half of the elipse (4 trees) did not require too much space and hence can be done quickly early game. Once nearby forests have been thined out by lumberjacks, gardeners could expand to the 8-tree eliptical layout. This allowed for a denser layout without sacrificing too much speed.

Team Rocket had a unique elliptical layout for farming...

A strategy we toyed around with before the seeding tournament was a hybrid between 'flowers' and 'sparse-forest'. Starting out with a 'sparse-forest' and with the right spacing, one could achieve a dense hexagonal packing similar to 'flowers'. Here, sections of the farm remains in a sparse layout with individual gardeners transiting to a 'flowers' layout once it senses a clearing. However, we weren't able to iron out issues with congestion before the tournament, hence reverting to a more stable 'ordered-grid' layout.

Our hybrid between flowers and a sparse-forest layout.

Unit Composition

The composition of offensive units is often the crux of a team's strategy. The choice of building tanks or soldiers would fundamentally alter the team's macro. After the sprint tournament, our team simply stopped building scouts as offensive units. Rather, once we sense neutral trees with bullets, a single scout is built to gather those bullets for an economic advantage. Although the majority of teams went with a soldier-centric build, some teams had other ideas...

Many Interesting Titrations was perhaps one of the more successful teams to optimize the early game tank rush. Their ability to consistently churn out tanks before round 200 won them quite a few games. Ultimately, well implemented soldiers that were more agile defeated their tank strategy.

Many Interesting Titrations focused on rushing out tanks as early as round 200.

Team test bot please ignore had a slightly different strategy in mind...By purely building lumberjacks, there were able to clear dense maps quickly and rapidly build up their economy. Furthermore, by arranging their lumberjacks in a gas-like cloud, they avoided friendly fire and effectively utilized their AOE attacks. The gas cloud was pretty tough to get through - that is, if your soldiers didn't avoid lumberjacks. Although an interesting strategy, soldiers with superior range will triumph after some time.

Team test bot exclusively spawned lumberjacks and used them to visualize a gas simulation.

Aside from Tanks and Lumberjacks, you really only have left Soldiers...With the reduced HP and damage of Scouts, most teams chose to build a force of soldiers as their main combat unit. A popular hybrid strategy would go somthing like early game scouts to harass after an initial 2-soldier spawn followed by building tanks late game.

That all important 2-soldier initial spawn decided a large number of games with a clear path between the two teams. Spawning scouts after the initial engagement allowed teams to get a leg-up on building their economy. The scouts would delay their opponent's economic growth through assassinating enemy gardeners. Tanks were more powerful than soldiers, but only if they can get close enough. Even so, tanks are more economically efficient than soldiers, thus building them late game when your economy can support their high cost would overwhelm an enemy force composed of purely soldiers.

Communication

After an engagement, soldiers disperse to scout previously unvisited locations. White dots mark the targeted locations of individual soldiers, while green lines indicate their direction of travel.

As individual robots do not share their field of vision, communicating between robots is crucial to have strategic cohesion. This year, teams each had a global shared array which was persistent through a match and could be read from/written to by each robot.

Thus we implemented the Broadcaster system - serialized 2D grids persistent in the global array. Each grid took up 400 channels (elements) and could store 32bits (integer-sized) of information per 10x10 grid square on the match map.

With a persistent grid in place, we could run classic BFS algo to find unvisited locations to scout as well as store reports in each grid's memory. A possible improvement upon our current system is to run BFS in a distributed manner (using all soldiers' spare bytecodes for instance). Furthermore, not every soldier had to run their individual BFS, a single scan would be sufficient to find the perimeter of unvisited locations for them to scout (after scoring each for closest distance perhaps).

When an enemy is spotted, combat units converge upon its location.

The capability to encode location information together with map information allowed us to queue reports to the global array. Combat units pull from this queue to determine their target location which result in behaviors such as them converging upon a recently spotted enemy or rushing back to defend a gardener under attack.

Soldier Tactics

After post-sprint tournament balancing updates, soldiers sprang into focus for many bots. Their high firepower and maneuverability made them the choice combat unit. Therefore, we focused much of our later development on improving our soldier's combat capabilities. We even created a map with 50 soldiers a side to simulate large-scale engagements and evaluate our soldier micro.

Red's soldiers at the back deflecting towards the sides.
The red soldier ball manages to form an effective surround on blue and wins the engagement.

Two main improvements we implemented for our soldiers were squishing and target-scoring. When two soldier balls engage, the side that won often is the side that can get more soldiers to the front and fire upon the enemy. Thus we added some code to make soldiers at the back of the soldier ball deflect towards the sides, thereby spreading out and behaving very much like when a (compressible) ball is squished...

The force of red soldiers splitting up to engage multiple enemy targets.

With our Broadcaster communication system in place, target scoring was pretty easy to implement. Iterating through the queue of reports and scoring each based on encoded enemy information as well as distance to target location allowed for such emergent behavior to manifest. A group of soldiers will naturally spread out and engage on multiple fronts as enemy numbers are diminished.

A month may seem to be a looong time...Not the case for Battlecode! One has to develop basic functionality for each robot - movement, making sense of surroundings, communicating between robots - before going on to implement hueristics for macro gameplay.

Abstract the AI! In other words, separate the main robot logic/boilerplate code from any decision making code. Doing so would allow your AI to be more flexible and makes it faster for you to edit strategy changes as the game meta evolves through the competition.

    if (spawnSoldierControl() && !has_built_robot) {
        has_built_robot = forceBuilding(RobotType.SOLDIER);
        if (has_built_robot) soldierTimer = rc.getRoundNum() + SOLDIER_DELAY;
    }
                        
Excerpt from our GardenerPlayer - A section of its spawning logic

It is simply a matter of encapsulating the conditions for spawning soldiers in its own function. This would keep the AI's decision-making layer abstracted from the main logic of GardenerPlayer.

    private boolean spawnSoldierControl(){
        if (rc.getTeamBullets() < RobotType.SOLDIER.bulletCost) return false;
        if (rc.getRoundNum() < MID_GAME &&  !enemyEngaged) return false;
        ...
        return true;
    }
                        
The control function for spawning soldiers
public strictfp class RobotPlayer {

    static BasePlayer curPlayer = null;

    public static void run(RobotController rc) throws GameActionException {
        while(true) {
            try {
                switch (rc.getType()) {
                    case ARCHON:
                        //Initializing type-specific robot player
                        curPlayer = new ArchonPlayer(rc);
                        break;
                    ...
                }
            } catch (Exception e){
                e.printStackTrace();
            }
            ...
                        

Using this structure allows for robots to inherit common code being executed in higher-level classes of robots (BasePlayer/CombatPlayer classes for TemplatePlayer's implementation). This enables your robots to have a common set of executable code being run at the start/end of a round for easy maintenance.

public class SoldierPlayer extends CombatPlayer {

    public SoldierPlayer(RobotController robot) throws GameActionException {
        super(robot);
        runRobot();
    }

    public void runRobot() throws GameActionException {
        init();
        for (; ; Clock.yield()){
            try{
                startRound();
                run();
                endRound();
            } catch(Exception e){
                e.printStackTrace();
            }
            ...
                        
The skeleton of a type-specific robot code.