For this contest, like many others, I began with an algorithm using heuristics. Lots of ugly if then else, loops over my factories and opponent factories, etc.
I planed to do an other algorithm with some kind of simulation later.
But my first algorithm worked not so bad. When I realized after a couple of days that the direct path between factories is not always the shortest, I recycled my Dijkstra function from TAN network puzzle to find the shortest paths. When 2 paths have the same length, I choose the one with more steps, because it allows to re-route the troops if needed.
With this improvement, I somehow managed to climb to the top 5 in the middle of the week. So I stuck to this algorithm I kept tweaking it for the rest of the week.
For each factory, I keep a list of incoming troops. It allows me to compute how many cyborgs I have to keep there to protect it and how many are available for increasing or to move.
My final algorithm looks like this:
- Bombs : As soon the opponent has factories with a 2 or 3 cyborg production, I send a bomb to the closest ones, while avoiding to send 2 bombs to the same factory within 5 rounds. I also added at the last minute a detection of incoming bombs. It’s pretty basic and it works only for a bomb sent in the 1st round, assuming it will target my 1st factory. It allows me to get out just before the explosion.
- Increase : If a factory has at least 10 available troops, upgrade it. Also, always choose one factory to be the next to be increased. It’s typically the furthest one from the opponent. Then, from the close enough factories around, send all available troops to it. I realized that increases are very important to win in this contest.
- Moves : for each of my factories with available troops, I find the destination with the best “score”. A score is better when the destination is closer, when it has less cyborgs in it and when its production is higher. I send to this factory (in fact, to the 1st factory in the path to reach it) the minimum number of cyborg to save it (if it’s mine and it’s in danger) or to capture it. If I still have available troops to send, I do the same thing with the second best destination and so on.
That’s pretty much it, and it gave me the 18th place!
It’s not a perfect algorithm. I noticed that it quite often looses against bots with lower ranking, but it also sometimes wins against the top 10 bots, so I suppose it’s why it made its way to the top 20.