Castle Defense I - Approximate methods

In the last post we considered a simple version of a tower defense game.
There were gameSoldiers, gameTowers and each tower had numHits it could take before crumbling and numKills soldiers it could kill in each round. Soldiers would start each round by shooting at a random tower removing one of its numHits. After all soldiers had fired, the remaining towers would shoot with each tower killing numKills soldiers.
In this post we will consider a slightly different variant of the game:

• A castle is attacked at sunrise, by surprise by a group of gameSoldiers soldiers.
• Each soldier carries a canon and a rifle. 
• The castle has castleHits strength, i.e. it can take castleHits before it crumbles. 
• In the first day, all soldiers fire their canons at the castle decreasing its strength to \(castleHits-gameSoldiers\).
• Assuming the castle still has \(castleHits>0\), it will then send their own defendersPerWave soldiers per day/wave/round.
• In the beginning of each day/round/wave, the soldiers shoot and each soldier can either hit the castle with a canon subtracting one of its castleHits  or the soldier can kill one of the castle defenders (if there are any) with its rifle.
• After all soldiers have shot,  the total k castle defenders shoot killing k of the soldiers (assuming there are k soldiers, if there are less then the defenders shoot however many soldiers there are and the castle wins the game). 
• If at this point the castle is still up and there are still soldiers, the castle will send defendersPerWave which will add up to whatever defenders are still out from previous rounds. I.e. at the end of each round the castle will send a fresh batch of defendersPerWave as long as castleHits>0.
• Notice that since the soldiers attack the castle by surprise, at the beginning of the first round the castle has not sent any of its defenders out (but it will at the end of the first round).
• The game ends with a win for the soldiers if both the castle and all of its defenders are dead and one or more of the soldiers is alive.
• It ends with a win for the castle if no soldiers are left and either \(castleHits>0\) or the number of defenders is > 0 (or both). 
• The previous point says that it is possible for the castle to win the game even if it has zero castleHits points as long as there are no soldiers left and there are one or more defenders left (presumably the defenders could then rebuild the castle).

We would like to know how fast can the soldiers destroy the castle and all its defenders, i.e. what is the minimum number of days/rounds/waves it takes for the soldiers to win the game.
If the soldiers can not win the game we would still like to know in which round will the castle prevail.
And we would like to keep track of the remaining gameSoldiers, castleHits and total number of defenders at the end of a round (which is the same as at the beginning of the next  round).  This will be, in general, greater than just defendersPerWave since some defenders remain from previous rounds.

REASONABLE SOLUTIONS: Attack the castle first or attack the defenders first

We can try to simulate what happens in each wave like we did in our previous post.
It seems that a possible best strategy to destroy the castle in the minimum number of waves/rounds is the following:

• If the number of soldiers in the wave is greater or equal than the castleHits, we have castleHits of the soldiers shoot at the castle causing it to lose all of its hit points. The remaining soldiers (i.e. \(gameSoldiers - castleHits\)) than shoot at any existing defenders (if \(gameSoldiers-castleHits \geq defenders\) the soldiers win the game in that wave).   
• If the number of soldiers in the wave is smaller than the castleHits but greater than the number of defenders, we have the soldiers eliminate all of the defenders and any remaining soldiers shoot then at the castle (that way the castle defenders can not shoot at the soldiers in that round).
• If the number of soldiers in the wave is smaller than both castleHits and the number of defenders, we have the soldiers shoot at the castle.

An algorithm based on this approach is then (as in our previous post we use the dictionary waveStats with the waves as keys and all quantities we want to track per wave as the values)

 def attackCastle(self,gameSoldiers,castleHits, defendersPerWave):
     totalDefenders = 0
     waveStats = {}
     wave=0
     waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
     wave = 0
     while True:
        wave += 1
        # case a: castleHits <= gameSoldiers
        # gameSoldiers first fire at the castle. 
        # causing castleHits to go to zero;
        # the remaining gameSoldiers - castleHits soldiers 
        # then fire at any defenders
        if castleHits <= gameSoldiers:           
           totalDefenders -= gameSoldiers - castleHits
           castleHits = 0
           if totalDefenders < 0:
               totalDefenders = 0 
        # case b: castleHits > gameSoldiers and gameSoldiers>totalDefenders
        # the soldiers
        # first shoot all the defenders and the remaining
        # soldiers then shoot at the castle 
        elif gameSoldiers > totalDefenders:           
           castleHits -= gameSoldiers - totalDefenders
           totalDefenders = 0
        # case c: castleHits> gameSoldiers and gameSoldiers<= totalDefenders
        # the soldiers shoot at the castle
        else:
           castleHits -= gameSoldiers
        if castleHits < 0:
           castleHits = 0  
        if castleHits == 0 and totalDefenders == 0:
           waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
           return waveStats
        # castle defenders kill as many soldiers
        # as there are defenders
        gameSoldiers -= totalDefenders
        if gameSoldiers <= 0:
            gameSoldiers = 0
            waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
   
            return waveStats
        # castle sends another set of defenders out
        if castleHits > 0:
            totalDefenders += defendersPerWave
        waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
        

