I wouldn’t really consider myself a top player, but my strategy for finding halite is the one I’m most happy with out of all sub-components of the bot, so I’ll share.
The method is basically the “Value Iteration” algorithm from reinforcement learning. You will need to tweak the basic algorithm a little (well, a lot) until it becomes useful and fast enough though.
The idea is to calculate, for each square, how much halite you could get with an empty ship, starting from that square, after 1, 2, 3, …
n turns. To calculate the amount, you have to consider two cases. Either you harvest (
value_still = halite / 4) or you move to an adjacent square. In that case you plug in that square’s value from the previous iteration:
value_north = previous_value_of_north_square * 0.9 - movement_cost.
The initial values can be chosen arbitrarily and the
0.9 is the discount factor. It makes the bot prefer nearby halite over far-away halite, even if there is more of it far off, because (among other reasons), someone else might get there first and leave you with nothing.
The new value for the current square becomes the maximum of the calculated values (i.e.
new_value = max(value_stay, value_north, value_east, value_south, value_west), because we want to know how much halite we can make with the best move out of the five) and this value is then used by the adjacent squares to update their own values in the next iteration. In the end, each ship can move to the adjacent square with the highest calculated value after
The devil is, as usual, in the details though. For example, naive application of the algorithm will lead to all ships going to the same place, which is usually not what you want…