Last week, the best programmers of the platform fought in the arena of  the “Ghost in the Cell” contest. 3508 programmers from more than 50 countries joined the competition. The game, a battle of cyborgs, fostered the use of heuristics. Let’s discover the strategies of the top AIs.

A Battle of Cyborgs

As you most probably realized, we took inspiration from the Galcon game. This game has already been used in the famous AI competition: Google AI challenge “PlanetWars” in 2010.

Ghost in the Cell consisted of a 2-bots battle to control factories which produce cyborgs. You could move cyborgs between factories and try to overrun your opponent. As usual, we try to make the game as exciting and fun as possible, so we added a few additional rules. Each player had two bombs which could temporarily disable a factory. Also, each player had the possibility to permanently increase  the production of a factory.

To have a better understanding of the game and its rules, I invite you to look at the Twitch stream we did with Charlotte on Monday:

I hope you enjoyed the stream and our beautiful French accents! This was the first programming stream for both of us. I must say that it was a bit stressful, but we genuinely had a lot of fun! We can’t wait to do it again!

From Bronze to Legend

Since I’ve joined CodinGame, I’ve discussed bot programming contests with a lot of programmers. A lot of CodinGamers think that they’re not good enough to compete in such challenges. I believe otherwise. Despite not being a software developer anymore, I’ve managed to reach the Legend league for a final ranking of 57th. To me, it shows that, with the right strategies, you can compete with the best programmers.

I’m not going to lie. It took me some time: approximately 12 hours of coding to reach Legend, and then an additional 5 hours to try to rank higher. But the code itself isn’t specifically complex: I’ve coded around 600 lines of for loops and if conditions in Java. I tried to follow the advice of Bob, a famous player on the platform, who shared his strategy at the end of the previous contest, “Fantastic Bits”: Be Lazy and Keep It Simple.

Ghost in the Cell is now my favorite contest! I think that I liked the optimization part of the game. I felt that it was quite easy to understand the areas where you could improve your AI by looking at replays.

Enough written about me; it’s time to discover the strategies of the three winners: Agade, Vadasz and Pango. Also, if you’re interested, a lot of players have already shared their strategies and feedbacks in the forum.

Agade Postmortem

This was Agade’s first win in a CodinGame contest. Congratulations, Agade! He was kind enough to share his strategy in details on Github.

Vadasz Postmortem

You probably remember his name, as he managed to rank 3rd at The Accountant. Maybe the winner of the next contest? In any case, great job Vadasz.

Moving of Troops

I built a matrix to store the states of each factory for 20 turns. So, if the game had 7 factories, I had 140 nodes in the matrix. For each node (a specific factory at a specific turn), I supposed that both players want to occupy it, and send all their armies there. For example, factory 0, turn 5: both players send the troops which can reach factory 0 in the next 5 turns. I then calculated the following results from these “all-in” attacks:
– Who owns the factory at the given turn (me, neutral or the enemy)
– I make a difference between my cyborgs and enemy cyborgs, and get a count of “unused” cyborgs. This means that, without these unused cyborgs, the owner remains the same.
For example: at factory 0, turn 5, my cyborg count is 10, and the enemy cyborg count is 25, then there are |10-25|=15 unused cyborgs, and the owner is the enemy — it does not matter if, at the 1st turn, the owner was me or the enemy, the calculation showed that in 5 turns, the enemy will own the factory, if he wants to.
From the matrix at turn n, I would have the number of ‘UNUSED’ cyborgs, and the owner would be ‘OWNER’. So I gathered ‘OWNER’ cyborgs at factories at distance ‘n-1’. I called these cyborgs ‘GATHERED’.
If ‘UNUSED >= GATHERED’, then the ‘OWNER’ doesn’t have to send any cyborg to the factory. He’ll remain for sure the owner of the factory. For example, it would happen if the objective is too far away, or if enough troops are already moving.
If ‘UNUSED < GATHERED’ then the ‘OWNER’ must send at least ‘GATHERED – UNUSED’ cyborgs from factories at distance ‘n-1’ from the targeted factory, if he wants to make sure to own it. After that, the number ‘GATHERED’ is decreased — the sent cyborgs cannot be used anymore.
I supposed that both players play the optimal way, and that they want to own all the factories that they can at minimum cost. Of course, it is not possible to send all armies to all factories at once, so I built a priority: the less turns to reach a factory, the more important it is. So, if I can definitely own a factory at turn 1 at the cost of sending X cyborgs, this is the highest priority; I send them. I didn’t consider concrete production number, but I calculate using only those factories which have a minimum production of 1.

