This post is a corrected version of my “Unleash The Geek” Post-Mortem, originally posted here.
Hi there ! I am ranked 341 after reached the top gold… Don’t test things at the last minute children. 😉
Before all, a great thanks to the CodinGame and Amadeus teams for this funny contest. And of course, GG to all the participants !
Civilities done, let’s talk code and strategy !
Wood to Bronze: The mower
Once my class model created and data stored in it, I decided to start simple by avoiding using traps and radars…
But without radars there’s not a lot of possibilities, so I just coded the following :
- If there’s no hole in x+1, digging that cell.
- If there’s a hole in x+1, moving in x+1.
- If the robot carry ore, going back to the base.
This was called the mower strategy on the #Fr channel, and was sufficient to pass Bronze.
Bronze to Silver: I see everything !
Now in Bronze, it was time to consider to put some radars.
Don’t knowing the distribution of the ores, I simply started by putting my first one at the center of the map. For the next ones, I don’t wanted just hard-coding the positions, so I created a function to find the best next position, which worked with a system of flood-fill.
I now had this :
- The nearest robot of the base is the scout. It request a radar, place it, and restart.
- The others robots are the miners, they dig the closest ore, and take it to the base.
- If there’s no more ore to dig, the miners use my wood “strategy”.
That was not enough to pass Silver, so I added some stuff:
- Decreasing the ore count on a cell when I send a robot to dig it, to avoid sending too many robots on a cell.
- Avoiding to dig the “dangerous cells”. To do that I consider the robots which stay at the base during one turn as “bombers”. Then, when the bomber stop again during one turn, I consider as dangerous the cell where it is and the adjacent ones if there’s a hole on them. I stop then considering the robot as a bomber.
Silver to Gold: Blow up them all !
My first modification in Silver concerned my trap detection, which became inefficient in front of the “fake traps”, since I stopped to consider a Robot as a bomber when it make a one turn stop. So I changed that by using the opponent score: I stopped to suspect a robot only if it get back to the base increasing the score, which mean it carry an ore and not a bomb.
This was not enough to reach Gold.
So I started to consider to put traps. But I had no idea how to do that efficiently, and without waste precious farming time. Then, I had an idea: Why don’t just use the opponent traps?
I already knew the possible positions of this traps. So I coded a function which calculate the chain of explosion from a trap, considering each “dangerous” cell as a trap, to determine the worst losses for me if I trigger this trap, and the minimum losses for the opponent. Then, before moving each of my robots, I executed this function on each of its 5 accessible cells. If for one of this cells, my worst losses were lower than the opponent minimum losses, I dug that cell.
This was very efficient! Blowing up groups of enemy robots and breaking radars! I passed to Gold directly.
Gold to nowhere: The long way to the top
- Once in Gold, I noticed that more and more players stopped to use traps, which was annoying for my last implemented feature. So I decided to put just one trap, at the start, next to the base.
- I also noticed that a lot of players built traps walls next to the base. So I modified my start like this:
- Turn 1: The scout request a radar and all the miners request a trap.
- Turn 2: The scout go put the radar in place and all the miners dig in x=1, to deceive the enemy traps detection.
- I won some places, but my radars placement was not optimal and penalized me. So after some tests, I simply hard-coded the first eight radars positions, and kept my old function for the late game.
- A new problem then appeared: The radars destruction. My bot obstinately replaced the destroyed ones, even if the zone didn’t have interest. So I saved the ore count on the cells previously covered, and used it to determine if it was useful to replace the radar.
- The next problem was the false positives in my traps detection. So I refined it a bit:
- I now keep a two turns historic of the map to detect a decrease of the ore on a cell next to a bomber.
- I now remove the “dangerous” flag of a cell if a non-bomber dig it and there’s no bomber around.
- Then, I was too vulnerable to the AIs with an “opportunistic kamikaze” strategy like mine, due to the tendency of my robots to dig the same cell. So when I send one of them dig a cell, I set the ore count of this cell to zero instead of just decrease it. The result was a spectacularly progression of about 200 places!
- The last big change I made was to totally rewrite my decision function, to give the best order to each robot, instead of just treat them in the inputs order. Here again, a big progression of about 100 places.
I was then 48th Gold.
The fall : Such is taken who thought to take…
In the top of the Gold league I encountered the following problem: The players didn’t puts traps, and my poor bot wasted a lot of time trying to trigger explosions. But, by deactivating this feature, I didn’t even reach the top 100… Then, I had a bad idea : Why not try to deactivate it, only when I’m sure that there’s no traps on the map?
So, I spent the last hours of the contest watching replays, parsing games data and computing statistics, with the goal to find a correct indicator of traps presence.
The first tries were disastrous. I finally managed to reach back the top 200, but never higher. So in the last hour, I pushed again my previous version… And never passed the 200 again. 🙁
Thanks again for this contest! See you!