Spring Challenge 2020 - Feedback & Strategy

[BenjaminUrquhart]

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.

[ndc]

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

[RoboStac]

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).

[nmahoude]

~ 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

[Neumann]

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 )

[AntiSquid]

@Neumann

The Voronoi helped to spread the pacs.

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.

[Neumann]

I didn’t included enemies in my Voronoi (can I still call that a Voronoi ?)

[AntiSquid]

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.

[aCat]

#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]

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:

1. 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.

2. 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.

3. 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:

1. 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.

2. 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:

1. Late introduction of fog of war, this allowed beginners to get started easily.
2. Open source referee, this allowed me to find the distance formula accounting for portals
3. 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.
4. 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!!!

[_BZH_TidyMaze]

Just for fun, here is a chart (update with F5) of the last fights.

https://docs.google.com/spreadsheets/u/1/d/e/2PACX-1vRdR4SpYZ-t8o11tqqMpMQruRPaMjRChAhyJAcWd38W41uExbPFK_I-TKpXjKll3-f6JkUod14jffDY/pubchart?oid=1159856779&format=interactive

[Michael_Howard]

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.

[_BZH_TidyMaze]

Gold in 2 days ? wow

[wlesavo]

Python, mid legend. Not much to say. I had a simple Monte Carlo with accounting for collisions by simply marking all the pacs I cant eat as walls. After searching movents for a pac, I would also mark a future possition as a walls. The point was that you don’t want to go after that pac anyway, so you might not try to calculate those path as well. Also I forbiden any kind of going backwards (in the single turn estimation, not for the whole game), same logic, you don’t want to go to the dead end anyway, unless it is worthy. Also checking dead end kills seemed to be effective and i had much fun implementing it.

From chat I got some good ideas which I grateful for. First was accounting for crossroads and “unseen” pellets in scoring, which is pellets you didn’t see once in a game. This makes pacs explore better and make sense in general. Another one was to give the discount to the pellets simmetrically to your own moves at first couple of turns, because most people run to supper pellets identically. Last one stollen was to use speed only on (odd, odd) cells. This way running on speed you will always end up in a crossroads, which would give you more vision and should be generally good. Even if it was not effective i really liked the idea and believed it should improve my bot.

So in the end I didn’t have much of the original ideas or rather almost all of my original ideas proved to be not worthy. I didn’t like the randomness aspect to the game in a way that bad bot could win against top bot reasonable amount of times. This made promoution to feel really strange, same bot could end up either #200 either #2, and hard to see if your improvements worked or made things much worse. And I think I ruled out some of the good ideas because of it.

Anyway, thanks a lot to CG for making this possible, and to the community for sharing the ideas and keeping it interesting, without it i would give up much earlier. Looking forward for the next one.

[Xeger]

#75 legend (#1 PHP)

(in french, sorry, I can’t do that in english)

Je vais écrire un PM pour une fois, par contre uniquement en français (mon niveau d’anglais écrit est bien trop mauvais).

Pour ce contest, je me suis tout d’abord demandé comment j’allais gérer la carte et ses différentes cases (et murs) … Plutôt que de le faire en mode “tableau” comme souvent, j’ai opté pour un système de nodes connectés sans trop savoir à quoi m’attendre (c’était une première pour moi) …

Avec le recul ça me semble être un bon choix et en plus c’était intéressant (et instructif) d’essayer quelque chose de différent

J’ai donc commencé par créer un node par case (utilisable) et j’ai ensuite connecté chaque node avec ses voisins. Chaque node dispose des informations suivantes :

• ID
• Position (X Y)
• Nodes connectés
• Nombre de nodes connectés
• Valeur de sa pastille (mise à jour à chaque tour)
• Informations impasse (si le node est dans une impasse, distance de la sortie, node du fond de l’impasse)

Pour calculer les meilleurs déplacements :

• Le code va calculer pac après pac le chemin le plus rentable sur une distance de 12 à 18 nodes environ (un pac peut s’arrêter avant la distance max mais ne peut en revanche pas faire marche arrière et continuer sa récolte pour des questions de timeout)
• Chaque pac tient compte du chemin du pac précédent pour éviter les collisions et éviter de cibler les mêmes pastilles
• Une fois le chemin de tous les pacs calculé, une boucle relance le calcul des chemins mais en changeant l’ordre des pacs (un “anti-timeout” stoppe le calcul des combinaisons en cas de besoin, indispensable pour les parties à 4-5 pacs)

Pour calculer la valeur des pastilles :

• Valeur réelle pour les pastilles visibles (en tenant compte aussi des cases visibles par les pacs mais vides)
• Valeur légèrement réduite pour les pastilles non visibles
• Forte réduction de la valeur des pastilles d’une impasse lorsque le pac aperçoit l’entrée d’une impasse et qu’il n’y a plus de pastilles (car fort probable que l’impasse soit complètement vide, sauf si position de départ d’un pac)
• Calcul simplifié de la “propagation” de l’adversaire, autrement dit, j’utilise les positions de départ et je détermine les cases qu’il a pu potentiellement atteindre à chaque tour (toutes les autres cases = 100% de chance de trouver une pastille)
• Prise en compte aussi de la distance du pac (valeur fortement dégressive) et s’il s’agit d’une impasse

Le code tient compte aussi :

• Des collisions face à face ou d’angle
• Des risques de se faire manger (ne pas déclencher le speed dans certains cas, switch si vraiment nécessaire)
• De la possibilité de manger un adversaire (lorsque c’est sûr)
• Des impasses (pour éviter par exemple de déclencher le speed si un adversaire à risque en vue)
• Des pacs collisionnés qui peuvent bloquer un chemin pour mes autres pacs
• Etc.

