Code of Kutulu - Feedback & Strategies

[MSmits]

I ended 4th in legend, just barely (less than 0,01) ahead of Illedan (still feel a little bit guilty). This was a very fun contest, but also very stressful. Sometimes you had no idea whether a newly submitted bot was better or worse than the one before. Ranks jumped around a lot. Here’s how I did it:

Precalculation

I precalculate a lot, namely:

1. Pathing from every square to every other square, this is used for wanderer simulation, but also to compute other distances.I used BFS for this.
2. Line-of-sight: to know for every square, whether it is in sight of another square. This is used for slasher logic.
3. Neighbours: To have a list of walkable neighbours for every square on the map.
4. Branch value: To know the total number of possible move combinations from every square. So for example, square [4,3] could have as a possible combination: left-up-right or down-left-up-up-right. I do this for 7 depth levels. This is used to calculate the maximum depth I am able to sim to from that particular square. Long hallways are more easily searched in depth than big floor-like areas.
5. I also have all maps in memory as static string arrays to be able to recognize the map I am playing on.

Simulation

I started by copying the entire referee and translating it to C#. I threw out all the visuals, multiplayer code and the pathfinding. I tried to use what was left but found it too hard. I kept the code as a reference and started anew, writing my simulation bit by bit and using the translated code. In the end I had a good sim that only disregarded light. I even simmed spawns and such (not sure if it is worth it).

The search

Once I had a good simulation, I simulated 1 turn, with the enemy explorers as wait bots. I tried all possibilities and picked the one that gave me the most sanity. This got me around rank 100. Then I switched to using random actions for enemy explorers and that got me to around rank 50. I had a really hard time coming up with a way to simulate further than one turn. It was around this time I finally had a good idea about how to search in more depth and it is a weird one! I have no idea if this method already exists, so I will just call it SmitsiMax . Max, because it maximizes all explorers’ sanity and has no other evaluation than that.

It works like this:

All players have a current position. They each get their own tree to choose moves from. They choose a path in the tree and after depth x (variable, will explain later), a simulation will be run. The result of the simulation (sanity change) will be backpropagated along the tree and all passed nodes will have this score. This is done for each explorer separately. So each explorer has their own tree and their own scores (see pic). The only thing they have in common is the simulation

The explorers pick the children-nodes randomly the first 10 times they get to a parent-node. After that, the UCB1 formula is used to pick the best branches. The UCB1 formula has a value (average sanity change) and an exploration part (based on number of visits to that node, with an exploration parameter). The simulations will (hopefully) converge on good moves for every explorer if you have enough sims. To do this, you have to know how “deep” you can go. If you go too deep, the moves will not converge and you get nonsensical decisions. Moves are picked for the best average sanity loss over the course of the turns covered by the depth used. Every explorer is treated the same in this search and only movement is considered. The reason it works so well, is that the resulting moves are both good (minimized sanity loss) and realistic (enemies minimize sanity loss as well). Because there are few parameters, it is easy to use, but also not very flexible. I could not tweak some parameter to avoid my explorer splitting from the group.

Variable depth

Sims go faster when there are few minions around. I cull my sim, throwing away far away explorers and wanderers to keep the sim lean. Even so, there may be too many minions and explorers nearby to have a lot of depth. So I use my branch cache for the square I am on (is it a big floor or 1 square wide hallway) and the amount of entities, to choose the depth. The depth usually varies from 3 (very crowded), to 6, me alone in a hallway.

Plan

I plan when I am lower than 210 or so health and have at least another explorer around me, or when there are only 2 explorers left total. This is one of the few heuristics I have. I only do this when waiting is a good option.

Light

I check usefulness of light with a formula which uses as input: the list of wanderers, and the players closest to these wanderers. I calculate whether the light will switch the targets of the wanderers away from me to the other player and if it does, i use it. It is not perfect and could be better but it works. I only do this when waiting is a good option.

Yell

My yell code is pretty good I think. I use 4-8 sims per turn to see if yell is a good idea. A yell basically is like this:

Turn 1: I yell and stand still
Turn 2: I move one square to the side.

Since I don’t know which way is the correct way to go to to avoid the minions, i try all 4 sides that are walkable. So I sim 2 turns for each direction. If any one of those sides results in 0 damage for me and at least 25 damage per stunned explorer, it is a good yell. So that means 40 damage for 1 player, or 80 damage for 3 players (2x 40dmg + 1x unaffected). As long as the average is over 25, I yell. I do my yell code before I do anything else. So if I choose to yell, I don’t do any other sims that turn.

Map recognition and hard-coding

