Challenge was fun! Alas I wasn’t very successful this time - stuck in Silver.
Wood 2 to Wood 1
As I knew new rules will follow, I didn’t want to design something big at this point. I wanted to make something small and dirty just to leave Wood2. To make it more challenging I decided to make it as small and dirty as possible.
So I ended up with 100 bytes JS solution:
(f=_=>[x,y]=readline().split` `)(g=n=>n&&g(n-1,f()))
g(y)
while(!g(f(g(f(f())))))print('MOVE 0',x,y)
It can be easily turned into one-liner, but I left it like that to keep readability, maintability and self-documentingness.
All this code does is ignores most of the input and just moves to the last pellet.
Wood1 to Bronze
This time I created a proper solution in Java.
If we consider that eating pellet has negative weight, then all we need is find the “shortest” path, i.e. path with minimal weight (usually also negative).
I used Dijkstra algorithm, though it’s not very suitable for negative weights, so I had to modify it a bit. Surprisingly, it worked pretty well and my bot reached Bronze right after the first submit.
Bronze to Silver
New rules and more intense competition required some fixes:
— implemented “fog of war” for pellets. It concidered every unseen pellet to exist until proven otherwise;
— fixed NPE when one of my pacs got eaten;
— fixed bug when 2 pacs blocked each other;
— intensified weight of nearby pellets (previosly best path was concidered only by total number of pellets, independent of how far they are);
— impemented Rock/Paper/Scissor mechanic to decide if path is blocked or not.
Every of this improment moved me 300-500 places upper, but with 2800 total players in Bronze that was not too significant.
Then I implemented SPEED command support and instantly my bot skyrocketed to Silver.
Silver
I found that sometimes my pacs walks in empty areas just because another allied pac already was there. So my first big improment was to choose paths that are not intersecting. Solution was pretty straigtforward:
- initially every pac chooses path indepently
- cells that are planned to visit are marked
- second run of pathfinding is executed with respect to plans of other pacs
This gave me pretty good results: from ~400th place to ~100th place.
Then I implemented enemy tracking: every time my pacs see enemy pac, a table is calculated, on which turn this enemy pac may reach each cell on the map.
I used this table to avoid colisions with enemy pacs, or intentially try to colide if pac is “eatable”.
I expected it skyrocket me to Gold, but it gave me nothing.
Then I found a nasty bug and after fixing it… I dropped from ~100th to ~700th!
Yes, broken enemy tracking gave better results then fixed one. That demotivated me and I gave up on further improvements.
Here’s one of my Bronze games: