Revisiting the problem of the best selection

Using Genetic algorithms to create a Warhammer 40k army

Photo by National Cancer Institute on Unsplash

Hello!

In the last post, we explained how to select an army of Warhammer 40K (W40K) using Linear Programming (you can read it here), but there was one thing I did not explain, and I promised to adress in the next post: how selecting some units might affect others. For example, in W40K, selecting a good HQ unit grants benefits, like extra dice rolls and increased chances of hitting the enemy. It is absolutely possible to express this in Linear Programming by adding extra restrictions and modifying the objective function. However this will increase dramatically the number of equations, making the problem more cumbersome and difficult to solve. In this post, we start by explaining how to add these restriction in Linear Programming, then we revisit the selection problem, but we will use Genetic Algorithms to obtain good selections.

Adding Extra restrictions

We want to include in the Linear model the extra damage caused when selecting a unit that grants extra benefits. So, let us consider the objective function f(P) of the W40K problem again as it was modeled:

Objective function:
f(P) = ... + 4*troops_ChaosCultists + 52*troops_PlagueMarines + troops_Poxwalkers

We cannot modify the vector c (c is for constants) but we can add another unit of every troop that is affected by this extra ability, updating the corresponding damage vector c (remember that the vector c is scaled):

Objective function:
f(P) = ... + 4*troops_ChaosCultists + 52*troops_PlagueMarines + troops_Poxwalkers + 5*troops_extra_ChaosCultists + 55*troops_extra_PlagueMarines + 2*troops_extra_Poxwalkers

Now, we must add restrictions to ensure that if an enhanced troop is selected, it must also select the HQ unit that grants the benefit, and if we have selected a troop, it is incompatible to select the troop and its extra (enhanced) version:

Restriction:
hq_ChaosLord >= troops_extra_ChaosCultists
hq_ChaosLord >= troops_extra_PlagueMarines
hq_ChaosLord >= troops_extra_Poxwalkers
troops_extra_ChaosCultists + troops_extra_PlagueMarines + troops_extra_Poxwalkers >= hq_ChaosLord
troops_ChaosCultists + troops_extra_ChaosCultists <= 1
troops_PlagueMarines + troops_extra_PlagueMarines <= 1
troops_Poxwalkers + troops_extra_Poxwalkers <= 1

The restrictions above will work as follows: if we select one troop of any of the units that have an extra damage, the hq_ChaosLord that grants its benefit must also be selected. Similarly, if we select the Chaos Lord as a choice of HQ, troops with the extra benefit must be also selected (at least 1). And finally, there could be at most one of the troops (if selected).

One can easily see that adding extra benefits on top of benefits can lead to a very large set of restrictions, thus making the problem harder to solve. Fortunately, we will see a technique that can help us to consider the benefits, at the cost of the completeness and soundness of the selection: Genetic Algorithms.

Thomas Splettstoesser (www.scistyle.com), CC BY-SA 4.0 <https://creativecommons.org/licenses/by-sa/4.0>, via Wikimedia Commons

Genetic Algorithms

Genetic research inspired this family of computer science algorithms, that claims that by making small changes to an input, one can achieve a good result. These algorithms are rooted in biology and sexual reproduction. It is outside the scope of this post to discuss the biology foundations, but I’ll try to give an overview. Akin to sexual reproduction, we have a population of chromosomes, that can represent different states. Each one of these chromosomes has a value, called fitness, that will be used to compare them and see if the chromosome is better adapted to solve our problem. These chromosomes can also reproduce in pairs, that is to perform a crossover, to obtain a third selection that can improve the fitness of its parents. And finally, with a small probability, a chromosome can carry a mutation, that is a modification to the chromosome that is not carried by its parents.

Overview of a Genetic algorithm (adapted from Artificial Intelligence a Modern Approach, Russell & Norvig).

Coming back to our example in the W40K selection problem, we consider a chromosome to be a selection of troops. I considered this technique interesting for the W40K selection problem because of the fitness function, that will allow us to obtain the damage output of a given selection, without having to specify all the restrictions beforehand, as in Linear Programming.

So, with that in mind we must create a Python code that must implement these methods:

1. Fitness: roughly speaking, how good is each selection.
2. Crossover: it must take two selections, and obtain a combination of them.
3. Mutation: a random change.

GENETIC-ALGORITHM(population: list of random selections):
  do:
    new_population = []
    for i=1 to size(population):
      parent1 = RandomSelect(population)
      parent2 = RandomSelect(population)
      child = Crossover(parent1, parent2)
      if (some_probability) then:
        Mutate(child)
      new_population.add(child)
    population = new_population
  while (Fitness is not enought) or (number of generations achieved)
  return max(Fitness(population))

The pseudo-code for the genetic algorithm is written above. RandomSelect can be performed in several ways: it can be truly a random selection over the pool, selecting proportionally to the fitness result (ROULETTE), or picking a list and selecting the better pair of the list (TOURNAMENT). I used the genetic algorithm code written by David Kopec, you can find here. I created a class that has all these functions and use the fitness function to compute the possible damage, by performing an average of 100 attacks and averaging the results.

Experiments

It is important to state that a genetic algorithm is neither a complete nor a sound method to find the best solution, and I will briefly explain why before showing the results. Since is an algorithm that depends on some probability to mutate or crossover, it has no guarantee to reach all possible combinations nor the best solution. It is, however, a method that can provide good results by approximation. Having said that, let us continue and see some interesting results.

Results for 10 experiments with 10 initial random selections and 10 generations, using the TOURNAMENT method.

To show how the algorithm converges towards a solution, look at the figure above. It shows the result of 10 experiments. In each experiment, we started with a genetic pool of 10 chromosomes, that is, 10 initial random selections. The method I used in this experiment was the TOURNAMENT method, that is, selecting a random list, and from that list the 2 elements that maximize the Fitness function. It is possible to see that each run of the experiments gives different results, and all of them converge towards a local maximum. If we augment the initial pool, results may increase:

Results for 10 experiments with 100 initial random selections and 10 generations, , using the TOURNAMENT method.

Notice that augmenting the initial random genetic pool, even if its completely random, it improves the final result. This is because my genetic algorithm relies heavily in its initial random selection to combine the best results. But what about the method used to select the selections?

Results for 10 experiments with 100 initial random selections and 20 generations, , using the ROULETTE method.

The main difference seems to be the number of generations required to converge. Notice also that since the ROULETTE method selects using a draw from all elements where the better the fitness is, the higher chance it has to be selected, but not guaranteed, it can result in the fitness decreasing temporally.

Conclusions

In this post I have shown a different technique to solve a problem of selection. It has its drawbacks, notably its incompleteness, but it can yield fast results if you have time constraints, and cannot afford to use Linear Programming to give you an exact solution. It can also give you more control over the value of each selection, in this case, it allow me to model more realistic damage and roll functions to simulate a W40K combat.

I hope you enjoyed this post also. And in the next post we will explore different problems maybe also using W40K as example.

Stay safe!