I tried my best to get some hard-coding in, but in the end I only really used it for those maps where you start far away from eachother. My bot had no overarching map strategy and only looked at the short-term situation (3-6 depth). Therefore it had trouble getting past a single wanderer to the other explorers. This was worst in Typhoon, so I just hardcoded a run to the other side, straight through a wanderer. This boosted my winrate for that map.

Thanks

to the creators for making this game. It was fun, challenging and (too) exciting.

[PatrickMcGinnisII]

I’ve been puttering around with these contests for over a year now. I started late and only put in around 10 hours, but I usually can get to Silver. I only managed bronze and ended up in the middle of the final leaderboard. People that get start early usually can get promoted easier. I see alot of posts that involve simple strategies I employed that got them to Gold. The 4 player contests always seem to force alot of submits and slow things down, I’m guessing due to the wild swings in ratings you could get higher results with same code and then wait to get bumped if lucky. Overall I didn’t enjoy the rules, when slashers were added it completely threw off my approach.
My approach was basically a bunch of different maps. I used a simple linear distance calculator on a map with id#s on it. It stopped each path when it found an entity whether it was explorer,wanderer, etc. So alot of entities ended up inaccessible (infinite distance). I should have revamped it, never did tho. I first checked if the closest bad guy was 1 distance, if it was I ran in the best direction possible done with a weighted map. If not, if I was sitting with an explorer, I planned or yelled depending if they were available. If I wasn’t with a player i sought the closest one. i also used light if able when alone and turn%5, but I think the varied summon times made this ineffectual. i attempted to weight the map with slasher components, but it didn’t help. I tried a few more tweaks, but without a sim and a pathfinder I knew I wouldn’t get out of bronze. I kept lists of all kinds of things, like minions who were targeting me and shelters. I never got to use shelters in bronze because they didn’t become available in early game, and most bronze games ended too early. My end result was an embarrassment for me as a coder.

[pjakubow]

Thank you for this comment - it was very enlightening I also tried to achieved minmax algorithm, but taking into account all players. Needless to say, the combination of all other players movements was too much and I cannot get even to depth 1 and therefore going higher than silver league.

[RoboStac]

Unfortunately I wasn’t around for the end (or beginning due to Thales) of the contest and only had a couple of days to develop my bot meaning I didn’t have a chance to try different strategies and ended up 22nd overall. I’m pretty happy with this as I was worried about reaching legend at the time of my final submit on Friday morning.

I used alpha-beta minimax algorithm against everyone within 5 distance of me (actual path-finder based difference, not manhattan), which iteratively deepened from 3 turns per player. The eval was always based on my score, so all enemies were considered as working together against me. My minimax only considered movement for everything except my first turn. . I precalculated the distance / next square assuming no light was present using BFS. I did originally try to use a beam search, but didn’t get this working well enough as enemy movement was so important.

With multiple players close by this wasn’t great if I included enemy sanity as a negative as it would always assume the other enemies went away from me as a group and I’d play catchup one square behind. Because of this I didn’t include enemy sanity at all in my evaluation meaning my usage of yell wasn’t ideal (I’d quite often yell to keep 3 people close to me). I didn’t include light at all in my solution and would use plan instead of wait if two enemies were within range and I had less than 200 sanity or at any point where I had less than 50.

My evaluation was:

• My sanity
• Distance to closest player
• Average Distance to all alive players.
• slight negative scores for using plan / yell so they would only get used when it helped with the above.

Overall I thought the contest was fun, though I think there might have been too many variables involved. Having to have strategies that worked across so many different maps with the variable start of game parameters for the sanity loss / spawn was slightly too much in my opinion especially when enemy actions affected the player so heavily. Having 1v1v1v1 on top of that meant it was very hard to test changes. I liked the input parameters not hiding anything important (with a single exception). The one exception was stalker last seen position which I feel should either not have been there, or been in the input.

I did like how easy it was to test the simulation - as all the player movement was resolved before anything else it meant I could take the player positions from the next turn and then run my simulation to ensure the minions moved correctly (if light was present or a tie was found for minimum distance I’d set a flag to not check this turn as I didn’t want to deal with light and couldn’t simulate server randomness).

[R4N4R4M4]

Hi Everybody

Thanks to the creators of this great survival game. It was a lot of fun and I finished #40 Legend with full heuristics.

So bad, on friday, my Internet connexion was broken.
I had to code my first submit on my phone, and it was a great experience

With this simplest logic, I was able to acceed to Wood3 :

• Is there a wanderer next to me ?
• If yes then find a safe cell
• If not then find a cell to get closer to the nearest explorer

