Halite II Strategies of a Top Player

Two Sigma’s Halite II has been the most addictive programming competition I’ve ever played. It provides online matchmaking to watch your code battle against other players worldwide. The objective is to control all planets and eliminate enemy players. To do this players must gather resources from planets to create more ships which can be used to attack enemy planets or ships. If you are interested in learning more about the game check out the website at halite.io.

Halite AI Programming Challenge

During the AI competition, we hit a max rank of 8 and finished the season at 26 using the following strategies. Some of these tricks were so clever, we felt inspired to share them.

To get started, the most important strategy is to prevent friendly ship collisions. Two Sigma’s API intentionally didn’t include collision prevention when navigating to planets, so modifications were made to the stock API. To determine if two ships will collide will require some calculus. The principle idea is to come up with an equation which finds the distance between two ships as a function of time (time is equivalent to turns but in continues form).

Ships collide when they try to occupy the same location on the map.

Equation 1: The Pythagorean theorem is the distance formula in disguise.

Next we need to find how ship1_x and ship2_y changes with time. This can be done knowing the ships’ velocity.

Equation 2: The ships position in the x-coordinate as a function of time. describes how the ship moves in the x-coordinate at various values of time

Now replace all the ships position with the above equation in there respective terms.

Equation 3: The distance between two ships as a function of time.

Graph of Equation 3: The distance between two ships. Here the two ships are initially two units away from each other and come to a minimum of one unit at three turns from its initial turn.

To predict if the ships collide we need to determine at what time will D be at a minimum. The minimum of D will be the located at the time at which the two ships are closest. To do this we take the derivative of D with respect to t (turns/time). We do this by solving when t is equal to zero.

Equation 4: Solve for t. This will be the time at which the two ships will be closest.

t will be the time at which the ships will be at there closest point. If the distance is below the fudge factor (about 0.5 units) then there will be a ship collision. Knowing this we can modify our ship’s angle to prevent the collision.

The next strategy is a little bit of a cheese. We call it the desertion meta. You program a ship to fly to one corner of the map in four player match to get second place even if your the first player to lose all planet control. You’ll get second place because you still have a ship alive although you control no planets usually because the enemies will wipe each other out until one is left standing. A better strategy is if your losing in a four player match is to abandon all your planets and command all ships to run away so that you are more likely to survive long enough to get second place. During the competition, we didn’t see anyone go after our desertion ship allowing us to win a minimum of second place in every four player match.

Planet priority calculation makes or breaks your strategies. The foundation we used for calculating the priority of the planet is the distance it is from the ship your issuing a move to. A greedy algorithm would be to have each ship fly and dock to the closest nearby planet. Then we considered the distance the target planet is from the middle. In four player mode we prioritize outer planets because docking inner planets earlier meant having to battle between all the enemy players but if you stay on outside you can focus one enemy. In two player mode we have found capturing the outer planets first not as important.

Equation 5: This gives the distance each planet is from the middle

Which ever planet has the lowest planet priority in our priority queue is the planet the ship attacks. If the planet is full then the planet is removed from the planet priority list or if enemy ships come in range of friendly docked ships the planet get added back to planet priority list. This gives a simple way to issue moves to each ship in a effective way so that your docked ships are safe and the planets your ships choose will be the best.

Here the yellow ships are out matched by the enemy so they evade.

Fight or flight determination is if your ships should attack or run. This is done by adding up all the nearby enemy ships and friendly ships in a suggested radius. The difference of nearby enemies to nearby friend determines if your ship should run or attack. Where should your ship run? Our solution is to run 180 degrees away from the average of all the nearby enemy ships. This would be similar to a negatively charge particle flying away from a set of other negatively charge particles.

That’s our secret to how we got a max rank of 8 and ended the season at 26. And thanks to Two Sigma for creating Halite, it’s been an amazing learning experience!

P.S. We are freelance software engineers that specialize in web apps for startups. You can visit our business, aescru, at aescru.com. We are always looking for work and the next big thing!

Written by James Jones and Ben Burns.