Choosing where and when to mine


#1

Right now, my “where to mine” code tells a ship to move to the adjacent square with the most halite, unless all 4 squares hold less than a certain amount – in that case, they move to the square with the most (halite amount divided by distance).

I have been using the “move to adjacent square with most halite” code for the past month and a half, and I’m wondering how the top players choose where to mine (besides inspiration). I also notice that many players choose to mine only a small amount out of some squares and I am wondering why they do this.


#2

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 n iterations.

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…


#3

That’s a really interesting approach! I’m a little confused though.

Are you saying that for a given position say (2,2), you consider it and the four adjacent positions only? Or you consider everything at least n squares away?

It seems like we’re doing something similar, but I’m not sure. I have been applying a kernel to the map in order to smooth it, which also pulls in information from neighboring squares into current squares.


#4

In each iteration, you look at the square and its immediate neighbors only. But since you repeat the calculation n times for all squares, in the end, you will have propagated all values for a distance of n, so you know approximately how much halite you can earn within n turns starting from each square.

The difference between value iteration and applying a kernel is the application of the max function, which tells you the best possible outcome instead of the smoothed or averaged outcome a kernel provides.

Interestingly, one could construct a convolutional neural netwok that does value iteration, a so-called Value Iteration Network, which would probably be ideal for halite…


#5

Essentially, finding a target is about maximizing halite per turns. So you need to calculate how much halite you think you can get, and how many moves it will take to get there, and return to a dropoff. Calculate this for every cell (or some subset of cells based on estimation) and you have a pretty great way of calculating which square to go to.
So, pseudo code:
Rate = halite collected/(turns to get there + turns to collect + turns to return to a dropoff)

And you want to maximize rate without stealing from your other bots.


#6

for my tile scoring strategy, I calculate the turns it takes for a ship to move to a tile and from that tile to the nearest base. Also calculate the minimum halite burned for these paths (i.e. the minimum halite burned for all shortest-length paths).

Then calculate score = (haliteMined - haliteBurned) / (turnsToMoveToTile + turnsToMoveHome + turnsStayedOnTile).

@DataWraith I like your approach a lot since it considers neighboring tiles into the score; I think that overcomes the disadvantage with my strategy since mine only considers tiles in isolation. it does not factor in how a ship could go to some location and mine multiple tiles before going home.


#7

@cowzow I was trying to implement exactly what you did, but ended up not doing it exactly like that, for a few reasons. One, i failed to do it efficiently lol. Determining the halite burned was too costly, especially trying to do it per tile in the whole map. Second, halite burned to the target tile is not that accurate, since its assuming you are not harvesting anywhere in between the target tile and your current location.

I also didnt include turns stayed on tile. I figured 1 turn stayed on the tile is a good enough estimate, in determining a tile score. Thus I only do

score = haliteHarvest / (turnsToMoveToTile + turnsToMoveHome)

But i do implement this for the entire map, per ship, per turn. And the ship closest to that tile, essentially have the highest score to that tile, will have the priority to go there. It will then subtract a potential maximum capacity (how much that ship can carry) from that tile. The other ships will then have a recalculated score of the entire map, assuming that the other ship, has already harvested that target tile. Of course it wont recalculate, if its max score tile didnt change, meaning it will only recalculate if some other ship took its

I thought this was pretty clever, until I saw Teccles comment in one of the forums stating that it is not necessary to have some grand whole-map strategy to do well. He’s definitely doing something right, he is in a different league, even against the top 10 players lol


#8

@En3rG - I feel I should clarify :slight_smile: I meant that you can do very well without looking at your fleet as a whole, targeting specific regions, and generally modelling macro-level dynamics. I didn’t mean that each ship shouldn’t look at the whole map, or that you shouldn’t think about how their targets interact. In fact, my own mining target algorithm is very much in the same family as yours and cowzow’s (though I’m afraid I’ll keep the details under wraps until the end of the competition, as there is a chance they are a big part of my secret sauce).


#9

@teccles Oh thanks for clarifying lol, that makes a lot more sense. But yea definitely dont spill the secret sauce, will be looking forward into reading about it after the competition.