4th place solution
Hi everyone!
First of all, I would like to thank Codingame and everyone I had the chance to talk to during the challenge. The rivalry between the Smurfs and the Gargamels was a lot of fun (although, sadly, Indrill and the Smurf team came out on top!).
Here is my approach :
Step 1 : Build a Graph Neural Network using PPO :
164 778 parameters: a 48-channel, 4-layer message-passing trunk over the grid graph (dilated neighbourhoods, zone edges), with six heads:
- policy : one logit map per action unit (3 rail cursors + 1 disrupt cursor), decoded sequentially under legality masks
- value
- enemy head : predicts the opponent’s four actions (cross-entropy under his mask)
- multi-horizon heads : which rails/zones will be active or inked at t+k
- active head : which of my rails will be on an active path at t+5
- a tiny deep-sets leaf distilled from the critic for the search (39 aggregates : value, int8).
My network didn’t start from scratch. I first trained it with behavioral cloning on my best heuristic bot to give it a strong starting point and avoid spending days before getting decent PPO results.
Step 2 : Build a smitsimax search algorithm :
That’s probably the most interesting part of my post-mortem. Without it, my GNN was around 7th/8th rank in the leaderboard, it added a lot.
One tree per player, one selection per action unit:
score(a) = Q(a) + C_camp·√ln n·(v+1)^-1 + W·ρ^d·prior(a)·(v+1)^-0.5, with Q backed up from a leaf = deep-sets critic + simulated revenue over an 8-ply horizon, priors from the policy head (our side) and the enemy head (their side), a root list of the top-6 cells for us and top-16 for the opponent, 32 candidates in depth, with around 1 700 iterations per turn on CG.
Two findings shaped it:
- Part of the search advantage came from self-exploitation. Locally, search versus vanilla looked like a +20 point improvement, but the first ladder results suggested otherwise: my vanilla model was actually better. The search was extremely good at predicting our own network. Making it play against exploiters and tuning the opponent exploration constant (C_ADV = 2.5, later increased as the game progressed) fixed most of the issue and eventually brought the bot to #1 on the leaderboard for about a day (before Indrill crushed us again
). - Restricting our own root list (K = 6) beat wider lists: the network’s top-6 was already good, extra candidates diluted visits.
Credits :
- Before working on this challenge, I tried this PPO + search approach on other challenges, especially Snakebyte, and Sheesh / sZoom helped me a lot on discord to answer my questions. My first PPO used a U-Net architecture, following an approach that Sheesh had successfully used in several previous challenges, before I eventually switched to a GNN.
- Shoutout to the Gargamel team, especially pduhard. We gave it our best shot against the smurfs, and even though we didn’t manage to beat them, the journey was what mattered most !