Using Genetic Algorithms for Game AI
by Greg James

Introduction
Genetic algorithms are one of a variety of AI techniques that have been extensively explored by academics but have yet to push their way into game development. However, they offer opportunities for developing interesting game strategies in areas where traditional game AI is weak.

This article will give an introduction to the theory and implementation of genetic algorithms. We will also discuss their suitability to use in computer game AI.

Primer
Genetic algorithms (GAs) are one of a group of random walk techniques. These techniques attempt to solve problems by searching the solution space using some form of guided randomness. Another technique of this type is simulated annealing.

Genetic Algorithms use natural selection as their paradigm for finding better solutions. Briefly, a candidate solution to a problem is encoded as a binary string, and a starting set (or population) of candidates is created out of random bits. The population of candidates evolves over many generations. In each generation the candidates are each assigned a fitness rating according to some criteria, and then that rating is scaled into a probability of reproduction. The candidates are then sexually recombined (by pretending the binary strings are DNA) to produce the next generation.

Let’s look at the different parts of the process: encoding, evaluation, and sexual recombination. Actually, let’s look at sexual recombination first since the sex is straightforward programming, but the evaluation and encoding are troublesome design issues.

Sex
Sex is our artificially glamourous description of the actual mechanics of GA evolution. The basics are simple, but there are many variants available, usually designed to compensate for certain problems in the evolution path. Programmers interested in the variants or who are having difficulties with the standard forms should consult a genetic algorithm text e.g. Goldberg (1989).

The fitness scores f are usually scaled before parents are chosen. The standard method is linear scaling: f ’ = af + b, where the coefficients a and b are selected each generation to cause the maximum scaled score to be a specified multiple (usually two) of the population average. This will preserve the genetic diversity in your population. Here’s some scaling sample code:

// Population has been sorted according to fitness
int iPopMin = member[POPULATION_SIZE - 1].fitness;
int iPopMax = member[0].fitness;

// Calculate the scaling factors

double dMean = 0.0;
for (int i = 0; i < POPULATION_SIZE; i++)
         dMean += member[i].fitness;
dMean = dMean / POPULATION_SIZE;

double delta = 0.0;
double a = 0.0;
double b = 0.0;
double scale = 0.0;
if ( iPopMin >
              ((SCALE_FACTOR * dMean - iPopMax) / (SCALE_FACTOR - 1.0))
         )
         {
               delta = iPopMax - dMean;
               a = (SCALE_FACTOR - 1.0) * dMean / delta;
               b = dMean * (iPopMax - SCALE_FACTOR * dMean) / delta;
         }
         else
         {
               delta = dMean - iPopMin;
               a = dMean / delta;
               b = -1 * iPopMin * dMean / delta;
          }

// Scale the population

for (i = 0; i < POPULATION_SIZE; i++)
      member[i].fitness = member[i].fitness * a + b;

For each candidate the probability of reproduction is its evaluation score divided by the sum of the evaluation scores for the population.

for (i = 0; i < POPULATION_SIZE; i++)
      member[i].p_repro = member[i].fitness / dMean * POPULATION_SIZE;

For each member of the next generation, pick a pair of parents from the current generation based on their probability of reproduction. The child then inherits its DNA from its parents according to the following code snippet:

for (int i = 0; i < DNA_LENGTH; i++)
{
      child[i] = parent1[i];
      if ( event(P_CROSSOVER) )
      {
                temp = parent1;
                parent1 = parent2;
                parent2 = temp;
      }
}

Then for each child in the new generation, mutate them. Bear in mind that mutation is very rare and serves to introduce randomness into your solutions; in good solutions this will likely be a bad thing. In humans rather than giving X-Men-like powers it virtually always leads to genetic problems like cystic fibrosis.

for (int i = 0; i < DNA_LENGTH; i++)
        if (event(P_MUTATION))
              child[i] = (child[i]++)%1;

As a rough guide P_MUTATION should be approximately 1/(2 * DNA_LENGTH).

Encoding
Encoding is a design task in which you decide what the bits in your binary DNA strand will represent in the game world. For example, three bits might represent one of 8 alternatives for a particular condition. Encoding is actually the most difficult part of the whole design/programming problem. This is because the way that you encode your solution implicitly defines your solution space, and thus what your answer will look like.

Let’s take a concrete example from StarCraft. Something that would be cool is if the computer AI could adapt its strategy to exploit player weaknesses. A simple GA could encode units to build based on the main type of unit being produced by the human player. The binary string would be quite short and evolution could happen quickly, but the scope of the AI is quite limited. It doesn’t prescribe how to use the units, and it only exploits one small facet of the player: their unit preference.

A more comprehensive GA would consider how their base is set up, how well they can cope with multiple engagements, unit mobility, combined force flexibility, and more. A GA could also be composed to define the behaviour of individual units rather than groups of units or the overall strategy. Changing your level of abstraction will obviously change your GA.