Although this simulation algorithm seems reasonable and works often it also fails sometimes. In fact following this strategy it will lead sometimes to the soldiers losing the game when they could win it with a different approach.
Consider for example the case where there are initially 10 gameSoldiers, castleHits=43 and the castle sends 8 defendersPerWave.

• In the first wave, the 10 soldiers reduce castleHits by 10. 
• The second wave starts therefore with 10 gameSoldiers, castleHits=33 and totalDefenders=8. Since \(gameSoldiers>totalDefenders\) and \(gameSoldiers<castleHits\), 8 of the soldiers kill the 8 defenders and the other 2 soldiers reduce castleHits to 31. The castle sends another 8 defenders.
• In the third round again 8 of the soldiers kill the 8 defenders and reduce castleHits to 29. Another 8 defenders are sent out.
• This pattern repeats itself in the 4th (castleHits=27), 5th (castleHits=25), 6th (castleHits=23), 7th (castleHits=21), 8th (castleHits=19), 9th (castleHits=17), 10th (castleHits=15), 11th (castleHits=13), 12th (castleHits=11) and 13th (castleHits=9). 
• In the 14th wave because \(castleHits<gameSoldiers\), the algorithm above makes 9 of the soldiers reduce castleHits to 0 and it makes the remaining soldier kill one of the defenders.
• The 7 defenders then kill 7 of the soldiers. Since the castle is "dead" it will not send any more defenders.
• In the 15th round, the 3 remaining soldiers kill 3 of the 7 defenders and the remaining 4 defenders then kill the 3 soldiers with the win going to the castle. 
• Notice how the castle has crumbled in the 14th wave but it still wins the game because 4 of its defenders remain and all soldiers were killed.

There is however a slightly different strategy that will lead to a win for the soldiers side:

• Everything proceeds as described above up to the 13th wave.
• In the 14th wave, again 2 of the soldiers should shoot the castle leaving it with 7 castleHits points and the other 8 soldiers should kill the 8 defenders. 
• In the 15th wave, 7 of the soldiers vanish the castleHits points and the remaining 3 soldiers kill 3 of the defenders. The remaining 5 defenders will kill 5 of the soldiers. 
• Finally in the 16th wave, the remaining 5 soldiers kill the 5 defenders and win the game.

This is indeed the solution which leads to the minimum number of rounds (16 days/rounds).

Another seemingly good algorithm is one that always has the soldiers killing as many defenders as possible, with the remaining soldiers shooting then at the castle. This would not lead to the correct minimum for the example above: the game would go on to a 15th wave (castleHits=5), 16th (castleHits=3), 17th (castleHits=1), 18th (castleHits=0, all 8 defenders killed and all 10 soldiers standing still). So the soldiers would win but in 18 days/rounds/waves instead of the minimum 16 waves.
Intuitively it is clear that while this approach protects the soldiers from the defenders it is not the fastest possible (in fact it will be the slowest possible). If the question we were trying to solve were "which approach/algorithm leads to the least number of soldiers killed" this would indeed be a good candidate.
In code this algorithm looks like this

