Spring Challenge 2020 - Feedback & Strategy

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.

5 Likes

Gold in 2 days ? wow

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.

10 Likes

#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 :wink:

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 :slight_smile:

9 Likes

Thank you very much!

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

2 Likes

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 !

10 Likes

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 :stuck_out_tongue: 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!

12 Likes

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.

2 Likes

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 :slight_smile:

3 Likes

Wow, that is probably the way to do it, thx

Mid-Silver here.

For the not so advanced coder like myself, seeing a game that was not fully dominated by simulations, giving a chance for the less-capable coder was a relief. Those “complete information” games simply give no chance for the "heuristic / if " basic coder, ones that can’t code deep searches properly. Thank you codingame for the fog of war. We were tired of games dominated by simulations that had frequently to be done out of codingame IDE. We should keep in mind that most competitors will never get to gold, and somehow games should target them mostly.

9 Likes

Incomplete information does not prevent simulations. It just force everyone to code something to handle fog of war, both heuristics and simulations.

Just look at all the top legend with beamsearch or dfs. Even if they don’t use a full simulation (with perfect collisions prediction), this is a simulation.

Fog of war does not prevent simulation to win. Massive branching can prevent simulations but not every time.

9 Likes

In most CG multi you can still enjoy the game without simulation and most of the time it’s easier without until gold (except maybe for Ultimate tic tac toe) or even legend. Then if you want to win the contest it’s likely that you need some kind of simulation and/or hard core programming which is expected as not anybody should be able to win. And this stands for any game with or without fog of war.

2 Likes

I ended 33th in legend. Thanks for another great contest.

I liked coding for the game at first, but got frustrated later on in the week when nothing I coded gave me a visible improvement. No feedback is a serious handicap when trying new ideas. The creators can’t be blamed for this though. This unpredictable behavior of the leaderboard is not easy to foresee and the game being fun and interesting to code a bot for is more important.

Normally I wouldn’t bother to write a large PM when I didn’t reach top 10 or at least top 20, but I think some parts of my bot are worth noting for future reference. I’ll go step by step to explain how the bot works and pay specific attention as to how the monte carlo search works:

The first turn

