14th - Legend
My first algorithm was a Monte Carlo:
- generate a random number of random commands for my factories at the first turn
- simulate for 30 turns
- evaluate the difference of units on factories after each simulation with a decay factor
Then I switched to a genetic algorithm:
- same random move generator using the genes as the random number generator
- uniform crossover
- no mutations, instead I injected some new random genes
- this performed a lot better than the MC, since it reused intelligent moves found before
Optimizations/tuning:
- a local referee allowed me to run a lot of local simulations, I usually did 1000 matches between my best AI and my new one, with a short 1 ms timeout to quickly tune the parameters/strategies
- instead of storing the troops, I just stored the difference between his troops and mine at each factory for each step
- opponent new moves were too costly to simulate, so I just assumed he would move from any factory to any factory with a decay factor over distance
- use the Floyd–Warshall algorithm to move units using the shorter path (I ignored the owner of the destination)
- my factories that were safe (not under attack by the opponent) were excluded from my evaluation, to avoid keeping unused units on them
This was a great contest again, thank you CodinGame!