def attackDefenders(self,gameSoldiers,castleHits, defendersPerWave):
     totalDefenders = 0
     waveStats = {}
     wave=0
     waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
     wave = 0
     
     while True:
        wave += 1
        # case a: There are (at least) as many totalDefenders
        # as gameSoldiers so the gameSoldiers
        # all shoot at the defenders, then the 
        # remaining defenders shoot back
        if totalDefenders >= gameSoldiers:           
           totalDefenders -= gameSoldiers
           gameSoldiers -= totalDefenders
          
        # case b:There are more gameSoldiers than defenders
        # so the soldiers kill all defenders and the 
        # remaining soldiers shoot at the castle
        elif castleHits >= 0:           
           castleHits -= gameSoldiers - totalDefenders
           totalDefenders = 0
        # case c: There are more gameSoldiers than defenders and
        # castleHits=0. The soldiers shoot all defenders
        # (and win the game)
        else:
           totalDefenders = 0

        if castleHits < 0:
           castleHits = 0 
        
        # soldiers win
        if castleHits == 0 and totalDefenders == 0:
           waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
           return waveStats
      
        # castle wins
        if gameSoldiers <= 0:
            gameSoldiers = 0
            waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
   
            return waveStats
        
        # castle sends another set of defenders out
        if castleHits > 0:
            totalDefenders += defendersPerWave
      
        waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
        # prevent infinite loops
        if wave>50:           
            return waveStats

As this example shows, the simple algorithms we described above do not work for every initial values of gameSoldiers, castleHits and defendersPerWave. We should keep looking.

Before we move on to look at an algorithm that does solve the problem correctly in all cases, lets write down the code we have so far.
The code is organized in 3 files:
castledefense.py: This is where the 2 algorithms above are (encapsulated in class CastleDefenseI) in two methods called attackCastle and  attackDefenders (this one to reflect the fact that the soldiers primarily shoot at the defenders and only then at the castle).
tests.py : This file contains all tests  (encapsulated in class CastleDefenseITest). In particular the example discussed above at length is the last one: test_26. Note how tests.py imports CastleDefenseI in order for each test to be able to access both of the methods attackCastle and attackDefenders .
main.py: This file simply creates a CastleDefenseITest object and runs its runTests method.
If you press run you can see which tests fail and which ones are correctly solved by one or both of the above two algorithms (you will need a little patience to run all 26 tests; if your browser freezes let the script keep running for about 1-2 minutes).
I summarize the results in the following table.
The cells highlighted in red indicate the algorithm predicts the wrong side will win (i.e. the castle will win when in fact there is a minimum number of rounds that lead to a win by the soldiers).
The cells highlighted in cyan indicates the algorithm predicts the correct side wins or ties but it takes more moves/rounds than the minimum.

