Hi all,
I ended up Legend #32. Felt good to get to Legend after several contests being unable to do so.
I want to thank to Codingame for hosting another great AI programming contest. I’ve been playing them for lots of years now and still eagerly await for them and really enjoy playing them 
. This contest was particularly interesting and well crafted, with good possibilities to very different strategies, be it heuristics, simulations or NN. Congratulations to the creators and keep this contests coming !
Congratulations to reCurse for winning and MSz and aCat for completing the top 3. Your bots are amazing, I really enjoyed watching some games by them. I would have enjoyed it more if they would have been more time to watch them though 
. I still don’t quite understand the need to only join in the last hours of the contest, but still…
I originally tried using Smitsimaxi (Decoupled UCT) but couldn’t make it work since the branching factor is so high and the potential actions depend on the state of the game. I ended up implementing a beam search of width 5 and depth 3 for each organism. I don’t simulate the opponent.
Here are some details of my implementation:
Actions
- I divide the actions into “walk”, “spore” and “non-walk”.
- Walk actions are non-spore actions to get closer to some protein or to the rival. They usually would be basic, but could be tentacles, harvesters or sporers depending on available proteins.
- Spore actions could be either just spore from an existing sporer, or a grow_sporer + spore combo which uses 2 turns. Non-walk actions are either harvesters that harvest some protein or tentacles that attack a cell with dist to rival <= 2.
Pruning
- I simulate every available non-walk action, but only simulate the most promising 2 “walk-towards-protein” actions, 2 “walk-towards-rival” actions, 2 “spore-towards-protein” actions
and 2 “spore-towards-rival” actions. So at each node expansion of the beam search I simulate 8 + N actions. - The heuristics for determining the most promising nodes is based on distance to rival and distance to most needed protein sources.
Eval
- 1 point per organ
- 0.5 points per unoccupied cell closer to player (voronoi style Voronoi Diagram - GeeksforGeeks)
- 0.35 points per protein
- Points per harvester. They decrease incrementally as the number of harvesters of the same type increases, following a logarithmic decay function.
- Points for being close to protein sources.
- Points for attacking cells close to the opponent.
- Big penalty for not having enough harvesters to allow me to grow any kind of organ (no A and no any pair of B/C/D).
- Penalty for distance to closest protein sources that I have no harvesters of.
Note: Points for harvesters and being close to resources decay over time and are lower the more proteins of that type I have.
Data structures and algorithms for efficiency
- Every cell knows if it’s being harvested by any player, attacked by a tentacle of any player, the distance to the closest cell from both players, the neighbors in every direction.
- At the beginning of each turn I run an initial bfs from every cell to calculate distances between any two cells, the predecessors in the paths of any 2 cells and the heuristics
score for closeness of proteins and opponent organs used in the action pruning. - For each organism I keep track of the frontier (the unclaimed cells dist 1 from any organ of the organism).
- I create every object I will need in the first turn. I have an action pool and a beam node pool.
- I use only 1 game state instance to run simulations.
- I keep track of the modified cells in each simulation to rollback more efficiently.
Thanks again and see you all on the next one !