Spring Challenge 2020 - Feedback & Strategy

Contests
#62

Thanks to the creators, CG and congrats to the winners ! It was a good contest. For some reason I tend to not do very good on fog of war contests (WW, OOC) and this was no exception. I ended up #203, dissapointing since i had a lot of the complex mechanics that many of the top players implemented. I think with some tweaking and bug fixing I should be able to be higher in the ranking.

The different thing from the others that I did was a smitsimax as the search algo. That search gave me good results in other contests, but I struggled with it this time around, specially with the ucb parameters. I never managed to make it work properly, and in the end I just used it as the battle algorithm when one or more of my pacs are close to a rival. As the main search algo I used a depth 15 dfs for each pac, with reruns to prevent blocking each other.

Do you know when will the multi be available? Or at least some beta version of it…

Thanks again and looking forward for the next contest (end of year, ouch…)

5 Likes
#65

Hello! I finished 76th in Legend.

My bot used a Search that was based on Smitsimax. This was my first contest on CG that I worked on from start to finish, so I was very excited to reach Legend.

First Turn

  1. Fill in the location of all enemy pacmen and all pellets.

  2. Calculate which pacmen has the shortest path to every super pellet.

  • If two pacmen are the same distance, but one pacman will kill the other, the weaker pacman should cede the super pellet to the stronger one.

Search Function

  1. For each pacman (mine and opponents), I built a tree of the pacman’s possible actions, with a depth of 4.

    a. Like most others, I only considered paths flowing outwards from the pacmen. They couldn’t turn around mid-path, unless they hit a wall.

    b. I did not make any assumptions about when a pacman has to use an ability, they could save it up if they wanted to.

  2. I ran Smitsimax. An action was chosen for each pacman, and those actions were simulated. This repeated until we reached a depth of four. At this point the board was scored. Repeat for N iterations.

Problems with my Search

At this point. I found that although Smitsimax was giving decent moves, it was hardly ever finding the optimal moves. So I added another layer to my algorithm. I decided to call it (for some reason) Lock and Rock. I think a lot of people did something similar, minus the Smitsimax.

Let’s say there are 8 pacmen. At this point we have the “best” set of actions for each pacman, as returned by Smitsimax.

Pacman1: NORTH, NORTH, EAST, EAST
Pacman2: SPEED, (NORTH, NORTH), (NORTH WEST), (WEST WEST)
…
Pacman8: SWITCH_SCISSORS, SOUTH, WEST, SOUTH

Let’s assume that Pacman2 - Pacman8 are going to follow those paths. But, what about Pacman1? We can try every possible action in Pacman1’s tree and evaluate it against the other pacmens’ actions. So given the other pacmens’ “locked” paths, determine which path is truly optimal for Pacman1. Repeat this process for the rest of the pacman. At this point all the pacmen are going to have a very good move.

I run this algorithm twice, and then for each pacman I do a final analysis on the two best actions for each pacman and choose the best one.

Evaluation Function

  • If pacmen have goals (to get a superpellet) +SCORE for getting close to that goal, or achieving it
  • -LOT for dying, +LITTLE for killing a pacman
  • +SCORE for eating pellets, -SCORE for opponent eating pellets
  • -SCORE for being far away from pellets
  • +SCORE for number of pellets in range (using something like voronoi)

Opponent Tracking

  • Because my Search also predicted the best moves for the opponent’s pacman, I assumed they made those moves, and marked any pellets that they would have eaten as “unlikely_pellets”
  • If I saw an opponent later in an unexpected spot, I would update their location.
  • If I didn’t see an opponent somewhere that I DID expect them, I would stop tracking them.
  • However, if I made a wrong guess I didn’t have any code to go backwards and figure out where they really might be, or what pellets they may or may not have eaten. I would have liked to do that if i had more time.

Overall, this was an excellent experience. Congrats again to all the winners, and thanks to CodinGame for a great contest!

9 Likes
#66

26th Legend / Java

