mlomb

Halite II Post-mortem

2018-01-28

This is my post-mortem for the 2017 Halite AI Challenge where I ended rank 7. Link to my profile
You can find my bot's source code in GitHub here.

In this write up I'll explain my bot's logic in a turn and some important decisions that I took while coding it.
I recommend you to read about the game before start reading.

Client

I've replaced the starter kit with my own classes. I feel like recreating the whole map every turn was unnecessary and it doesn't let me save information between turns inside an specific entity.

Task system

I based my entire high level strategy using a tasks system. This is how it works: There are tasks that ships should complete. Task types are: SUICIDE (not used), ATTACK, WRITE, DEFEND, ESCAPE and DOCK. Each task must have a target location. A task can optionally have a target entity and a max_ships value and some other information relative to that specific task.

Tip: If you are using Chlorine with my messages.json you can check the assigned task of this ship with the Angle Messages feature.

Generating tasks

At the beginning of the turn I generate all the tasks for the current turn like this (Instance.cpp:473):

Assigning tasks

We've now created all the tasks but now we need to assign to each friendly ship a task. Some ships have a fixed task, like docked ships, so we manually assign the tasks for those ships. For the rest of the ships we use a priority system.

First we put all the (friendly) undocked ships inside a queue. This queue will contain all the ships that don't have a task assigned.

Sometimes ships can't find a suitable task, so at the end I just assign them to the closest ATTACK or DEFENND tasks.

Relative priority

To calculate the priority of a ship for a task I calculate the distance from the ship to the target location and assign it to a variable d (Instance.cpp:765). Then I modify this variable depending on the task type like so (very rough idea, the code will explain it better):

Then priority = 100 - d / 100.

Compute Move

Given the task assigned each ship should issue a Dock/Undock move or create a NavigationRequest (or do nothing).

A NavigationRequest (Navigation.hpp:32) represents where and how a ship wants to navigate to a location. Basically it stores this:

Computing the move basically occurs this way (Ship.cpp:80):

Map

I represented the map as a grid where each map unit were divided into MAP_DEFINITION (4) map cells. Each turn the map is cleared and generated again.

Each map cell contains:

To generate the map first we iterate over all cells covered by a planet and mark them as solid (Map.cpp:24).

After that, we add all ships into the map, this also include the ships that will spawn next turn near a planet to increase the accuarity.

For each ship, depending on whether they are commandable or are undocked ships, friendly ships or enemy ships we fill the cell's values like this (Map.cpp:121):

Frozen ships are ships that will not move in this turn like ghost ships (ships that will spawn next turn) or ships that the navigation decided not to move.

These are some images of the map after filling it (displaying nextTurnFriendlyShipsAttackInRange and nextTurnEnemyShipsAttackInRange):

Map2

Map1

With all this information, we can now perform navigation.

Navigation and Combat

My navigation and combat work very tight together. I choose where to move a ship depending on the number of ships sorrounding and the distance to the desired target. No clustering going on.

My navigation works like this (Navigation.cpp:135):

This process have some anti-timeout checks that will execute all the selected navigation options even if conflicts still exists because we run out of time.

Scoring the NavigationOptions

This occurs inside CalculateScores (Navigation.cpp:80) where we iterate all the NavigationOptions of all the NavigationRequests. For each option, we check if there is static collision using max_thrusts (max_thrusts is calculated before calcuating the map (and when modifing the map) and it contains the max thrust value this ship can issue in a determinated angle, due ship-planet and ship-docked_ship collisions). If there is a problem, score will be set to -99 if not, it will be delegated to GetPositionScore. GetPositionScore will calculate the score using the corresponding map cell information like this:

Basically, if we are avoiding enemies, we will prefer the option that have the less enemies in range next turn and then the closest one to the target. If we are attacking, first we check if the ships that can reach to this point are more than the enemy ships can reach and attack us. If thats possible, we'll maximize nextTurnEnemyShipsTakingDamage and then by proximity to the target.

Writing

Halite Message

Here is an example game.

I did this because it was simple to implement and it shouldn't have any impact on the game. Although I have to say that sometimes I time out doing this in very rare cases.

Writing things was possible only on won games so I first thought to write "GG" or something like that but it was too short and boring. I just ended up writing "HALITE" using ~45 ships.

The most "complicated" part was to write the coordinates of each point that form the letters (which you can find in Instance.cpp:584) after that it was trivial just add a new task type and lower down the priority.

To know where to position the message I just use a nice bruteforce algorithm (Instance.cpp:54) using the map to find the 140x22 rect closest to the center where no solid objects exists.

To start writing the message I detect that the game is won like this:

// we should have at least 90 ships
if (myShips > 90) {
  // we own the 85% of the planets or all the planets - 1
  if(myPlanets / totalPlanets > 0.85 || myPlanets >= totalPlanets -1)
    // we won, start writing
  }
}
Once we start writing ship docking is disabled 25 turns so we can give it some time to the ships to write the message.

Debugging

Logging

The most important way to debug the bot. I tried to log everyting that generates a big decision on the game, like task assignment or target location selections. At the end it doesn't matter what I log because I disable it with a flag during compilation (Log.cpp:21).

A Stopwatch

To measure the time each of my functions were taking I created a simple Stopwatch class (Instance.hpp:17) and use it like this:

{
  Stopwatch s("Clear and fill the map");
  map->ClearMap();
  map->FillMap();
}

So when the Stopwatch object gets out of scope it measure the time between its instantiation and its destruction. Then at the end of the turn I get something like this:

Clear and fill the map: 42ms

Chlorine

Chlorine created by fohristiwhirl was the most important debugging tool I had. I contributed by adding zoom to it. Then I used it to inspect in detail the micro-movements of top players.

I modified it a bit so I could draw some important ranges apart from the ATTACK_RADIUS that was there already. Here is a pic:

ChlorineRanges

The ranges displayed are:

With this and watching a lot of replays I managed to build my map grid and my entire combat strategy.

Thanks

Thanks everyone in Two Sigma for creating this awesome competition. I wasn't here for Halite 1 but definitely I'll be here for the Halite 3, 4...
Thanks to fohristiwhirl for creating Chlorine it really helped me a lot.
Also we had an awesome community on the Discord server, hope to see them next Halite again!

hello@mlomb.dev
Copyright © · All rights reserved