The encoding trade-off is one between flexibility and search space. A more focussed search will yield results faster. On the other hand, one of the attractions of this type of AI is that it can produce clever solutions that you are not likely to have thought of yourself. The more constrained your search space, the less likely this is to happen.

Evaluation
Evaluation is the decision of how good a solution a given candidate is. In our sample code, it’s where you assign initial (unscaled) values to member[i].fitness. Programmatically it’s usually quite easy, but as with encoding the main task lies in the design phase and is difficult to do well.

This is because you have to quantify statements like, "I want it to play StarCraft really well." The "really well" is the sticky bit. What does that mean?

Again, you are faced with tradeoffs. At the easy end, you could just base the fitness on the score achieved at the end of the game. Unfortunately, this means that a game has to be played for every candidate of every generation, and that could take a very long time. Further, in any game a score will vary by some amount due to random factors, not least of which is the random placement of the players in the beginning. Differing scores lead to differing evolutionary paths.

I’ll also predict that score-based evaluation is also going to lead to some peculiar behaviours: for example, your StarCraft score increases the more minerals you mine and the more buildings you build, but is unaffected by time. Thus, a global AI can increase its score by hanging around at the end of the game building useless buildings and harvesting minerals. Not what you had in mind, hmm?

A faster alternative is to create an objective mathematical function that can operate on the binary string very quickly. This has the advantages that i) it’s faster than the simulation evaluation, and ii) it’s more deterministic in terms of the evaluation provided for a given candidate. However, it has one huge drawback: in games it’s usually impossible to tell from the binary string how well it is going to perform various tasks. Even in the simplest of games like The Prisoner’s Dilemma and RoShamBo (Rock/Paper/Scissors) the various strategies need to be played out against one another.

A middle ground may be to break the AI into discrete subsets and writing playable scenarios and evaluation criteria that never make it into the final game. For example, use a GA to encode building strategies, and then evaluate it (in the StarCraft case) based on how quickly units get built and technology advanced.

When should I use genetic algorithms?
The main issue with genetic algorithms is that there are few jobs that GAs can do better than a heuristic-based search. Generally speaking, if you have some ideas of how to solve your problem, you’re probably better off implementing those ideas that you are turning your problem over to a GA, which is relying on randomness. But there are two issues in game development that may warrant their use: noise and data access.

By noise I mean that the evaluation of a given candidate solution may vary randomly. Our previous example of using the total score from StarCraft is a prime example of a noisy evaluation. GAs deal with noise well because they are slower to react to seemingly relatively fantastic or abysmal evaluations, and the noise will tend to get smoothed out over many candidates, populations, and generations.

Data access means that you may not have the ability to get at the information you want into order to make good decisions with other more obvious types of AI. For example, when humans play StarCraft they usually set up some sort of defence for their base depending on what type of attack they’re expecting. Any heuristic algorithm needs to have an analysis of the defence in order to produce a recommended offence, and writing that programmatic analysis could be extremely difficult.

Further, genetic alogirthms do have the advantage that with appropriate encoding they can invent solutions that don’t require the intervening abstraction. Thus, if you can’t discover a way of abstracting a problem, get a GA to bypass it. This usually means making the encoding flexible enough (read: has a large enough search space) to encompass all decent solutions and then hoping it finds one.

They also have the benefit that they can find non-intuitive solutions. And solutions of this nature are the best for games, as in my opinion they provide the best experience for the player. Getting your ass kicked in a predictable way gets boring. In a confusing way? That’s interesting.

Time
Traditional game AI has usually involved fighting with the graphics and sound programmers for scarce CPU time and resources. Genetic algorithms are computationally expensive, and work better the more resources you can throw at them. Larger populations and more generations will give you better solutions. This means that GAs are better used offline. One way of doing this is by doing all of the GA work in-house and then releasing an AI tuned by a GA. You could also have a GA engine work on the user’s computer while the game is not being played. To my knowledge this latter track has never been tried, but could be really cool.

Conclusion
Genetic algorithms offer a way to solve problems that are difficult for traditional game AI techniques. Though better equipped to deal with the problems of noise and strategy abstraction, they also come with their own set of problems: it’s computationally expensive and doesn’t work as well on well-understood problems.

Genetic Algorithms in Search, Optimization & Machine Learning by David Goldberg, Addison Wesley (1989).

Bio
Greg James is a programmer/analyst who has been entranced by computer games since the days of Pong. He holds a BSc in Cognitive Science and an MSc in Computer Science, and has worked for the Alberta Research Council and Radical Entertainment. His MSc involved (among other things) using genetic algorithms to evolve XTank designs and control programs. He currently works as a Research Programmer for Matrox Graphics in Montreal, Canada.
www.infidels.org/~greg
greg@ejor.com

<<<Back to GIG Home