For the puzzle version of this game we intend to include a visual indicator on screen to differentiate between “SPEED” frames and normal turns.
I will probably end something like 35th in legend league.
For the contest itself, it was fun, but not THAT fun. Probably because it’s the third time in a row that we have a contest with incomplete information, forcing everyone to code something for the fog and check before that if the bruteforce method will not be enougth. But games with too much incomplete informations also create a shifumi metagame. So you got some opponent where you got 100% winrate and some other opponent where you got 0% winrate. And fixing the second will makes you lose against the first.
As for my code :
- I use a beamsearch for each pac. I search the first best action for the first pac. Then i search the first best action for the second pac. When i’m done with all the pacs i search the next action. I stop when i don’t have time anymore.
- My evaluation function is pretty basic, just eat some pellet, go the big nearest pellet. Don’t die and try to kill the opponent.
- You have to ignore deadend at the start of the game. In fact, i calculate what i called an “easy score”, it’s the score you can have when you eat everything that is not in a deadend. When the players scores is above 90% of this easyscore, my AI will start exploring deadends.
- My opponent simulation is very basic, i only make him moves for 3 turns. My beamsearch can reach depth 10 easily but it’s useless to assume the ennemy position after 3 turns.
I didn’t find any good solution to handle the fog of war. So my code just don’t handle it. If an opponent pac is not in my inputs, it does not exist for my code.
TBH, this was extremely fun and I enjoyed every bit of it. There were too many things that I thought I knew, but turns out I barely scratched the surface. I had to learn way too many things that I’ve never encountered before. Definitely a better learning experience than all my school years combined. Looking forward to more competitions in the future!
BlitzProg, 286th (4th PHP)
This challenge was very familiar to me (a few Codingamers will know why) so I started with big hopes. But unlike what I expected, this tournament ended up being really unpredictable. fog of war gave so much uncertainity that I had no idea if anything I was coding would improve the AI or not, which was really unmotivating and frustrating and prevented me from progressing for quite some time.
I was stuck inside the Bronze league for most of the week, unsuccessfully trying to code some excessively complicated approaches. Most upgrades to get into the Silver & Gold league were finished during my final two days.
Wood 2 to Wood 1
- Just tell your team to go to the last pellet of your list.
Wood 1 to Bronze
- in addition to the above, if any other pellet is near, grab it first. Also make it so can’t choose to go to a cell that you’ve already chosen to go using another pacman, to avoid endless collision.
Bronze to Silver
- Pathfind to the closest pellet for each pacman.
- Pathfinding to what is given to you was not enough to complete this league, so I had to start from a map filled with pellets and remove which were missing from my field of view.
Silver to gold
- BFS to farm faster. if no pellet is near, it falls back to the pathfind algorithm for that pacman. I use a decay factor, so pacmans will flavor short term rewards.
- Not so obvious but powerful upgrade that helped me immensely: put a large penalty on pellets that were BFS’ed through by another pacman. This got my team to spread and avoid minding with each other’s business, and farm much faster.
Other little upgrades:
- I pushed another code with minor adjustements. Slightly longer BFS search, removing useless and strange behavior related to dead pacmans and removed a few starting pellets on the start map by symmetry with the starting position and deal with disappearing power pellets out of view, since it mean something was eaten there. Overall noticeable but very little benefit for my rank.
I still have no idea of any simple way to deal with the opponent, other than just consider that I shouldn’t stay close. I deal with type disavantage by considering anything near visible enemy as a wall that I can’t pathfind or bfs through. I did realize very late that enemy score is actually meaningful and could have been very useful to attempt to estimate what the opponent is doing outside of my FoV.
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 
201st / 4976 (85th gold not that it matters)
I do like the game, despite the RPS mechanic which imo shouldn’t be there. Could probably use some other skills to differentiate between bot strength. Power-up that you pick up as the cover image suggested would have been much better.
The leaderboard + fog of war + 5 pacs max that can clean up all pellets in 20 turns led to an awful lot of randomness.
Either no fog or less pacs or much bigger map size, or even a different ranking system would have made this a great contest.
The result was unfortunately way too random and too hard to test for improvements. A higher depth game would have probably punished the bugged bots (which includes mine) instead of making people play ranking lottery, which is what i did for most part of the contest. Submit -> switch tabs watch some movie or stay in CG chat.
The timing for it wasn’t good either. It came just after another hidden information game. And i’ve done some UTG inbetween (can only blame myself for the UTG though).
I do like this game an awful lot more than OOC and UTG and WW.
(OOC = Ocean of Code, UTG = Unleash the Geek/Crystal Rush, WW = Wondev Woman)
My strategy:
Get all possible moves (suicidal moves are considered impossible).
Incomplete simulation for current turn, me and enemy. First find best turns for enemy, then my own.
I also do tracking and eliminate pellets based on enemy moves, but when fog is up i apply my own scoring function for best moves, so not ideal. 
If i see enemy appear at an unexpected location, i bring up the move history and fix the pellet state all across the board.
Used C# ending somewhere low in Legend.
Glad to see the huge amount of players joining this one 
What didn’t go well:
- Updating C# language before the opening of the contest?! - all those crashes killed my early progress
- Non optimal workplace… As we are selling the apartment, I had to turn my office into a pretty guest room, putting myself on a coffee table:
Not an optimal setup for motivation as I do miss my dual screen, mousepad and space
- Trying to find inspiration to write yet another Fog of war tracker. And early on without the dead indication.
My code:
My final code is mostly what I had the first Saturday sitting 1st for a long time.
- Find a sequence of moves with a max depth of 22. Don’t allow going backwards unless you are on top of a Super pellet or in a corner with only 1 neighbour.
- Score: Negative score if passing allies. Assume wall if there is a stronger enemy in the way. Score pellets along the way with a decay based on depth.
- Assign the best of these sequences to a the pac it belongs to.
- Repeat from step 0, but have negative score when moving into the same tiles as previously selected paths.
- After all pacs have assigned paths do some simple heuristic if a pac should use SPEED, stop if there is a nearby Pacman going into the same tile, change form if I’m in a corner and might die or simply walk to the next (or 2nd if speeding) step of the found path.
- Assume enemy Pacmans are located where I saw them the last time, but remove them if we have vision of that cell, or if it’s more than 15 turns since I saw them.
I should be placing around 283rd place (Gold).
This is the farthest I’ve ever gotten in a contest, so that’s cool.
Now for the strategy:
The core of my bot didn’t change all that much from my first submit: walk up to the nearest pellet and eat it. There’s nothing all that magical about it.
For pellet tracking, I assumed all empty tiles had a pellet until proven otherwise. I do this by drawing my own line of sight for each pac and using the pellet data provided by the referee to correct any discrepancies. Also, since pacs and pellets cannot exist on the same tile, I made sure to mark pac locations as not having pellets.
Something I did do for pellets was track the last place an enemy pac was and where they reappeared. I then marked all the tiles in between as having no pellet. I didn’t do this very efficiently, so I’m not sure how much impact it actually had.
Collisions I found the most interesting. First of all, I made sure that my pacs never visited the same tile at the same time. To do this, I stored the path each pac was taking as a list and made sure that no tiles shared indexes.
Now, I had to deal with collisions with the opponent. Collisions are fairly easy to detect: if your previous position is the same as your current position, you hit something.
If you collide head-on with the opponent, there’s no real mystery and you should probably fix your pathfinding 
However, if you hit at an intersection, you have four options:
- Do Nothing: pretend it isn’t happening. You either effectively disable both of your pacs by repeatedly colliding or one of you gets eaten by pure luck. Don’t do that.
- Attack: try and kill the opponent’s pac by switching
- Defend: same as attack, but you stay put and see if they come to you
- Flee: turn around and don’t deal with it
I ultimately chose a variant of the attack strategy.
Note that you don’t have to see the enemy pac to know what type it is. Collisions only happen in 2 cases:
- 2 or more pacs on the same team try and enter the same cell
- 2 pacs on different teams with the same type try to enter the same cell.
If you collide with an enemy pac, it’s the same type as yours.
Finally, the super pellets. At the beginning of the game, I assign each pac to the closest super pellet. I do this by performing a floodfill on each super pellet until I reach one of my pacs (enemies count as walls). Then, instead of going to the nearest pellet, my search goes to that super pellet. Simple and effective. I could optimize it a bit more by using the best-scoring path, but I ran out of time and what I had made the bot worse 
All in all, this was a really fun contest. My only problem with it was the volatile leaderboard. You can submit the same code at different times and be placed several hundred places apart.
That’s all for me.
Kotlin, bottom of Legends.
My bot was pretty simple:
On first turn:
- Build a graph and calculated visible nodes for every part of maze.
- Find which big pellets are closer to opponent’s pac and exclude them from search.
Then, on each turn:
- Compare visible nodes and visible pellets to find which nodes does not have them and mark them visited. Find isolated groups of pellets.
- If big pellets available, find closest pac and run to them.
- Run recursive path search with simple heuristics (count unvisited nodes with score decreasing with distance from start) in 10 nodes radius.
- If path was not found, run for the closest pellet ( = unvisited node) that belongs to biggest group of pellets.
- Check i need to switch if enemy with stronger type is too close.
- Speed up if ability cooldown == 0 and pac is safe.
I used BFS for everything - path finding, distance measuring, etc.
For collisions I simply marked occupied nodes as blocked. For stronger enemies their neighbors was marked as well, weaker enemies were ignored. Collision was checked only for close distance from the start.
This contest was a bit random, I think I finished in legends only because lucky submit placed me 7th in gold (previous were ranging 50-250).
P.S. My best play vs golden boss: https://www.codingame.com/replay/465559828
Ended up 12th (Rerun didn’t go my way - 6th before rerun). I really enjoyed this at the end, but found it hard to get motivated at the start for another competition with enemy tracking which tends to involve a lot of work and fixing edge cases. Once I submitted the beamsearch version (I got to mid gold with a python version doing simple bfs) and it got 2nd place I felt I could do well with a lot less work than I was expecting. I was still adding features 30 mins before the cutoff (dead end detections).
- Beamsearch for my pacs. Depth 20, done for each pac individually with my other pacs standing still. Best score chosen, then I redo the beam search for remaining pac’s with the first pac moving as found in the first set. Repeat until you’ve got a path for each pac (so 5->4->3->2->1 beamsearches to generate paths).
- To reduce options after the first turn of the search a pac wasn’t allowed to return to it’s previous cell unless it was at a deadend. I also didn’t allow speed to move 1 cell unless it was a dead end.
- Scores for pellets based on picking up quickly + a bonus based on how may turns since that pellet was seen (as pellets I’d seen recently were more likely to still exist).
- Collisions between my pac’s instantly dropped that branch of the search
- Collisions between me and enemies were worth 5 pellets on turn 0 (positive if I’d kill them, negative otherwise), dropping in value by 50% per turn. Enemies of a type that would kill that pac had a zone of 1(2 with speed) squares around them that had a large points penalty on the first turn of the search. If I started the sim in this zone dead ends were also scored badly to prevent fleeing down a deadend.
- Bonus points for speed moves that moved to a visible cell (less likely to die, knowledge of pellets).
- At the start I work out the time to get to every cell for every pac (assuming no collisions). For the first 10 turns I give penalties for reaching a cell at the same time as an enemy that would kill me and bonuses for the opposite.
- No other enemy tracking / prediction . If I could see them they didn’t move, if I couldn’t see them they didn’t exist (unless they were causing collisions with one of mine round a corner). Exception was on first turn where I did create them as I’d know exactly where they were.
- Pellet tracking. At the start I set every square to a pellet. Whenever I saw a pellet removed I’d clear all connected pellets until it reached a choice (this could pass over junctions if only 2 of the exits had cleared pellets). At the start if any enemies were in a deadend I’d clear from the start location to the first junction.
- If an enemy was causing collisions for multiple turns I gave a large bonus to any pacs that could reach his square and kill him.
I never bothered with switching (I don’t even take into account the possible enemy switch if cooldown is 0 on my final version as this seemed to play better against the top of legend - I almost put this back in partway through my final submit as it wasn’t doing well at the bottom of legend).
~ 50 Legend.
I have a mix feeling about the contest. Loved the gfx, the concept. But the fog was here for no real gameplay purpose and something(more info?) was missing in order to use the fog efficiently (too much corner death or I missed something)
My algorithm goes like this :
- minimax depth 4 (me - him -me-him) for each pac that is afraid of another pacman -> give forbiden & winning actions for each pacman
- bruteforce all paths individually to depth 14 (taking forbiden cells into account)
- reconcile paths with a genetic algorithm (don’t count pellets twice or more)
- some magic
- some bugs
lot of room to improve, certainly some bag bugs too
Hi, 90 Legend.
Search :
For each pac, I BFS (as in BFS the actions tree and simulate them) every move/speed combination up to depth 4 (allowing only once in the sequence to turn around on a previously visited cell), using previously found sequences of other pacs in the simulation, and considering the enemy doesn’t move.
Enemy tracking :
For each enemy pac, I mark the cells in which he could be in the next 4 turns (1 mask per frame, so I know which cells are fine at each frame), using floodfill. If the enemy is visible, I start this floodfill from his current position. If I didn’t see him for N turns, I start from from his old known position and spread the floodfill during N turns until I reach the current turn, assuming he would always use speed asap. While floodfilling in the past (i.e. on previous turns for unseen enemies), I remove at each frame the cells that were in my fov at the time.
For every mask that this got me (2 frames per turn for the next 4 turns), each marked cell is weighted like so :
probability(markedCell, frame_number) = 1.0 / (1.0 + <number_of_turns_since_i_saw_him> + (<frame_number> / 2))
i.e. the probability of the enemy being on each marked cells decreases as the time goes by
Evalution :
The evalution is the number of eaten pellets, the danger ratio of the cells I walked on, and a Voronoi to each pellet from my pacs (with distance weighted by a patience term). The Voronoi helped to spread the pacs.
Late addition :
I detect dead-ends and corridors, and if I see a pellet has been eaten by the enemy in one of those, I assume the whole corridor/dead-end probably has been cleaned (probability of pellet divided by 3 for the corridor cells that aren’t in my fov).
Conclusion :
I was stuck on the bottom of legend the whole week-end. I think I should have gone for a different search with a bigger depth. Also my enemy tracking was too pessimistic and my pacs would often be scared of leaving a corridor even though the “danger” has been missing for 10 turns. I tried to weight things differently but nothing worked …
EDIT : Yeah … Reading other PMs I definitely should have worked on a high-depth search and stop focusing on poorly-designed enemy tracking 
Thanks CG (I hope the next contest will get rid of incomplete information )
I think the voronoi also helps gain more “territory”. Basically you end up picking the pellets that are between you and enemy first. Didn’t implement this, but obviously very important.
I didn’t included enemies in my Voronoi (can I still call that a Voronoi ?)
Was considering it might be a great idea to compare territory gain for each move at turn one since game is symmetrical and you know the enemy starting points + 1sec to calculate all that.
#121 (#4 in gold)
University of Wrocław #1 school
Acknowledgements
I will start with acknowledgments. Many thanks to @Zylo and other people from the polish slack CG community for many fruitful talks and sharing ideas. That was a nice experience, and I hope we will extend in time (reach @Zylo or me if you want an invite).
Thanks and congratulations to all our students and other members of UWr team. Great job, I hope you all enjoyed the game! That was definitely harder this time (previously we didn’t even need @DamianS help) and yeah - 7 out of top 10 unis are french, top 2 not :P…
Winners won, so they already know they did an amazing job, but that’s never enough - congratulations to everyone on top!
Last but not least, thanks to the entire CG team for making this contest!
The game and contest
I have mixed feelings regarding the game. At first I didn’t like it - I think it is overcomplicated. Yes, with time, I get used to it, and I think it is interesting, but still. Combining hidden information with controlling multiple entities and uncertainty plus so many instakill situations - that’s a little too much. The game is great but awfully complex as for the CG environment. Plus the visualization should contain debug mode with limited visibility… this was a pain to understand what is happening without this. (Also, the wood leagues were a joke :P.)
C# language issues - yep, thanks, that was not fun.
About the contest length - 10 days contests are awful. In a 1-2 days one, you just sit for a time and code what’s faster. In a month one, you can start in the middle and have nice results (see everyone from our uni during OOC), so it’s not that you have to sacrifice your life to CG. 10 days… if you’re gone for 2-3 days then things are getting messy, and if you’re not a fast-pacer but like to carefully think and write/debug every part - then either you’re a life-goner or out of the top.
My solution and history
So overly I’m a bit disappointed, given the time I put in. But the contest was hardcore, and not coding for a few days kicked hard. If I see descriptions of what seems a simpler bot in legend than ehhh… Sad cat :(.
My first approach was nearly no micro but a combination of pathfinding and opp/pellet tracking.
Pathfinding was based on BFS+Markov. For each pac separately, make BFS with counting my other pacs and opponent stronger positions(+this turn reachable) counted as walls. Then, from the most distant squares, I computed square value as a fraction of best + fraction of all neighbors from depth +1, and the base square score. This base score is a pellet value (if there is one) times discount on not seeing the square for long times the probability the pellet is still there (see later). Then greedy choose best actions for current turn and resolve conflicts by running the algorithm again with more walls to bfs if two pacs collide with each other.
As for an opponent prediction, we came out with @Zylo with a nice algo to track possible paths of the opponent when we see him again. We count upperbound on how many steps he may cover during this time, and for all squares assume that the ones with distance to old position + to the new position less equal than upperbound may bo on the path. Then we set the probability the pellet isn’t there for each square based on the length of the track going through that square and all squares that may belong to any such track. This very often detects just one track and give sure information about gone pellets.
This code was ~#70 on Tuesday, and still ~#230 on Sunday,
Then I wanted to improve pathfinding. And because I had some outside stuff, I kinda finished it on Sunday - not, as previously planned Thursday/Friday. This was the change I hated, rewrite the basics of the system, not incremental update. Probably still bugged, but works. Somehow.
What I did was entirely switch to frame-based architecture. Each pac took into account paths of other pacs, and the path computation went similarly as previously, but for 3 turns deep (I’ve tried with more but timeouts happened).
Each pac created his path on each turn deep computing new Markov with the pills and other bonuses/discounts properly updated. On the upper level I took all combinations of first/second/third computation order for three pacs or less. For a larger number, all pacs were computed as first, and then greedily, the best one was chosen the real one, then more complicated stuff for the second etc.
I added straightforward opponent prediction 3 turns ahead based on simple flow (no additional filtering on visibility etc) to discount in proper (I’m still certain there are bugs out there) turns squares that may be occupied by the stronger opponents.
I also added a few simple micro rules, and was in the middle of implementing tunnels but gave up on this as, without better opponent tracing, the discovery of such situations were very rare.
At this stage, my code became a mess, and I wasn’t sure of anything.
Last superfix, #230->#final @DamianS gave us ‘last advice’ on slack, to usually avoid dead-ends when taking the pills at the beginning. This was a default behavior of my bot, that a day or to ago I tried to force-change. This was actually easy to revert - one uncomment, and bam + 100 places.
WINWINWIN #1089th
Awesome contest and my first serious participation. Was a pleasure to participate in the largest codingame contest.
The codingame team not only managed the considerable strain of almost 5000 participants, they also coded awesome bots of their own, so a big hand to
@[CG]Thibaud, @[CG]Nick, @[CG]OlogN, @[CG]SaiksyApo, @[CG]Maxime, [CG]XorMode and the rest of the team!!
About my code,
I used python3 for its in-built functions as I really did not want to code them myself 
It was a very beginner friendly contest and it is quite easy to make it till Bronze, after this the Switch, Speed and fog of war joins in.
Wood2 --> Wood1
Move to the nearest Super Pellet,
If no Super pellets move to the nearest pellet
Else move to a random point
Wood1 --> Bronze,
Extend the Previous code to join multiple commands by the Pipe symbol ’ | ’
Bronze --> Silver
I added Switch to switch to the eating type if an opponent`s pac is quite close. This was enough to get a decent rank in bronze, after this I added a bit of collaboration:
1) A targeted flag to the pellets so no 2 pacs move to the same pellet.
2) To avoid favoring the pacs with lower ids, I also looked at which of my pacs was closest to the target(Super pellet or pellet) and sent my pac only if it was the closest one.
The min(args, key = function) is especially useful for this.
This was enough to get till silver, after this it got a lot more competitive for me.
Bottom to mid Silver:
-
collision avoidance : I did not know How to implement a BFS so I just looked at whether my pac was in the same place that it was in earlier and switched targets then. This prevented collisions from repeating.
-
Pellet tracking: I updated the value of a cell every time I saw a pellet or a pac. One thing that helps to improve its accuracy is removing the pellets from visibility and taking it from input to update for pellets that were eaten while you were not looking. To get visibility a simple break when you hit a wall will do.
-
Speed: I was not able to implement speed properly and spent most of the contest without it. This was because I set the target to 1 unit away, this made the speed worthless. Adding a threshold only made matters worse due to an endless shuffling between 2 pellets
What worked for speed was deciding the target without considering speed, speeding only when the target was more than 2 units away.
What I did badly:
-
Wasted a lot of time: I noticed that there were several similarities between this and Ocean of code( The pathfinding and the fog of war mechanic), so I spent a considerable amount of time trying to understand top players Ocean of Code post mortems. Unfortunately, the salient difference of you knowing the orders vs you occasionally knowing location rendered all that wothless.
-
Very poor data management: It should have been obvious from the beginning that the map should be stored as a 2 dimensional array, but I stupidly used a single dimensional array of point objects as I wished to store several attributes within a cell. This was a terrible idea.
About the contest
The contest was perfectly designed making it interesting for beginners and experts alike. It held the interest of all and this made the top 3 extremely dynamic with @Kovi holding the lead for a long time in the middle.
Pros of the contest:
- Late introduction of fog of war, this allowed beginners to get started easily.
- Open source referee, this allowed me to find the distance formula accounting for portals
- Very helpful chat, In spite of the fact that I was very unconventional in my approach, the #World and #India chat were extremely useful, @Cegprakash, @eulerscheZahl and some others were full of good advice.
- Gap between league openings, this allowed me to improve my code gradually
Congrats to the winners, really looking forward to the next contest, good luck all!!!
Just for fun, here is a chart (update with F5) of the last fights.
That was awesome. Well done & thanks to everyone making this happen.
I joined this game 2 days ago, and CodingGame a week ago, having done nothing like it before but will definitely be back!
Wood -> Bronze
Playing with heuristics, adding fairly simple rules like pills are good & stop going round in circles.
Bronze -> Silver
Rebuilt it based on a BFS of the map. Start from each pacman’s cell, branch out, give each cell a score, e.g. +30 for power pill, penalty for back-stepping, paths crossing, etc. and scores fall off with distance as far stuff will change before you get there. Compare paths at the end & go to cell one.
Silver -> Gold
Maps of things that may no longer exist. Contorted battle logic. Beefing up the path scoring rules with every low-hanging fruit I could think of before the clock ran out. Lots of tweaking & testing & seeing what works. Lots of watching bots get stupidly killed & trying to make them STOP THAT!
Often lots of work would have barely any impact, then one change would just kick through the ceiling. Three things that took me up more than everything else combined:
- Noticing why SPEED doesn’t work. (See every 3rd post in the other thread.)
- First test run of the new prototype map search, that I’d expected would just break everything spectacularly.
- A pretty simple model of how likely each cell was to contain a pill.
So many thing I had no time to do, like proper pack-hunting & changing strategy based on how the opponent plays. Wish I’d come along a week earlier!
So, 383/4976, #2 in Swift. I’d have loved to reach Legend just to learn from the best bots and get a sense of what is possible. Gold felt like it got a lot harder towards the end, I wonder what Legend was like in those final hours.