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”.
- First, there’s the obvious “battle” part of the game : this is what we all played.
- 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:
- Search what the opponent would do if I went always straight
- Re-initialize and search what the opponent would do if I went always on the right
- Re-initialize and search what the opponent would do if I went always on the left
- Re-initialize and search what the opponent would do if I went always faster
- (you know the drill
) - …
- 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
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