24th Java referee based
It took me some time to write the post mortem, but here it is!
A great challenge as usual
I reached bronze league with a simple logic based on manhattan distances without any simulation.
I then started again from the referee code, and kept it for the whole competition. I did not had time to improve performances, but having the referee code was a huge gain in time.
Regarding performances, with this code and my evaluation function I was able to run maximum 600 simulations with the available 50 ms.
My bot proceeds first to an analysis of the situation to adjust some parameters (High level AI more details bellow). It then try to define what is the best order by doing a brute force search 3 turns in advance for each ship, considering the other ships are doing their best move if already defined, else considering they wait.
I start with the opponents ships and then compute this for my ships.
In the brute force search (A MaxNTree with only one player) I consider mining and firing only for the first turn in order to limit the branching factor (and cost to compute fire target) for the 2 next turns.
And that's it !
A few details:
High level AI:
Depending on several conditions, I adapt a few parameters.
If there is more than two barrels left, I adjust the MAX_SHIP_HEALTH to 150 to trick the ships and make them believe they will have the entire rhum of the barrel. So that the ships do not wait near a barrel because they will have more rhum in 3 turns if they wait.
If there is no more barrel left, I adjust several parameters of the evaluation function in order to change my ships behavior. Main differences are for example the distance to the oponnent ships that I try to maximize if I am leading and I try to minimize on the contrary. More details in the evaluation function part bellow.
Sailing distances vs Hexa distances:
When I brainstormed on paper, I noticed that depending on the orientation and speed of your ship, the hexa distance and the minimum number of turns required to reach another cell is clearly different. Since I don't see far away in the turns, making a difference between ships oriented differently can make the difference between a ship that turns or stays static because the barrel is behind it and in all cases in 3 turns it can't be closer.
So during the first turn, I initialize 3 huge arrays of 50*50 integers where I brute force over the first 5 moves of a ships in the center position the minimum of moves required to reach a cell. I then complete the entire map by considering all the ships will be at speed 2 starting from the borders of the initialized cells.
Each map represent the "sailing distance" for each 0 1 2 speed with a fixed (0) orientation.
Speed 0, orientation 0:
Speed 1, orientation 0:
Speed 2, orientation 0:
You noticed how the cell next to you when you have a speed of 2 is in fact already 5 turns away from you
When I compute the sailing distance of 2 positions later on, I extract the ship speed and orientation, I compute the initial vector that it represent, I perform a rotation of this vector in order to put the ship in the 0 orientation, and I do a translation so that the ship is in the center cell. I then extract from the map the distance.
Using the Cube representation it's quitte easy to do, and having these maps precomputed during the first turns it cost almost nothing more than computing hexa distances. Thanks codingame by the way for the article on the hexa grids, it was really helpfull!!
I first try to find barrels where an oponent ship is closer than me considering the sailing distance, and that I can fire on it before the opponent ship can reach it (still based on sailing distances and time to travel for the canon ball)
If there is none, I have an array of integers initialized to 0 for each ships and for each cell of the map. During the brute force search, I sum the health of the ship on each cell where it is present if it is greater or equal to it's original health.
It builds a kind of presence probability for the next turns that take into account the fact that the ships will try to avoid damages, and favor capturing barrels.
I extract the cell with the maximum value and if I can fire on it in less than 2 or 3 turns I keep this as a possible target.
I also consider shooting to the mines, using the presence probability map in order to compute the sum of the neighbors divided by 3. I'll shoot to the cell with the greatest score either a mine, either based on presence probabilities.
This fire order is then added to the list of possible moves and in my evaluation function I have a bonus when I fire in order to favor this move.
My evaluation function takes into account several parameters:
- Difference of total health with the one of my opponent. This one has by far the biggest coefficient.
Sailing distance to nearest barrel
Number of barrels that have a sailing distance less or equals to one of my ship compared to opponent ship
- Distance to nearest allied ship (sqrt(abs(distance-4)) so that it tries to avoid beeing too close
- Distance to nearest enemy ship
- Sailing distance to nearest mine
- If the ship fired on first turn
- If the ship is on the border of the map
Depending on the situation, some parameters change and for example if there is no more barrels, either I try to flee from the opponent ships, either I try to get closer depending if I am leading or not.