I spent very good time playing this contest, it was not so easy due to the fog of war and the number of moves combinations!

Pretty proud to have contributed to the 1st place of Thales and 9th of INSA Toulouse :grinning:

Wood to Bronze

First, it is important not to spend too much time when we do not know all the rules so i try to reach quickly bronze with the minimum of code and strategy.

Here, i just move pacs to the closest super pellet or if not any the closest pellet. I use speed whenever i can. For the distance, i used manhattan at this moment.

Strategy to reach Legend

Precomputed data
I use the first turn to compute as much possible data to save time after:

  • position : instantiate a Position object for each coordinate. Just a trick to avoid garbage collector pressure when creating too much objects

  • distance : for each position, save the distance to each other position using a BFS

  • line of sight : for each position save the positions in sight

  • moves positions : for each position save the positions we can reach with speed 1 and speed 2

  • deadend : mark position in deadend and save the position list associated to find the whole deadend position associated so it is possible to get the start and end easily

  • paths : list of possibles paths for each position computed using a DFS depth 10. Turn around is done only when reaching a deadend

Init data
A pellet board is created marking all empty position with no super pellet and no pac.
I use for that a bit board with one long per line.
At turn one, i deduct from my pacs positions the opponent pacs positions and type.

Update data
Each turn, i update my pellet board with information i have using pac line sight.
I try to guess also pacs positions. For that i have a list of possible position/visited for each opponent pac i update each turn so when the opponent reappears i can update my pellet board removing the visited positions.

Engine
I have implemented the engine so i can play easily actions and see what happen managing also collisions. I was thinking i could do a depth evaluation at this moment but when i try all permutations moves it was really too slow and i timeout regularly with 5 pac and depth 1… (my evaluation function was in cause too)

Compute
Like i said before my first try was to play all permutation moves and evaluate the game. It lets me reach silver but some timeouts in 5 pacs maps prevent me to reach gold.
Then i try to play iteratively. I compute the best move of one pac, then i compute the best move of the second one using the best move of the previous one and so on. It works well and let me reach legend (with some other stuffs).

Evaluation
In that game, it is important to control the whole map and to have a good distribution so i was thinking it is pretty like Tron game with voronoi. My main evaluation is based on that.

  • evaluate positions : affect points based on the distance of each pellet to the closest pac positive for my pac and negative for opponent pacs. value = pelletValue / dist
  • score : 10 * (myscore - oppscore)
  • kill : +/-500 for each pac alive
  • best path evaluation : evaluate the best path using precomputed dfs and a decrease at each depth. score += pelletValue * coeff^depth. i do not care of other pacs position for the path but if a position is closer to another pac i can not eat it bring 0

Tips & Tricks

  • Start : start strategy is really important and i have to precompute some moves. I affect super pellets to the closest pac and a pac can have multiple targets if he can reach another before other pacs. i compute also the opponent start move so i can during some time avoid taking into account in my evaluation function super pellet i am sure i can’t reach before the opponent. So my pac will not be in danger trying to reach them and also will not go on paths where pellets are already eaten.
  • Ability : i use speed as much as possible but i verify if my position is safe before using it. I can switch if i am in deadend and my position is not safe.
  • Prevent Hunting : to avoid hunting an opponent which can flee, i will simulate the opponent move if there position is not safe so my pac will attack only if the opponent can not flee.
  • Deadend Hunting : if i know i can hunt a pac in a deadend i do it. For that i have to be able to eat him before he flees or he recovers his ability
  • Pellets potentially eaten : as i try to guess the opponent i know the potentially visited positions so i decrease these pellets value in my evaluation function

Conclusion
Really pleasant contest. I can’t wait to see the leader strategy!

13 Likes
#67

Why do you need separate DFS pass for paths if you already have BFS pass for distances? Can’t you save all-pairs paths info during BFS phase?

#68

DFS gives me all the paths of a given length while BFS gives me only one as i do not visit positions multiple times

2 Likes
#69

