The problem of the best selection

Creating a Warhammer 40k army using Linear Programming

Photo by WTFast on Unsplash

Hello!

Last week I wrote a small article where I showed how to use the Python PuLP library to solve a Linear Programming problem (you can read it here). After writing the article, I was wondering if I could use the same script to solve more problems while also providing more examples of Linear Programming, and I decided to model what I consider an interesting problem that I call the Best selection problem (don’t search, I invented it!), but it really is the same problem as we seen in the shopping aggregator problem.

Let us consider that there is a pool of resources P, with n resources p1,p2,…,pn. Each of these resources has a non-negative value and a different performance attribute, expressed in the form of a vector c, such that we can express them as a function f(P)=cp1+cp2+…+cpn. And let us consider also that we have a set of different constraints over these resources P, that is a matrix A, and an array b. I just defined a generic linear problem, and don’t worry if it seems a bit difficult, let us use an example I think fits perfectly with this problem: Warhammer 40k.

In the grim darkness of the future there is only math. Ultramarines army (picture from author’s collection).

Warhammer 40k

Warhammer 40k is a wargame that I love, and as much as I want to talk about it, let’s focus on theme of the post. In Warhammer 40k (abbreviated as W40k) there exists many different factions, grouped in 3 categories: Imperium, Chaos and Xenos (aliens). Each player can create his army from a list of available troops for each faction, filling detachment roles such as the HQ, basic troops, elites, vehicles, fast attack units and so on. Also, every unit has a range of weapons available, suitable for different situations (long range, close quarters combat, etc…). Each unit and weapon has its own statistics and value, measured in points, and in a matched play, the most common way to play, each player must have a similar number of points.

Personally, I own two armies that I collected over some years: an Ultramarine, and a Death Guard, which I usually play with. I tried to collect at least one unit of each available for the Death Guard, but I’m still missing some units. I will use this army as example for the rest of the post, so beware of some names that may seem a bit…repulsive. The problem, formulated as a question is, given the units and weapons available for each army, and the number of points, which would be the best selection of troops to play a matched game?

Maximizing the objective function

Before answering this question, let us model this as a Linear Programming problem, as indicated above. We start by considering the set of resources P, as the different units available in the army:

P = [ChaosLord, ChaosLordTerminator, DaemonPrinceNurgle, LordContagion, MalignantPlaguecaster, Sorcerer, SorcererTerminator, Typhus, ChaosCultists, PlagueMarines, Poxwalkers,...]

We refer to each element of P, pn as a variable, and the variables depicted above are only a sample of the available troops (HQ and troops, to be exact). Next, we need to obtain the values of c, containing the constants to form the objective function f(P)=cp1+cp2+…+cpn we want to maximize or minimize. In this case, we should consider as the elements in c, the damage every unit can cause to the enemy, so we want to maximize the function f(P).

Obtaining these values is not trivial, as there are statistics and dice rolling to be considered in a game of W40k. So, with that in mind, I created a small combat simulator for W40k, where I enter the statistics for the unit, the weapon the unit is using, and the statistics of the defending unit. For example, consider a unit of 5 Plague Marines (like the space marines, but carrying plagues, diseases and more resistant to damage), fielding 3 marines with bolters and 2 with Blightlaunchers:

Histogram of the damage for each weapon individually, and the total for 1000 shoots against a standard Space Marine unit.

        Bolter_1 Bolter_2 Bolter_3  Blight_1    Blight_2    Total
count   1000.00  1000.00  1000.00   1000.00     1000.00     1000.00
mean      0.23     0.23     0.21    1.20        1.20        3.08
std       0.46     0.46     0.43    1.46        1.50        2.23
min       0.00     0.00     0.00    0.00        0.00        0.00
25%       0.00     0.00     0.00    0.00        0.00        1.00
50%       0.00     0.00     0.00    1.00        1.00        3.00
75%       0.00     0.00     0.00    2.00        2.00        4.00
max       2.00     2.00     2.00    6.00        6.00       10.00

