Coders of the Caribbean - Feedback & Strategies

Contests
#35

Yes I still used it briefly on and off one day (Friday if I recall) to quickly test different sets of weights. I ended up keeping one bot that seemed to do well enough and indeed improved my real world results too. I think at least 2 of these weights are still in the final code. But I needed real results during the last weekend so I did not use it again. Maybe I should have. Such testing was critical in FB, and I did not even have anything near the nice setup I have now back then.

Yes, 5 for each ship, but only in one ship games. I prefered capping it to 5 to get faster results anyway, but maybe on rare occasions 6 could be reachable. Not sure how helpful that would be in practice. Two and three ship games were very often on 4, but sometimes only 3 for complex scenarios.

The only way to speed up tree search, other than faster state updates (which I also did in between brute force and minimax, maybe made them 2-3x faster), is efficient tree pruning coming from all the sources I mentioned in the article, and you can still do a lot more if you keep digging the chess wiki. I am not sure which pruning you are referring to for that number, nor on which games, but I don’t think you can describe so easily the average for different games, or even different scenarios of the same game. I could collect some stats from my bot later if you are interested.

I built a list of pairs, matching each allied ship with all the enemy ships, sorted by decreasing distance. I then ran minimax for each pair in succession, keeping the best moves found in between, for the other ships not involved in the search.

Exactly. I started by only evaluating firing at the sweet spots I talked about, but as the search got better I could handle many more firing locations, which ended up in this AI paranoia.

7 Likes
#36

Hello everyone, great contest :slight_smile: I ended up 23rd with a genetic algorithm.

Metagame

Because of the huge amount of rules in this game, I figured out very late what I think the “correct” metagame is.
Given that it’s quite hard to actually hit a cannonball or a mine, many games end up with ships running out of rum over time, which means whoever has the ship with the most rum has a great advantage.
With that in mind, I made up 3 eval functions for my GA:

  • If there are still barrels around, pick up barrels
  • If there are no more barrels and I have the ship with the most rum, sail in circles and try not to get hit
  • If there are no more barrels and the other player has the ship with the most rum, focus all my energy on trying to hit this ship, and this ship only

Maybe the third case deserves a few more details:

  • All my ships had a reward for being in front of the bow of the target ship
  • I added an extra reward if the speed of the target ship was zero, which encouraged my ships to collide with it
  • I only allowed my ships to fire at the enemy ship with the most rum, and totaly ignored the other ones

Simulation

I didn’t feel like implementing heuristic rules to avoid being hit by stuff in the game, so I re-implemented the referee in C. In the end I could run between 150k and 300k simulations of turns in ~40ms, which I believe is more than enough for this contest.

Some people wanted to have a look at the implementation, so here it is: link. (It compiles and I believe for now it makes your ship shoot at themselves, but I don’t have the IDE to test it :confused: )

Genetic Algorithm

Nothing outstanding to say here, I had a depth of 5 turns, a population of 50, 50% mutation and 50% crossover.
The evaluation of the fitness was the sum of the fitness for the next 5 turns, with decreasing weights over time.

At each turn I used the best solution from last turn as a starting point, gave myself 5ms to make my ships move, then 10ms for the enemy ships, then I dealt with connonballs (see below), and the remaining time (somewhere around 20ms) to make my ships move and fire again.

Firing

Ok, so, that’s the one idea I’m proud of in this contest. But, spoiler alert, it didn’t work at all. I think I ended up with the worst firing algorithm of the top 50.
Still, I’ll spend some time explaining it :smiley:

The starting point is simple, I wanted to quantify the gain of having a cannonball arrive at a given spot and turn, so that when I compute my fitness, I could take this gain into account when firing.
This way, one of my ships could change his course in order to make a better shot and maximize its fitness.

The other thing I wanted to achieve is to not shoot to hit, but shoot to minimize the fitness of the target. So a shot could force an enemy ship to slow down, get closer to a wall, etc. This way I could sort shots from a minor annoyance to a garanteed hit.

In order to do that, I listed all couples (coordonates, delay) that had a chance of hiting the enemy ship with the most rum, and for all these, I ran a GA with only 3 generations to try and find an escape route for the enemy ship.

The difference between the original fitness and the fitness assuming a cannonball was fired at a given coordonate+delay gave me the gain of firing at the said coordonate+delay.

The problem (I think) is that in only three generations, a GA often wrongly thinks that a cannonball cannot be dodged.

TODO list

Overall there are many areas in which my bot is lacking.

  • The prediction of what my opponent will do is attrocious (he can’t fire or mine)
  • I mine randomly
  • My shots are way off
  • I still get stuck in walls sometimes :disappointed:

