Cool contest! Finished at the bottom of legend.
Personnally, I still felt pretty burned out by the intense 4 weeks of the last contest so I decided not to invest too much time in that one. Instead I gave myself a challenge: see what the least amount of code required is to get to legend (without doing any golfing).
While the original idea was to not get too invested, in the end I think I probably spent more time trying to force a minimalist bot into legend than if I wrote a proper one to begin with…
Mission accomplished though: my final bot made it to legend with less than 300 lines of Kotlin!
Absolutely no focus was put on reducing the number of lines. In fact, it should be possible to trim it down to like 200 lines without even hurting readability much. See for yourself:
https://forum.codingame.com/uploads/default/original/3X/b/6/b6024ebc3200763febf90edb6958716b04a20ce6.png
Now as for the bot itself, first I put in some useful precalculations during the first turn:
- Possible moves: a hashmap containing for each walkable cell the list of accessible walkable cells
- Vision range: a hashmap containing for each walkable cell the list of walkable cells in vision range
- Dead ends: an array of walkable cells that can be considered dead-ends (includes cells part of a tunnel that leads to a dead-end)
- Distances: a 2D array containing the distance from each walkable cell to every walkable cell (created using Floyd-Warshall with the map of possible moves above)
Initialization at the start is pretty standard:
- Every walkable cell starts with a normal pellet on it (super-pellets will be read from inputs every turn and placed accordingly)
- Ennemy pacs out of line of sight in the first turn are initialized based on the fact they are symetrical to mine.
Then comes reading the inputs every turn:
- Update information for pacs in line of sight, remove dead ones, increment ‘stale’ counter for invisible but not dead ennemy pacs
- Remove ennemy pacs marked ‘stale’ for more than 2 turns (bit arbitrary but that yielded the best results)
- Update pellets based on line of sight of friendly pacs
- If any super-pellets are on the map, try to ‘intelligently’ assign one per pac, based on their and ennemy distances to them
Finally comes the search:
It is a pretty standard DFS, ran for each friendly pac individually to depth 15.
Since it’s a bruteforce anyway, a BFS would achieve the exact same results but I chose DFS because the recursive implementation simplifies back-propagating scoring and such.
Obviously the search results for previous pacs is taken into account in order to avoid collisions.
Also, pacs with the least possible moves will play first to try to avoid situations where a pac will leave another with no good option.
- Speeding pacs are handled by running the search twice, once for each subsequent move (obviously only the second MOVE order is sent in the output)
- Switching is handled by running the search for each pac type, and if a better scoring is possible by switching (basically it avoided getting eaten or ate an ennemy), the pac will do so.
If the cooldown is up and switching doesn’t improve scoring, then just SPEED instead (there’s no ‘saving’ powers for later). Pacs are forbidden from going back on their steps (dramatically reduces branching) and if a dead-end or collision is reached, the current score is back-propagated.
At each step of the DFS, a score for the depth is calculated with decay:
currentScore = previousDepthScore + currentDepthScore * 0.8^currentDepth
The 20% decay makes pacs prioritize more immediate rewards, especially important since the ‘better’ rewards located further might have already been taken by the ennemy out of line of sight.
The scoring at each depth consists of:
-
pellet score: bonus based on pellet type (if any) on the current cell, with a small malus applied if the cell is located in a dead-end
- prioritizes not going into dead-ends whenever there’s better options
-
distance to pellet score: very small malus based on distance to the closest known pellet
- this drives pacs towards remaining pellets that are outside of the DFS range in the late game
-
distance to super-pellet score: malus based on distance to assigned super-pellet if any
- this drives pacs toward their assigned super-pellet in the early game
- ennemy score (see bellow)
I tried to give a small score bonus for pellets that are in line of sight (since they are sure things), but strangely enough that made the bot tank spectacularly.
Ennemy management:
My search assumes ennemies don’t move and outright ignores ennemies past depth 4 (because by then, they will be elsewhere far away)
If a cell on the search path is ‘occupied’ by an ennemy (more like ennemy is somewhere close actually, since it will move), the following rules are applied:
- If the ennemy type wins against my pac, or doesn’t but has his cooldown up, the path ends here with a strong scoring malus (pac died)
- If the ennemy type is the same as my pac and his cooldown is not up, path ends here with no score change (considered like a wall)
- otherwise, I win the encounter but my pac only gets a score bonus if the ennemy pac is either in a dead-end or I’m speeding and he’s not
(this is to avoid having a pac run after an ennemy forever and never catching it)
Conclusion:
There you have it, that’s all of the 300 lines explained. Obviously it’s very minimalist so there’s a bunch of shortcomings with everything, but it did the job.
Some simple ideas could potentially improve the bot by a lot without even increasing the number of lines of code too much:
- The algorithm for assigning super-pellets is currently wonky and doesn’t work well for every situation, sometimes losing a reachable super-pellet
- Making ‘stale’ (out of line of sight) ennemies move by running them through the same search as my pacs would probably greatly improve things!
- might avoid pacs getting eaten from a corner (which is currently not handled at all)
- could potentially guess which pellets were eaten out of line of sight, improving farming
- Similarly, making ennemies take their next turn (still using the same search and assuming my pacs don’t move) before starting my own search might also improve things
- more relevant search through knowing that ennemies might get in/out of the way
Those things were on my TODO, but in the end not required to make it to legend.
I was never really competitive this time, but I had a lot of fun with my self-imposed challenge!
Big thanks to everyone for the contest, it’s always a treat 