Genetic algorithms in Reich

In this post I talk about the first implementation of the enemy A.I. that I’ve made for Reich, a turn-based tactics game.

Post illustration

After reading the excellent Introduction to Genetic Algorithms book by Melanie Mitchell, I got really interested in genetic algorithms and genetic programming and decided I would use GAs to create the CPU opponents in Reich.

I made an interpreter for a small c-like language, an algorithm to create random mini-programs and another to mix and match programs according to their fitness. In the game, every CPU-controlled unit generates hundreds of these mini-programs and evaluates them to decide which one to use for their movement.

Early version of the interpreter with the GA algorithms crossing code together
Early version of the interpreter with the GA algorithms crossing code together

To evaluate how good a movement pattern is, I have a series of fitness functions that each AI player uses that I’ve divided into three types:

  • Recon: functions that evaluate how good the performance of the mini-program that is being analyzed is at reaching new places and patrolling areas;
  • Attack: functions that evaluate how good the performance of the mini-program is when it comes to getting closer to enemy units/structures and attacking them;
  • Defense: functions that analyze how good the mini-program is at finding the best tiles to stand on, how close the unit is to structures that are under-attack and so on.

I then have variables that measure how much energy is allocated to each of the three types. At the end of the turn I record the game’s current state (number of CPU units, number of structures, amount of tiles that are under fog-of-war, etc.) and how effective the current parameter attributes were on advancing the computer’s position.

Later on the CPU will poll this information in order to adjust the parameters for a given game state. The mini-programs with the best fitness results are also recorded and polled on other turns, to hopefully get some inter-generational evolution as well.

Each CPU opponent has a set of variables that I’m calling AI parameters:

AI parameter diagrams
AI parameter diagrams

Each AI parameter has a corresponding fitness function, these basically attribute a score that ranges from 0 to 1 to each move that a program creates:

Fitness functions
Fitness functions

The AI parameters combined with the fitness functions help classify a given program:

Program fitness evaluation
Program fitness evaluation

This ends up shaping behavior without telling the unit what to do exactly: A bigger percentage attributed to the recon parameters, for instance, will have the unit roaming about the terrain trying to uncover foggy tiles. Having more in the attack will encourage aggressive behaviors - more proximity to enemy tiles, more attacks, etc.

Every time the CPU starts a turn it defines how much of a percentage it is going to attribute to each parameter:

AI parameters definition
AI parameters definition

This is done by polling past records of turns and selecting the turns with the higher fitness for a given game state. By game state I mean how the CPU is perceiving the game in a current turn: How many units does the CPU have? How many enemy units do I see? How many tiles are uncovered?

After I get a sample of turns filtered by the state, I use the AI parameters for the ones with the best fitness and randomize them a little. The amount of variance I use when randomizing the parameters is a function of how many records I have on my database. I’m doing this because I believe that I can have a bigger confidence in the results as the number of recordings increase.

Generating the unit movement is standard GA practice:

Unit move evaluation
Unit move evaluation

Here, too, I have a data store with programs used in past turns. These are used to get some inter-generational evolution to complement the regular intra-generational one provided by a GA cycle. I filter the data store by the game state and randomly pick a program with the ones with the bigger average fitness having a bigger chance to be selected.

After this particular program is evaluated I record its performance back to the store. The best program to come out from the GA cycle is recorded there as well.

After the turn is done I record the performance of every unit averaging the fitness by its unit type, and the whole process is repeated in the next turn.

Move generation process
Move generation process

Generating unit moves like this created some interesting emerging behavior. However it also ended up being too resource-intensive for this task.

In the end, after watching some of Dave Mark’s presentations on AI and reading his book on the subject - Behavioral Mathematics for Game AI - I ended up using another technique called Utility System that I will discuss in a later post.