Unleash the geek – Post Mortem (2019-10-19)

Contests > CodingGame

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!

Something to say?

Leave a Reply

Your email address will not be published.