Test Number	Test Values	Min Rounds	Rounds for attackCastle	Rounds for attackDefenders
0	gameSoldiers=10 castleHits=11 defendersPerWave=15	Soldiers win in 4	Soldiers win in 4	Castle Wins in 3
1	gameSoldiers=3 castleHits=10 defendersPerWave=4	Castle wins in 2	Castle wins in 2	Castle Wins in 3
2	gameSoldiers=2 castleHits=10 defendersPerWave=1	Soldiers win in 9	Soldiers win in 9 (1 soldier standing)	Soldiers win in 9 (2 soldiers standing)
3	gameSoldiers=11 castleHits=12 defendersPerWave=9	Soldiers win in 2	Soldiers win in 2 (11 soldiers standing)	Soldiers win in 2 (11 soldiers standing)
4	gameSoldiers=12 castleHits=32 defendersPerWave=5	Soldiers win in 4	Soldiers win in 4 (12 soldiers standing)	Soldiers win in 4 (12 soldiers standing)
5	gameSoldiers=12 castleHits=44 defendersPerWave=6	Soldiers win in 7	Soldiers win in 7 (10 soldiers standing)	Soldiers win in 7 (12 soldiers standing)
6	gameSoldiers=7 castleHits=10 defendersPerWave=8	Soldiers win in 4	Soldiers win in 4	Castle wins in 4
7	gameSoldiers=4 castleHits=6 defendersPerWave=7	Castle wins in 2	Castle wins in 2	Castle wins in 3
8	gameSoldiers=8 castleHits=10 defendersPerWave=6	Soldiers win in 2	Soldiers win in 2 (8 soldiers standing)	Soldiers win in 2 (8 soldiers standing)
9	gameSoldiers=4 castleHits=5 defendersPerWave=5	Soldiers win in 3	Soldiers win in 3	Castle wins in 3
10	gameSoldiers=5 castleHits=8 defendersPerWave=5	Soldiers win in 4	Soldiers win in 4	Its a tie!
11	gameSoldiers=10 castleHits=50 defendersPerWave=9	Soldiers win in 37	Castle wins in 33	Soldiers win in 41
12	gameSoldiers=19 castleHits=50 defendersPerWave=15	Soldiers win in 8	Castle wins in 6	Soldiers win in 9
13	gameSoldiers=10 castleHits=50 defendersPerWave=10	Soldiers win in 2	Soldiers win in 2	It's a tie!
14	gameSoldiers=8 castleHits=9 defendersPerWave=18	Castle wins in 2	Castle wins in 2	Castle wins in 2
15	gameSoldiers=9 castleHits=11 defendersPerWave=12	Soldiers win in 4	Soldiers win in 4	Castle wins in 3
16	gameSoldiers=5 castleHits=37 defendersPerWave=5	Castle wins in 2	Castle wins in 2	It's a tie!
17	gameSoldiers=9 castleHits=33 defendersPerWave=8	Soldiers win in 22	Castle wins in 18	Soldiers win in 25
18	gameSoldiers=8 castleHits=21 defendersPerWave=7	Soldiers win in 11	Castle win in 8	Soldiers win in 14
19	gameSoldiers=12 castleHits=13 defendersPerWave=50	Castle wins in 2	Castle wins in 2	Castle wins in 2
20	gameSoldiers=7 castleHits=31 defendersPerWave=5	Soldiers win in 13	Soldiers win in 13 (2 soldiers standing)	Soldiers win in 13 (7 soldiers standing)
21	gameSoldiers=19 castleHits=50 defendersPerWave=14	Soldiers win in 7	Soldiers win in 7 (5 soldiers standing)	Soldiers win in 8 (19 soldiers standing)
22	gameSoldiers=20 castleHits=50 defendersPerWave=18	Soldiers win in 12	Castle wins in 8	Soldiers win in 16
23	gameSoldiers=3 castleHits=30 defendersPerWave=1	Soldiers win in 15	Soldiers win in 15 (2 soldiers standing)	Soldiers win in 15 (3 soldiers standing)
24	gameSoldiers=2 castleHits=50 defendersPerWave=1	Soldiers win in 49	Soldiers win in 49 (1 soldier standing)	Soldiers win in 49 (2 soldiers standing)
25	gameSoldiers=9 castleHits=43 defendersPerWave=7	Soldiers win in 17	Castle wins in 16	Soldiers win in 18
26	gameSoldiers=10 castleHits=43 defendersPerWave=8	Soldiers win in 16	Castle wins in 15	Soldiers win in 18

Here are some interesting facts we can glance from this table:

• There are a few tests in which both algorithms agree with the minimum number of rounds (soldiers win) but the attackDefenders algorithm always leaves more soldiers alive than the attackCastle approach.
• If the castle wins it wins in 2 rounds always.
• When the castle wins, the attackCastle algorithm always predicts correctly the castle win in 2 rounds.
• The attackDefenders algorithm also predicts correctly that the castle wins but sometimes it takes 3 rounds.
• When the attackCastle algorithm predicts the soldiers win it always takes the minimum number of rounds (and therefore it is always correct in those cases). The attackDefenders algorithm will in several tests require more rounds for the soldiers to win.
• The attackDefenders algorithm will sometimes lead to a tie (in tests 10, 13 and 16) while the attackCastle will never lead to a tie. If you look at the algorithm code you will notice a condition at the very end of the infinite loop

  # prevent infinite loops
  if wave>50:           
     return waveStats 

  to prevent the loop of never ending in cases where there is a tie.

Both algorithms make mistakes but it is clear that overall the attackCastle method is better (makes less errors) at predicting the minimum number of days/rounds it takes for the soldiers to win.

In our next post we will look at a couple of approaches/algorithms that solve this problem correctly always.

Tower Defense I

Most of us have played, have heard or have seen somebody play a Tower Defense style game. 
The list of such games is very large: Bloons Tower Defense, Plants vs Zombies, Kingdom Rush, PixelJunk Monsters, Defense Grid, geoDefense, Jelly Defense, Dungeons Defenders and on and on.
Hopefully you’ve spent some quality time setting up your defenses, killing enemies and advancing through several rounds/waves.

The basic idea of these strategy/turn based games is simple: The game progresses in rounds/waves. In each round your opponent (usually the computer) has a certain number of "soldiers" that traverse a maze along which you sprinkle, in strategic locations, one or more "towers" (how many towers you place depends typically on how many you can afford, since each tower will have its own price).
The towers will fire at the approaching soldiers; it might take one or several hits to kill a soldier (you earn "money" with each successful hit).
The goal of the towers is to prevent any of the soldiers to reach the exit of the maze. Each soldier that leaves the maze will cause you to lose one life.

