Wizards, Giants, Linear Programming and Sage

I've been playing a game on my phone for a couple of months now called Clash of clans. It's one of those freemium games that tells me to do something on my phone every now and then:

In essence during the game you build your base with buildings to obtain resources, create troops and defend against attacks.

Here's a screen shot of my base at the moment:

As well as building your base, you can also put together a raiding party and attacking other bases.
In this post, I'll describe the use of a mathematical technique called linear programming so as to get the best combination of Giants, Wizards etc in a raiding party.

To train a warrior costs Elixir (a resource that you mine and/or plunder) but also costs space in your army camps.

Here are the various warriors available to me at the moment (as you build better buildings you get more warriors etc...).

1. Barbarian (Damage per second: 18, Hitpoints: 78, Housing Space: 1, Elixir Cost: 80):

2. Archer (Damage per second: 16, Hitpoints: 33, Housing Space: 1, Elixir Cost: 160)

3. Goblin (Damage per second: 19, Hitpoints: 36, Housing Space: 1, Elixir Cost: 60)

4. Giant (Damage per second: 24, Hitpoints: 520, Housing Space: 5, Elixir Cost: 2000) 

 5. Wall Breaker (Damage per second: 32, Hitpoints: 35, Housing Space: 2, Elixir Cost: 2500)

6. Balloon (Damage per second: 72, Hitpoints: 280, Housing Space: 5, Elixir Cost: 3500)

7. Wizards (Damage per second: 125, Hitpoints: 130, Housing Space: 4, Elixir Cost: 3000)

8. Healer (Damage per second: NA, Hitpoints: 600, Housing Space: 14, Elixir Cost: 6000)

9. Dragon (Damage per second: 140, Hitpoints: 1900, Housing Space: 20, Elixir Cost: 25000)

To summarise the information about the players I'm going to put the costs in a vector \(c\) and the housing space in a vector \(h\) (indexed using the same order as the images above):

\[c=(80,160,60,2000,2500,3500,3000,6000,25000)\]
\[h=(1,1,1,5,2,5,4,14,20)\]

Currently I have a capacity of 50 housing spaces per camp and I have 4 camps so I have an upper bound on the total amount of housing space of \(K=200\).

If I let the vector \(x\) denote a raiding party so that \(x_i\) is the number of warriors of type \(\i) (using the ordering above) then we have the corresponding housing space constraint:

\[\sum_{i=1}^9h_ix_i\leq K\]

I can now try and do two things:

1. Get a full set of camps by minimising the overall cost.
2. Get the most powerful raiding party that can fit in my camps.

I will solve both of these problems using what is called Integer Linear Programming. The integer part of that is due to the fact that I must have whole parts of warriors.

1. Minimising my costs

The cost of a given rading party \(x\) is given by:

\[C(x) = \sum_{i=1}^9c_ix_i \]

Thus to minimise this cost and fill the camps we need to solve the following minimisation problem:

\[\text{minimise }C(x) = \sum_{i=1}^9c_ix_i\]

such that:

\[H(x)=\sum_{i=1}^9h_ix_i= K\]
and
\[x_i\in\mathbb{Z}_{\geq0}\]

How do we solve this? I've blogged about a similar type of optimisation problem that I use to schedule my class assessment and for that I used the awesome sagemath. You can read that blog post here. Here I will do the same thing.

The following Sage code is what is needed to create the linear program and also obtain the solution:

# Set up parameters:
K = 200  # Set the upper bound
c = [80,160,60,2000,2500,3500,3000,6000,25000] # The the cost vector
h = [1,1,1,5,2,5,4,14,20]  # Set the 'housing space' constraints vector
n = len(c)  # Get the number of warriors

C = lambda x: sum([x[i]*c[i] for i in range(n)])  # Define the cost function
H = lambda x: sum([x[i]*h[i] for i in range(n)])  # Define the housing capacity function

