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
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.
This was Agade’s first win in a CodinGame contest. Congratulations, Agade! He was kind enough to share his strategy in details on Github.
Moving of Troops
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.
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.
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).
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.
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.
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.
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.
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.
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.
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.
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.
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
Congratulations again to the 3 winners, and thank you for sharing your strategies with the community!
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