May 29, 2017 TCO17 Marathon Round 2: An Analysis

TCO17 Marathon Round 2 featured a task called AbstractWars. The author of this task stated explicitly in her blog that this task is not intended to be solved by a common technique. However, it looks like the leaders of the provisional standings have used a method called Simulation to choose the best strategy for a given game. Psyho holds the lead for most of the match, and finished in 1st place before the system tests. Everyone who placed in the top 30 did a great job and most of them will earn TCO Marathon points.

Trivial Solutions

There are some predetermined strategies that worked well enough. By “predetermined” I mean that they do not consider a simulation of the game several times before making a move. I used one of them, thus will cover this theme. Feel free to skip this section if you had scored better than 577475.73 in the provisional standings.
The first observation one could make is that all of the opponents do not do anything in the beginning of the game. This is our chance to conquer some bases while getting no attacks on the bases that are already ours.
Then a question arises: which bases are wise to attack? Evidence shows that bases that produce more units are desirable. However, the further an enemy base is from the attackers the longer it will take to get to that base, so we are potentially under-producing units in our current bases. It turns out that attacking a base that has the lowest distanceij / growthRatej ratio is a good way to start.
How do we know the growthRatej then? Let us recall the growth formula for a base j:

    numberOfUnitsj += growthRatej + numberOfUnitsj / 100

The growth rate thus is pretty easily calculated during steps 0 and 1. Record the amount of units of all bases during step 0. In step 1 you will get new information about the bases, so as long as all of the bases have less than or equal to 10 units initially, we can ignore the numberOfUnitsj-dependent term in the formula: it will be zero because of integer division. Then, calculate the growthRate as follows:

    growthRatej = numberOfUnitsj(step=1) - numberOfUnitsj(step=0)

Now we can attack enemy bases knowing the expected profit of each attack. Let us consider the simpler cases first where we have an advantage. In order to strengthen the advantage and not lose, it would be nice to observe how our opponent is beating us. They collect as many units as they can, and only then sends a sequence of attacks to our bases. This is a strategy that lends itself to too many unnecessary lost units, but there is one thing we can understand from it: the bigger your base, the more units it produces. Thus it might be wise to wait with all of your attacks until the base is close to overflow, so let’s say you should send units to attack if there are more than 950 units at a base, otherwise wait. If there are 988 units or more, in the next step it is going to overflow. One way to save the units from further attacks is to send half of them to any friendly nearby base. We can use random numbers to choose which base to send our units to, with near bases having higher probabilities, much like the opponents do with their attacks.
So far so good but we can do better. Why aren’t we doing anything in the beginning, like our opponents? Let us attack them instead even if we have a small amount of units. We need to stop this blitz strategy when one of the opponents starts sending their troops.
The next step is to attack even more in the beginning. We can achieve this either by sending all units from one or two growing bases to bases with growth = 3, one-by-one in each step. Later we will send attacks from 3-growth bases only. Of course, we need to stop this after someone else starts their attack. An alternative way is to send collective attacks to enemy bases. I did not succeed at this, but top participants report that they did exactly that in the beginning of the game.
Now we can estimate when an enemy will send its next attack. For that, we keep track of the amount of units in all steps, and calculate the expected amount of units at the enemy base had it sent half of its troops on an attack. If this amount matches the current step amount on the base, we update the minimum amount of units for each player, needed for him to send the troops away from a base.
Another trick is to predict an expected base that enemy troops will attack. A brute force solution for this would be to check all of the base pairs and validate hypotheses that a given troop goes from base i to base j. For this we might want to store the troop’s location history. This is a very expensive way to calculate it, but it worked in most of the tests. A better way is to notice, like mugurelionut did, that on each step you get the same order of troops from the visualizer. That is to say, once you calculated the destination for a troop, you do not need to redo this at a later step: use your previous value.
Now we can estimate amounts of units at enemy bases after several turns and plan our attacks accordingly.

More Complex Solutions

A good way to improve this is to simulate the game with different attacked base sequences, like the leaders did. I will point to the Post your approach thread in the forums, which is a must-read if you want to improve on Marathon competitions. The leader, Psyho started this discussion with providing an excellent overview of his solution, with a link to the source code. Many top participants followed by presenting their ideas. Do not miss it even if you are tired after the match!

Next Steps

The next and final qualification round of the TCO17 Marathon track is scheduled to start at 9 PM July 5th EDT. Take a rest and I will see you there!