Spring Challenge 2020 - Feedback & Strategy

[MSmits]

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!

[AntiSquid]

This game was heavily favoring simulation.

@Zuabros

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.

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?

[Magus]

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.

[Insufficient]

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.

[pb4]

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)

[cegprakash]

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.

[wlesavo]

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

[zasmu]

Finished 3rd !

Intro

Congratulations to everybody, espacially Saelyos, Romka and the CG team for hosting these events.
I don’t know if it’s the prize pool or the marketing or both, but seeing almost 5k contenders is amazing !
Keep it up CodinGame, your work is wonderfull.
I’m obviously very pleased of the outcome, this is my second contest podium after Code a la mode but this one was not pure heuristic so I feel the competition level was higher. This is my first PM, I usually don’t feel like sharing.

Journey

Got to bronze as fast as I could with python to get a feel of the game with the full rules.
I worked on the simulation the first weekend, I realized collision handling didn’t need to be perfect. Then I wondered what kind of algorithm could be good.
Tried with pure random search depth 10 with the simpliest eval and felt like the result was ok.
Didn’t feel like aggresive bot could be effective until last weekend when I saw some amazing tricks done by other bots.
I almost instantly felt like FOW mitigation would become necessary but this was intimidating so I started to work on that only last saturday.
My bot almost focus exclusively on farming.
Each feature was tested with CGBenchmark <3

Final bot

The main search algorithm is inspired by Magus Fantastic bit genetic algorithm.
The point was that I felt this could make Pacs cooperate as Wizards did without needing to tell them so.
A Particularity is that I randomize only on valid output for each pack, so I simulate each turn before randomizing the next.
Merge and mutate were done on a single whole Pac path.
I did manage 10 to 30k full 12 depths simulation per 50 ms.
For ennemy I run same algo for 10 ms before with my pacs standing by. I only simulate ennemy pacs if I’m sure of their position (line of sight or if the FOW mitigation tells me so).

The eval is the simpliest possible (myScore-OppScore) with huge bonus/malus in case the victory threshold is passed. I sum up eval each turn for the whole solution score so pacs focus on closest pellets.
At the end of simulation I minimize for each pac the distance to the closest pellet because I saw my pacs wondering endlessly at the end of games when no more pellets were close by (none in 12 depths).

The FOW mitigation system :
Each turn I compute all paths possible starting with symetry. I then remove some based succesively on :

• Line of sight (pacs, pellets present, pellets missing…)
• Score, is this path possible according to opponent score difference between this turn and the previous one ?
• I use observed collisions and deaths to trim paths
• reduce paths length themselve if all shares common prefix marking those cells as having no more pellets.
• only keep last cell if all paths score = 0
• deduplicate
• if numbers starts to grow to high, remove paths with less size (meaning opp pacs would stand still or move only 1 cell instead of 2 on speed), remove paths with less score, meaning opp pac would be dumb…
  This way I could generally go through mid game.
  Then when there are fewer pellets remaining paths number explodes, so I clear it and goes blind for this particular opp pac until I see it again.
  I would use paths to :
• pin point an opp pac if possible to use in sim and avoid certain death.
• reduce cells value (pellets score) by % of occurrences in paths to use in sim (ex: if 8 paths out of 10 has cell (x, y), going on it only yield 0.2 score).
• try to avoid ennemy embush

I have a turn 0 brute force to exclude all actions which could lead in immediate death, this works defensively.

I also added in the last night a quick trapping system which might detect a trapped opponent situation taking advantage of the FOW mitigation, it doesn’t occures very often.

Misc

I’m very impressed by the bots which pacs cooperate to trap !
Mine is only a farming machine, I realized only at the end that killing was an option and the fact that two different approaches could both yield very good results makes me think that this contest is a success. Surely future multi top bots will be a combination of the two.

Was hopping to win the contest when I saw a 10% overall win rate improvement after implementing a new feature when I was already top 3 on the leaderboard yesterday evening !