The challenge was very … “challenging”. I was hoping to see the code of other people! Is there any way to do so?
May be someone would send me their code in message so that I could compare my code with theirs?

#70

why should use move to a random point
the game will end before this case
am I right?

#71

Hello all,

#800 at the end, I don’t remember exactly, was #60 or so in silver and didn’t reach gold sadly, Python3

This was my first contest, and it was quite interesting, both as a developer and as a person / competitor.

I learnt A LOT of things in the contest, and here is how it went.

Start on May 8th, motivated and all. I quickly get in Bronze, and get all the rules. I follow my very first ideas, lacking actual big problem programming knowledge (I will work on codingame puzzles more to learn !):

  • Naive distance (x and y difference)
  • Define target by best cost (value - distance)

And it worked surprisingly well until the first Sunday, where I fell quite hard.

One big frustration of the contest for me was the lack of information about timeouts : like, my bot timeouts and I don’t even have the full print, and also sometimes not the error that lead to that… It makes debugging quite hard.

I understood I would need better ideas. So I started looking for things I’ve learnt back in school, such as A*… Worked quite fine, but still not enough for silver.

Then, looking on the forum, more ideas, like BFS (note : I’m talking about calculating distances, not simulating the game), registering the state of cells as you pass through them and see them…

In the end, I was defining targets based on real distance, available new informations (i.e. “see-able” cells - “known no pellet” cell), pellet value of course, and dead ends. Then, defining the next move (2 cells or one cell depending on Speed) based on the cost of the move (-1 if it gets you closer to the target, -1 if you eat a pellet) and the obstacles (own pacs moves are considered as obstacles, and opponent position + neighbor cells for opponent are considered as obstacles if he is of a dominant type or can instantly change type). I actually never used SWITCH for the final version of the bot! All in all I’m quite satisfied with that, as I learned A LOT of things, and didn’t feel confident enough to try and implement any simulation.

Also, it was a good learning opportunity as a person. I got discouraged on Thursday 14th as I couldn’t get out of bronze and as all my ideas were reaching the timeout… And hopefully found motivation again to “rethink” my algorithms on the Saturday, reaching silver and almost gold in the process. For the personal lessons, I should remember the following for the next contest :

  • Keep as much information as possible at all moments : memory is not an issue, until it is (but it was not an issue in that contest)
  • Don’t discard ideas because you feel they’ll timeout and you won’t be able to debug them, try and you may have good surprises
  • If ideas time out, try to rethink the algorithm (doing DFS for all single cells is quite a bad idea, yeah, but sometimes you don’t see the bigger picture…)
  • Keep trying new things. You have absolutely nothing to lose if your implementation or idea fails, and that’s the best way to learn.
  • Check for bugs across leagues with new rules (Silver bugged my code in ways I didn’t imagine… as dead pacs were visible, they were at first considered as obstacles…)

All in all, the contest was pleasant, but sometimes really frustrating (not knowing what timed out, or when it timed out is pretty frustrating (in my case at least, trying to print into a while that would timeout would not print anything :(). I will definitely consider participating in the fall challenge and hope I can reach gold this time!

1 Like
#72

Sorry if the answer is obvious, but how do you evaluate the “30 closest” pellets?

#73

Hello everyone,

I tried to be invested in this challenge but I have done a lot of wrong decisions at the beginning and didn’t make it to legend before the end.

I am now 24th in legend in multi thanks to few improvements not finished before the end of the contest.

FIRST LAP

  • Data computed at first lap:
  • Distances from every point to every point (stored in a map)
  • Possible moves of distance 1 and 2 from any position
  • Deadend cells
  • Groups of cells (cells between two intersections or between an intersection and a deadend cell)
  • Associate BIG PELLETS to pac-mans (several versions, never perfect…)

MY PATH
I only compute all paths at a distance of 7, with the possibility to visit a cell twice.

I currently store the path taken by my pac to avoid taking same tiles with other pacs. But I do it only once so first arrived first served… It would be a great improvement to perform it in different orders and find the best situation.

Eating an opponent with simple math:
dist <= diffSpeed && dist<=pac.cooldown
If this is not true, I have another rule if my opponent is in a deadend cell:
distToLastDeadCells - speedTurnsLeft <= pac.cooldown
In other word, if I can reach the end of the deadend before he can cooldown, I can purchase him.

In order to add it in my evaluation function, I add a huge score to reach my opponent position and the positions at a distance of 1 around him.
My evaluation funciton:
SCORE = 1000000*eatingPosition*turn^0.9 + 1000 * pelletPercentage*0.9^turn – 10000*riskBeingEaten*0.9^turn + 10*minDistMyOtherPacs (+ 100*minDistNearestPellet if no pellet taken)

OPPONENT TRACKING

What didn’t worked:
I tried to store the possible paths of my invisible opponents, but it was always ending in timeout even after cutting many branches. I have seen in some feedbacks that some have been able to do it, CONGRATULATIONS!

I finally only stored the possible opponent positions and use it as a coefficient for remaining pellets. Once I saw an opponent, if the maxDist - shortestDistFromLastSeenPosition < 8. I was performing all the possible paths and was removing the surely taken and applying a coefficient on maybe taken one.
I am also doing it when a big pellet have been removed.

PELLETS

I stored a matrix of percentage per tile according to opponent’s moves.

I didn’t see if other players did it too, but I am using groups (the one computed during the first turn).
If all the visible cells of a group are taken, I assume that all the invisible ones are taken too. I keep them just in case they are the only remaining once.

COLLISIONS

Avoid collisions with my own pac (if collision, the one with the smallest id won’t move).

If collision with an opponent, keep trying to reach the position without using my cooldown. If he uses its cooldown, I will be in the desired spot. If he switched, I can now switch too. Otherwise I will speed.

POWER

If in danger (opponent could eat me directly), or in a deadend cells and a dangerous opponent see me, switch type. Otherwise SPEED.

Thanks to one of the feedback, I implemented the fact that if more than 60% of my intersections tiles at a distance <=10 are at an odd distance, I prefer to move first and then SPEED. This leads to have more seen tiles naturally. And knowledge is power :grinning:

IMPROVEMENTS

  • When two or more of my pellets are near, find the best paths by computing their best paths in different orders.
  • Compute opponent position when collision with an unseen opponent.
  • Being close to opponent I could eat? Being far to opponent to could eat me?
  • Voronoi for nearest pellet. I tried once but results were worst. Maybe I have to perform it only at the end game. Or there was a bug in my code…

Thank a lot for this contest, it was interesting even if my first ideas were bad. I still prefer longest contest because I am always having a lack of time.

4 Likes
#74

In my case I calculated the manhattan distance for every pellet and then sorted the list.

I could have also walked the graph keeping track of the depth, but the first method was fast enough.

1 Like
#75

Legend 5th.

Great contest, I had so much fun :slight_smile:

【Algorithm】
Beam Search from each Pac. The depth is 8 turns. (To be exact, I used Chokudai Search, but this is almost the same as beam search)
Doing this search twice. (For example, if we have 5 Pacs, search 10 times.)
First one is to determine the order of Pacs for the main search. This uses 10 milliseconds.
Sort in order from the Pac who can create the game state with the highest evaluation value.
In this search, all teammates and opponents other than himself as a stopped.

Second one is the main search, to determine the action to output. This uses 35 milliseconds.
The action will be decided each Pacs in the priority order decided in the first search.
In this search, all teammates that has lower priority order and all opponents as a stopped. (But opponents are sometimes move to avoid death, details are described in the “Customize Simulation” Section.)

Using the same evaluation function in both searches.

【Evaluation Function】

１．Number of turns taken to eat super pellets
This is the most important evaluation. I have wanted to make the Pacs to eat Super Pellets as fast as they can.

２．Number of pellets eaten
The cells that are out of sight are substituted with the pre-calculated probability of pellets.

３．Number of pellets around each Pacs
Doing bfs and count the number of pellets on each path. Select the best path for each Pac, then evaluate the number of pellets on that path.

４．number of dead or checkmated oppontent Pacs
If the pac is in a dead end and he can’t get out of it or use abilities earlier than my Pac can reach, the opponent Pac is checkmated.
Dead = 10pellet, Checkmated = 9pellet score bonus.

【Predict Opponent Positions and Pellet Probabilities】

Doing bfs from the last spot that an opponent is found and guess his current position using the number of passed turns.
I don’t to consider about turning back on the way. So if he goes to the edge of the map, he is treated as missing.
We can narrow down the opponents’s position to some extent from the information that “the cell with a pellet is not passed by any Pacs” (In order to do this, also keep the opponent’s movement path).
Additionary, by calculating all the positions and paths where the opponents may exist, we can also calculate the probability of existence of pellets in each cell that are out of sight.

Then, when an opponent comes in sight, we can (roughly) calculate the path and determine the pellets eaten by the opponent.

【Customize Simulation】

When the simulation in the Beam Search described in the “Algorithm” section, in order to determine a more realistic Pac kill, I customized the simulation as follows.
１．My Pacs will be treated as dead when it enters the movable range of an opponent Pac who is stronger type to my Pac (I didn’t give a negative evaluation to this, because he is already disadvantaged in that he cannot move afterwards and get more pellets.)
２．When at the same cell as an opponent weaker to my Pac, let the opponent escape to neighbor cell, or use the ability if his AbilityCooldown equals 0. This allows to perform a simulation that kills only opponents who have no escape route (=checkmated).

【Conclusion】

My bot has a strong checkmate routine, eating a lot of opponent Pacs in many games.
Prioritizing attacks over exploration may reflect my personality haha

20 Likes
#77

First of all, I agree with you, the winning rate between people ranked between 60 and 80-100 is fairly random and depends a lot on the map and the bots specificities. But then I disagree on the point where you say that if you lose a lot against bottom ranked bots but a lot against top 60 you should rank in the top 60. This is basically because ppl ranked high have likely made compromise to consistently beat lower ranked bots while you didn’t. So it wouldn’t be fair to rank you better just because you fit your bot against higher ranks and neglected lower ranked ones.

Also how did you compute your winning rate compared to top 40-60 bots when you are ranked 100? Given the high uncertainty of winner/loser depending on the map and the opponent, it feels like your stats are likely biased if you didn’t have many games with those opponents. With which frequency will you end up in the top 60 and how many games did you have against them to be able to provide such data?

2 Likes
#78

Great job! Like you simple and effective algorithm.

#79

Ended up in mid silver. Spent most of my time trying to grind out of bronze due to the fluctuation. It didn’t feel like beating the boss was enough, but eventually I got through.

The grand majority was spent debugging, especially ensuring efficiency of not going only 1 space if you have speed, but also ensuring that we acknowledge that said pellet inbetween is gone.

The three major parts involved are as follows:

Defensive switching:

I had thought of an idea to have a different tactic depending on how many pacs are spawned (2-3 pacs = win by killing them, 4-5 pacs it’s not worth the time so just devour pellets), but just ended up with a simple “oh, there’s a scissors within 5 squares of me, so I should become rock” and that took care of most situations.

A Pellet Map:

Like others mentioned, a map of pellets (since we get that nice grid to work with) can be made based on all the empty spaces, and once we see that pellet update it on the map. If we run over a square or see an enemy pac run over a square, remove that pellet. If we have speed or they have speed, remove all pellets 1 around them after doing calculations. If I had more motivation, I’d have implemented line of sight checking too, since we didn’t just have the knowledge of the visible pellets that weren’t there any more, we had to deduce it, but I didn’t bother with that.

The Pellet Finder

Obviously, this wasn’t the greatest as people had chess-engine-like searches, but I liked what I had done. Last time when I did this sort of thing, the first thing I controlled had priority, but that’s inefficient, especially for this, as pac 0 who was downtown would end up with priority and go for the big pellet while there’s a pac right next to it. The solution was to have a barrel of commands (since the order of what pac was commanded didn’t matter, this was easy to set up and have execute) and add to it when you find the nearest pellet. Pellets that we know exist (also easy to implement by just having the unknown ones start with a value of 0) were given a bit of priority since we know they’re there. Those with speed would try and target something at least 2 squares away, and if they had targetted something 1 square away, they were told to change their target.

Simple but effective. After adding to the barrel of commands what movement they wanted to do (speed and switch were also commands added), ie what pellet they targetted, the next pac was queried the same way. Beforehand, they just ignored pellets that were already targetted, but now they would compare their distance to the pellet to the other pac’s distance to the pellet, and if it’s closer, it would remove the other pac’s command from the command barrel and continue shuffling through pellets finding the closest one before making a command. This would go on for every pac until we went through each once, and then it would loop back through all unaccounted for pacs again and again until everyone had a command, and then just execute the commands.

Overall it was fun, though I personally am not a big fan of pac-man, but it was still lots of fun. I’m pumped and ready for the next challenge on the horizon!

3 Likes
#80

Legend #106:

Wood2 to Wood1: Closest Pellet (prefer star pellets)
Wood1 to Bronze: Do the same with multiple pellets
Bronze to Silver (hardest league): Collision avoidance + SPEED + Defend from opponent
Silver to Gold: Pellet tracking, Team co-operation
Gold to Legend: Path finding, Track hidden opponent for avoiding deaths

I did not add much after reaching legend as anything I added did not give fruitful results. I had a simulation with custom depth. If my player has 1 pac, I’ll go upto 20 depth. If I have 5 pacs, then I’ll go upto 12 depth. (I only use speed on depth 0). I also assume opponent’s intention is to kill me. So usually end up finding a safe path rather than an optimal one. In most of the games I would have killed many opponents (even though I don’t ask my bot to kill) but still lose the game because they took an optimal path and took lot of pellets before their death.

2 Likes
#81

Finished #29. I’ll try to not make this post redundant with the 80 other posts above it :blush:

Small suggestions

Let me first start wtih a couple of small feedback points for CG

  • Starter packs: this was my first contest where there was no started pack, it didn’t really matter for me but I do think that starter packs can be a huge help for new coders as it gives them a template to organize their code. Helps avoid ending up with a big much and let them work more on their ideas, while also to some extent learning about organization!
  • Getting input files: an easy way to reproduce and debug a game seen on CG is (when both bots are deterministic) to just get the input file and use that as an input in their own IDE. Now to get the input, I just add a bunch of prints to error for all inputs, then copy the output and remove the extra information. When I want to reproduce the end of several games, this starts to be pretty annoying. A few easy suggestions (anyone of them would be great) are:
    • Just have an option to download the input file as a text file, that would be awesome!
    • Have an option to download exactly what was printed to the console without any alteration for new turns
    • Have an option to only show what was printed to the console without any alteration for new turns so that it is at least very easy to copy paste that without having random numbers and/or text in the middle for new turns

Now as for my bot itself, I’ll focus on my algo and inferring some of the incomplete information as I thing everything else I could say has already been covered

Pathfinding algo

  • Start by running a DFS for all of my pacs that do not have a move already assigned. Depth was 12 to 15 depending on my number of pacs alive. I did not allow to visit the same cell twice, except when I reached a dead end or a super pellet, in which case I just erase the visited history to make all cells accessible again
  • Keep the one with the highest score and assign it a move based on its best path
  • Propagate the effect of its movements to a copy of my game state. So for example, if it is supposed to go and grab a pellet next turn, completely discount that pellet. If it is supposed to grab one in 10 turns, still discard it but much less
  • Repeat

Picking the pac with the highest score at each step meant I could not find optimal combinations of paths where none of the individual paths were optimal on their own. However, rerunning the DFS for all non-assigned pacs after assigning each pac meant that they still worked pretty well together. The other downside was that I had to run n! DFS where n is the number of pacs, just because the eval changed with each new assignment. I did not find a way to avoid this though (if anyone sees a way, please let me know!)

Regarding abilities, I initially switched if I knew an enemy pac could try and kill me next turn, but I then realized that at the top of the leaderboard no one ever does that. I even saw one guy who always assumed no one would try to kill his pacs if their cooldown was 0, so who actually used the speed boost right next to one of my stronger pacs… Anyway, at that point I removed switch altogether, and since I did not implement any sort of attacking for sure kills or preemptively defending against those, I just never switched.

I also saw a few people mention they only used their speed ability at (odd, odd) cells. I think this is slightly too aggressive and I had another approach: since I have an estimated path for > 10 cells, I just check if I ever step on the same cell during moves 0 and 2, 2 and 4, 4 and 6, 6 and 8 or 8 and 10 and if not, that means I can go ahead and use speed now without wasting one of its uses.

Inferring hidden information

This is what I spent most of my contest on. Unlike others, I don’t find incomplete information games annoying, on the contrary it is quite fun to come with more and more subtle ways to get an extra slither of information out. There is one caveat though: this is fun only if more information does give you more edge. Here unfortunately, after a certain point more information about pellets completely stopped helping. I think this was due to the nature of this game being more random. Thinking about it, I do believe this randomness (and therefore the leaderboard randomness) is due to the impossibility to always avoid “unlucky” encounters across a corner where you just die without being able to avoid it, so any decent bot can easily win a couple games against #1. This was an unfortunate feature of the game, but in my opinion was impossible to have been predicted by the creators so this is not a reproach in any way, just a fact.

Anyway, what made me jump to top 15 was the following relatively easy feature: whenever I see an opponent or a pellet that I know just disappeared (usually super pellets) and could have been eaten by only 1 opponent, I look for all possible paths this opponent pac could have taken since its last knows position, I then remove paths for which I know there currently still is a cell with a pallet on it, and I intersect the remaining paths to get all cells this enemy pac MUST have visited. This very often leaves you with only 1 possible path.

I then decided you could do better, and worked on adding memory of all cells at all time to remove even more paths. This is actually the exact same algorithm MSmits described in details so I won’t repeat what he wrote, but similarly to him this took me a while to finish and yielded no result, which was extremely frustrating. Retrospectively, we both should have acknowledged the randomness sooner, realized that given this getting 90 or 92% of the information would not have changed anything and moved on to try to mitigate the randomness more by better enemy tracking or to coding other features (my bot didn’t even have features such as sure kill detection which would have been helpful both for defense and offense, or super pellet allocation when I just hope the furthest pellet is in my DFS breadth length). While we wasted our time on this feature, we both slowly drifted down in the leaderboard as others worked on more useful things :frowning:

Conclusion

I found this contest very entertaining, and I did learn a lot as well! A big thanks to the whole CG team for organizing it, and I am looking forward to the next one! :slight_smile:

11 Likes
#82

Here is my PM : https://github.com/Saelyos/Spring-Challenge-2020 :slight_smile:

Don’t hesitate to ask for any detail.

28 Likes
#83

I find the starter “files” enough to get started. What else would be included in that pack?

I think the only input of the game is the seed. Everything else is generated by the game engine.

#84

For me a good way to debug was to print all stdin in my stderr. Then with the great tutorial https://www.codingame.com/playgrounds/53705/contest-tools-and-workflow/introduction from @eulerscheZahl you can easily get your stderr and replay games and debug them. Personally it was my first contest in C++ and I made great use of that to understand where my pointers/local variables went wrong in the global algorithm. In c++ I would have something like that:
bool isIde = false;
if (isIde) {
string myID = “1114834”;
ifstream* inputFile = new ifstream(“resources/467005582-” + myID + “-stderr.txt”);
cin.rdbuf(inputFile->rdbuf());
}

3 Likes