6th in Legend
My code isn’t that complicated and lacks of some features as prediction of hostile bombs and a danger level (how many troops can attack me in turn X, if my enemy will send them now?) to be able to defend against a big number of attacking troops. I tried the latter one, but it made my bot too shy.
You know, how many troops will reach a factory at what moment. So you can simply define an array and add (or subtract for your own troops) the incoming troops with their arrival time as index. After parsing the input, calculate the owner for each turn and add the produced troops.
Nice gotcha: when an enemy is about to conquer a neutral factory and you can still make it in time, set needed to 1 (or whatever is needed to keep the factory neutral). You will send 1 troop and the enemy will kill the neutral troops for you, so you can take the factory in the next turn.
Here is a replay showing what I am talking about: https://www.codingame.com/replay/196806568
In turn 7 I send one troop to factory 5 to keep it neutral and take it in the turn after that.
I looped over all my factories and selected targets for them independently.
For each source I calculated my prefered targets (production/(distance^2*needed[distance])) and attacked until I had no more troops left, subtract the troops from needed ones.
This greedy approach makes mistakes (e.g. sending from 0 to 2 and then from 1 to 2, because factory 1 is closer to the target, making to troops from 0 to 2 unnecessary). So I loop over my plans to find these late arrivals, remove them and repeat the process.
An important part is not to attack directly, if your target is far away. This would allow your opponent to prepare for the attack, make you inflexible for changing your mind and sometimes even costs you a turn, as the direct path is not always the shortest.
For doing so I implemented Floyd-Warshall to find the paths at the beginning of the match, maximizing the number of hops, if there are two paths with the same length. I ignore, that there might be hostile factories on the path.
I treated upgrades as neutral factories with 10 troops needed and production 1, that I have to conquer. This way it is easy to combine upgrades, instead of having two factories collecting troops independently. As I don’t know if it is save to upgrade (I don’t compute the possible number of attackers in the next round), I only upgrade, if the next hostile factory is at least 3 turns away. My bot doesn’t upgrade, when bombs are coming (though I am still not sure if this is a good idea).
I try to throw bombs early to slow down the enemy on the first rounds. Targets are selected by production, then by time, the bomb needs to arrive, including factories, that the enemy will conquer in the next turns, taking currently moving troops into account. If I can throw a bomb now or make it arrive at the same target in the same round (because I will for sure conquer a factory closer to the target soon), I wait with it. This way I might be able to find a better target. If not, I didn’t lose anything.
This contest made a lot of fun. Upgrading and bombs made it complex enough to be interesting.