A few days before the end of the competition, its rank was fluctuating between 95-108.
The bot is based on hand-coded rules, no machine learning stuff, except the use of genetic algorithm for parameter tuning. The drop-offs were not planned (The bot with drop_off forecasting performed worse), so the drop-offs resulted in an emergent behaviour. Stochastic methods were used to rate halite cells instead of calculating their actual costs (This saved time and performed equally well). Spawning decisions were made based on weighted functions. (Spawing functions were different for 2p and 4p)
(Starting with the most important thing)
Each ship has a radius which was calculated as a function of game_map.width, it was such that the scan range of a bot roughly equaled the size of map, so it could look at nearly all squares. Each ship calculated the halite_gain_by_turns for every cell in its scan range:
halite_gain = halite_on_cell/4
halite_burned = halite_on_ship_position/10 * turns_to_go_there
(Note: This is not calculating the actual cost, just approximating by accumulating the current cost
by multiplying with the turns it takes to reach there)
halite_gain_by_turns = (halite_gain - halite_burned) / turns_to_go_there
The cell with highest halite_gain_by_turns ratio was set to be the destination for that ship
If the cell was next to or occupied by an enemy, or was already occupied or was marked as destination for a friendly ship, then a penalty would be subtracted from the halite_gain_by_turns ratio. This reduced ships from going to the same cell for mining.
The ships would calculate the halite_gain_by_turns ratio for every cell but if a cell was within 4 cell radius of an enemy ship then its halite gain was doubled, This significantly increased my win count for both 2p and 4p because my bot would mirror my opponents movements by being close to them for bonus
Drop-offs were not planned, though i tried drop-off forecasting but it performed worse for some reason. Every ship calculated the following:
- Average halite in scan_range
- Check if a drop-off is already in progress
- Check if the cell has structure
- The number of drop-offs exceeded max limit or not
- The status of global flag for investing
- Distance from nearest drop-off
- Friendly count vs Enemy ship count
- Available halite is enough for drop-off
if average_halite > 188 and not drop_off_in_progress and not cell.has_structure\
and len(my_drop-offs) <= max_limit and distance_from_nearest_drop >= 20 and \
investment_flag==True and friendly_ship_count > enemy_ship_count\
and me.halite_amount + cell.halite_amount + ship.halite_amount >= 4000:
Build_drop_off()
else:
Continue_exploring()
Notice that 188 is a magic, the one i hate to be there...
It was mostly handled by an investment flag. The investment flag is a function of following things:
- enemy_halite/my_halite (ratio of our halite)
- enemy_ships/my_ships (ratio of our ships)
- halite_remaining_on_map/halite_available_in_beginning (normalized halite remaining)
- remaining_turns/max_turns (normalized turns remaining)
So the value was calculated by the following function:
function = w1 * ratio_halite + w2 * ratio_ships + w3 * norm_halite_remaining + w4 * norm_turns_remaining
The weights w1, w2, w3, w4 were calculated by genetic algorithms between 50 bots for several itterations and the weights came out to be different for 2p and 4p.
For 2p: w1 = 0.01, w2 = 0.07, w3 = 0.15, w4 = 0.85
For 4p: w1 = 0.00, w2 = 0.00, w3 = 0.25, w4 = 0.75
whenever the function output exceeded 0.5 the investment flag was raised, means that our bot was allowed to invest halite, otherwise not.
For returning, i did something similar to investment flag. The return flag was a function of following things:
- inverse of distance from nearest drop-off (1/d)
- normalized ship halite amount (0 to 1)
- inverse of average halite in scan_range (1/avg_hal)
- normalized distance from next best gain cell
return_function = w1 * inv_nearest_drop_distance + w2 * norm_ship_halite + w3 * inv_avg_hal + w4 * norm_dist_from_gain
These weights were also found by genetic algorithm and were found to be: w1 = 0.08, w2 = 0.63, w3 = 0.07, w4 = 0.64
If the function value output is greater than 0.5, the return flag is raised for that ship.
The returnung ships could stay on a cell to gain more halite if there was space in cargo for that gain The returning ships did not consider enemies within 2 cell radius of the drop-off, this avoided ships being blocked by some naughty enemies who try to surround your drop-offs
Collision avoidance was as simple as it could be, a function found the future locations of all ships(for next turn) and returned the ship ids of all the ships occupying same cell
Then a function would recursively override the movement commands of all the ships that were colliding The movement commands were changed into Direction.Still command
I could have done better but it seemed to do the job for the time being.
-
The bots also attack enemy ships nearby with more than 500 halite in their cargo The bots attack only if their own cargo has less than 100 halite
-
The bots use state machines, the states being "Explore", "Return" and "Suicide" Suicide state was for the end of the game when all bots come crashing on drop-offs
-
The ships were prioritized based on their halite amount, the ships with higher halite could override other ships destinations
I tried depth first searches for best possible future moves using recursive functions but that bot seemed to perform worse and maybe i could not do it right...