Source code for mine bot that most probably is going to place 2nd on Halite 2 programming contest.

Before you check the source code, I highly recommend going through this write-up.

Intro / First Submissions

Originally, I intended to put only few hours into the contest. I failed, hence you can enjoy this write-up :)

I opted for the starting kit (since I like to have something working as soon as possible) and one by one I tried fix major leaks in my bot with as small changes as possible. If you're looking for a relatively simple code that achieves decent results you can check my early submissions (#25 and above). My first submission that broke into top 10 (#35) was around 250 lines (disregarding starter kit and my template code).

Summary of the most important changes (more or less in the order of importance):

• Use global greedy strategy with evaluation function for selecting destinations for ships (more on that below).
• Avoid collisions. I still used default navigation, but I avoided collisions in a most naive way: I reduced speed of a ship until it didn't collide. Since default navigation avoids stationary ships this is guaranteed to work since stationary ships shouldn't collide with anything. (this was obviously removed later).
• Send correct number of ships to each planet (count ships already on the way)
• Limit amount of ships that can follow a single enemy ship.
• Primitive way of retreating when being outnumbered (called evasion in my code)
• In 4-player games, bump priority for planets furthest away from center, as well as drastically reduce priority for planets in the middle to avoid 3+ player battles.
• Hide in the corner for 4-player games.

My final submission is not much that different from the early versions. From high-level point of view, it's actually much simpler. The biggest reason for ~4x increase in code size is the amount of dead code (leftovers from prototyping / debugging) and bloated pre-processing part where I compute various features with non-descriptive variable names.

Understanding The Problem

Halite 2 is quite simple game with a lot of depth. It's easy to get consumed with all potential cases that may arise during the gameplay. I won't focus on the details, since there are just too many of them. Each time I was able implement something from my TODO list, three new positions were added there.

The golden rule is to just focus on the things that have the biggest influence on your solution while keeping everything simple. The usual workflow is to watch few replays, see where your bot sucks, add some code that possibly fixes that and submit new version. Hard parts are the ability of finding our weakest point and be able to give up when we're not able to find any simple way of fixing it. Implementing things in a simple way is only hard at first - sooner or later you'll get there so don't worry.

To give you an example, it was clear right away that fixing navigation system is one of the most important things. Unfortunately, rewriting it is a rather big task. I opted for pushing this away as long as I could in order to figure out what's the easiest way of including it in my solution. As a temporary measure I added self-collision avoidance as a post-process step since I knew I was able to quickly implement this. It may look like an insignificant decision, but thanks to that I avoided potentially huge refactor of my code in the future while I was able to keep a steady flow of improvements.

My general mindset was to avoid any metagame-specific problems (situations that occur exclusively due to currently dominating style of playing) and instead focus only on issues that after fixing them the outcome would be positive no matter how my opponents are behaving. I also focused almost exclusively on 4-player games, because they had much higher impact on the final ranking (everyone will have twice as many 4-player games as 2-player games). All of my 2-player or 4-player specific strategies are just small modifications to evaluation function (more on that below).

Core Concepts

Before I dive to explaining my solution, let's explain two core concepts that might not be familiar to everyone.

Evaluation Function

Evaluation function is a similar concept to fitness function. Basically, it's a function that given some state/decision/situation will evaluate it to (usually) a single number. Allowing us to order states/decisions/situations from best to worst.

Designing solution around evaluation function means that you call your evaluation function with all potential choices and you select one that gives the best result. This means that if you want to give some type of decisions higher priority than to others, you need to bump up their values.

If you have some machine learning experience, you can think of evaluation function as a model with high-level custom features and hand-crafted weights.

Evaluation function is generally used as a replacement for decision trees (random forest vs neural network analogy) or analytic solution. Good example of analytic vs evaluation is movement. You can try to calculate optimal move for ship directly (bad idea), or you can call your evaluation function for all possible angle/thrust values and select the best one. For example, the most naive pathfinding would be to evaluate all moves, for those that collide return -infinity and for those that don't collide return -distance_to_target. And that's already far superior to default navigation.

As for decision trees (i.e. nested if-else clauses), there are several advantages of evaluation functions over trees:

• Keeps all decision-making logic in one place, which helps with quick iteration process
• Doubles as a design pattern and keeps your code well organized
• Allows for easy way of combining several high-level features
• Allows for (semi-)automated weight adjustment
• Discourages you from using decision-tree logic (decision-trees are not necessarily bad, but people tend to overuse them)

So, to summarize. It may look like a small thing, it may feel awkward at first, but it's a way to go when designing behavior of AI-based systems. Especially when the environment is more on the simple side as its the case with Halite. Just don't treat it as a remedy for all of your future problems.

Global Greedy Assignment

There's a common problem in AI-battle tasks where you have N units to your disposal and each of them can perform some set of actions. There's also a standard way of dealing with it. If the evaluation of (unit, action) doesn't depend on results of other units, you can just iterate over all units and select the best action for each one. If it depends, things get slightly more complicated. When your evaluation function is comparable between different units, you can use global greedy assignment (not an official name of algorithm, but it's quite descriptive).

Works as follows:

while (len(units_without_actions) > 0) {
  best_ship = null
  best_action = null
  best_eval = -infinity
  for unit in units_without_actions {
    for action in possible_actions {
      eval = evaluate(unit, action)
      if (eval > best_eval) {
        best_eval = eval
        best_unit = unit
        best_action = action
      }
    }
  }
  update(best_unit, best_action)  
}

For most problems this is going to work really well and will give result close to perfect matching. The only downside is that the algorithm now takes O(ships^2*actions) instead of O(ships*actions). But well, just learn to write fast code ;) Since this loop was expensive for me, I cached best action for each ship and recalculated it only when evaluation value for that action changed. This works, because my evaluation function could not improve after update() equivalent. Which means, if action gave the same value, it's guaranteed that it's still the best choice. Small trick but slashed down execution times by 50-100x in worst cases for whole phase.

Phases

Now that we have our basics explained, let's see how each of my turns look like:

1) Pre-Process

This calculates various global/ship/planet features that are going to be used later.

There isn't much to talk about here. The reason why I'm calculating all of the features beforehand is to have as short decision code as possible. Also, very ugly, please ignore.

2) Calculate Orders

This assigns high-level orders to each ship by using already-mentioned greedy assignment.

I have only two types of actions: go to planet and colonize it & attack enemy ship. In my code there are few other types, but those are just leftovers from experimenting. So, for each of my ships I iterate over all empty planets & all enemy ships. For each of them I calculate evaluation function and I take the action that returns the best score.

The core of this selection can be mostly formulated as: If there's enemy ship within X distance, prioritize enemy ship. Otherwise go to the closest empty planet. Both ships & planet values are augmented by few other features but that's the core concept.

3) Calculate Moves

Based on high-level orders, calculate move (i.e. angle/thrust pair) for each ship.

By now each ship should have an assigned action (order) to it. Either it's going to try colonize planets or attack enemy ships. In rare cases (usually at the end of the game when I'm winning) no orders are assigned, but it's fine since the game is finished anyway.

Moves are calculated using another evaluation function. I iterate over all (angle, thrust) pairs, discard all moves that end up colliding and select the one that maximizes evaluation function. Depending on the type of move, evaluation function is called with different set of parameters that enable/disable various components of evaluation (distance to target, penalty from being close to enemies, bonus for being close to allies, etc.).

For collision checking I'm using currently calculated mov