Looking forward for the next contest, hopefully with even more contenders and nice prize pool so other top coders join us !

[CaliforniaQT]

Hello! I found this website and the spring challenge on Thursday, and spent the weekend trying to break out of bronze league. I was able to crack silver within an hour of the final countdown.

It was so fun to write a basic AI and then tweak it by watching it play! I seriously spent probably 8 hours every day for the last three days just watching pacs and making code adjustments. It was very satisfying to finally get the bump up to silver! Can’t wait to join the next tournament from the beginning and have more time to mess with my code.

One thing I’d like to do differently in the future is to actually use the fancy BFS, etc. that people talk about here - all of my “AI code” was just spaghetti and if/else statements. I’m looking forward to learning a more advanced way to write this code.

[jke]

I finished 112th in Legend and used Go.

I had tons of fun! I’ve never done a programming contest or any AI programming before. I have read the “Red Blob Games” blog before so I had some ideas. Excuse me if I use wrong terminology.

At first I thought I wouldn’t enjoy it much, but it was easy to get into and I was hooked.

My final approach was something like this:

First turn

Walk the map building a graph of nodes, and marking dead ends and corridors to dead ends. This made some heuristics easier to code later.

Game Turn

1. Load in pacs and calculate visibility. If a pacman was missing, I try to find a likely path for them to have taken, otherwise store their hidden location for later. Also process visible pacs by finding their last location and assume all pellets between them have been eaten.
2. Load in the pellets and remove missing pellets in line-of-sight. If a pellet is missing down a dead end area, I mark them as likely being gone which is used in heuristics.
3. Analyze whether enemies should be attacked or change type in defense.
4. Execute pathfinding: A* on all of the big pellets and on the 30 closest pellets
5. Sort the paths by most valuable per spaces traveled.
6. The pac with the most valuable route will get first pick, and then mark all the steps in the route as assigned (used in heuristics).
7. Reprocess the next most valuable routes based on this new data and repeat until all pacs are assigned a route.
8. Output

A* heuristics

Pellets and empty paths cost very little to traverse and pathing through a unit costs a ton. I didn’t want paths to be completely blocked by other units otherwise they would have found no path when trapped by units.

Paths also accumulated value based on:

1. Pellets (duh)
2. Neighbor pellets
3. Far from other friendly units

Paths lost value when:

1. Close to enemies (especially if they can eat the pac)
2. The path is in a dead end
3. The path includes another unit’s path this turn

Each turn typically took < 2ms.

Tools and Methods

A few days into the game I got tired of waiting for results so I built a small wrapper around the referee to run the game 1,000 games concurrently. I used my previous bot as the “champion” and in-development bot as the “challenger.” Once I had made progress I would submit to rank up and then promote the challenger to the new champion.

I also got frustrated with regressions so I started writing tests for situations my code was trying to address. I would take a small map as input and assert the moves taken were correct. Here’s an example input of collision avoidance:

#############
#...#.:.#...#
#..####.#...#
#.....C.C...#
#.....#.#...#
#.....#:....#
#############

(C is a pac and : is a pellet)

The tests were a huge benefit as I could refactor code and try new things out knowing the bot still behaves in the way I expect.

GGs

Thanks for this competition and great competitors! I look forward to learning new algorithms. Keep the write ups coming!

[thibpat]

That contest was awesome!!

My goal was to reach Legends while streaming everything (on twitch.tv/thibpat), but I ended up in gold, 220th in the general ranking.
My main problem was not tracking the opponent position, so in the end I’m happy to be that high in the ranking without this feature

AI
My bot precomputes the visible cells and all shortest possible paths between each walkable cells on the first turn.
Every turn I try to find the best path out of all possible paths, while having a score for each pellet (a close pellet is better than a far one).
I started to store the opponent positions when I see them, and tried to clear the path between their two last position if there was only one possible path between these two last positions.

You can view everything (approx 17h) from the first lines of code to the last debugging issues on Twitch: https://www.twitch.tv/collections/dBeOIFg8EBZENg

