GAPI1 is the first algorithm for computing pile-ins. It serves primarily as a proof of concept, that using a genetic algorithms works to discover pile-in strategies. GAPI1 kicks off the project to develop a more sophisticated and robust A.I. that can handle more complex pile-ins, and adheres to the game's rules and physical nature more closely.The algorithm of GAPI1
Like any genetic algorithm, GAPI tries a number (population size) of random solutions. These solutions are evaluated, and the best are selected for reproduction, recombining their properties. Over the span of a few generations, the best combination of properties is pushed forward. So how does that translate to pile ins in GAPI1?
In-depth look in GAPI1's elementsThe Chromosome
- GAPI1 moves all models randomly, each in an arbitrary direction and distance (up to 3").
- GAPI1 then evaluates which one scores best:
- Points are gained for being in combat range
- Points are lost for breaking unit coherence, being out of reach, or stacking bases.
- A maximum score of 200 can be scored per model (being range, no stacks and not breaking coherence).
- The worst solutions are deleted, matching the crossover rate. So at 70% crossover rate, only the 30% best will remain.
- A new generation is made:
- New offspring is produced, according to crossover rate. So for 70% crossover rate, 70% of the new generation will be offspring by combining parents. Mutation is applied throughout this proces, according to mutation rate.
- The remaining population is filled with exactly 1 clone of each parent. Cloning is different from copying, in that it can introduce mutation.
- Back to step 2
, is the pile-in strategy.A gene
is a single pile-in move. A randomly generated gene is a random move of a single model in any direction and distance up to 3". The genes are strictly ordered, with the position of the gene denoting which model is moved by the pile-in as well as the order in which the model is moved. Therefore, models are always being piled-in from left to right.A mutation
replaces one gene with an entirely new one. So, one move in the entire pile-in strategy is changed by a random move. A mutation does not retain any information from its source, other than the starting position of the model.The fitness function
is rather crude, but seems to work:
- The fitness is the sum of a per-model score only. There is no overarching scoring.
- +200 points for a model that is in combat range of an enemy.
- -400 points for a model that is stacking bases (friend or foe).
- -400 points for a model that has no friendly model within 1/2".
- -1 point for each mm of distance to the nearest enemy.
A single model can score at most 200 points, and a whole lot of negative points as worst. This ensures that pile-in strategies that get all models in combat, but break coherence or stack bases, will lose out to strategies that are not perfect, but don't break any rules. Still, it is important at the start of the evolution to support broken formations as long as they also evolve "in the right direction".The Elimination rate
is the amount of bad solutions being removed, which is the set to be the same as the crossover rate. The remaining population (100% - crossover rate) are the only eligible candidates for offspring. As a result, we can not support 100% crossover rates as this would delete the entire population.The Crossover rate
is the percentage of the new generation that will be created through recombination (offspring). This is implemented as a fixed size with respect to the population, not as a chance for offspring to be a recombination. Uniform parent selection
gives all survivors of the elimination an equal chance to produce offspring. Their fitness is no longer taken into account. Furthermore all parents are cloned. This is a logical consequence of how crossover works in GAPI1. A crossover rate of 70% kills 70% of the population. For the new generation 70% are children from recombined parents. This leaves a 30% to be filled by clones, which is the exact amount of parents left.Tweaking the parametersPopulation size
determines how many pile-in strategies are tested in each generation. A larger population permits more exploration per generation, and thus increasing the chance of finding a solution. But it also requires more calculations per generation, where a smaller population might try several generations with the same effort.Crossover rate
determines how many of the new generation are off-spring by combining 2 results. Currently, this also indicates how many of the worst results are removed to make room for this offspring. The bigger this number, the stronger the selection. This will increase the focus to a single solution, but also kill off looking for creative answers. Mutation rate
increases the chance for a single pile-in move to be replaced by a new one. This permits the algorithm to get unstuck, for example when it has 2 models blocking a third. A very high rate can make the program unfocused and jumpy. On the other hand, a low rate will limit the AI's ability to look at juggling about a few models.What works
What seems to work is a high population (200+), high crossover rate (80%) and high mutation rate (20%). Arguably, the search space for bad pile-in strategies is so big that it a strong selection quickly narrows down the search to a reasonably good combination of individual moves. However, this also makes the algorithm "stuck" when 2 models block a third. And so a high mutation rate is required to move models about a bit.
I love me a bowl of numbers to crunch for breakfast. If you need anything theoryhammered, I gladly take requests.Furnace of Arcana
, a warhammer blog with delusional grandeur.
"I move unseen. I hide in light and shadow. I move faster than a bird. No plate of armour ever stopped me. I strike recruits and veterans with equal ease. And all shiver at my coldest of whispers."
- The stiff breeze