On saturday morning, Internet worked again. So I could attack the hard work.
First thing of all : Read the tchat, because on a mobile phone, the tchat is not available. Second thing : analyse a lot of matches

But to pass the Wood3 Boss, it was not a simple thing. Some said that to acceed to Bronze, you’ll have to code your real final engine. I had no motivation to do that, so here is how I got to Bronze on Sunday :

• Have a graph of all walkable cells
• Precalculate all distances with BFS
• Evaluate the best cell to go :
• Malus for distance ^ 1.5 from the nearest explorer
• some magic number bonus for distances 0, 1 and 2 from the nearest explorer
• Bonus for distance ^ 0.4 from each wanderer
• Bonus for distance ^ 0.4 from each slasher
• Great penalty for all fatal cells : where wanderers can go on the next turn, and cells on the line of sight of slashers when they are next to RUSH
• Some simple logic conditions to YELL
• PLAN when there is at least one other explorer next to me and some other logic conditions
• LIGHT where wanderers are far enough and some other explorer too
• A great idea was to penalize the cul-de-sac on the map (predetecting them)

With some tuning on my magic numbers, my code was #2 Bronze on Sunday night.

So I didn’t need big ameliorations to pass the next leagues :

Silver : #12 when league opened
Gold : #9 or #10 when league opened

Legend :
On Friday, when the legend league opened, I was #16, and the Gold Boss was #11.
So my code needed some improvements. During the previous leagues, I had the time to code some other heuristics, like Voronoi and Floodfill. So passing Legend was relatively simple :

• Use Voronoi to detect all cells which are accessible without danger
• My Voronoi includes minions’ distance + Spawn temporisation
• Calculate the surface of those cells on each direction
• Add bonus surface ^ 0.5 to my cells evaluation

Not staying bottom Legend :
Here began the real problems. I think my heuristics was not able to compete against IA search engines. However, I had not coded the Shelter features yet. So why not, and other ideas :

• Add a malus for distance ^ 1 to the next shelter with energy > 1
• Avoid other explorer YELL with a great penalty on some logic conditions

On last days, my pushes were between top20 and bottom legend. I played with all my parameters. A lot of matches were lost due to a bad understanding of the slashers state. Sometimes my explorer avoid the rush a turn too early. Sometimes he fully ignored the slashers and staid on them. It was very difficult to reproduce the cases in IDE because of the non deterministic engine.

Finally, I pushed the code I thought the best, and it finished #40.

What a challenge ! Thanks to All_the_Creators_of_kutulu JohnnyYuge, nmahoude, and eulerscheZahl. That was great !

[Illedan]

Great contest, complex, fun and frustrating!

Ended at 5th, barely behind @MSmits, both in rank and C#!

PM: https://github.com/Illedan/Post-Mortem/blob/master/Kutulu.md
Just add an issue if anything is wrong or hard to understand.

Few comments:

• Little too complex target logic ( would be better without targetid state )
• Not suitable ranking system.

Anyway, good job @ creators in making a great contest!

[miklla]

Hello there from #6. I was very intrigued when understood that this is semicooperative game. Overall I got good impression of the game and ranked highly is ever (my best rank before was #8).

My strategy was inspired by Agade’s postmortem in CotC but with a twist. I assume all players play against me. My intention is to find 2-3 what I call “scenarios”: how other players cooperate against me and my answer to it (full list of my and enemy’s moves up to depth D, starting depth D = 1, then incrementing up to 5).

For simplification let assume that we are player 3. First scenario I initialize as WAIT for all players. Then for players 0, 1, 2 I find the worst move (to minimize estimation function for me) each time assuming that other players move according to scenario and then update scenario with this move. After this for player 3 (me) I find the best move assuming other players move according to scenario and hence first scenario on depth D=1 is ready. Then I initialize second scenario by first, find the worst moves for players 0, 1, 2, each time update scenario with them. And here comes the twist, to find my best answer to 2nd scenario I don’t use evaluation for me but instead use minimum of evaluation functions among all scenarios of the same depth! I think it adds diversity to other player’s moves and works pretty well. In final version of my program I generate 2 scenarios for each depth from 1 to 5.

As many other participans I found out that too big depth is too pessimistic for reality so I cut off search at depth 5. Technically my engine gives me 25k full simulations per move when not more than 1 light on the map and around 5k simulations with at least 2 lights (by the way it is possible to reach significantly higher number of simulations but not during the contest). Most of the time I had too many simulations for my logic so planned at the start beam search was never needed. In the middle of contest I came up with an idea to keep track of psychological portrait of my opponents or at least statistics of prefered moves, but unfortunately I never had time to test it since I had only 4 free from job days during the whole contest.