Overall I enjoyed the contest, and I loved this fresh visual aspect

[CowZow]

Hello, I finished rank 10.

I focused on the farming strategy for my bot and it was heuristic-based. I was very impressed by the bots that implemented trapping and good combat mechanics, this was an area my bot was weak in.

I’ll share what I did for the farming since I think this was the strength of my bot. The algorithm is as follows:

For each of my pacman:

1. Perform a BFS starting at the position of the pacman in the map. Use the BFS to calculate the distance of each point from the pacman; (i.e. 2-d array bfsGrid where bfsGrid[x][y] is the distance of position (x, y) from the pacman.

2. Perform a DFS from the pacman now with the following policy - for a given node you open at (x, y), you will only examine its neighbors (nx, ny) where bfsGrid[nx][ny] > bfsGrid[x][y].

   I think this is basically the same as if you run Djikstra’s on the pacman and you have this graph where the path from the root to every node in the graph represents the shortest path from the pacman to that node. You are going to now run DFS on this graph starting with pacman at the root.

   So with that intuition in mind, here is the scoring fn that does this DFS. Point (x, y) represents
   a position on the board. The boolean thruPac refers to whether you visited a pacman during this DFS.

scoreFn(Point (x, y), boolean thruPac):

    # Get the tile score, if we visited a pacman, this is 0 b/c the pacman we pass through will get it.
    tileValue = 10 if (x,y) is a bigPellet | 1 if (x, y) is pellet | 0 if floor
    if thruPac:
        tileValue = 0
   
    # Base score is just tile value divided by distance to tile
    baseScore = tileValue / (distance from pacman to (x,y))
    
    # Get all the neighbors (up, down, left, right) neighbors of (x, y) that follow the bfsGrid requirement
    # described above.
    Point[] neighbors = {neighbor (x', y') of (x, y) where bfsGrid[x',y'] > bfsGrid[x,y]}        
    
    # for the next recursive calls, thruPac' is only true if the current position has a pacman or we
    # passed through one already AND if there is only 0 or 1 neighbors to visit.
    # If neighbors.size > 1, that means we can now take a diverging path to not go through a pacman.
    thruPac' = ((x, y) is a pacman OR thruPac) AND neighbors.size <= 1

    scores = []
    for n in neighbors:
       scores.add(scoreFn(n, thruPac'))
    
    # Note here we check thruPac and not thruPac'
    if !thruPac:
      return baseScore + max(scores)
    else:
      # If we pass through a pacman, they're gonna walk down the best path,
      # so we give ourselves the second highest path score (second highest value in scores[]).
      return baseScore + secondHighestNumberIn(scores)

This is the intuition of the scoring algorithm. Now I run score(x, y, thruPac=false) on every pacman for each of their neighbors {up, down, left, right} directions and move my pacman in the direction of the highest score.

This works pretty well; the pacmans naturally kind of spread out and avoid each other due to the thruPac management. The scoring method needed to be tuned though; I did some things like:

• If the current pacman is not the closest pacman to the position, multiply the tile score by 0.5
• If distance > 10, multiply score by 0.5; etc.

Beyond this, the features I implemented:

• Enemy tracking - The enemy tracking I did was to run the algorithm above on my enemies to guess where they would move if they were in fog. I would update the pellets as well based on these projected movements. If I see something to invalidate my opponent model for an enemy pacman I would remove that pacman from the list of tracked enemies and wait to see it again (i.e. seeing a pacman in a different location or seeing a pellet that the pacman should have collected still be present are invalidators).

• Combat - I implemented a 1-ply search of all actions my opponent could do and check if my move would cause my pacman to die. If so, the move would be assigned a large negative score.

[DimSumSaying]

…I didn’t aware Golden boss have such kindness.

[eulerscheZahl]

I finished 14th.

Another fog of war game. These are painful to debug, as you need the full match history (where have the pellets disappeared already? where have I seen the opponent). I described my approach how to handle this on tech.io. In the following I will use some illustrations from this replay.

I split my turn in three phases: tracking, killing (with higher priority) and harvesting.

Tracking

Initially the opponent positions are known (mirrored to your own).
Then I list all possible following states for each individual opponent as long as they don’t become too many. It’s possible to exclude some in later turns (when I see a pellet, it hasn’t been eaten) or in the same turn already (observing the score change it’s easy to detect all opponents speeding at once). For an opponent path only a few things matter: the eaten pellets, the final position and the cooldown. It does not matter if the opponent randomly walks around while invisible to me.

Let’s have a look at turns 2-4:

The opponent rock with ID 0 moved 2 cells at first. I know that because of the score gain. There are a few possible locations for the opponent. Then a super pellet is missing with ID 0 being the only opponent in range. So it’s clear who picked it up and which path was used. I can now safely remove all pellets on that path. When I see the opponent again later on, I can filter for the according states. If there are multiple, they might share some of the eaten cells at least.

As you can see, there are float at my pellets. These are probabilities that they still exist. It’s not the result of a statistical analysis but some numbers that seemed to work. I also apply some heuristics here. E.g. when I see the entrance cell of a long corridor with a missing pellet, I assume a lower probability for the remaining cells there as well. The opponent won’t start harvesting and then turn around. Even visible pellets may have a probability below 1, when an opponent is close than me.

Fighting

I only attack opponents with a cooldown greater than 0. Otherwise they could just switch and kill me. For each opponent and group of 1-2 of my own units (only those capable of beating or at least blocking the opponent, you don’t attack a rock with a scissors and cooldown > 0) I try the following:
List all possible cells, where the opponent can go and that are not blocked by me. Then move my units as close as possible to the opponent (taking the furthest possible opponent location for each of my own units). If my unit can beat the opponent, remove that cell from the possible opponent locations.
Repeat this until the opponent cooldown is 0 or there are no opponent positions remaining. If the latter is true, we can go for the kill.
You can see a 1 vs 1 kill at the beginning of the replay linked above. A 2 vs 1 fight starts at frame 29 with a rock blocking the escape route and a paper eating the opponent.

Harvesting

I use a beam search here. I do it for one unit after another. When one is fixed, I keep those moves while simulating the next. I run the search twice in reverse order of my units to avoid one harvesting in the territory of the other and making that one unemployed. The depth varies from 4 to 8 turns depending on the amount of units I have to control.
My scoring rewards collecting pellets with some decay for later turns. I also score the final position my taking the minimum distance for each pellet to the closest of my own units into account. I multiply these numbers for each pellet by their probability.

Here’s an animation of the replay from above:

It helped me to spot bugs like not removing some pellets easier.

[kovi]

The structure and tone of this PM is pretty similar to my OoC one.
Nice game, with lost of players and strong competition (besides the usual, many marathon veterans from another site), gratz for the winners!

This time I have reached #1 early and stayed there for most of the time. First with heuristics, than with simple search and prediction. Last few days were more challenging (+randomness of near 50% winrates), after a long weekend/nights I was still hoping for a top3 result. But recalc did justice once again, I fell down to #6.

As usually my code is not based on a simple “super-algorithm”, but many heuristical features:
-search: multiple tries with varying order and depth (up to 17) of independent DFS for each pac
-eval: based on single map (with all/predicted pacs) + pellet probability map
-last resort: BFS to nearest (avoiding bump or being killed)
-speed: positions with “x+y parity” are preferred (to avoid 1-step waste and give more visibility), need a delay (but which give speed advantage)
-switch: when “forced”, especially when another type have better winrate vs. enemies than current one
-bump/repeat: detect, continue with it, but let other pacs go for the same targets
-chase/trap: check stuck enemy (BFS) or when with speed advantage or when cant see - chase (even with switching)
-enemy “prediction” (track of disappeared enemy): multiple steps, prefering pellet take, set probabilities
-enemy reapperance: pick direct path and set pellet probabilities; if no direct path use backward-prediction
-superpellets: avoid if better enemy pac have advantage; handle enemy just taking it
-pellet (post)prediction: handle new empty positions and lower probabilities “around” it
+1 learn enemy behaviour: an important thing which i had no time

[Michael_Howard]

Hope this doesn’t start a religious war, but I notice C++ dominates the top of the leaderboard but not so much further down. Is it just a great language for this sort of thing, or is there some reason winners are especially drawn to it?

[Neumann]

@CowZow

If I see something to invalidate my opponent model for an enemy pacman I would remove that pacman from the list of tracked enemies and wait to see it again

Do you have stats about how often that would happen ? Or about how acurate this prediction model was ?

Thanks for the PM

[CowZow]

I never ended up coming up with stats for this, but just tested this by eye. I had each pacman print out where they thought the enemy was (with same ID as my pacman). There were some players (like Kovi ) who printed out their next move in the game as well, so I would run games between myself and these players and then see how often the coordinates I printed out matched theirs in the replay. Here is an example: https://www.codingame.com/replay/467342481

I think it worked OK… but yeah definitely can also go wrong at times. I wish I had a better way to quantify the accuracy.

[tutubalin]

Challenge was fun! Alas I wasn’t very successful this time - stuck in Silver.

Wood 2 to Wood 1
As I knew new rules will follow, I didn’t want to design something big at this point. I wanted to make something small and dirty just to leave Wood2. To make it more challenging I decided to make it as small and dirty as possible.

So I ended up with 100 bytes JS solution:

(f=_=>[x,y]=readline().split` `)(g=n=>n&&g(n-1,f()))
g(y)
while(!g(f(g(f(f())))))print('MOVE 0',x,y)

It can be easily turned into one-liner, but I left it like that to keep readability, maintability and self-documentingness.
All this code does is ignores most of the input and just moves to the last pellet.

Wood1 to Bronze
This time I created a proper solution in Java.
If we consider that eating pellet has negative weight, then all we need is find the “shortest” path, i.e. path with minimal weight (usually also negative).
I used Dijkstra algorithm, though it’s not very suitable for negative weights, so I had to modify it a bit. Surprisingly, it worked pretty well and my bot reached Bronze right after the first submit.

Bronze to Silver
New rules and more intense competition required some fixes:
— implemented “fog of war” for pellets. It concidered every unseen pellet to exist until proven otherwise;
— fixed NPE when one of my pacs got eaten;
— fixed bug when 2 pacs blocked each other;
— intensified weight of nearby pellets (previosly best path was concidered only by total number of pellets, independent of how far they are);
— impemented Rock/Paper/Scissor mechanic to decide if path is blocked or not.

Every of this improment moved me 300-500 places upper, but with 2800 total players in Bronze that was not too significant.

Then I implemented SPEED command support and instantly my bot skyrocketed to Silver.

Silver
I found that sometimes my pacs walks in empty areas just because another allied pac already was there. So my first big improment was to choose paths that are not intersecting. Solution was pretty straigtforward:

1. initially every pac chooses path indepently
2. cells that are planned to visit are marked
3. second run of pathfinding is executed with respect to plans of other pacs

This gave me pretty good results: from ~400th place to ~100th place.

Then I implemented enemy tracking: every time my pacs see enemy pac, a table is calculated, on which turn this enemy pac may reach each cell on the map.
I used this table to avoid colisions with enemy pacs, or intentially try to colide if pac is “eatable”.

I expected it skyrocket me to Gold, but it gave me nothing.
Then I found a nasty bug and after fixing it… I dropped from ~100th to ~700th!
Yes, broken enemy tracking gave better results then fixed one. That demotivated me and I gave up on further improvements.

Here’s one of my Bronze games:

[Lysk]

Thanks for the PM! Do you run this on each pac in sequence (decide pac 1 > decide pac 2…)? Would that favor the first pac since it would have less often a thruPac (being the only one to move)?