Halite Bot

This is my submission for the Halite AI Programming Challenge. Halite III is a resource management game. The goal is to build a bot that efficiently navigates the seas collecting halite, a luminous energy resource. Check the rulebook here.

The bot

Navigating through the map involves traditional algorithms for searching the best path combined with a unique way of ranking the value of each cell on the map.

Ships' status Each ship has a given status at any turn of the game:

• Collecting - the ship is mining for halite
• Returning - the ship is full of halite and returns to the shipyard
• Free         - the ship just returned the halite to the shipyard
• Ending     - in the final turns of the game, all the ships return to the shipyard

Navigating Each cell has a value according to the ship who wants to visit it. The general formula is:

where:

• x is the cell's position on the grid,
• s is the ship's poisiton on the grid
• H(x) is the amount of halite at the given position
• D(s, x) is the Manhattan distance from the ship to the cell
• E(x, r) is the number of enemy ships in an r radius around position x
• C is a variable which grows proportional to the enemy's number of ship

At each turn of the game, each ship "books" a cell they want to visit (obviously the one with the highest Γ value). A cell can't be chosen if another ship already has booked it this turn.

Lee's algorithm is applied to find the shortest route from the ship to the cell. To avoid ships colliding, each other ship's next position is considered an obstacle when computing the route to the cell.

To avoid colliding with the enemy, if a friendly ship has more halite stored than the enemy ship, then all the possible next positions an enemy could take are considered obstacles. Otherwise, collision with the enemy is in our favor and the route computes without the taking the enemy into acocunt.