General Feedback

Thanks again to all the CG staff for this really nice contest. As much as I enjoy reverse-engineering, I think providing the referee code is a very big plus.

Still, there are a few points I think could be improved in the following contests:

  • There was no place for low efficiency languages here, I had to drop Python on day one in favor of C.
  • Rules a bit overcomplicated: hew grid, collisions, three boxes per ships, ‘clunky’ move function, etc. I feel like some of it could have been removed. For example the fog of war was probably too much.
  • Really hard to follow cannonballs on the replay screen.
  • As marchete (brilliantly) pointed out, wood was really hard to pass.
  • Legend boss arguably a bit to tough

See ya all at the next one!

11 Likes
#37

Thanks, I’m so glad to see such a post :slight_smile:

I also compete in scala since a few years and I’ll have a deep look at your github project.

I also shared some scala ai stuff which can relate to CodinGame but the code is not really documented for the moment (except with the unit tests).

2 Likes
#38

Hello Tyrcho, feel free to leave comments on the codes.

This time, It took me a lot of time to handle the timeout and to optimise the arena performance. I realized that operations with immutable map and set in scala are time consuming. I will continue the optimization work once the contest is released in practice mode.

Some articles I find interesting www.lihaoyi.com/post/BenchmarkingScalaCollections.html and www.lihaoyi.com/post/StrategicScalaStylePrincipleofLeastPower.html

#39

@reCurse thx for the awesome post-mortem. I learn lots of things. You mentioned a replay downloader in your post

Replay downloader: A program to download the JSON files used to store replays on CG. The main use case is for producing a crude but practical suite of nearly exhaustive unit tests for the simulator code at a very low cost. Replaying thousands of matches and validating the expected result turns a simulator cannonproof very quickly, making optimizations and refactors very safe.

could you please share more details about this tool? How do you download replays in Json with which API? How to you make tests?

2 Likes
#40

It is completely undocumented and unsupported by CG, so you will need to reverse engineer all of it. :slight_smile: I think it would take longer to explain the details than figuring it out by yourself. Judging from a few who started doing just that in chat (presumably from reading my article), it seems straightforward enough. Just inspect the network traffic when using CG.

#41

It took me 2 hours to code a replay download/analyser. But it’s my job to do this kind of things. I don’t really want to publish it. It download all replays from the last battles page of someone. If everyone start to use it, Codingame will put a limit on it (like the submits with CGSpunk).

If you code in java, all you need is Apache Http Component and something to read the JSON (i prefer Jackson, but you can use Gson or standard java JSONObject).

#42

Assume that I know how to download replays in Json :stuck_out_tongue: , how do you approach the testing part?

Thx

#43

Thanks :slight_smile: I have read most of what LiHaoyi posted !

I’ll integrate some of your ideas in my next contests, like the Bundler and jmh tests.

A suggestion : keep in separated repositories common library code, and code specific to each CG contest. Those should be in private repositories actually … otherwise someone could just copy/paste your solution and achieve top100 in practice mode. I use gitlab for those.