It was fun to tweak coefficients of estimation function to decide when I should run from a wanderer and when I have to come through it to meet with other players. It seems I didn’t actually succeed in it and sorry for bad english!

[yanamal]

I’m #62!

I thought the game concept was really interesting! Lots of trade-offs to consider.

This was my first contest, so I don’t have much of a comparison point. But it was fun! Then frustrating. Then fun again, then frustrating again. I feel like I’ve documented my frustration in enough detail in the bugs thread already, but basically my two general gripes were the difficult-to-reason-about rules and the hard-to-interpret (and volatile) ranking stuff that other people have mentioned. I still have a suspicion that my second-to-last submission was better than the last-minute tweaks I applied. But I am just not sure.

My habit/instinct when writing AI or behaviors is to minimize assumptions about what is a good strategy, or at least defer them until as late in the code as possible (and first, collect/process information that’s objectively important. For some value of “objectively”). And also to avoid, as much as possible, magic numbers and numeric formulas unless there’s a really good underlying reason for why those numbers should be added and multiplied in that way.

This is all to explain that my bot is quite weird compared to most people’s, I think. And I ended up writing a pretty long doc to try and explain what the heck I was trying to do. Here it is: https://github.com/yanamal/CodinGame-Write-ups/blob/master/Code-of-Kutulu/Post-Mortem.md
(I’m happy to elaborate/clarify/answer questions)

Additional misc. thoughts and lessons learned:

• Don’t submit large poorly-tested changes and then go to sleep right before Legend opens up. I was in the 20s before that submit. When I woke up it took me a full day to get back up to speed!

• I need a better set-up than typing code directly into the CodinGame editor, then pasting it into a file for version control with diffs. More generally, I have soo many ideas now about how to set up tooling and workflow! And I’m also much more aware now of existing tools others have made (e.g. found out about cgstats on Saturday)

• I might want to practice doing CodinGame challenges in a more strongly-typed language than Python, with easy lightweight structs, so I don’t have to remember what the hell my mess of dictionaries of arrays was supposed to represent and why there is one more value in my tuple now. Right now I’m still definitely faster in Python, though.

• (something I just picked up from this thread) In the few cases where I am directly trying to predict the game’s behavior, it’s a good idea to check those predictions against the actual game state and flag (in debug) when I got it wrong, so I can fix the algorithm.

• In analogy (or contrast?) to “I don’t have to outrun the lion, I just have to outrun my friend” - “you don’t have to write a robust algorithm, you just have to write one that’s compatible with others”

[anon4743054]

In analogy (or contrast?) to “I don’t have to outrun the lion, I just have to outrun my friend” - “you don’t have to write a robust algorithm, you just have to write one that’s compatible with others”

This perfectly describes the contest.

[code_of_the_dead]

thanks for your feedback ! i struggled to fit the problem with a montecarlo tree search solver without success. Taking the ucb1 evaluation to reinforce a tree path was smart !!

[RockyMullet]

Hi ! I finished 79th aka 8th in gold. I tough the coop concept in an actually PvP situation was pretty cool, hard to do it in other than 1v1v1v1, I liked the conflict between should I group or should I leave those guys to die.

I didnt have much time to code in both weekend so I had to code in small bursts during the week, so I went for something easy to do small iterations on. I mostly reused a mix of what I’ve done for HS and what I’ve done for CotC. I made a “heat/danger” map, the source being the minions, so it was pretty easy to just run in the direction of the lowest danger, the danger was stacking from a minion to another, so it was easy to make the difference between danger from a single minion and a group minions.

I made a A* in The Great Escape that is meant to be easy to reuse, pretty simple to change the cost, the heuristic and the path blocking conditions, so I made… 5 versions of it for Kutulu, the main one being an A* where depth is used as time in the futur, so I can assume that at a certain time I would take damage going in that direction, it made my bot good to run away from “pincer” attacks from wanderers.

I also used a simpler A* for the wanderers to know what was the distance and the cost from their target. Keeping the distance between the closest wanderer of each explorer, I used that info to yell at others, knowing I was safe and they were not. But I mainly used that info to make a second pathfind for every wanderer targetting me, faking I was using a light, to know if it would make them change target, if they did and I was out of danger, thats when I would use my lights.

My plan code was pretty naive… it was pretty much “plan when there is at least another guy or your very low and that your are not almost full hp and would waste healing”, but it made the difference in maps where explorers all start at the center, surounded by spawners.