# Create and solve the optimisation problem
p = MixedIntegerLinearProgram(maximization=False)  # Create an optimisation problem with minimization as the goal
x = p.new_variable(integer=True)  # Create a variable with the requirement that it must be integer
p.add_constraint(H(x)==K)  # Set the housing constranit
p.set_objective(C(x))  # Set the objective function
p.show() # Show the optimisation problem
p.solve()  # Solve the optimisation problem

# Solve the optimisation problem

print 'Has solution:' 
for i, v in p.get_values(x).iteritems(): 
    print 'x_%s = %s' % (i, int(round(v))) 
print 'Housing spaces used: %s' % H(p.get_values(x))

The output is (disappointing but expected): \(x=(0,0,200,0,0,0,0,0)\) which implies that I should have 200 Goblins.

If you're familiar with the game this is not a very sensible way to go as Goblins are really only good at getting loot from defenceless bases.

We can add a couple more constraints so that we don't have too many goblins (let's limit it to 10) and also so that we have at least one healer:

p = MixedIntegerLinearProgram(maximization=False)  # Create an optimisation problem with minimization as the goal
x = p.new_variable(integer=True)  # Create a variable with the requirement that it must be integer
p.add_constraint(H(x)==K)
p.add_constraint(x[2]<=10)  # Don't want more than 10 goblins
p.add_constraint(x[7]>=1)  # Want 1 healer at least
p.set_objective(C(x))
p.show()
p.solve()
print 'Has solution:'
for i, v in p.get_values(x).iteritems():
    print 'x_%s = %s' % (i, int(round(v)))
print 'Housing spaces used: %s' % H(p.get_values(x))

This gives us \(x=(176,0,10,0,0,0,0,1,0)\).

This is again not very satisfying as we're basically filling our raiding party with the cheapest options. That was the purpose of this approach though. 

The next thing we'll look at is how to actually get a good raiding part.

2. Getting the 'best' raiding party.

As you can see on the images, every warrior is different: some fly, some are better against buildings, some have more hitpoints than others etc...

One way of getting the 'best' raiding party could be to maximise the damage per second of the raiding party. To do this, let's define the following vector (which is just the damage per second that can be read off of the images above):

\[d=(18, 16, 19, 24, 32, 72, 125, 0, 140)\]

Now our maximisation problem can be written as:

\[\text{maximise } \sum_{i=1}^9d_ix_i\]

such that:

\[H(x)=\sum_{i=1}^9h_ix_i\leq K\]
and
\[x_i\in\mathbb{Z}_{\geq0}\]

Here's the Sage code to do this:

damagepersecond = [18, 16, 19, 24, 32, 72, 125, 0, 140]
C = lambda x: sum([x[i]*damagepersecond[i] for i in range(n)])

p = MixedIntegerLinearProgram()  # Create an optimisation problem with minimization as the goal
x = p.new_variable(integer=True)  # Create a variable with the requirement that it must be integer
p.add_constraint(H(x)<=K)
p.add_constraint(x[2]<=10)  # Don't want more than 10 goblins
p.add_constraint(x[7]>=1)  # Want 1 healer at least
p.set_objective(C(x))
p.show()
p.solve()
print 'Has solution:'
for i, v in p.get_values(x).iteritems():
    print 'x_%s = %s' % (i, int(round(v)))
    print 'Housing spaces used: %s' % H(p.get_values(x))

The result of the above is \(x=(0,0,2,0,0,0,46,1,0)\). I.e take 2 goblins, 46 wizards and 1 healer.
The problem with this raiding party is that wizards are actually quite fragile (archers towers and cannons can pretty much just pick them off).

So perhaps instead of maximising the damage per second we could maximise the total hit points of the party.

To do this we need to define the vector of hitpoints:

\[p=(78, 33, 36, 520, 35, 280, 130, 600, 1900)\]

Now our maximisation problem can be written as:

\[\text{maximise } \sum_{i=1}^9p_ix_i\]

such that:

\[H(x)=\sum_{i=1}^9h_ix_i\leq K\]
and
\[x_i\in\mathbb{Z}_{\geq0}\]

