Hello everyone! 3rd place legend here for my first participation. It was a loooot of fun.
An especially big kudos to the CG dev team, this website and the bakend behind it are awesome.
Also, as many people already mentioned, I really liked the fact that different kind 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 units 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:
- Compute the ‘gain’ to send troops from any factory to any other factory.
- Bruteforce combinations of the previous moves to find the source factory with the best combinations of targets.
- 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 ‘upgrade’, ‘defend’, ‘attack’, ‘capture’ or None, and an amount of available cyborgs, which is the maximum it can send to complete quests without going in the negatives in the next 4 turns.
What I implemented looks like that:
- For each quest, loop over factories, starting with the closest from the quest, and ending with the furthest away from it.
- For each of those factories, add all available cyborgs to the quest pool.
- If the quest pool is big enough to complete the quest, stop here and estimate the gain of doing the quest (still a delta cyborgs 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 factory 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
Once the opponent’s turn simulation is done, it’s my turn to 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 cyborg 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’ dilemna
The problem is: if you’re last to inc, you loose. But if you inc to fast, you get swarmed.
I don’t really have a solution to that, I think 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:
- The one for which the first node is the closest first.
- 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, that would sacrifice travel time in order to pass by a lot of other nodes and eventually change targe 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 inc factory zero before the very late game, do it ONLY IF I would lose without incin’ it
- Never inc if I have two or more prod than the other player
- 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 red 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 learned:
- while loops are very cheap.
- the dot (foo.bar) is expensive, it’s faster to use arrays to store data, and 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 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 
).