Notice that the 3 bolters cause no damage on 80% of the shoots (due mainly to the defensive stats of the Space Marines), but the blightlauncher is able to cause a lot more damage. After executing this script for some units, I discovered a website that performs this calculations: Mathhammer, so I use it to create the values of c, remember that c is the damage every unit can cause, that we want to maximize. A quick note before continuing: there are a lot of units that can cause a heavy impact on the battlefield, while some units seem unable to damage anything (like the bolter example above) and have damages around 0. To avoid any miscalculation and rounding to 0, I decided to scale the different damages to have the minimal damage that a unit can cause set to 1 (Poxwalkers) and the maximum to 100 (Typhus, and the Deathshroud and his scythes).

With the damage vector c computed in the fashion explained above, and the variables in P, we multiply them and we have modeled f(P):

Objective function:
f(P) = 11*elites_BiologusPutrifier + 25*elites_BlightlordTerminators + 47*elites_DeathshroudTerminator + ... + 4*troops_ChaosCultists + 52*troops_PlagueMarines + troops_Poxwalkers

Death guard with their Primarch Mortarion. (picture from author’s collection)

Adding restrictions

Now, we must create the matrix of restrictions A, and the vector b. To do so, we must consider the notion of detachment. A detachment in W40k is a selection of troops that gives some extra benefits if all roles are correctly filled. For example, one of the most common is the patrol detachment, that requires at least a choice of HQ and a maximum of 2 HQ, and one choice of troops up to 3. You can fill other roles that are optional like elites, heavy support or fast attack. So the matrix A,b will have to reflect these restrictions, for example for the HQ:

Restriction: 
hq_ChaosLord + hq_ChaosLordTerminator + hq_DaemonPrinceNurgle + hq_LordContagion + hq_MalignantPlaguecaster + hq_Sorcerer + hq_SorcererTerminator + hq_Typhus >= 1
Restriction:
hq_ChaosLord + hq_ChaosLordTerminator + hq_DaemonPrinceNurgle + hq_LordContagion + hq_MalignantPlaguecaster + hq_Sorcerer + hq_SorcererTerminator + hq_Typhus <= 2

where A correspond (aprox.) to the left side of the inequalities and b to the right side. Right now there is only one thing left, that is, the points value. A matched game consists on two players fielding a number of units that add to the maximum points allowed, for example 1000 points of minis. So we can extend A and b to include this restriction:

Restriction: 
175*hq_Typhus + ... + 40*troops_ChaosCultists + 123*troops_PlagueMarines + 60*troops_Poxwalkers <= 1000

Now we have modeled the problem of the best selection. And it is time to solve it. As with the other post, we use Python and PuLP to solve it, and this is the result:

elites_Helbrute = 1               # 72 points
fastattack_FoetidBloatDrone = 1   # 99 points
heavysupport_ChaosPredator = 1    # 90 points
heavysupport_Defiler = 1          # 152 points
hq_DaemonPrinceNurgle = 1         # 146 points
hq_Typhus = 1                     # 175 points
troops_PlagueMarines = 2          # 123*2 points
Objective = 605
Total cost: 980

The Objective number is irrelevant to us, because of the scaling we performed on the damages of the different troops, however it is interesting to analise the resulting army, because I often use a similar army (I do not have a Chaos Predator tank, however I love the Defiler) with small changes.

Conclusions

The results obtained show the created list as a very similar to the list I use, and is a completely viable army. I must note that I only considered the rules of the 8ed of the game (currently is in its 9 edition), and only the points and damages considered in the Codex: Death Guard book released some time ago, hence some information may be different if you update the points and the damages. Finally, I also considered the damage isolated from buffs that some units grant to allied units nearby. This will be adressed in the next post, I promise!

The code I use is available here.

I love playing W40k, and the hobby related to it (collecting, assembling and painting the minis), and I really love when I can bring together computer science and games. I hope you read this post and you like it!

Stay safe!