The 2 main down side of my bot was grouping and the Slashers. Since my bot was decent at running away, I would stop grouping when the sanityLossLonely == sanityLossGroup or when only one other explorer remains, cause the important is not how much sanity you lose, but how much you lose relatively to others, so when only 2 remains, grouped or not, you will lose as much. But my bot will only group when safe or using the path toward the closest explorer as a tie breaker, meaning if I had a wanderer really close I woudl run forever and hope the others will group with me, I would lose a lot of games because of the others grouping as 3 with me alone never grouping, always running.

And the slashers, the heat map wasn’t good at all for them. The heat map was pretty much used as “there is danger at that time” but it wasn’t true for slashers, slashers were more “there could be danger”, so I would have bugs like a slasher one side and a wanderer on the other side and my bot would stop, thinking it was trapped while it could have ran through the slasher. The best I did to make the slashers kind of not that bad was to make long lines of “danger” on my map and had to check if I was on a slasher path of destruction and make my bot look for a closer safe spot.

In the end I’m pretty happy with what I’ve done with a simple solution like that. This game was pretty fun, it was cool to have a game where you don’t necessarily fight each other, but run from common enemies. Thanks to the creators, specially Johnny who was really active on the chat to answer people’s questions.

[GoofyGas]

When will we get codinpoints for this contest?

[_CG_SaiksyApo]

Tomorrow

[blasterpoard]

During the first few days, I experimented with different heuristics and I watched how they performed against the top bots at the time. One in particular seemed promising - start a BFS from my explorer and from all the wanderers to find all the squares I could safely reach before the wanderers could. I’d compare how many squares I could safely reach after every possible turn and choose the best one (after the contest I learned that I did a Voronoi against the minions). In theory, this should help against getting ‘boxed in’ by the wanderers. However, this approach has a lot of flaws, some apparent, some less so:

• Grouping up with the other explorers
• Avoiding slashers
• What to do if there are no safe squares at all
• Multiple wanderers on 1 square
• …

Grouping up with the others

For the several first moves (wandererSpawnTime + (one third of the distance to nearest spawn) moves at first, then less), I hardcoded my bot to output MOVE x y, where (x,y) is the position of the nearest wanderer. I also added more weight to the squares near the other explorers(a square with an explorer who has 2 plans was worth about 5-6 squares) to make separating from the other explorers less probable (at first, I did the same for shelters, but their positions on many maps - e.g. Typhoon, Shelter in Peril - made me reconsider that). Also, I added 1/sqrt(x) of distances to all the explorers (of course, multiplied by an ever-changing lengthy formula dependent on their sanity, number of plans, periodic sanity loss… ) to my evaluation of possible moves. At this point, I realized that I will probably need to calculate distances between squares quickly, so I decided to calculate distances between all pairs of squares during the first turn.

Avoiding slashers

Now that we’re pre-calculating stuff before the first turn… 1000ms is a lot, so let’s also find all pairs of squares that are in line of sight, and if they are, how many turns do I need to get out of line of sight. Now I could tell in how much danger I was from the slashers, so this became the next part of my evaluation of moves.
Also… why not just add slashers into my Voronoi? I can easily tell in how many turns they can rush, so let’s just pretend that there is a wanderer that can reach every square in their LoS in this number of turns.

What to do if there are no safe squares

In every game I would eventually get to this situation, and Voronoi was useless here. I tried comparing the number of wanderers/slashers that could reach every cell next to my explorer, but the results were unsatisfactory. I needed a simulation, because it would also solve the problem of multiple wanderers in one cell. So I wrote one. I used it in 2 different ways:

• Simulate what would happen after every possible combination of moves from all the explorers and add the lowest sanity I could have after each move to its evaluation. The purpose of this was to avoid taking extra damage if it could be avoided.
• Simulate what could happen after every combination of my next 5 moves, while simulating the other explorers with simple heuristics(run away from wanderers and slashers, run to each other), add the highest sanity I could have after each first move to its evaluation. This should help with with situations where looking only 1 move ahead is not enough. This is also the only thing that makes my bot move to shelters.

Later on, the evaluation changed from my sanity to (4*my sanity) - (sum of sanities), because I saw some other bots triggering slashers who would then spook the other explorers and I found it cool. After some fiddling with the weights, I achieved what I wanted: If there was no danger, my bot was controlled by heuristics, and in immediate danger, simulation took over.

Abilities