Would you like to collaborate on a public repository of scala libraries for CG / AI stuff ? Maybe @csj would be interested too. Mine is a bit of a mess at the moment (https://github.com/tyrcho/scala-ai/), it would motivate me to organize it better :slight_smile: There are for instance some generic implementations of minimax/alphabeta/MCTS.

1 Like
#44

24th Java referee based

It took me some time to write the post mortem, but here it is!
A great challenge as usual :slight_smile:

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 :slight_smile: !

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.

Example (cropped):

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 :smiley:

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!!

Fire positions:

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.

Evaluation function:

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
  • Speed
  • 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.

22 Likes
#45

Finished quite low at 808.
Here is my post mortem

1 Like
#46

video is no longer available.
Did you download it … ? :confused:
plzzz say “yes” :wink:

#47

Hard to find this topic again with 2 R on CarRibbean… looked for “cotc” instead… :slight_smile:

2 Likes
#48

thanks, fixed :slight_smile:

I believe Discourse search is quite bad too :stuck_out_tongue:

1 Like
#49

I guess it’s long overdue for me to write my Post Mortem…

Here are in no particular order some thoughts that I implemented in my AI:

Game analysis

I am a firm believer that contests should be approached very progressively, by spending enough time to analyze the game with pen and paper. Writing code that is unused in the end is often a waste of time.
With that said, I believe that Coders of The Caribean is “2 games in 1”.

  1. First, there’s the obvious “battle” part of the game : this is what we all played.
  2. Second, there’s the very long term part of the game : assuming that you can dodge cannonballs perfectly, you win if you take the last barrel (yes, I simplified…). This is similar to the game of Nim (Marienbad). I don’t think anybody during the contest could approach a level where such long-term thinking was used.

A game of battle ? or a game of survival ?

Question was: is it more important to fight well and kill the opponent in battles ? or think strategically and pick the last barrel ?

My answer at the time was: given the low frequency at which mines can be placed, the long flight time of cannonballs, the fog-of-war and the speed of ships, it would be difficult to kill an enemy ship.

Additionnally, the referee specified movement rules where a ship comes to a stop when it collides with any other ship. This is the main situation when a ship is at risk. Hence, I expected that any kill / evasion maneuver would appear in cooperation between several ships.

Hence, I’ll pick an algorithm where I can focus on evading & coordination between ships to pick the last barrel.

Genetic Algorithm, once again ?!

Surprised ? Yes, I did use genetic algorithms. Why so ? Here are a few reasons:

  • Focusing on evasion, there is often one dangerous paths and many safe paths. A genetic algorithm will easily find one of the many safe paths.
  • Cooperation is a no-brainer.
  • Search depth can typically be higher than tree-search algorithms

From genetic algorithms to trendy minimax

In my previous Post Mortems, I have described my “standard” approach with genetic algorithms : (1) Search what the opponent would do (2) Search what to do against this opponent prediction.

This approach isn’t optimal in COTC, because you might optimize against a specific predicted behavior 4 turns deep. The opponent prediction is highly imprecise and it should be considered so by the algorithm.

The basic algorithm can be modified in the following manner:

  1. Search what the opponent would do if I went always straight
  2. Re-initialize and search what the opponent would do if I went always on the right
  3. Re-initialize and search what the opponent would do if I went always on the left
  4. Re-initialize and search what the opponent would do if I went always faster
  5. (you know the drill :slight_smile: )
  6. …
  7. Search what I can do against all opponent predictions. When evaluating the score, consider the worst case scenario as if the opponent chose the worst path against me.

This is similar to a depth 1 minimax algorithm, because I choose the path that **max**imizes my **min**imum score.

Following this principle, many options may be considered to represent the opponent behavior. I presented the simplest in this post-mortem, but believe me: I tried everything :slight_smile:

Evaluation

Not much to say here. The only thing that I did not see in the thread was how I defined a “time-to-team-death” metric considering “perfect play” by my ships. This is basically :
rum_of_the biggest_ship + sum ( min(30, rum_other_ships) )

Other parts of the eval were already described by many people in the thread.

In hindsight, I would add the “special distance” described by @Manwe in his post-mortem : I really like the distance maps that were built :slight_smile:

8 Likes
Mean Max (CC01) - Feedback & Strategies
Sogeti Codefest - Feedback & Strategies
#50

Hello Manwe, Thank you for sharing your experience. I really appreciate your way of thinking about distance. But there is one thing I don’t understand : How do you initialize your 3 huge maps during the 1st turn considering you can change the speed of the ship during the travel time?
Again thanks a lot

#51

Make the map twice as big in each direction and place your ship in the center. Then all you have to do is to add an offset to your real ship and target location to move the ship to the center of your lookup map.
That way you only have initial speed and direction as parameters (I guess you can get rid of the direction too, but it’s fast enough without that optimization), so you have to run 18 breadth first searches on a map with 4 times the nodes of the actual map.

#52

Ok, I understand that but i’m not sure how to run a BFS involving a modification a speed : For exemple if your initial speed is 0 and you want to go straight on to reach a goal 6 tiles in front of the center of your boat you will only need 3 turns : 1st you send “FASTER” and move foward one tile, then faster again and move foward 2 tiles and then a simple “WAIT” and you move foward 2 tiles and now the bow of your ship reach the goal tile. This is the simpliest exemple but it could be trickier with initial speed = 2 and a goal tile behind you.

#53

You don’t try to reach a specific field, you find the distance to every field on the map.
From the initial position you have several options: WAIT, FASTER, SLOWER, RIGHT, LEFT.
This gives you up to 5 new positions that you can reach within 1 turn. For each of these apply the possible moves again. That might sound like a lot of possible states, but you will reach duplicate states (with speed 0 a RIGHT, LEFT is the same as LEFT, RIGHT or SLOWER,WAIT for example). The only important information for a state is your location, speed and direction, not the intermediate states you reached on the path, if you are interested in the distance only.

#54

Oh ok thank you very much :slight_smile: