The topic where you can tell how you liked the challenge and how you solved it.
As the challenge game will be released soon as a classic game on the platform, please don’t share your code publicly.
4 Likes
Rank: #88 (30th in gold)
Approach: MCTS, one per drone, only at strategy level (objectives: which fish to scan or push, when to report)
Tracking: Bitboard (40x40)
Moving: Simple search, closest point to objective without collision
Game: Didn’t appeal to me, too much luck/random, nightmare submits
8 Likes
Rank: #102 (44 in Gold)
Bot: Implements basic movement with collision avoidance.
Strategy: keep changing hardcoded values of reporting timing. Leveraging (RPS) and a lucky submitting can be effective against high-ranking players.
RPS: Rock-Paper-Scissors (RPS) in this context refers to the strategic interplay between three elements—Rock, Paper, and Scissors. For example, Strategy A may be effective against Strategy B while vulnerable to Strategy C …
8 Likes
aangairbender, Legend 11th
you can find PM here
Thank you CodinGame for hosting such contests. This one looked simple in the beginning, but turned out to be quite deep. I got my personal record in this one. Looking forward to participate in Spring Challenge 2024!
31 Likes
Rank: #243
Bot: Hardcoded down and up strat with “collision management” lel
Strategy: Go down whilst choosing between different paths based on amount of fishes on each side of each drone, if remaining bot fishes <= 3 and color_bonus > 0? → is_drone_pos.y < foe_drone_pos.y - 600 → Go up and if the condition is still true, search for unseen mid and top fishes. Otherwise keep searching for fishes and try to eject foe bottom unseen fish.
Challenges: Avoiding monsters was the biggest struggle for me, especially if multiple monsters surround a drone.
Game: I love fog of war, it may seem unnappealing for a lot of top competitors but not for me, Top 3 games with Spider Attack and Green Circle
6 Likes
Apofils, Legend 40th.
You can find my PM here
Thanks you everyone, very appreciated this contest!
See you in Spring 
11 Likes
Hi, #3 Legend here.
First of all, congratulations to reCurse for a second RL win after Spring 2021, inspiring. Good job to MSz too for keeping up. And to everybody for making a challenging competition.
So, my bot. First, the tracking, pretty important when there is fog of war. Once you have a position, you can almost 100% keep it accurate until the end of the game. The only time you lose it is when a fish collides with another fish that you don’t have the position of, and the same goes for uglies, which is extremely rare. I keep a record of the position or square any fish can be. I use symmetry and backtrack to previous the turns to get the speed of symmetric uglies I don’t see. I use opponent success scans and previous radars to narrow squares. Things I didn’t try but probably should have is making use of failed scans (both mine and opp). Estimating the speed vector of fish should be possible with some radar sequences too, didn’t do.
Second part: assigning a destination to each drone, either surface or a fish with intend to scan or square. To decide if one drone should surface, I compute points, different variables for both player, carrying, total, current bonus, potential bonus, maximum possible, realistic maximum … I use points to decide scenarios, and then I look for each drone scan and step to surface to do the call. Target assignment is done with a score computed for each drone to each fish and minimizing this.
To choose the move, I do a depth 2 genetic algorithm between 180 angles for 40 ms, with light included. Eval was tuned with psyleague, thanks to Psyho. In it there is :
- huge malus in case of emergency
- some bonus to keep the battery
- some malus if the number of steps to surface increases
- a part to scare a fish:
- come close
- increase vx of fish
- get the fish closer to the edge
- actually push it out
- in the early game, I try to save battery until I get to type 2 fish.
- then light is used based on battery and expected distance to fish
- I not only go to the target but also minimize the distance for each unscan fish to closest drone, which enables some cooperation between my drones.
That’s it!
Thanks to codingame for hosting the challenge.
25 Likes
Rank : #8
In this fog of war challenge, informations is key to success.
Knowing where creatures are and will be in the next turns is crucial.
In the first part, I’ll talk about ways to predict positions and speed of creatures.
Secondly I’ll talk about avoiding collisions as Colliding with a monster often result in a loss.
Finally I’ll have a small word on my overall strategy which remained pretty simple throughout the whole contest.
Creature position and speed prediction
For a creature, there are two possibilities.
Either I have enough informations to know exactly its position and speed, or not.
If I do not know it, I use some scan and radars info to create a rectangle zone to track the creatures but it’s less valuable.
Exact position and speed of a creature
In order to have this info, there were two possibilities
-
The creature must be have been in your scan range (2000 if lights) (else 800 or 1100 depending of creature type) at some point in the current of previous turn.
-
It’s the symetrical creature of a visible creature which was not disturbed by a drone before this turn. (All creature with an even ID n had its symetric creature equals to ID n+1.) It means that for a creature of position(x,y) and speed (vx,vy), the sym creature has a position (9999-x,y) and speed(-vx,vy).
It is almost certain if the symetrical creature has not been disturbed by a drone. To know that, we can keep track of positions and lights of all drones at each turn to get the first disturb turn of a creature, then calculate back to current state.
A fish can be disturbed if in motor range of 1400, and a monster if in range of light.
That being said, it’s a very good option to light drones at different heights especially in the Y = 2000 to 5000 range to have more chance of preventing collisions with monsters. Each drone was lighting at different turn during descent.
Track the remaining creatures
If we don’t have enough info to know the exact position, we can still use some tools to narrow down the positions of the remaining creatures into rectangles.
For that, we use :
- Radar blip of both ally drones of current turn. (result in 2 rectangles)
- Previous turn rectangle updated with previous maxXSpeed and maxYSpeed depending on drones positions related to the previous rectangle.
- If it’s a fish and has just been scanned by a drone, which results whether in 1600x1600 rectangle or 4000x4000 rectangle depending of drone use of light.
- Habitat delimitation rectangle.
We then retrieve the remaining intersection of all the previous rectangles which result in the current turn rectangle.
Avoid collisions
To avoid collision we first must know pretty well about the monsters positions and speed. Which is why previous paragraph is very crucial. In this part, I did only took the monsters I knew the positions and speed. Combining this to a clever lighting to cover the most height possible helped me avoid almost all collisions without ever needing the creature rectangles. In fact I nearly always knew the monsters speed and position before having a chance to collide to them. Though It could still have some rare chance to happen and I could have improved it with the rectangles.
Simple avoidance
When avoiding a monster, we must not only prevent the collision but also keep as close as possible to the objective (scan a fish, chase a fish out, go back to top). For that I look at different directions (around 30) around the drone and I choose the path that helps me reach my objective faster while not colliding.
The collision detection was done by using the getCollision method in the referee while the objective was whether to go as close as possible to a target position, or reduce distance between a fish and the edge of the map.
It works already pretty good, one issue though is that if I wait until the last moment to prevent collision, it usually makes me lose time as it will make my drone turn around the monster.
To prevent that I simulate two turns in advance to make the path smoother and side step monsters before reaching them.
Taking foe drone into account
Almost all information is known to know what is the best path to avoid collision if you have the position and speed of monsters close to the drone. One missing info was important though. The path of the foe drone. It could often change the monsters path and close a route which made my drone lose an incredible amount of time to turn around. This usually happens when you are a little bit behind in the descent. If that’s the case I usually try to make some basic prediction of ennemy next step so I can go the other way around.
One additional feature I could have tried to add is in the case I am the drone in advance, to try to block the foe drone behind. I did not think of that until now that I am writting PM. But it’s a feature that I definitely thought about while ascending to reach top, trying to put some monster on top of some foe drones behind to make my other drone arrive top first. I did not take the time to implement that.
Strategy
Lighting
Appart from the descent where each drone is alternatively lighting once every three turns,
my lighting was highly dependant of the probability to scan a fish with less probability required if battery was high and it creature type was 2.
If the next position of a fish was known I knew exactly if it will be in my scan zone or not (also if it was <= 800 I would not light). (probabiity was then 0 or 1.)
Otherwise to calculate the probability, I was simulating 100 random positions inside the next possible rectangle to see if my drone next position would be in range of 2000 or not.
Then I had my probability : (nbInRange / 100)
Then my strategy was relying on the following choices :
- Going down as fast as possible without losing fish on the first descent, and try to scan all remaining fish on second descent.
- Chasing fish away if I had an opportunity or if my drone was behind in the ascension.
- Going up as fast as possible while trying to scan the remaining fishes.
Descent
Each of my drone begin their descent by following a predetermined path until Y = 5000 depending on its starting position. Their path is slowly moving them to the side in order to prevent fish lost while going down fast. Though if there is no radar on the side for type 0 or 1, they will stop following this path.
If there is a fish on a way down that I can chase, I’ll simulate the fastest way to chase it by staying as close to bottom as possible.
If there is a fish out of reach from my initial Path, (I can know that if the symetrical fish has been scanned the previous turn by the drone which is closer to the side), I will calculate the intersections of 2 circles. One circle for my drone move range (600) and one for the creature next position scan range (2000).
The bottom intersection of the two circles will be the perfect position that my drone will need to reach to scan the fish by losing the least time.
After reaching 5000, I’ll start moving towards the closest type 2 fish according the center of their rectangle.
Returning top or stay
The condition for a drone to return top is to have at least 1 scanned type 2 fish, or if the other one has 2 scanned type 2 fish. Then if the drone will not arrive after all the foe drones, it will go top.
It was a choice based on the fact that if one manage to return first with 10 fish (8 + 2), a loss is impossible.
While going top, a drone will try to go to the closest type 0-1 fish remaining to scan if this doesn’t make it lose its scan order with the other foe drones.
If the drone is behind all the foe drones, it will stay at the bottom to try to chase away the remamining foe creatures before scanning the rest of my remaining creatures. If there is a foe staying because of that, my drone will go up.
Conclusion
This challenge has been very instructive and like a lot of others I didn’t think there would be so many possibilities to try out. My strategy sure has some lacks. The go to the closest fish strat which I implemented since first day stayed until the end. And I did nothing to prevent foe the chase away my creatures if I was backing up first. I tried but did not succeed. I am also unhappy about the chase away strategy, I did not manage to program the correct time to let a fish go or keep chasing it before foe drone arrives.
Thanks to everyone for this challenge.
18 Likes
#106 (48 Gold)
I also had 3 main components, tracking+prediction, search & path planning
With the radar I draw bounding boxes around every fish, and for the first 10 turns I also restrict them taking into account map symmetry. The bad part is that every turn I overwrite previous boxes instead of updating them adaptively.
Simulation: I keep track of relevant game state and simulate the creatures’ position & speed in parallel with the actual game state, I also do this 5 turns into the future find better paths to moving fish & evade monsters. I fallback to center of radar’s boxes if my predicted position is invalided by a blip.
My bot works in two steps:
1.In the initial dive for the first 9 turns I go for scanning the fishes that are on the outside of the map, & try to scare them away if I can do this in 2 turns or less. This is because I could not figure out a way to better abstract this into a search.
2.After that I run minimax on an abstract game consisting of 3 types actions, for all 4 drones. (Scan one of the closest 2 fishes, surface or scare one of the closest 2 unscanned fish by opponent).It usually runs till the end of the game because at this point there’s few fishes remaining that are unscanned. I also had a variable depth limit depending on the remaining fishes to avoid timeouts, which when hit just returns myMaxScore - oppMaxScore.
My path planner that executes the action looks 3 steps ahead to validate that I don’t hit a monster that I know about, but unfortunately it picks the move from the first step which is closest to the destination, instead of computing the distance in the 3rd step and minimizing that one. This causes my drone to sometimes dive head first towards a monster that it knows about, only to immediately turn the other way to avoid it.
Turns out the most important part of the game are the initial 9-10 turns where radar tracking & path planning are crucial, which are the parts I focused on the least. Execution was also lackluster due to me not investing enough time into a proper CG dev env which probably cause me to waste at least 5 times as much time debugging in the web editor than it would have taken to develop the local tooling & integrate with some of the existing tools that were mentioned.
All in all, loved the game, learned a lot. Congrats to you guys in Legend
5 Likes
#78 / #20 Gold
Bot is pretty straightforward, on each turn it does the following:
-
Calculate fish areas. Fish areas calculated based on radar blips. For monsters I ran a simulation if they were visible before.
-
Calculate scores. I tried two different versions:
- my drones report scanned → opponent report everything → my unscanned fish reported
- drones report ordered by Y coordinate → opponent unscanned fish is reported → my unscanned fish is reported
Both variants didn’t work well (first one is too optimistic, second one is too conservative), so I started switching between them depending on enemy behavior.
-
Select drone targets. First moves are hardcoded, latter are selected depending on predicted scores from p.2 :
- Move to the next unscanned fish areas. Both areas are selected by minimum distance between area center and the drone with a preference to higher type fish.
- Deliver scan to the surface.
- Move to chase fish not scanned by opponent.
-
Check collisions. Planned moves are tested for collisions with known monsters. If monster is close, multiple moves from the current drone position are checked and safe route closest to the original target is selected. I also added restricted zones near bottom corners of the map since my drones were often trapped there.
-
Lights are enabled every odd turn - it works pretty bad but my other solutions were even worse.
5 Likes
I enjoyed this challenge that seemed very friendly for heuristics. The visuals were quite nice in my opinion which is a plus. I finished #260 (202gold) with a bitter taste as I think legend is reachable here just with good ideas.
Wood to Bronze: Straight down and up when I reached the bottom, with light switched every 4th turn I believe.
Bronze to silver : Copy of the collision function from the referee. Test 72 angles while encoutering a collision and choosing one that prevents it. I think this alone was enough to go up.
Silver to Gold : I added a lot of small features and in the end I do not know what was the most useful. One that seemed to help was to create 2 clusters of fishes that I gave to my drones so they do not cross the map to get a fish that is closer to the other drone. I had a condition to go up when I had scored half of the possible points. I also increased the lightning to be every 3 turns without any further logic on its activation.
Gold : 2 days before the end of the challenge I implemented a tracker that I added to my bot. I am not sure it even helped its ranking as it was probably clunky this close to finish. I improved my condition to go up based on the user-friendly boss of @Apofils. Whenever I had scanned a type 2 fish I was going up. I have a very basic function to push a fish that is close to the border if my opponent did not scan it yet. Instead of picking a random angle while fleeing an ugly I pick the one closest to my aim. Nothing fancy to be honest, so I think being in the top half of gold is not that bad all things considered.
5 Likes
Rank #1, my PM is here since forums are apparently dying: reCurse's Codingame Fall Challenge 2023 Postmortem · GitHub
Thanks CG for the contest and the competitors for being great again!
36 Likes
Happy to read that my boss helped you to improve 
1 Like
#5, Legend
Endgame
Evaluate all possible “plans” by each player. Example: if the remaining fish are 012 for me, and AB for the opponent, then a plan for me could looks like:
2SB,AS10 (1st drone goes to fish2, then surfaces, then sabotages fishB. 2nd drone sabotages fishA, etc)
Then do a min max search (assume I choose my plan first, so it’s pessimistic). If I find a non-losing “plan”, then use that, otherwise estimate the nash equilibrium (of this matrix game) and pick the highest % chosen plan.
Midgame
Similar to the endgame, but plans consist of just my remaining fish, and objective is to minimize the total turns until I have a “surface-able” position.
Early game
Prioritize rows with “outside fish” (within 2000 of the edge), otherwise move to “midpoints” (pairs of unscanned fish of a certain depth on one side of the board)
Monster Avoidance
brute force 2 step search, minimize distance to “long term target”
Misc
Lots of other tactics/fine tuning, such as:
-
heavy use of the x-symmetry of the game, for example: when seeing an “undisturbed” fish (1 of the 8 starting speeds) or monster (non-moving or very early on), backtrack to figure out where its “mirror” started
-
if a drone has a 1 or 2 turn sabotage available, do that instead (with various restrictions)
-
track upper and lower bounds of the x and y values for each unseen fish/monster, and expand the ranges a bit each turn to factor in the uncertainty
-
lots of areas where efficiency can be gained, such as 1-step look ahead for executing plans (i.e. sabotage in a way which minimizes distance to the “next” target)
16 Likes
Using lights are bad - Monsters chase us
Not using Lights are bad - Can’t scan/gain vision
Moving is bad - Motor would be turned on and fishes can hear and start to flee making us difficult to track
Moving closer to fishes in the edges is bad - Fishes might flee out off map and make us miss combos
Not moving closer to fishes in the edges is bad - We can’t push the fishes outside map making opponent miss their combos…
Moving left and right are bad - as time to go down and reporting back increases
Not moving left and right are bad - as we get less information from radar
Moving towards closest fishes are bad - As this leads to a lot of zig zag for our drones
Moving towards deepest fishes first are bad - as we end up getting chased by monsters while opponents happily scan fishes
Basically anything we do in this game is good and also bad making the game chaotic and random and I felt it’s a very bad game design that’s so imbalanced.
TOOO MUCH DARKNESS I enjoyed the contest only till I reached Gold. Implementing the sim was very hard. The sim won’t work without proper tracking as it needs the position and velocity of fishes and monsters. With so much hidden details I had to go with positions resulted from my bad tracking. Fish’s hearing range is too OP they just flee and my bad tracking end up even worse due to their hearing range… Monster speeds are too OP… Giving them 540 speed and a 500 hit range is insane as they are already hidden and tough to track…
I had a very bad contest and ended up in bottom gold with no clue on how to improve.
3 Likes
Very friendly for heuristic players, very challenging for sim players.
I like it, because newcommers can have fun, and who want to try hard, can do a lot of improvements.
With more days of contest, top players do not have a clear good final version. Even recurse have a room for improvements.
I was #200 with a full heuristic bot, nothing very different for others PM.
Congratz @reCurse @MSz @zasmu and @blasterpoard , it was amazing watching the last day submissions and bot improvements
7 Likes
Viva la neuroevolution 73th gold.
As with Keep of the Grass I used evolution strategies and coevolution, where each genome in population fought each other 2 games.
NN architecture was simple MLP and the inputs were adjusted to the drone’s POV. The drone could see only nearest 1 monster. Because this was a game with hidden information, a network with memory would be much beneficial. I could use RNN, LSTM or transformers or whatever kids use these days, but I went for simplest - some of the NN outputs were fed back to the inputs. At first I had 3 outputs - vx vy and light, so continous actions (in theory ‘infinite’ resolution) but it was very slow to learn. Discrete actions were much faster. At first I had 8 angles around the circle and full speed, then later switched to 16, then finally to 32 angles around the circle, 1 for light, and some outputs for the next inputs.
At first the fitness was just getting as much points as possible per game mostly ignoring opponent. It was not so bad in the early bronze, but it was not enough. I tried different settings. I tried some penalty when it got eaten by monster, but the way how fitness works, if I gave too much penalty for that then it would figure out that doing nothing is the best. I settled for the simplest - coevolution, where each genome fight each other 2 games and win is 1, draw 0.5 and lose 0. Unfortunately this is also most time consuming, increasing popsize grows quadratically, and the game had much variance so bigger population was needed for better diversity. At first I had 80 genomes, then upped to 120, 160, 240… Last week the evolution had 700 genomes per generation, that’s 490k games per generation and it took 1 minute to finish the generation.
As in previous contest, I needed to restrict obviously stupid moves in order to climb in rank. It learned to avoid monsters on its own for most time, but still could often get eaten in the most stupid ways. Firstly I had restricted moves (made them illegal) that would go to monster. No simulation just very simple rules involving monster position and speed. The winrate really spiked. Then I got another massive improvement with collision detection and also simulated subset of next turn monster vs drone. The drone could avoid swarm of monsters within 1 turn. If monster went out of sight, I kept his position for 1 frame and assumed he was going towards me. This made the drones somewhat intelligent since the early generations - they were going down and up and avoiding monsters and that was enough to gather some points. My last manual intervention was to restrict going to y to 500 if drone was going up with scanned fish, this sped up fish scanning and reporting a little.
I was watching some replays to get idea what else could be improved for the NN, but nothing came to my mind. It was also fun to see how the bot would be stuck in weird local optimum for few thousands generations. For example, the bot was in upper half of gold easily, but when it was going to surface with scanned fish, it was going a little diagonal or zigzaging instead of going straight up and it was losing by 1-2 rounds because of that. I saw some sharp spikes in winrate charts, it was when the NN was finally started going straight up. There were few such spikes meaning the evolution got unstuck from some local optimum and found some important strategic things.
This time I didn’t get into legend. Apparently leaving things to computer isn’t always good. I liked the game overall, but it contained too much variance in the leaderboard. 1 submit was 80th, then the same resubmit was 30th, and overnight it climbs to 15th, then submit of ‘better’ bot made it to 60th. It was frustrating. At first glance the game looked simple, but it has some depth to it 
. Though I imagined I would see some very weird strategies like dumping monsters into opponent or something like that. Thank you codingame for another contest.
15 Likes
Hello there, 80th gold, 138th global here.
Main strategy
Tries to find the best path to catch all fishes with a score function.
If I have enough points to win or if my opponent will be able to win if I don’t go back to surface right now, I simply go back to surface.
Creatures area
Like everyone I try to estimate the fishes area, for this I use the previous area, the living zone of this fish type and the radar. Could have been really improved without so much efforts by using the opponent’s scans, my drone’s light radius and the creatures symetry.
Uglies avoidance
Find the closesest destination from my target where my drone won’t be eaten by an ugly in the given turn. Works very well for simple cases, but since I have no simulation for multiple turns my bot can end up trapped between multiple uglies, or not find the most optimal path.
If an ugly was already found before I keep a track of it’s potential position given it’s last position and speed.
Light
Score computation using my light area, all creatures positions/areas and types.
For each fish I compute the probability to catch it, and Above a given global score I will decide it’s worth to turn on the light.
Conclusion
I really hesitated about doing a simulation since it can be so complicated to have something accurate with the fog. My bot ends being really basic, and I’m impressed by what other players achieved.
I wasn’t very excited about the subject, I think it could have been deeper and a little bit more complex even if there is such amazing bots and work right here.
Really congrats to everyone and especially the legend players and the winners
And of course thanks to CodinGame !
2 Likes
Di_Masta, 460th
Even though the contest seemed pretty random at the end, I’ve enjoyed it.
I’ve spend a lot of time, working on it every day and evening for 21 days straight. This time I really wanted to reach top 100 and fulfil a small dream of mine. But even with the enormous efforts I’ve invested, I wasn’t able to do it and I’m pretty disappointed of myself. But at least I’ve managed to improve my results form previous contests, which puts a little smile on my face. Also I’m happy that I’ve managed to implement every idea that I had, even tough most of them didn’t work at the end.
How did I approach the task:
-
In the first leagues I wanted to research the game using just a simple heuristics bot. And it paid of at the end. I discovered that a predefined path for my drones to follow, works pretty nice. I’ve scattered Check Points with radius 600 in the middle of all habitats, two points per drone and make my drones follow the CPs if the drone is in the radius of the CP target the next one.
-
When the monsters came making one full lap without being hit was pretty hard, so I’ve surface the drone after hitting a CP and that moved me to Silver.
-
There I’ve noticed that in order to collect enough fish I need a simulation of the entities. I wanted to implement accurate simulation and keep the data for the detected fish for the next simulations. This was really hard for me, I spent days porting the referee simulation logic to C++, after that I needed new several days to debug and polish the simulation. I cannot understand why I spent so much time on that, does it happen to anybody else?
-
For the first time I’ve read and used the Java referee code, which was definitely a good idea.
-
When I polished the simulation I noticed that my Check Points weren’t working very well in different scenarios. So I wanted to make an AI search algorithm with simulating the future. I first tried GA with evaluation for each drone, but this didn’t work at all, for days I couldn’t come up with a nice evaluation. Actually I always struggle with this evaluations, could someone give me an advise how to approach them properly. I even made my own visual debug tool to analyze the GA but it didn’t help also.
-
After the fail with GA I tried MC with random moves, simulating the game until a drone is hit or a Game Over, didn’t work at all again…
-
After so many fails I decided to implement DFS for each form getting him closer to the next Check Point without being hit by a monster. I’ve managed to run DFS with 5 turns depth and finally I saw good results which moved me to Gold, the bottom of Gold.
-
There I noticed that my CPs are not working very well in all cases, so I decided that I need more precises targets for my drones. A friend of mine advised me to use the Drones’ radars to estimate the positions of the fish. And I came up with the idea to average the radar direction for all remaining fish taking the directions for fish on the right of the right drone with bigger weight and ignoring them for the left drone and vice versa. This worked well moved me to 185th in Gold, so close to my dream…
-
Then I decided to send the drones to report only if they are above of one of the enemy drones otherwise I wanted to scare unscanned fish by the enemy. Took me days to implement decent scare logic. Tried the new bot against the 100th player and my bot won 8 out of 10 matches, got pretty excited and submitted, moved me 100 places behind …, fixed some bugs again good tests against the new 100th player, submit, 100 places behind …, and again and again … I reverted to my 185th both but maybe it was too late it didn’t reach the same place.
Mistakes:
- Probably I should have been more active on Discord.
- For future in Gold league I’ll first test my new bots in separate account before submitting in my main.
Request:
- CodinGame @TwoSteps , for the next contest please consider a more simulation friendly game, with this collisions and vectors it’s very easy to mess up even with having the game code ending up in days of debugging. The randomness of the fog of war is also very hard to deal with by the average player. Perfectly, I would suggest something that could be solved with MiniMax, I know it’s old school but a nice game, I believe will be a good challenge for the top NN players also. Some classic board game like: Chinese_checkers
3 Likes
17th legend, first python.
Thanks for another nice challenge. It had much depth to it and there was no “clear solution” which kept things interesting and surprising during the competition.
When the challenge was just revealed, It seemed like an easy task - go down, grab some photos, go up.
In the beginning, this was literally the case - my first submission in bronze was just instructing my bots to go up and down blindly, and it went straight to the top 100 and stayed there for almost a week.
As I thought about it carefully, it seemed like getting a good old search algorithm wouldn’t work here in python, since the devastating results of a bad action will usually come up many turns ahead (for example: If I don’t scan a crab and go up, it might let the opponent as many as 20 turns to scare it, which might be catastrophic as it will loose also it’s trophies). I imagine that even @reCurse’s RL bot had a problem learning those kinds of things and misevaluated losing scenarios.
Also, due to the stochastic fog of war type of game, I correctly assumed that games would be inconsistent. Therefore it wasn’t important to always win, but it was important to statistically win more times.
So I went on with a (mostly) heuristic bot and a lean approach, finding the most common reason for me losing games, fixing it, and repeating.
The final bot:
Tracking:
As people previously mentioned: exact tracking with abusing the symmetry, and rectangles for the fish I didn’t see yet.
Differences from the previous PMs:
- cutting the tracked “fish rectangle” with a circle, and not a rectangle.
- losing exact track of creatures that collide with ‘fish rectangle’, except for monsters.
Descending state
During the first descent, it was highly beneficial to scare fish close to the edge with my side bot. accordingly, it was important to send my “center” bot towards the side, to scan their symmetric counterparts before the opponent scares them.
The adjustment in the movement was done to put the bot in the bottom-most position after scanning/scaring the relevant fish.
Once no such fish are left to scare or scan close to the wall, go to hunting state.
Hunting state
Searched for the paths that would bring both bots to the surface with enough creatures to ensure a tie or a win. Later patched this search mechanism to also scare fish away and go for the 2nd dive.
Lighting
Use light only when there is a high enough probability to find a fish.
during descent:
- Not lighting more than one bot at a time. The only exception is if there’s a creature to scan before it can be scared.
- If no lights are to be used 2 turns in a row, force light on the bot with the higher battery. important to not blindly run into a monster.
Monster avoidance
3 rules here:
-
Don’t get eaten this turn. The closest direction to the fish is calculated in the fish’s frame of reference (there the fish is static, and my bot moves towards it with a relative velocity of
bot_v-monster_v, and with some basic linear algebra and trigonometry the direction limitations can be calculated)
- Try not to agitate monsters by keeping 800u from them the next turn. Also some trigonometry here.
- Then I check that the final position doesn’t result in my bot being alive but trapped the next turn.
The combination solved nearly all losses due to monsters.
Math
Some basic linear algebra and trigonometry (especially the law of cosines) came very handy in this challenge. It gave me the option to calculate exact solutions quickly, giving me the small boost required to pass the other heuristic bots.
5 Likes