I used LIGHT and PLAN when evaluation of WAIT was the best one or close enough and some additional conditions were met - LIGHT required at least one other explorer to be at least 6 squares away from me, PLAN required a certain amount of explorers (which decreased with my sanity) to be close to me. My simulation ignored LIGHT.
YELL was a bit more tricky - I simulated what would happen after yell, and then decided if it was a waste or not by comparing it to simulation without yell. Later on I improved upon this, but the idea stayed the same.

More problems with Voronoi

My heuristics had one funny side effect: My bot didn’t run away from wanderers, it ran TO the wanderers, because this technically increased the number of safe squares (the squares that were safe before stayed safe, and some of the squares between the explorer and the wanderer became safe). This became a big problem, because it meant that when a group of explorers was running away from a group of wanderers, my bot ran the other way or waited until they came to the square next to it, and only then started running. What’s even worse, in the case of 4 explorers in 1 cell and several wanderers in a cell 2 squares away from it (this position and others similar to it are quite common), my algorithm would give a huge weight the square the explorers were standing on and it would try to keep it safe - by waiting on it, which usually resulted in getting yelled at 3 times in one turn and losing ~100 sanity. After I removed this problem (by not giving more weight to the squares near the other explorers if these explorers were next to me and were closer to the closest wanderer than me(or as close as me) and this distance was short enough, and by subtracting the number of wanderers that are targetting me from the evaluation), my winrate went from 34% to 42%.

I think that the idea to create a bot that uses heuristics to stay in safety and switches to simulation when it’s no longer possible is what made me reach rank 1 despite the fact that there were other contestants with better heuristics or better simulation. I liked that there were so many ways to approach this game (and it looks like the best option is to somehow combine them), but the unstable ranking made testing a bit difficult - after reaching the top ranks, I rarely submitted my code because I knew that I wouldn’t get any relevant information from the rank it would reach, and instead I looked at games against different opponents in the IDE and made changes when I saw my bot make a move I didn’t like.

[yanamal]

My heuristics had one funny side effect: My bot didn’t run away from wanderers, it ran TO the wanderers, because this technically increased the number of safe squares (the squares that were safe before stayed safe, and some of the squares between the explorer and the wanderer became safe)

If I understand this problem correctly, you might have been able to address it by accounting for wanderer movement (especially toward you) when calculating number of safe squares after your move: otherwise, you are sort of implicitly assuming that they’ll stand still on that same turn as you move toward them, and so you’ll “gain some ground” over them.

So in a linearized example, suppose you were 7 squares away from a wanderer:

W 1 2 3 4|3 2 1 Y

(W=wanderer, Y=you, | = where I reckon your Voronoi would put the border of being ‘safe’)
If you consider moving toward the wanderer as he stands still, this would indeed make it seem safer:

W 1 2 3|3 2 1 Y .

But if you assume the wanderer also moves toward you, the “safety border” would stay in the same place:

. W 1 2 3|2 1 Y .

…Not that you particularly needed it.

Very cool approach! and not just because mine was somewhat similar and so I get a little more insight into what was or was not actually important to focus on

[blasterpoard]

Hi!
Sorry for an unclear explanation, but I actually accounted for the wanderer movement; you are right that when I’m moving towards the wanderer the border stays where it was; however if I’m moving away from the wanderer, the border moves towards me. and the safe area becomes smaller. If the original position was
W 1 2 3 4|4 3 2 1 M .
then there is a difference between safe areas in
. W 1 2 3|3 2 1 M . .
and
. W 1 2 3 4|4 3 2 1 M

[yanamal]

ohhh yeah hmm that’s a harder problem.

[Agade]

I finished 2nd and here is my postmortem.

I quite liked a lot of the design aspects of this game, as mentioned by others. 1vN is a change, especially with enforced interaction and even cooperation. It felt quite fresh although it turned out to be quite simulation heavy (e.g: Smits’ postmortem using only sanity as eval and finishing 4th) which I’m just personally growing weary of.
I was kind of annoyed by the number of bugs in the game. Slashers were described, even with a graphic (fixed later), totally differently from the implementation which is misleading and time wasting to say the least. It also felt like quite a waste of time to go and understand referee bugs to reproduce them (e.g: navigating 15 java files with Magus trying to understand why PLAN exists on turn 5 yet does not heal) (same deal with LIGHT).
Congrats to CC team I wouldn’t have played it this much if I hadn’t liked it.

[Kodle]

Hello fellow codingamers! Ended up #25 with a simulation approach in Python3

First off, congratulations to the community team JohnnyYuge, Nmahoude, and EulerscheZahl (Toad_of_Kutulu haha) for another great contest I really enjoyed! Stunning performance by Blasterpoard in his first contest as well, holding pole position for most of the contest!

