Computer Gaming

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.

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 (Giacopassi et al 123-148).

Sex

Sex is our artificially glamorous description of the actual mechanics of GA evolution (Oh and Hsu 618-637).

The fitness scores f is usually scaled before parents are chosen. The standard method is linear scaling: f ' = af + b, where the coefficients a and b is 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 ...