Le code ne gère en revanche pas le fog of war … C’était probablement la fonctionnalité indispensable pour monter plus haut en légende. Mais bon j’avais déjà passé suffisamment de temps sur ce challenge à mon goût, je n’étais pas sûr de pouvoir “rentabiliser” ces ajouts avec le timeout (et pas vraiment la motivation de coder ça à vrai dire) donc je me suis arrêté là pour ce contest

[piter239]

Thank you very much!

Such a great write-up! Learned a lot from it.

[Flo]

Hi there, ended #11.

I used beamsearch as well, depth 7. I relied on two evaluation functions for pruning:

• the first one for pruning individual pacman moves (enemies nearby, pellets taken and future potential pellets). I kept the best 4 moves for each pacman.
• the second one for pruning pacman moves combination (4^5 max), evaluating the pacman spread and avoiding collisions.

I also used some sort of beam search for enemy tracking. Each turn I expanded the possible enemy positions for each id. I pruned the possible enemy positions depending on the missing pellets and using the possible score gain of each position.

My bot was mainly focusing on farming, and was lacking some more aggressive techniques. I think this made me miss the top 10. I had a lot of fun anyway, many thanks to the CG team !

[k4ng0u]

k4ng0u, 48th Legend (C++)

This challenge was very fun and I liked how it was easy to start but very hard to master due to the multiple map configurations. Even now I am not sure of what really improved my bot and what didn’t. It ended up with a lot of magic constants tweaking.

For me the key points were:

• Map symmetry
• Tracking the pellets left
• Farm efficiently
• Avoid dying to opponents
• Eliminate the opponents when possible and worth

Use map symmetry
Initially, compute opponent pacs thanks to the symmetry and as such deduce all the cells with pellets as well.

Tracking the pellets left

At each turn, depending on the visible pellets and your pac position, you can know which cells had their pellets emptied.

As such intersections are important to get more information. That’s why before using speed I checked the distance between my pac and all the intersections with a distance of less than 10, if more than half of them are even distances, then I speed, otherwise I move and speed the next turn. (=> this made me pass to Legend)

Another interesting concept that @Indrill introduced to me is the corridor: any chain of cells with at most 2 neighbours. I tried to implement some logic to say if a cell of a corridor is empty then it means that all cells of the corridor until a visible pellet or a pac starting position are likely empty. This is because when a pac enters a corridor, he usually goes all the way until the end. However I didn’t manage to integrate it well in my path scoring so it was discarded from my final bot.

Farm efficiently

I didn’t find a good way for that so I just did a depth 15 brute force on each pac to find the best path, then I would take the best and recompute the paths for the other pacs applying a penalty for visited cells, etc until all pacs have a path. In the end the scoring function was something like:

cellScore = pelletValue*0.9^distance*(hasAlreadyBeenVisitedByOtherPac ? 0.4 : 1)*uncertaintyMagicCoeff

A path would only be allowed to go back if there is no option left (dead end or all other possibilities are dangerous cells).

Avoid dying to opponents

Ideally you would want an efficient opponent tracking. I didn’t bother with that, so I just had simple heuristic on visible pacs (which from time to time resulted in my pac dying one or two turns later)

Pacs were to avoid dangerous cells (during first turn, don’t step into a distance inferior to 1 to a better pac, during second turn, don’t step into a distance inferior to 2)

If no good escaping path is found, if you have your cd up, transform into the type that beats your opponent. Else try to get some pellets before dying.

Kill the opponents when possible and worth - TODO

I didn’t have time to implement this one. But in some situation you are sure that you can eliminate the opponent pac. In those situation a good way to do so would be to check how many turns you need to eliminate him, how many pellets you could gather in the same time and how much a pac is worth (a good approximation could be remainingPellets/remainingPacs).

Contest final ranking

Not sure if it’s just an impression but I feel like the final score computation relies a bit too much on the last leaderboard state. On a last lucky push I reached top 40. Then with 43% victory rate (basically losing record against all players around me) at 60% of progression I barely lost 0.5 and was still around #45 I won’t complain about it but it’ likely frustrating for people who got down because of a lot of last day submission with bad match ups.

A word on C++

This was my first contest in C++ but in the end I coded almost like I would in java. I was willing to use primitive and native arrays but it quickly became a pain. My advice for C++ beginners like me is to use std libraries until you really need to improve performances Also I tried to use some pragma I found on CG forum but it made my code slower for some reason…

Thanks a lot to Codingame for this contest!

[k4ng0u]

For the crossroad thing I computed the distances of all crossroads at a distance of 10 of less from my pac I speeded up only when a majority of crossroads are at even distances (sometimes in some scenario crossroads can be separated with a odd distance making the odd,odd heuristic not totally relevant) Also if I am contesting a super pellet that is more or less at the same distance from my pac and opp pac, I would speed regardless to not lose time and be the first there.

[GreatTux]

Top-ish Gold (C++)

Contest was fun as usual, kudos to all the coders and the CG Team, always a pleasure to see people from all around the world compete against each other.

Keys points of my implementation:

• Each frame, give a score to each cell (pellet value, is it explored or not, decrease the value if the cell is part of a deadend)

• Each Pac then adds a relative score (decrease the value if opponent with opposite type on the path, value of the cell decreases with the distance from the Pac, to make close cells more attractive etc.)

• Get all paths from Pac with depth 6 then take the best one

• Partial opponent tracking, I track the visibility of opponent and set the value of pellet to 0 if only one path possible between the previous and current position

And then some specific code for collision handling, defensive switch type (no aggressive behaviour).

Feels like I wrote lot of code but most of it is boilerplate. That’s a bit the negative point for me, I’d like more time to actually implement my ideas and evaluate them, but I need to be better prepared maybe