##Kutulu

I enjoy games with discrete movement (grids) and no collisions!!! (phew) Meanmax/FantasticBits were a headache unfortunately. CodeRoyale had a much better handling of collisions (resolving up to a finite 5 sets of collisions via discrete movements in 0.2 frames). This left me much more time to explore decision strategies rather than coding boilerplate code for physics simulations…

Seems like EulerscheZahl ranked right above me at #24 running 1ms on c#. A 50x speed boost from Python3->C# sounds about right (likely another magnitude higher). Gonna to try porting my bot over into C++ and add enemy simulation to get higher performance when multi comes out. Not too familiar with the language so didn’t attempt it in contest time-frame.

Movement using UP, RIGHT, DOWN, LEFT should be explicitly stated in the rules. I only found this one out by watching replays. Rules should be kept up-to-date with any changes/errors (Slasher state transition from SPAWNING->RUSHING immediately caused quite some confusion but wasn’t updated in the rules).

##My Strategy

###Scoring Moves
As many of you have pointed out, the initial Wood1 boss was really strong… In past contests, rushing a simple heuristic would get me past into Bronze but in this contest I had to compute Wanderers’ next move and search to depth 1 movement before getting promoted. In the end, this code got me into Silver as well (this bot was around top50 when Silver opened).

I assumed all wanderers move towards me (pessimistic) and scored adjacent cells, picking the highest scoring to travel in. If I can afford to WAIT, use some delicious spaghetti to decide which skill to use.

While my heuristic bot was climbing it’s way into Silver, I spent the time implementing a simulation to process current state into the next. The finite state automata of Wanderer/Slashers were pretty easy to understand and I was able to get a sim working with sufficient accuracy (wanderer spawns as well) by Tuesday.

Unlike past contests where I had to really dig into the referee code, the rules were clear enough and simple enough to implement without looking through the referee. Some of the things like path priority cycling through URDL was not stated in the rules and I only knew about that looking at the chat haha (thx!) and Magus noticing the 4/2 bugged duration of PLAN/LIGHT instead of the stated 5/3 duration.

Overall I found the simulation to be much easier to implement than in recent contests.

###Optimizations

Python3 is obviously slow, so to prevent myself from using too much time calculating the paths of wanderer/slashers, I instead ran a BFS from each valid cell to exhaustion, recording which cell it propagated from, then flipped that direction and stored it in a huge dictionary. Something I picked up doing Battlecode

Screen-cap from an old Battlecode video

So here you can see in order to path to the cell circled in Purple, all we have to do is query the direction recorded in the cell we are on and execute that move! And this works from anywhere else on the map towards this targeted cell.

Unfortunately, even with 1000ms, python3 can’t compute this exhaustive BFS 4x* in each of the priority directions (for me to then cycle through as the rounds progress) so I only stored and used the URDL ordered one, some inaccuracies but works sufficiently well (was running into the occasional wrongly simulated wanderer but this was relatively rare).

Tried doing precomp offline, identifying maps using their string and copying a hardcoded dictionary over but with that many maps and essentially storing 4*(numCells^2) values per map, I ended up with somewhere around 1m characters…

Another optimization was to precompute all valid adjacent directions on each cell rather than cycling through URDL and checking for validity every time we want to propagate.

I still computed Slasher LoS cells every turn tho, should’ve precomputed as well! (realized this after reading MSmits PM)

###A*Star (or BFS with pq and heuristics)

I was inspired by the AStar search after searching around and finding this nifty tutorial on maze pathing. It seemed to me that we have a pretty straightforward fit for this game into AStar pathing. Instead of a distance heuristic, we optimize for length of survival and end sanity score.

t_bfs = time.time()
pq = queue.PriorityQueue()
while (not pq.empty() and time.time()-t_bfs < time_left):
    priority_score, move, state, path = pq.get()
    new_state = procState(move, state)
    # Evaluate state
    # potentialScore() -> gives a heuristic score to board position to tie-break sanity
    new_score = new_state.sanity + potentialScore(new_state)
    # Propagate
    for adj in adj_map[new_state.position]:
        # min-heap so we inverse our score
        pq.put((-new_score, adj, new_state, path[:]+[adj]))

And that’s the gist of my A*Star search algo used to path through possible moves. The sanity loss per turn provided a nice dropoff in priority_score so that I’ll start to explore previously ‘bad’ paths after going a few rounds being isolated or when I get Spooked some time into the future. This isn’t ideal but it works decently, allowing me to find a path which will allow me to have the highest sanity longest.