This gives us \(x=(0,0,0,0,93,0,0,1,0)\): a raiding part of wall breakers.

The problem with this is that wall breakers are good for just that: breaking walls. They carry a bomb up to a wall and then they explode. So let's add some more constraints to our optimisation problem so as to get something a bit more useful.

• Let's make sure that we always have at least 20 housing capacity worth of distance attackers (Archers or Wizards):

\[x_1h_1+x_6h_6 \geq 20 \]

• Let's ensure that we have at least 1 air attacker (so that once the air defenses are out of the way we can finish off the base):

\[x_5+x_8\geq1\]

• Let's ensure that we always have some wall breakers to clear the walls for our ground units (1 per 5 giants and 1 per 20 barbarians say):

\[5x_4\geq x_3\]

\[20x_4\geq x_0\]

The code to solve this is given here:

p = MixedIntegerLinearProgram()  # Create an optimisation problem with minimization as the goal
x = p.new_variable(integer=True)  # Create a variable with the requirement that it must be integer
p.add_constraint(H(x) <= K)
p.add_constraint(x[2] <= 10)  # Don't want more than 10 goblins
p.add_constraint(x[7] >= 1)  # Want 1 healer at least
p.add_constraint(x[1] * h[1] + x[6] * h[6]>=20)  # Want at least 20 capacity worth of distance attackers
p.add_constraint(x[5] + x[8]>=1)  # Want at least 1 of air attackers
p.add_constraint(5 * x[4] >= x[3])  # Want at least 1 wall breaker per 5 giants
p.add_constraint(20 * x[4] >= x[0])  # Want at least 1 wall breaker per 20 barbarians
p.set_objective(C(x))
p.show()
p.solve()
print 'Has solution:'
for i, v in p.get_values(x).iteritems():
    print 'x_%s = %s' % (i, int(round(v)))
print 'Housing spaces used: %s' % H(p.get_values(x))

This gives \(x=(1,20,0,23,5,0,0,1,2)\): so take 1 Barbarian, 20 Archers, 23 Giants, 5 Wall Breakers, 1 Healer and 2 Dragons.

The above would give us the most hit points but now we're missing out on the damage power of wizards.

Perhaps we could try and balance both hitpoints damage.

In essence we have what's called a multi objective optimisation problem. One approach to solve this is to simply weight both objectives.

We're going to use \(\alpha\) to denote the importance of the hitpoints and \(1-\alpha\) the importance of the damage.

Our optimisation function then becomes:

\[\alpha\sum_{i=1}^9p_ix_i+(1-\alpha)\sum_{i=1}^9d_ix_i\]

Using the same constraints as before and taking \(\alpha=.5\) (so that both damage and hit points have equal weighting) we get \(x=(11,0,0,25,5,0,5,1,1)\). Thus we should be taking in to battle: 11 Barbarians, 25 Giants, 5 Wall Breakers, 5 Wizards, 1 Healer and 1 Dragon.

This feels much more balanced than anything we've had so far and not far off what I've been using as my own raiding party.

Given that everything is nicely coded we can quickly obtain the make up of the optimal raiding party for a range of values of \(\alpha\):

We see that as \(\alpha\) increases (so that we care more about hit points) the number of Wizards we should use slowly decreases (at one point the constraint for ranged attacking units kicks in and we replace the Wizards with Archers).

You could easily tweak the constraints to perhaps ensure your party always has some Goblins or otherwise. I think this is a nice example where a mathematical model can be used to solve a problem but at the same time must not be taken far from the problem itself. There might be some players who only choose to attack bases with a particular type of defence so they can tweak/add constraints to the problem accordingly.

Feel free to play around with the code in the Sage cell below:

The mathematical techniques used in this post rely on Linear Algebra, Higher Dimensional Geometry and obviously the ability to write code :)

(On another note I'm still not in a clan on the game so if anyone has any space in a clan let me know!)