I do the following things:

  1. Read the map and identify walls and setting all non-walls as having a possible pellet (except those at pac start-locations.

  2. For each cell that is not a wall, I store all neighbors in an array.

  3. I identify all dead ends of the map and put them in a list.

  4. I set up the two pac teams as “Pac” objects.

  5. On the first update I mirror all opponent pacs I don’t see.

  6. I assign each pac a super-pellet as destination if it is closest to it (this part of my bot was weak and could have been much improved).

The update

  1. I do the regular update from the input given. Also storing a copy of each pac from last turn, so I can compare changes.

  2. For each possible pellet on the map I keep a pellet-history (for all 200 turns). For each visible pellet I see in the current turn, I set all pellets as being uncollected for all turns before that. So even if I did not see the pellet in earlier turns, I know it must have been there.

  3. I list all visible cells and mark cells as visible if I can see them that turn. I mark all cells that have no pellets and remember that.

  4. For all opponent pacs I keep a visibility history. I know for each cell if I saw that an opponent pac was not there that turn. So this is not about where the pac was, but where it wasn’t.

  5. For dead ends I floodfill outward until I hit a pellet, so that my monte carlo search knows not to enter into this area without pellets. This helps reduce branching.

Elimination of invisible pellets by opponent pac routes

In a game it happens very often that you will see a pac in a certain turn, then it disappears and you see it again 10 turns later. You then have two locations and there must be a path between them. If the new location is far from the old location, there are often many cells, that the pac must have travelled through to get there. All those cells will no longer have pellets. It is useful to mark these as collected, so your search won’t try to go there. I do this as follows:

  1. I start at the last seen location and make a “future” speed-analysis, moving the maximum number of cells. You have a lot of information about the speed history of each pac, even if you dont see it for a long time, because you have the speedturnsLeft and cooldown.

  2. I flood outwards using the speed it has in each turn from when it was last seen. Any pellets it crosses are checked for whether they existed that turn (using the pellet history). If the pellet existed, then the pac cannot have passed it. This is why it is important to do this procedure only when you see the pac again, so you can use the full pellet-history information you have at that point. I also check whether the locations the pac passed were observed by other pacs. If they were observed and the pac was not there, then the pac can’t have passed through there either.

  3. I will end up with a flooded area which I use as a limited set of cells to create a BFS-searched path from the last seen location to the new location.

  4. If there are any cells that the pac must have passed through to get to the new location, they must be part of this shortest path, but this shortest path might contain non-mandatory cells as well and thus not be the only route. So I take the shortest path and for each cell on the path, I remove the cell from the flooded area and then I check if a BFS route is still possible within the distance travelled by the pac. Any cell which causes a BFS route to become impossible when it is removed, must have been passed by the pac and the pellet is marked as collected.

This feature worked quite well and I was often able to eliminate 5-10 pellet locations at once upon viewing an opponent pac. However, this is one of the features for when I added it, changed nothing on the leaderboard… which was unfortunate. You can imagine the amount of code that goes into this feature.

Blocking the entrance to dead ends

One of the latest additions to my bot was the blocking of dead ends when an opponent pac is near that can kill my pac. I didn’t get around to testing this well enough, so I don’t know it works. Basically I just did another speed analysis and a lot of BFS-distance testing to see if it was safe to be in cells inside a dead ended-area.

Tracking the opponent current possible positions

Assuming the opponent travels at maximum speed (speed chaining). I calculate for each opponent pac all possible positions it could have travelled too also taking into account cells viewed and pellet history just like when I am eliminating pellets as explained earlier. If there are not too many positions like this, I can use this information to avoid being killed around corners. I think it sometimes worked, but I am not sure. It wasn’t well tested.

Opponent pellet prediction

For my monte carlo search I mostly viewed opponents as being walls when they are dangerous and ignored them otherwise, but I did do a floodfill which recorded for each future turn for each cell whether the opponent could have reached there. If, during the monte carlo, my pac would collect a pellet too late from this cell, it would receive less points.

The Monte Carlo search

This is easily the best feature of my bot. When I finished it, 4 days into the contest, my bot jumped to rank 2 immediately. I can’t honestly say if my bot ever really improved after that. If it did, it happened so gradually I didn’t notice. It works as follows:

My monte carlo simulates 8 turns deep (there is no limit really, it could have gone 12 deep also). I could test over a million plans (combinations of routes over 8 turns) in turn 1 and 100k in other turns, which was overkill.

When i say 8, I mean to say both normal and speed move, so it could be 13 cells travelled. Basically, I choose random moves for each pac keeping some restrictions namely:

  1. Pacs can’t move backwards in a corridor during the sim (except in first turn of sim). This is a slight reduction of freedom, because sometimes it might be worth grabbing a quick pellet and turning around. The exception is, of course, a dead end. I store the previous location each time a pac moves, to prevent it from turning around.

  2. For each pac I have a series of blocked cells, because an opponent pac can travel there in the current turn, killing my pac. Opponent pacs are walls in the sim if they are dangerous this way. So not all pacs will have the same walls, because of different types.

  3. Pacs wont go into dead-ended areas with no pellets.

  4. Pacs wont cause friendly collisions. When two pacs want to go to the same place, one will wait (randomly). I do this in the “Resolve collision” functions below

The simulated turn is built up like this:

  • Apply speed ability if necessary
  • Generate random moves.
  • Resolve collisions.
  • Generate random speed moves (if a pac can speed).
  • Resolve speed collisions.
  • Apply all moves and calculate score per pac and total score.
  • Reduce cooldown timers

Repeat this 8 times
After 8 times, check if the current plan gives more score than the previous best plan. Replace if so.
After calculation time is up (which is often after between 50k and 150k plans) apply the best plan to all pac moves.

Lost pac assignment

I keep a score per pac in the monte carlo. If the chosen plan gave 0 score for a specific pac, I default to a BFS route to the nearest uncollected pellet. This way I don’t get pacs just randomly moving around.

Hardcoded destinations and hardcoded moves

My monte carlo also had a system for hardcoded destinations, where instead of generating moves randomly it would just let pacs move closer to the destination, collecting pellets on the way. This way the hardcoded superpellet collection for some pacs does not conflict with the monte carlo plan for other pacs. I also had a system for “first sim turn” moves to avoid nearby opponent pacs, do switches and such, but I never ended up using it.

To do list

My to do included “kill code” (to kill pacs that you are in range of killing), improved superpellet assignment and many tests i didn’t get around to doing. My code was a 2.5k line mess at this point and I just couldn’t summon up the motivation to add these last things. Almost all of the above stuff I explained gave no visible improvement (except the MC search) and this is why I lost motivation.

During this contest I learned the power of a monte carlo search. I never took it seriously before because it seemed worse than mcts or minimax or even beamsearch, but I will look at it differently from now.

See you next contest!

27 Likes

This game was heavily favoring simulation.

Ya i think most games favor simulation. I don’t know how you can not favor it at all. I mean predicting many turns ahead the outcome of a move is very much required.

Can you give a single example where simulation isn’t better?

If you omit very old contests (when the global skill of the community was not even remotely comparable to what is now), simulation always win. (well, i think that there’s some exception. Code A La Mode for example).

But the simulation is not always used with a search algorithm. For example, Recar won the Platinum Rift 1 contest by using a simulation to simulate the 50 nexts turns with it’s own AI for all players. If you look at Ghost in the cell contest, Agade won using a simulation too but not with a search algorithm (most of his code was heuristic, the simulation is only used for a specific point).

It seems that if you want the top, you always need a simulation. Sometimes a partial simulation (without collisions for example). Sometimes a false simulation to speed up performances. And sometimes a full simulation bound to a search algorithm.

6 Likes

47 Legend. Python3.

This was my first ever competition of this type, having stumbled upon CodinGame about 3 weeks ago (since then I have obsessively built bots for some of the older competitions.) When I first started this competition I did well with a quick and lazy approach on the opening day, but over time as people started building better bots, my rank started slipping and I essentially lost motivation. I had some ideas of what I could do but not the confidence or willpower to try and get it to work and keep trying until it worked, and I couldn’t see exactly how to implement it, there were some gaps missing in my mental image of what I wanted to do. That all changed when my friend, Jarcan, joined the competition. He had some good ideas and I could see what I could do if i used some of his ideas, but it felt like my bot would simply be a cheap imitation of his bot. On wednesday night when I had pretty much given up the contest and was rank ~600, Jarcan encouraged me that my implementation would be sufficiently different, there was still time in the contest and there was still lots of room for improvement. Thursday morning idk what came over me but I built the bot. By 2am Saturday I was rank 30. It was a furious 2 days of bashing out code and theory crafting and trying things and failing and then sometimes improving. I couldn’t have done it without Jarcan - he connected dots for me I would not have otherwise seen and enabled me to have the additional insights I had that got me here. The strategy went like this:

  1. Find the shortest paths between all points on the map and store them - this was what I had had a lot of trouble with on my own, finding a way to do this without timing out. Jarcan came up with a pruned floodfill approach using hashmaps which did the job nicely. This was the first big step.

  2. Every turn, for each of your pacs, look through all available paths for that pac and score them with a heuristic function - this infact was not all possible paths but a pruned list of squares deemed worth re-visiting. This scoring function had several layers to it. The heuristic function had a lot of insight baked into it - but here is a brief summary:
    a) don’t walk into enemy pacs that can kill you or go on same paths as allied pacs
    b) eat pellets with 4 priority layers: super pellets, pellets you can see this turn, pellets you have recently seen, squares you have not yet visited and which might contain pellets. The weightings of these categories were scaled with how far into the path youre considering you are as well as having weights updated by game state dependent information each turn.

  3. taking guaranteed kills - when you could see an enemy pac that was trapped and it had no cooldown to switch and you could definitely kill it, do so. this was done using our handy dandy path dictionary again.

  4. switch in the shadows - the absence of information available to the enemy is a great weapon, they cannot help but bump into you or meet you at junctions from time to time, and they have no way of knowing what type your pacs are if you switch when they cannot see you. Further it would be very difficult to counter such a strategy, as you’d then get it wrong if you’re against someone who doesn’t switch in the shadows. In short - track enemy pac types and last seens, when they’re all the same type/2 types, there is an objectively strongest type your pacs should be - so switch to it. There was also some very basic switching logic for particular situations when it was likely a good idea to switch.

But there you have it - a heuristic bot which looks at paths available to each pac and picks the best one based on a scoring system, along with an override of some switching and going for kills here and there. 500 lines of code, but a lot of that is comments or now obsolete code, so this could probably be trimmed down to under 400 lines.

Thanks to CG for this fun challenge - and thanks for bringing me and my old friend together again - it felt like we were 18 again bouncing ideas off each other and discussing theories together.

14 Likes

Observed winrate between pairs of players during the rerun:

Expected winrate between pairs of players after fitting a score to each player (alternative ranking independent from CG):

Difference between the two figures above

(a strongly coloured dot indicates an observed result which was not expected according to the ranking model)

7 Likes

hey @pb4 thanks for your images. I feel my rank (100+) is not justified considering I had 55-60% win rate against rank 40-50 bots. Just because I had lesser lead in the lower bracket does not mean I shouldn’t be paired with higher ranked bots. My bot was fine tuned to beat better bots and not weaker bots. The initial calibration definitely favoured the rank 40-50 bots. If only they dare to fight my bot with some small probability we would know they are weaker than mine. It also gives the me a chance to climb back in case the calibration went bad.

2 Likes

Interesting that there is the same “clear cut” areas as for OOC, thx for the stats.