I have YELL and PLAN simulation but no LIGHT simulation other than a heuristic to use it if I can impact wanderer’s targeting and WAIT was the best option. YELL/PLAN was seeded into the pq at the start with some spaghetti and allowed to play out and evaluated alongside initial moves.

Whilst exploring these paths, I’ll record the highest-scoring deepest path thus far for each available initial moves (a comparison of len(path) then priority_score). Once time ran out, I’ll look through the stored moves and select the one with the highest score.

Things that worked:

• Changing my scoring from end_state.sanity into an accumulative scoring of state.sanity scaled by 1/x (x: depth) + end_state.sanity (cuz it’s end sanity that matters - but this prioritized better immediate rewards which mitigated inaccurate predictions)

• Adding a higher weighing to nearest explorer (makes me beeline towards them on large separated maps)

• Penalize running into a dead-end heavily (avoid dodging into a corner and inevitably going insane)

Improvements in the other direction:

• Taking into account possible Enemy YELLS (made my bot pro-actively suicide into wanderers rather than be stunned for an extra turn)

• Simulating usage of my own Skills past the initial turn (additional branching factor notwithstanding, unsure other explorers will be in a position for me to effectively use PLAN/YELL --> heavily reliant on an unreliable enemy prediction)

I implemented this searching beyond depth 1 algo sometime around Wednesday and shot up to top20 where I stayed around ~#12 for most of the contest. This surprised the heck out of me… I mean Python3! Search?! I was getting on average 150-200 executions of procState() before running out of time. Debugging the paths explored, I could see that I explore up to 3/4 move depth when I don’t get Spooked and sometimes reaching 9 move depth when many paths are pruned (sent to the back of pq) due to me walking into a wanderer or slasher rush. This is by no means an exhaustive exploration, merely expanding the highest-scoring path thus far, so I still miss out on some more optimal path due to time running out.

Wait, what about other Explorers? Yea, I couldn’t afford to run a simulation for them as well, so I assumed others run my Silver Heuristics code and used that to simulated enemies instead This led to my performance changing quite a lot during the last weekend when everyone else in the top fixed their simulation or used a better heuristic and my bot couldn’t predict accurately where other explorers would go.

Still, this approach resulted in many nice strategies my bot will use to prolong it’s survival, for instance, baiting a slasher into STALKING then turning down an alley in the last second to transition it into STUNNED so I have 6 more turns of relative safety. Or baiting other explorers into following me when a slasher targets me then turning out of LoS in the last moment and landing the slasher on them instead. Pretty cool watching it ‘discover’ such paths on its own without me coding explicit heuristics for such behavior

Slashers were I feel, a fresher kind of minion than the classic baddie chasing you around.

##Contest Analysis

I wasn’t around for Hypersonic (and for most of MeanMax) so this was my first contest other than 1v1, and boy was it fun Loved the competitive co-operation aspect of the game but yes, this introduced much randomness to both games and ladder scoring. Many games are lost by a wrong turn (away from everyone else) at a junction and this was pretty frustrating to deal with… The increased number of players also meant an increase in time taken for games to be played and towards the end it was taking ~1hr for 50% games on submits, meaning I couldn’t test my code as much as I liked to.

Once again thanks to CodinGame for hosting another great contest and our Community Creators for taking their time to craft this wonderful game! Loved the subtle graphics too (color changes, idle animations!).

[dolmen1234]

Congratulations to the creators, that was a great contest.

About the game :

• I liked in particular the semi-cooperative twist. Sticking with friends, not knowing when one will betray the others was stressful but refrehing …
• The game mechanics were coherent with the Cthulhu theme
• It was a welcome change from the last geometry heavy contests.
• I think some features added unnecessary complexity : plan, light, minion’s rotating path, variable sanity loss, slasher’s behaviour
• The matches were guite random, you often lost by just going left when your buddies turned right
• Despite that, the rankings didn’t feel as random to me as others said, because I usually ended around the same rank.
• The submissions were way too long. Perhaps the matches could have been shortened, with less initial sanity, or max turn < 200

I created a genetic algorithm, which seemed like a good idea for this semi-cooperative game. I simulated everything except the lights.
I used it at depth 4 for each opponent, and then at depth 6 for my explorer.
My evaluation function was similar to what has already been said. I also calculated the number of exits for each cell’s area, trying to avoid being trapped in corridors.
Every time my simulation returned a WAIT, I considered if it was useful to put a LIGHT. I also forced a LIGHT when the first wanderers spawn, hoping to avoid
the initial minion rush.