The calculation described above does not take into account which player is the owner of a factory, so there is 1 additional cyborg in case the factory owner changes at the given turn.

Short Pseudo Code

DO
    all_in_matrix.Calculate()

    -- Search from only those nodes, where the owner had to send some cyborgs to the factory
    highest=all_in_matrix.GetHighestPriorNode() 

    -- If enemy is the owner at highest node, he moves. If I am the owner, I move
    MoveNecessaryTroops(highest) 

WHILE highest is not null

In each iteration, the count of cyborgs that can be moved decreased, so in the end there had to be a node, where no player could send a cyborg.

Increase of Production

I created neutral ghost factories with 0 distance for each factory with 9 cyborgs, so that move actions handle the “INC” action in my algorithm. The only problem I had is that the priority affected to this “MOVE” was too high (equivalent to turn 0), so I had to manually set it to a lowest priority. I also checked that the original factory had to be controlled by me for at least 10 turns before I could attempt to occupy the ghost factory. So, basically, I wouldn’t increase the production of a factory I had just acquired.

Bomb Management

Dodging: When an enemy sent a bomb, I started a counter, and when a bomb could arrive to a factory I own, I sent all my cyborgs to the nearest factory from there.

Sending:At the first turn, I would separate factories into 3 categories:

  • Those closer to me than to the enemy
  • Those closer to enemy then to me
  • And those at equal distance from the enemy and me

To send my 2 bombs, I’d choose factories from the 2nd category which have the highest production.

Thanks for the contest again; it was great fun — looking forward the following one! :)”

Pango Postmortem

Special kudos to Pango, who managed to rank 3rd for his first participation in a contest! Impressive! It’s been a long time since a python bot didn’t reach the podium of a challenge. GG Pango!

“I really liked the fact that different kinds of algorithms/languages could be viable even at the top of the leaderboard (with a preference for heuristics, admittedly).

Metagame

I think it’s been given the name of “INC strategy.” My goal was to take control of my half of the map as fast as possible, upgrade it as fast as possible, then send every remaining unit to the zero factory, and hope that at that point I’d have more bots than the opponent.
The idea behind this is that it’s the minimum required to win a game, so it probably requires the minimum amount of thinking to solve.

One-to-many Moves

The first algorithm I used to decide my actions aimed to find the best moves for one factory with one or multiple targets.

It worked in three steps:
1. Compute the ‘gain’ to send troops from any factory to any other factory.
2. Bruteforce combinations of the previous moves to find the source factory with the best combinations of targets.
3. If the best gain is zero or less, stop. Otherwise, send the troops and go back to step one.

The amount of troops to send is defined as the minimum amount of troops to guarantee ownership of the destination, and the gain is defined as the delta total cyborgs after 4 turns (4 is arbitrary).

This worked especially well in the first few turns.

Many-to-one Moves

I later realized that combining the efforts of multiple factories on a single target was a must have.

I assigned to each factory a quest, that can be either ‘upgrade’, ‘defend’, ‘attack’, ‘capture’ or ‘none’, and an amount of available cyborgs, to represent the maximum it can send to complete quests without going into the negatives in the next 4 turns.

What I implemented looks like this:
1. For each quest, loop over factories, starting with the closest from the quest, and ending with the furthest away from it.
2. For each of those factories, add all available cyborgs to the quest pool.
3. If the quest pool is big enough to complete the quest, stop here and estimate the gain of doing the quest (still a delta cyborg after 4 turns).

Then, find the quest with the better gain, launch the orders, and repeat until all quests are done or none of the remaining quests can be completed.

This made my micro management to upgrade/capture factories a lot more efficient, and allowed me to capture/defend positions more often.

Opponent’s Turn