In this post we will consider a simple version/variant of the game. 

Lets suppose the game starts with gameTowers towers, and gameSoldiers soldiers.

Each tower can kill numKills soldiers per round (one hit one kill) and can sustain numHits before the tower crumbles. 

Each soldier in turn can hit one random tower per round causing that tower to lose one of its numHits. More than one soldier can hit the same tower in the same round.

The game proceeds in the following manner: for a given wave/round each soldier will hit a tower. When all soldiers have done so, each tower will then hit numKills soldiers. If there are any soldiers and towers left, the game moves to the next wave. Otherwise if there are only soldiers/towers left, the soldiers/towers win. 

One last important detail: At the start of each new round the surviving towers will get reloaded with numKills. Those are fully spent within the round when it is the towers turn (if there are enough soldiers; the towers can only shoot one of their numKills per soldier; if there are not enough soldiers to shoot at, that will be the last round and the towers win the game). The damage they suffer however carries over from round to round. I.e. all towers start the game with numHits but those will decrease from round to round (and within the same round) for those towers hit by the soldiers.

Given these rules and the 4 constants gameSoldiers, numHits, numKills, gameTowers we would like to know how fast can the soldiers destroy the towers or if that is not possible (i.e. if the towers will win). 

In which round all the soldiers/towers will be destroyed and how many soldiers/towers are left in that round? If only towers are left we would also like to know how many hits and kills each of them has left. (It is not possible for the game to end with a tie.)

We can go one step further and ask how many towers and soldiers are left after each wave/round. We can gather this information in a dictionary where the keys are the wave number and the values are a list of the values we are interested in tracking after the end of each round. We will call this dictionary waveStats.

An Algorithm to Maximize the number of Towers destroyed

A simple algorithm that maximizes the number of towers destroyed is the following

 def attack(self, gameSoldiers, numHits, numKills, gameTowers):
        totalHits = numHits * gameTowers
        gTowers = gameTowers
        gSoldiers = gameSoldiers
        waveStats = {}
        wave=0
        waveStats[wave] = {'gameSoldiers':gameSoldiers,
                           'gameTowers':gameTowers,
                           'numHitsLeft':numHits*gameTowers,
                           'numKillsLeft':numKills*gameTowers}
        
        # keep iterating as long as there are towers and soldiers
        while totalHits>0 and gSoldiers>0:
            wave += 1
            # first the soldiers fire
            totalHits -= gSoldiers 
            # break if no tower is left
            if totalHits <=0:
                waveStats[wave] = {'gameSoldiers':gSoldiers,
                           'gameTowers': 0,
                           'numHitsLeft': 0,
                           'numKillsLeft': 0}
                break   
            # then the towers fire
            gTowers = (totalHits + numHits-1)/numHits
            
            if gSoldiers > numKills * gTowers:
                gSoldiers -= numKills * gTowers
                waveStats[wave] = {'gameSoldiers':gSoldiers,
                           'gameTowers':gTowers,
                           'numHitsLeft':totalHits,
                           'numKillsLeft':0}
            else:
                waveStats[wave] = {'gameSoldiers':0,
                           'gameTowers':gTowers,
                           'numHitsLeft':totalHits,
                           'numKillsLeft': numKills* gTowers - gSoldiers}
                gSoldiers = 0
                                   
        return waveStats

The idea of the algorithm is simple:
We compute the number of total hits the towers can take. That number is initially the product of each tower's hits by the number of towers.
Then as long as the number of total hits is greater than zero and the number of soldiers is also greater than zero (if one of these is zero or smaller than zero the game is over) we perform round after round of the game (each iteration of the while loop is one wave/round of the game).

In each round, first the soldiers still alive (gSoldiers) fire removing \(gSoldiers\) hit points from the total of hits available.
Then the towers still available (gTowers) shoot back killing \( numKills * gTowers\) and leaving \(gSoldiers - numKills * gTowers\) soldiers for the next round.

If however \(numKills * gTowers\) is greater than \(gSoldiers\), then the towers will only shoot \(gSoldiers\) and keep the remaining \(numKills * gTowers - gSoldiers\) (this will only happen in the last round of a game won by the towers).