I first assume that the opponent is going to do all the actions cited above (one-to-many and many-to-one). The first goal is to make his amount of available cyborgs more realistic, since he has to defend/capture factories in his territory. The second goal is to predict obvious attacks, in which case I can sometimes counter-attack at the same turn and base-swap.

Then, I assume that any of his bots remaining that can reach one of my factories in 3 turns or less will either do so or stay where it is. Which means they end up duplicated in the game state.

My Turn

After doing the simulation of my opponent’s turn, I apply the one-to-many and many-to-one algorithms.

Then, after turn 4 (I like 4, it’s 2*2), I start sending all available cyborgs to the factory zero (unless my side of the map is under attack, in which case instead of sending to zero, I send to anything that’s being attacked in my side).

The ‘INC’ Dilemma

The problem is: if you’re last to increase, you lose. But if you increase too fast, you get swarmed.

I don’t really have a solution to that. Machine learning could be a good approach, but I didn’t set up an offline simulator to generate datasets.

What I did is something like: if my production is at least two more than the opponent, I don’t inc. Which worked “ok,” but it’s really not satisfying.

Pathfinding

I bruteforced my way through all the combinations of paths that were at least as fast as the direct traject, and made the approximation that they all took the exact same amount of time (it was too complex to deal with variable travel times).

My rule to prioritize paths was:
1. The one for which the first node is the closest first.
2. Only pass through nodes that are owned or have zero cyborgs in them.

I also had a second pathfinding function that I used to send troops to the zero factory; this would sacrifice travel time in order to pass by a lot of other nodes and eventually change targets mid-way.

Bombs

Nothing noteworthy here. I targeted factories with a high production, and sent both bombs very early.

I assumed my opponent would target my factories with the highest production, and evacuated before impact.

Hacks

Here is a non exhaustive list of hacks I added in my logic that made the whole thing work better:
– Never increase the production of the factory 0 before the very late game. Do it ONLY IF I would lose without increasing it.
– Never increase if the total production of my factories exceeds by 2 the total production of my opponent.
– Never try to attack or capture a factory that is closer to an enemy than to me. That wouldn’t end well.

Python2 Specific Tips

The first version of the code I submitted only did the one-to-many logic, and it had the tendency to take more than 50ms on big maps… I then read a few articles on the subject, re-wrote everything and made the whole thing run in less than 1ms.

I’m far from being an expert on the subject, but I’d like to share some of the things I’ve learned:
– while loops are very cheap.
– the dot (foo.bar) is expensive. It’s faster to use arrays to store data. It’s also faster to use local references for functions and methods.
– memory allocation, despite being very easy to do in python, still takes a lot of time. It’s faster to allocate memory only once.
– you can’t inline in python, so functions called in loops can get very expensive. Sometimes it’s better to write all the code directly in the loop.
– not computing the same thing twice is a good way to gain time.

Conclusion

It was a blast; thanks to everyone who organized, as well as everyone on the chats.
You can count me in for the next one for sure :smiley:

Congratulations again to the 3 winners, and thank you for sharing your strategies with the community!

What’s Next?

We have just released the game “Ghost in the Cell” on the platform until Bronze league! We will release a new league every week until the Legend league. This is the opportunity to get back on your algorithm, as it’s still fresh in your mind (note that you can find your code of the contest on the finished contests page). If you haven’t participated in the contest, no worries. You can start at your own pace from the Wood leagues.

That was fast, right? We’re actually already thinking about the next contest, “Coders of the Caribbean,” which will come faster than you think — in only 5 weeks from now. I would like to emphasize on the dates and times because they’re different than usual. The contest will start on Friday the 14th of April at 12pm EST and will end on Monday the 24th of April at 4am EST, for a total of 10 days with two full weekends!

About a new possible stream on Twitch: we wonder if some of you would like to stream as you code the next contest. We could build some kind of calendar with all the streams sessions (with their levels and programming languages) that we will host on CodinGame channel. Let us know if you’d like to watch such streams by filling this one-question poll. In case you’re interested in streaming, please contact me at [email protected].

Also, some players have already asked me about CodingHubs for the next contest. There will be hubs! As usual, you can find all needed information and the list of hubs on a trello board.

We’ll see you all for Coders of the Caribbean. Yo-ho-ho