A final note on how we compute the number of towers (gTowers) available after the soldiers shoot on each round.  Intuitively we would divide the number of hits available by the number of hits per tower
$$gTowers = \frac{totalHits}{numHits}$$.

This works if  totalHits is a multiple of numHits. If it is not a multiple it will give us a smaller number of towers. For example consider \(totalHits=11\) and \(numHits=5\). Doing \(totalHits/numHits=2\) but obviously there are 3 towers (2 that can take 5 hits each and 1 tower that can only take 1 hit) not 2. Similarly if \(totalHits=4\) and \(numHits=5\) we get \(totalHits/numHits=0\) but again there is 1 tower (that can take 4 hits points) instead of 0 towers. We see that this division always under-counts the number of towers by one when the two numbers are not divisible.

If we instead add \(numHits -1\)  to \(totalHits\) before dividing the whole thing by \(numHits\) we will be guaranteed to round the division by one. For the example above  \(totalHits=11\) and \(numHits=5\) we get \((totalHits + numHits -1)/numHits=(11+4)/5=3\). And if \(totalHits=4\) and \(numHits=5\) we get \((totalHits + numHits -1)/numHits=(4+4)/5=1\).

It is important to notice that the number of towers destroyed can vary enormously.
For example imagine we have 2 towers with 4 hits each and 3 kills each and we have 5 soldiers. The 5 soldiers could shoot one of the towers twice and the other three times. Both towers would stay alive and would then kill the 5 soldiers in the first round.
In the approach we just presented, the soldiers will shoot one of the towers 4 times thus destroying it and shoot the second tower once (from our discussion above \(gTowers = (3+3)/4=1\) is the number of towers at the end of the first round). That tower will go on to kill 3 of the soldiers and the game would go on to a second round where the remaining tower would still kill the remaining soldier.
In other words in the algorithm we presented the soldiers will always destroy (in each round) the maximum number of towers they can. Take some time convincing yourself that this is the case.

Below is the code. Press the Run button to execute the examples. It might take 3 or 4 minutes to run all 19 examples. Be patient and you will be rewarded (you can also delete/comment out a few of the tests in the all_tests list of the run_tests method and thus shorten the runtime quite a bit).

Lets look at the first test result

Executing test 0
Starting numbers
----------------
Number of Soldiers: 13
Number of Towers: 8
Total hits left: 16 (2 and 0 per tower)
Total kills Left: 24 (3 and 0 per tower)
                                            
End of Wave 1
Number of Soldiers: 7
Number of Towers: 2
Total hits left: 3 (2 and 1 per tower)
                                            
End of Wave 2
Number of Soldiers: 7
Number of Towers: 0
Total hits left: 0 (0 and 0 per tower)
                                            
Soldiers win in 2 rounds

We start with 13 soldiers and 8 towers. Each tower can take 2 hits (16 total) and can kill 3 soldiers per round (24 total). In the first wave, the 13 soldiers destroy 6 of the towers and leave 2 towers one with 2 hits left and another with 1 hit left. These two towers then kill 6 soldiers leaving 7.
In the second wave those 7 soldiers destroy easily the remaining two towers winning the game in two rounds.

You can also run some of the tests graphically using the game below. We will come back to this game in a future post.
One thing that you might notice (in particular in test 11) is that  for some tests the result of the game is not the same!
If you run the last test a few times, the towers will win most of the times. There will be however a few times in which the soldiers will win. 
This happens because the towers are placed randomly. Thus although most of the times the soldiers shoot at the closest tower sometimes two or more towers are within the same range of closeness to the soldier and therefore the soldiers shooting does not result in the maximum number of towers being destroyed in one wave. Instead the soldiers will spread their bullets evenly over two or three close towers leading to an extra tower to survive to the next round. In that case enough towers might survive each round that the towers have enough firepower to finally win.
Wins by the soldiers will happen when the towers are placed such that the soldiers shooting results in maximal number of towers destroyed. 

 An Algorithm to Minimize the number of Towers destroyed

 It is interesting to consider the opposite case in which the soldiers try to destroy the least number of towers in a given round. Of course that is not in their interest but it is very much in the towers interest. Because the towers can only shoot after the soldiers they are at a disadvantage and will be happy to accept any give away.

Intuitively, to achieve this, the soldiers should spread their shots through all the towers (or as many towers as possible) instead of focusing their aim in as few towers as possible to destroy those few towers.
Lets consider the three different cases:

a) \(gameSoldiers = gameTowers\)

Soldiers should shoot each tower equally in the first round. If \(numHits=1\) then all towers are killed. Otherwise since  \(numKills>0\) the towers will then kill all soldiers in the first round (because \(numKills * gameTowers = numKills * gameSoldiers \geq  gameSoldiers\)).
So this strategy guarantees the soldiers defeat every time in the first round if \(numHits>1\)!
In fact in this case there is no way the soldiers can ever win even if they destroy the highest number of towers they can in each round. All they can do is prolong the game a few extra rounds: consider 2 towers, 2 soldiers, 2 numHits per tower and 1 numKills per tower. If the 2 soldiers destroy one of the towers then the remaining tower will leave one soldier and the game goes an extra round before that soldier is also killed.
Here it is a "proof" that the towers always win if \(numHits>1\) no matter the soldiers strategy:

• The number of towers destroyed in the first round is \(gameSoldiers/numHits=gameTowers/numHits\). The number of towers that remain is then \(gameTowers-gameTowers/numHits=gameTowers(numHits-1)/numHits=gameSoldiers(numHits-1)/numHits\). These remaining towers will then kill \(numKills*gameSoldiers(numHits-1)/numHits\) soldiers. This is smallest when \(numKills=1\). Lets assume that is true in the following.
• At the start of the second round \(gameSoldiers/numHits\) soldiers are left and \(gameSoldiers(numHits-1)/numHits\) are left. If  \(numHits>1\) this is half or less of the soldiers. Lets assume then \(numHits=2\) in order to maximize the number of soldiers. This will minimize the number of towers as well. So we have in the second round \(gameSoldiers/2\) soldiers and towers (each tower with 2 numHits and 1 numKills). We are then in the same situation we started with (i.e. the same number of soldiers and towers) so we repeat the reasoning. The towers and soldiers are halved to \(gameSoldiers/4\) entering the third round.
• In general entering the \(nth\) round there will be \(gameSoldiers/2^{n-1}\) soldiers and towers.
• Eventually there will be a round where only 1 soldier and 1 tower are left (assume for simplicity that \(gameSoldiers=2^{n-1}\) so this will happen in round \(n\)). The soldier can shoot off one of the 2 numHits left and the tower will then kill the soldier. Game over!

b) \(gameSoldiers < gameTowers\)

In this case the \(gameSoldiers\) should shoot \(gameSoldiers\) towers. Assuming that \(numHits>1\), all towers survive and given that \(numKills>0\) they kill all soldiers in the first round.
If \(numHits=1\) on the other hand  it is possible that even with this bad strategy the soldiers will win sometimes: Suppose the game starts with 4 towers each with \(numHits=numKills=1\) and there are 3 soldiers. The soldiers kill 3 towers. The remaining tower kills one soldier and it is then killed in the second round by one of the remaining two soldiers.

c)  \(gameSoldiers > gameTowers\)

It is harder to find a strategy that minimizes tower destruction consistently. If \(numHits=1\) then the soldiers win right away.
Otherwise if \(gameSoldiers/gameTowers = n\) (\(n\) being an integer) we can consider two cases:

• If  \(n>=numHits\) the soldiers win right away. 
• If \(n<numHits\) lets suppose n=2. Then at least half the soldiers are killed in the first round (if \(numKills=1\); if \(numKills>1\) more than half of the soldiers will be killed in the first round). The second round starts then with at least an equal number of soldiers and towers  or more towers than soldiers and we fall in one of the previous two cases. If n=3 at least one third of the soldiers are killed in the first round (if \(numKills=1\)). The start of the second round is the same as the case n=2. Similarly for \(n=4,5,...\) we can always reduce the problem to \(n-1\) but starting at a later round. Thus if \(n=10\) we know that the start of the second round can be reduced to the case \(n=9\), the start of the third round can be reduced to the case \(n=8\) and so on until the start of the ninth round can be reduced to the \(n=2\) case.

We will leave to the reader to analyze the case were \(gameSoldiers/gameTowers\) is not an integer.

This last section was intended to make us think a bit beyond the initial problem posed (how fast can the soldiers destroy the towers). Our analysis was not completely rigorous but it did provide a way to understand what the game outcome is depending on the relation between \(gameSoldiers\) and \(gameTowers\). The important takeaway is that it is useful to break a problem in steps and sometimes reduce some of those steps to previous steps that we are able to solve/reason about.