Chapter 15. Genetic Algorithms
It is the game designer’s job to create a challenging game environment for the player. In fact, a large part of game development involves balancing the game world. It needs to be challenging enough for the players, or the game will seem too easy and they will lose interest. On the other hand, if it’s too difficult, the players will become frustrated. Sometimes players can discover loopholes, or exploits, with which they essentially can cheat. This can be a result of a game design issue that the developers simply overlooked. Another game design problem stems from the fact that the skill levels of different players can vary greatly. Creating a truly balanced and challenging game for players of different skill levels can be a daunting task. Fortunately, genetic algorithms can help.
In this chapter, we are not going to attempt to model a true genetic system. A true genetic model probably wouldn’t be practical or beneficial in a real computer game. Instead, the system we are going to discuss is merely inspired by a biological genetic system. In some ways it will be similar, but we won’t hesitate to bend the rules if it benefits the game design process.
In the real world, species constantly evolve in an attempt to better adapt to their environments. Those that are most fit continue to survive. Charles Darwin proposed this phenomenon in 1859 in his famous work entitled “On the Origin of Species.” Those that are most able to survive in their environments are able to pass on their traits to the next generation. The individual traits are encoded in chromosomes. In the next generation, these chromosomes are combined in a process called crossover. Crossover is a recombination of the chromosomes in the offspring. Figure 15-1 illustrates this process.
In Figure 15-1 we used random letters to represent chromosomes. As you can see, each parent passes half of its genetic material on to the child. However, in the real world this crossover process might not be exact. Random mutations also can take place. This is illustrated in Figure 15-2.
Random mutations are nature’s way of trying new things. If a random mutation improves the species, it gets passed on to future generations. If not, it doesn’t get passed on.
This constant recombination of chromosomes from the most successful members of the previous generation, combined with random mutations, creates future generations that are better adapted to survive and flourish in their environments. You can apply this same concept in games. Just as in the biological world, the elements in a game world can be made to evolve and adapt to changing situations.
Evolutionary Process
You can break down the implementation of genetic algorithms in games into four steps. Figure 15-3 illustrates this four-step process.
As Figure 15-3 shows, the first step involves creating the first generation. The entire population is seeded with a set of starting traits. Once the population starts interacting with its environment, we need a way to rank the individual members. This is the process of ranking fitness. This tells us which members of the population are the most successful. The process of ranking fitness aids us in the next step, which is selection. In the selection process we choose certain members of the population to create the next generation. We essentially use the most successful traits of the previous generation to create the next generation. The actual step of combining these traits to create a new, and hopefully fitter, generation is referred to as evolution. Genetic algorithms are essentially optimization processes in which we’re trying to find the fittest set of traits—we’re looking for the optimum solution to a specific problem.
First Generation
Each individual in the first generation represents a possible solution to the problem at hand. One way to approach the creation of the first generation is to arrange the chromosomes randomly. In a game environment, however, randomly arranging chromosomes might not always be the best solution. If the game designer already knows which combinations of chromosomes are likely to produce a fit individual, a true random combination probably won’t be necessary. However, it is still important to create an initial diverse population. If the individuals are too much alike, the genetic process will be less effective.
Encoding is the process of storing the chromosomes in a structure that can be stored in a computer. This, of course, can be any type of structure the programmer chooses to use. Genetic algorithms frequently use strings of bits, but arrays, lists, and trees also commonly are used.
Figure 15-4 shows an example of a first generation of flowers. These hypothetical flowers would include random chromosomes that would affect how well they thrive in their environments.
Ranking Fitness
This step in the evolutionary process involves evaluating each member of the population. This is where we attempt to identify the most successful members of the population, and typically we accomplish this using a fitness function. The purpose of the fitness function is to rank the individuals in the population. This tells us which individuals are best at solving the problem at hand.
Figure 15-5 shows how the flowers would be ranked. We assume the flowers that grow the tallest are the fittest.
Selection
In the selection step we choose the individuals whose traits we want to instill in the next generation. In the selection process typically we call the fitness function to identify the individuals that we use to create the next generation. In the biological world, usually two parents contribute chromosomes to the offspring. Of course, in game development, we are free to use any combination of parents. For example, we are free to combine the traits of the top two, five, 10, or any other number of individuals.
Figure 15-6 shows how we use rankings calculated by the fitness function to determine which individuals to use when creating the next generation. In this case, we selected the two tallest flowers.
Evolution
In the final step we create new individuals to place into the game environment. We do this by using individuals from the selection process. We take the individual chromosomes from the fittest members of the population and begin combining their chromosomes. At this point it is also important to introduce random mutations. Once the evolutionary process is complete, we return to the fitness ranking step.
The evolutionary step is where crossover occurs. This is where we combine the chromosomes of the fittest individuals. In this case, we combine the chromosomes of the two tallest flowers to create a new flower. We also introduce two random mutations. This is illustrated in Figure 15-7.
Evolving Plant Life
This first example shows how to apply a genetic algorithm to successive generations of flowers as they attempt to thrive in their environment. We define a series of hypothetical environmental conditions in which the flowers must grow. Each flower then contains genetic information that indicates its ideal growing environment. Flowers whose ideal growing environments most closely match the actual conditions grow the tallest. The tallest flowers will be considered the most fit and have their genetic information passed on to successive generations. This should result in a general increase in flower height as generations progress.
Encoding the Flower Data
We start by defining the six hypothetical environmental conditions, which we consider to be the actual conditions of the flower world. These are shown in Example 15-1.
Class ai_World
{
public:
int currentTemperature;
int currentWater;
int currentSunlight;
int currentNutrient;
int currentBeneficialInsect;
int currentHarmfulInsect;
ai_World();
~ai_World();
};As Example 15-1 shows, the six conditions are currentTemperature, currentWater, currentSunlight, currentNutrient, currentBeneficialInsect, and currentHarmfulInsect.
Encoding is the process of storing the chromosomes in a structure that can be stored in a computer. This, of course, can be any type of structure of the programmer’s choosing. Example 15-2 shows the structure that we use in the flower evolution example.
#define kMaxFlowers 11
Class ai_World
{
public:
int temperature[kMaxFlowers];
int water[kMaxFlowers];
int sunlight[kMaxFlowers];
int nutrient[kMaxFlowers];
int beneficialInsect[kMaxFlowers];
int harmfulInsect[kMaxFlowers];
int currentTemperature;
int currentWater;
int currentSunlight;
int currentNutrient;
int currentBeneficialInsect;
int currentHarmfulInsect;
ai_World();
~ai_World();
};As Example 15-2 shows, we use six arrays to represent the six environmental conditions. These include temperature, water, sunlight, nutrient, beneficialInsect, and harmfulInsect. Each contains a chromosome that indicates the ideal conditions for each flower.
First Flower Generation
As with all genetic algorithms, first we must populate the world with the initial generation. If we consider the genetic process as searching for the optimum solution to a problem, the first generation consists of a group of our best guesses at a solution. We also need to ensure that we have a diverse set of possible solutions. Example 15-3 shows the creation of the first generation.
void ai_World::Encode(void)
{
int i;
for (i=1;i<kMaxFlowers;i++)
{
temperature[i]=Rnd(1,75);
water[i]=Rnd(1,75);
sunlight[i]=Rnd(1,75);
nutrient[i]=Rnd(1,75);
beneficialInsect[i]=Rnd(1,75);
harmfulInsect[i]=Rnd(1,75);
}
currentTemperature=Rnd(1,75);
currentWater=Rnd(1,75);
currentSunlight=Rnd(1,75);
currentNutrient=Rnd(1,75);
currentBeneficialInsect=Rnd(1,75);
currentHarmfulInsect=Rnd(1,75);
}As Example 15-3 shows, we begin by randomly encoding the chromosomes of the flowers. We use six arrays to indicate the ideal growing conditions for each member of the flower population. The arrays include temperature, water, sunlight, nutrient, beneficialInsect, and harmfulInsect. Each array contains a value from 1 to 75. This range was tuned for this example. A number smaller than 75 makes evolution occur more quickly. However, if evolution takes place over just a few generations, there won’t be much to observe. Likewise, using a higher number slows the evolution process, requiring more generations before an optimum solution is found.
The flowers grow best when the actual conditions closely match the ideal growing conditions encoded in their chromosomes. We use a for loop to set the values randomly in each array. This will ensure a diverse population of flowers. Once the for loop has executed, we assign the values of the current conditions; these include currentTemperature, currentWater, currentSunlight, currentNutrient, currentBeneficialInsect, and currentHarmfulInsect.
Ranking Flower Fitness
For the purpose of this genetic simulation, we assume the fittest flowers are those that are most capable of flourishing in the current environmental conditions. The chromosomes in each individual flower are encoded with their own ideal growing conditions. We essentially measure how close each flower’s ideal conditions are to the actual conditions. Those that are closest grow the tallest. This is shown in Figure 15-8.
Figure 15-8 shows the initial deviation among the flower population. Those that are best suited to grow in the current conditions are the tallest. As the figure shows, some are noticeably better at flourishing in their environment. Next we look at how we actually determine the fittest members of the population. This is shown in Example 15-4.
int ai_World::Fitness(int flower)
{
int theFitness=0;
theFitness = fabs(temperature[flower] - currentTemperature);
theFitness = theFitness+fabs(water[flower] - currentWater);
theFitness = theFitness+fabs(sunlight[flower] -
currentSunlight);
theFitness = theFitness+fabs(nutrient[flower] -
currentNutrient);
theFitness = theFitness+fabs(beneficialInsect[flower] -
currentBeneficialInsect);
theFitness = theFitness+fabs(harmfulInsect[flower] -
currentHarmfulInsect);
return (theFitness);
}As Example 15-4 shows, we use the Fitness function to calculate the total deviation between the current environmental conditions and the ideal conditions needed for each individual flower to flourish. We begin by initializing the variable theFitness to 0. We then increase the value in theFitness by the absolute value of the difference between each flower’s ideal condition and the current condition. This gives us a sum of the total deviation of all the growing conditions.
Evolving the Flowers
The ultimate goal of any genetic algorithm is to produce offspring that are more fit than their parents. Our first step was to create the initial population and then determine the fitness of each individual. The fitness ranking process enabled us to select the best members of the population. The final step is the actual creation of the new generation using the traits of the most successful members of the previous generation. Besides crossing over the traits of the fittest flowers, we also introduce random mutations. The Evolve function in Example 15-5 shows both the crossover step and the introduction of random mutations.
void ai_World::Evolve(void)
{
int fitTemperature[kMaxFlowers];
int fitWater[kMaxFlowers];
int fitSunlight[kMaxFlowers];
int fitNutrient[kMaxFlowers];
int fitBeneficialInsect[kMaxFlowers];
int fitHarmfulInsect[kMaxFlowers];
int fitness[kMaxFlowers];
int i;
int leastFit=0;
int leastFitIndex;
for (i=1;i<kMaxFlowers;i++)
if (Fitness(i)>leastFit)
{
leastFit=Fitness(i);
leastFitIndex=i;
}
temperature[leastFitIndex]=temperature[Rnd(1,10)];
water[leastFitIndex]=water[Rnd(1,10)];
sunlight[leastFitIndex]=sunlight[Rnd(1,10)];
nutrient[leastFitIndex]=nutrient[Rnd(1,10)];
beneficialInsect[leastFitIndex]=beneficialInsect[Rnd(1,10)];
harmfulInsect[leastFitIndex]=harmfulInsect[Rnd(1,10)];
for (i=1;i<kMaxFlowers;i++)
{
fitTemperature[i]=temperature[Rnd(1,10)];
fitWater[i]=water[Rnd(1,10)];
fitSunlight[i]=sunlight[Rnd(1,10)];
fitNutrient[i]=nutrient[Rnd(1,10)];
fitBeneficialInsect[i]=beneficialInsect[Rnd(1,10)];
fitHarmfulInsect[i]=harmfulInsect[Rnd(1,10)];
}
for (i=1;i<kMaxFlowers;i++)
{
temperature[i]=fitTemperature[i];
water[i]=fitWater[i];
sunlight[i]=fitSunlight[i];
nutrient[i]=fitNutrient[i];
beneficialInsect[i]=fitBeneficialInsect[i];
harmfulInsect[i]=fitHarmfulInsect[i];
}
for (i=1;i<kMaxFlowers;i++)
{
if (tb_Rnd(1,100)==1)
temperature[i]=Rnd(1,75);
if (tb_Rnd(1,100)==1)
water[i]=Rnd(1,75);
if (tb_Rnd(1,100)==1)
sunlight[i]=Rnd(1,75);
if (tb_Rnd(1,100)==1)
nutrient[i]=Rnd(1,75);
if (tb_Rnd(1,100)==1)
beneficialInsect[i]=Rnd(1,75);
if (tb_Rnd(1,100)==1)
harmfulInsect[i]=Rnd(1,75);
}
}You can implement a crossover function in many ways. Game developers are not burdened by the limits of the biological world. In the biological world the crossover would involve the chromosomes to two fit parents. In game development, crossover can involve any number of parents. In the case of this flower evolution example, we are going to identify the least fit member of the population. The first for loop calls the Fitness function to identify the least fit member of the population. We then reassign the traits of the least fit flower to those of random members of the flower population. The next two for loop blocks randomly mix up the traits of the flower population. Essentially we already reassigned the traits of the least fit flower, so at this point the flower population as a whole should be an improvement over the previous generation. Unfortunately, no individual trait can be any better than it was in the previous generation because the same traits were passed on. We now need a way to try to surpass the previous generation. We accomplish this through random mutations. In the last for loop block, each trait of each flower has a 1% chance of randomly mutating. If the mutation is a success, the trait probably will be passed on to the next generation. If the mutation results in a flower being the least fit member of the population, it will be dropped. Figure 15-9 shows the end result of multiple generations.
As Figure 15-9 shows, all the flowers are at or near their maximum heights. The area beneath the flowers also graphs the fitness of each generation. As the graph shows, there is a general upward trend in the fitness of each generation. However, not every generation was an improvement over the one before it. The graph does show some downturns. This is due to the random mutations introduced into the population. However, as the graph shows, the genetic process eventually will find the best solution to the problem.
Genetics in Game Development
In games, genetic algorithms are simply a method of finding an optimum solution to a problem. Of course, there are lots of problems to be solved in game AI, and not all of them are good candidates for a genetic algorithm. Pathfinding, for example, can be solved with a genetic algorithm, however it’s usually a problem better suited to something such as the A∗ algorithm. Genetic algorithms work best when the elements of the problem are somewhat unpredictable. This allows the game AI to adapt to a situation the game designer might not have been able to predict. In game design, the most unpredictable element of the game environment is the player. To some degree, the game designer must be able to predict the player’s behavior to create a challenging adversary. Unfortunately, it can be difficult to predict and account for every possible player behavior.
Genetic algorithms basically involve a trial-and-error approach. You essentially populate the game world with many possible solutions and then determine which solutions work the best. Of course, the solutions won’t always be the same for every player. That’s the beauty of genetic algorithms. The game AI will adapt to individual players.
Role-Playing Example
Genetic algorithms are useful in any scenario in which a computer-controlled adversary must respond and change due to player behavior. For example, consider a hypothetical multiplayer role-playing game. In this game the players would be able to choose from many different types of character classes and abilities. This means the computer-controlled characters would have to be able to present a challenge to many types of player-controlled characters. A player could choose to play a warrior character that would fight mainly with brute force. Of course, with this class the player would be able to choose from a multitude of weapons. The player could attack with a sword, axe, or any number of other weapons. The fighter class also would be able to wear an assortment of armor. On the other hand, the player might choose a totally different class. A magical class would produce a totally different player behavior. The various combinations of class and weapon types would make it difficult for a game designer to create a single type of computer-controlled individual that would be a challenge to every type of player-controlled character. It could be even more complicated in a multiplayer game. In this type of game the computer will have to be a challenge to a group of diverse players working in combination. The number of possible combinations quickly would become more than a game designer could account for.
Encoding the Data
We are searching for a type of computer-controlled character that will be a challenge to a player or group of players. This isn’t a search that you can precalculate. Each player or group of players would behave differently. We need to determine the situations and responses that will either increase or decrease the level of fitness in the population. For example, one possible situation could be when the player attacks a computer-controlled character with a magic weapon. We can create several possible responses to this player action. The computer-controlled character could attack the player in response, attempt to flee, or attempt to hide. We could assign this situation and response to a chromosome. If this chromosome is set to create an attack response in this situation, the player will be attacked when using a magic weapon. However, what if this scenario always leads to the defeat of the computer-controlled character? In that case, the computer-controlled character would be deemed less fit, and therefore, less likely to pass on that trait. In successive generations this scenario would lead to a different behavior, such as a retreat whenever the player wields a magic weapon. Example 15-6 lists some of the possible scenarios we address in our hypothetical example.
#define kAttackedbyFighter 0 #define kAttackedbyWizard 1 #define kAttackedbyGroup 2 #define kHealerPresent 3 #define kAttackedByBlade 4 #define kAttackedByBlunt 5 #define kAttackedByProjectile 6 #define kAttackedByMagic 7 #define kAttackerWearingMetalArmor 8 #define kAttackerWearingLeatherArmor 9 #define kAttackerWearingMagicArmor 10 #define kImInGroup 11
Figure 15-5 shows the possible situations in which members of the population will behave differently. We use a different chromosome to store the response to each situation. We begin with the kAttackedbyFighter constant. This chromosome will store the response whenever the computer-controlled character is attacked by a player-controlled fighter character. Some creature types might be more or less effective when doing battle against fighter characters. Similarly, the kAttackedbyWizard chromosome will store the response to being attacked by a player-controlled wizard character. The kAttackedbyGroup chromosome will indicate the behavioral response to being attacked by a group of player characters. The kHealerPresent chromosome indicates which behavior should be used when a player healer is present. If the players can be healed repeatedly, it might be a futile situation in which retreat would be most appropriate.
The next four chromosomes, kAttackedByBlade, kAttackedByBlunt, kAttackedByProjectile, and kAttackedByMagic, determine which response to give for each type of weapon the player can wield. The next three, kAttackerWearingMetalArmor, kAttackerWearingLeatherArmor, and kAttackerWearingMagicArmor, determine the best response to the various types of protective armor the player can wear. Some computer-controlled characters can choose from a selection of weapons. For example, a blade weapon might be more effective against leather armor. The final chromosome, kImInGroup, is used to determine the best response when the computer-controlled character is fighting in a group. Some types of creatures, such as wolves, can be more effective when fighting in a pack.
A real game probably would have a much more thorough list of possible scenarios, but for this example our list should suffice. Example 15-7 shows the possible responses to each scenario.
#define kRetreat 0 #define kHide 1 #define kWearMetalArmor 2 #define kWearMagicArmor 3 #define kWearLeatherArmor 4 #define kAttackWithBlade 5 #define kAttackWithBlunt 6 #define kAttackWithMagic 7
Each constant shown in Example 15-7 defines a possible character behavior; they each assign a behavior to one scenario shown in Example 15-6, and we start with the kRetreat constant. As the name implies, this behavior causes the computer-controlled character to run from player characters. The second constant, kHide, makes the computer-controlled character enter a state in which it will attempt to elude detection. The next three constants, kWearMetalArmor, kWearMagicArmor, and kWearLeatherArmor, make the computer-controlled character switch to each respective type of armor. The final three constants, kAttackWithBlade, kAttackWithBlunt, and kAttackWithMagic, define the type of attack the computer-controlled character should use against the player.
Now we create an array that contains a behavioral response for each possible scenario shown in Example 15-6. We will use one array element for each possible scenario. We accomplish this with a simple C++ class structure, as shown in Example 15-8.
#define kChromosomes 12
Class ai_Creature
{
public:
int chromosomes[kChromosomes];
ai_ Creature ();
~ai_ Creature ();
};As Example 15-8 shows, we create an ai_Creature class that contains an array of chromosomes. Each element of the array represents a trait, or behavior, for the computer-controlled character. We define each possible behavior and then we link each chromosome to each behavior. We use an array size of 12 because Example 15-6 shows 12 possible situations.
The First Generation
So far we have defined the possible scenarios that we use for the genetic tests, defined the possible behaviors associated with each scenario, and created a structure to store the genetic data. The next step is to create the population. We start by expanding on the code shown in Example 15-8. Example 15-9 shows the modifications.
#define kChromosomes 12
#define kPopulationSize 100
Class ai_Creature
{
public:
int chromosomes[kChromosomes];
ai_ Creature ();
~ai_ Creature ();
};
ai_Creature population[kPopulationSize];As Example 15-9 shows, we added the constant kPopulationSize to define the size of the creature population. We also added an array of ai_Creature whose bounds are set to the values assigned to kPopulationSize. The next step is to begin linking individual behaviors to each possible situation shown in Example 15-6. We start by adding a new function to the ai_Creature class. Example 15-10 shows the modified ai_Creature class.
#define kChromosomes 12
#define kPopulationSize 100
Class ai_Creature
{
public:
int chromosomes[kChromosomes];
void createIndividual (int i);
ai_ Creature ();
~ai_ Creature ();
};
ai_Creature population[kPopulationSize];The new function, ai_createIndividual, initializes a new member of the population. However, we don’t want to initialize each individual using a set of predefined constants. We want the population to be as diverse as possible. A population that isn’t diverse won’t be as effective at finding the best solution. The best way to create a diverse population is to assign the behaviors in a random fashion. However, we can’t simply randomly assign the behaviors shown in Example 15-7 to the situations shown in Example 15-6. Some of the behaviors don’t apply to the listed situations. We solve this problem by using a block of conditional statements, as shown in Example 15-11.
void ai_ Creature::createIndividual(int i)
{
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedbyGroup]=kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedbyGroup]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedbyGroup]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedbyGroup]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedbyGroup]=
kAttackWithMagic;
break;
}
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kHealerPresent]=kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kHealerPresent]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kHealerPresent]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kHealerPresent]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kHealerPresent]=
kAttackWithMagic;
break;
}The first case statement assigns a random behavior to the kAttackedbyGroup chromosome. For this chromosome we choose from five possible behaviors (kRetreat, kHide, kAttackWithBlade, kAttackWithBlunt, and kAttackWithMagic). The idea is to try to determine if any of these actions provide a noticeable advantage or disadvantage when a group of player characters attacks the computer-controlled character. For example, the process of evolution might show that retreating is the best course of action when attacked by a group of players.
The second case statement sets the value in the kHealerPresent chromosome. Again, we want to determine if creating a diverse population, in which the response to this situation varies among the members, will give some individuals an advantage or disadvantage. As in the case of the kAttackedbyGroup chromosome, we use the following five responses: kRetreat, kHide, kAttackWithBlade, kAttackWithBlunt, and kAttackWithMagic.
Now we consider the possible behaviors to link to the various types of attacks the player could use. Again, we randomly assign appropriate behaviors to each possible attack method. This is shown in Example 15-12.
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedByBlade]=kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedByBlade]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedByBlade]=
kWearMetalArmor;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedByBlade]=
kWearMagicArmor;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedByBlade]=
kWearLeatherArmor;
break;
}
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedByBlunt]=kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedByBlunt]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedByBlunt]=
kWearMetalArmor;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedByBlunt]=
kWearMagicArmor;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedByBlunt]=
kWearLeatherArmor;
break;
}
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedByProjectile]=
kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedByProjectile]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedByProjectile]=
kWearMetalArmor;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedByProjectile]=
kWearMagicArmor;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedByProjectile]=
kWearLeatherArmor;
break;
}
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedByMagic]=kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedByMagic]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedByMagic]=
kWearMetalArmor;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedByMagic]=
kWearMagicArmor;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedByMagic]=
kWearLeatherArmor;
break;
}As Example 15-12 shows, we consider four possible attack methods by the player (kAttackedByBlade, kAttackedByBlunt, kAttackedByProjectile, and kAttackedByMagic). Each possible attack is linked to its own chromosome and is assigned in a separate case statement. Each will be randomly assigned one of five possible responses: kRetreat, kHide, kWearMetalArmor, kWearMagicArmor, and kWearLeatherArmor.
These chromosomes will help us determine which types of armor are better suited for each possible player attack. They also will tell us if retreating or hiding is the best response to some attacks. For example, if members of the population are repeatedly defeated when attacked by magic, retreat might end up being the best response.
Now we consider the possible effects resulting from the various types of armor the player might be wearing. We follow a similar case statement structure, as shown in Example 15-13.
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kAttackWithMagic;
break;
}
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kAttackWithMagic;
break;
}
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kAttackWithMagic;
break;
}
}Example 15-13 uses three case statements to assign responses randomly to the various types of armor the player can wear. Hopefully, this will help us determine the best type of attack to use against the various types of armor. The type of armor we consider includes kAttackerWearingMetalArmor, kAttackerWearingLeatherArmor, and kAttackerWearingMagicArmor. Each will be randomly assigned one of five possible responses, including kRetreat, kHide, kAttackWithBlade, kAttackWithBlunt, and kAttackWithMagic.
Ranking Fitness
At some point we need to try to determine which members of the population are the fittest. Remember, we are searching for members of the population that are the greatest challenge to the players. We need some way to quantify and measure the level of challenge. We can consider several different approaches. Role-playing games typically assign hit points to each character. These hit points are reduced as the character is injured during battle. The character dies once the hit points reach zero. So, one way to quantify the level of challenge is to keep a cumulative total of the amount of hit-point damage done to the players. Each member of the population would track its total damage inflicted. Conversely, we also could track the amount of damage done by the players to the members of the population. Example 15-14 shows how we would expand the ai_Creature class to include variables to track the damage done and damage received.
#define kChromosomes 12
#define kPopulationSize 100
Class ai_Creature
{
public:
int chromosomes[kChromosomes];
float totalDamageDone;
float totalDamageReceived;
void createIndividual (int i);
ai_ Creature ();
~ai_ Creature ();
};
ai_Creature population[kPopulationSize];As Example 15-14 shows, we added two new variables to the ai_CreatureClass. The first, totalDamageDone, will be increased each time the computer-controlled character inflicts damage to a player; it will be increased by the amount of the hit-point damage done. Conversely, the totalDamageReceived variable would be increased whenever the player injured the computer-controlled character. As in the case of totalDamageDone, the amount of the increase would be equal to the hit-point damage done.
Of course, you should consider other game elements when determining the fitness of the individuals in the population. For example, the total player kills would be another good indicator.
Selection
The next step in the evolutionary process is to search for the fittest members of the population. These individuals will exhibit traits we want to pass on to the next generation. Once again we expand on the ai_Creature class. We calculate the ratio of damage done to damage received. We keep a running total of damage done and damage received in the totalDamageDone and totalDamageReceived variables. The fitness variable will contain the ratio of damage done to damage received. Example 15-15 shows the updated class.
#define kChromosomes 12
#define kPopulationSize 100
Class ai_Creature
{
public:
int chromosomes[kChromosomes];
float totalDamageDone;
float totalDamageReceived;
float fitness;
void createIndividual (int i);
void sortFitness (void);
ai_ Creature ();
~ai_ Creature ();
};
ai_Creature population[kPopulationSize];As Example 15-15 shows, now we have a variable to quantify the actual fitness of each individual. We use the fitness variable to calculate the fitness of each individual and then sort the population from most successful to least successful. We also added the sortFitness function to the ai_Creature class. This calculation and sorting are shown in Example 15-16.
void ai_ Creature:: sortFitness (void)
{
int i int j;
int k;
float temp;
for (i=0;i<kPopulationSize;i++)
ai_Creature[i].fitness = ai_Creature[i].totalDamageDone /
ai_Creature[i].totalDamageReceived;
for (i = (kPopulationSize -- 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (ai_Creature[j-1].fitness < ai_Creature[j].fitness)
{
temp = ai_Creature[j-1].fitness;
ai_Creature[j-1].fitness=ai_Creature[j].fitness;
ai_Creature[j].fitness = temp;
temp = ai_Creature[j-1].totalDamageDone;
ai_Creature[j-1].totalDamageDone =
ai_Creature[j].totalDamageDone;
ai_Creature[j].totalDamageDone = temp;
temp = ai_Creature[j-1].totalDamageReceived;
ai_Creature[j-1].totalDamageReceived =
ai_Creature[j].totalDamageReceived;
ai_Creature[j].totalDamageReceived = temp;
for (k=0;k<kChromosomes;k++)
{
temp = ai_Creature[j-1].chromosomes[k];
ai_Creature[j-1].chromosomes[k] =
ai_Creature[j].chromosomes[k];
ai_Creature[j].chromosomes[k] = temp;
}
}
}
}The sortFitness function begins by calculating the damage done to damage received ratio for each individual in the population. This is accomplished in the first for loop. The actual ratio is stored in the fitness variable. Once we have calculated the fitness ratio for each individual, we can sort the entire population array. The sort is handled by the nested for loops. This is just a standard bubble sort algorithm. The end result is that we sort the entire population array by the fitness variable, from most fit to least fit.
Evolution
Now we have an easy way to identify the most successful individuals in the population. Calling the sortFitness function will ensure that the lower positions in the ai_Creature array will be the fittest individuals. We then can use the traits of the individuals in the lower array elements to create the next generation. Figure 15-10 shows how the chromosomes in each array will be combined to create a new individual.
As Figure 15-10 shows, we use the crossover process when creating the new individual. Now we update the ai_Creature class to include a new crossover function. Example 15-17 shows the updated ai_Creature class.
#define kChromosomes 12
#define kPopulationSize 100
Class ai_Creature
{
public:
int chromosomes[kChromosomes];
float totalDamageDone;
float totalDamageReceived;
float fitness;
void createIndividual (int i);
void sortFitness (void);
void crossover(int i, int j, int k);
ai_ Creature ();
~ai_ Creature ();
};
ai_Creature population[kPopulationSize];The new crossover function will take the traits of two individuals and combine them to create a third. Example 15-18 shows this function.
void ai_ Creature:: crossover (int i, int j, int k)
{
ai_Creature[i].chromosomes[0]=ai_Creature[j].chromosomes[0];
ai_Creature[i].chromosomes[1]=ai_Creature[k].chromosomes[1];
ai_Creature[i].chromosomes[2]=ai_Creature[j].chromosomes[2];
ai_Creature[i].chromosomes[3]=ai_Creature[k].chromosomes[3];
ai_Creature[i].chromosomes[4]=ai_Creature[j].chromosomes[4];
ai_Creature[i].chromosomes[5]=ai_Creature[k].chromosomes[5];
ai_Creature[i].chromosomes[6]=ai_Creature[j].chromosomes[6];
ai_Creature[i].chromosomes[7]=ai_Creature[k].chromosomes[7];
ai_Creature[i].chromosomes[8]=ai_Creature[j].chromosomes[8];
ai_Creature[i].chromosomes[9]=ai_Creature[k].chromosomes[9];
ai_Creature[i].chromosomes[10]=ai_Creature[j].chromosomes[10];
ai_Creature[i].chromosomes[11]=ai_Creature[k].chromosomes[11];
ai_Creature[i].totalDamageDone=0;
ai_Creature[i].totalDamageReceived=0;
ai_Creature[i].fitness=0;
}As Example 15-18 shows, three variables are passed into the crossover function. There are three array indexes. The first two are the parents whose chromosomes will be combined to create a new individual. The third variable is the array index of the new individual. On each line we alternate between the j and k array indexes. This essentially mixes the chromosome of the parents when creating the offspring.
Although mixing the chromosomes of two fit parents should create a new fit individual, we also want to try to improve on the previous generation. We do this by introducing random mutations. We start by updating the ai_Creature class to include a random mutation function. This is shown in Example 15-19.
#define kChromosomes 12
#define kPopulationSize 100
Class ai_Creature
{
public:
int chromosomes[kChromosomes];
float totalDamageDone;
float totalDamageReceived;
float fitness;
void createIndividual (int i);
void sortFitness (void);
void crossover(int i, int j, int k);
void randomMutation(int i);
ai_ Creature ();
~ai_ Creature ();
};
ai_Creature population[kPopulationSize];As the updated ai_Creature class in Example 15-19 shows, now we need to add a random mutation function. A random mutation enables us to build a fit individual with what is essentially a guess at what might make it a little bit better. Example 15-20 shows the random mutation function.
void ai_ Creature::randomMutation(int i)
{
if (Rnd(1,20)==1)
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedbyGroup]=kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedbyGroup]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedbyGroup]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedbyGroup]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedbyGroup]=
kAttackWithMagic;
break;
}
if (Rnd(1,20)==1)
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kHealerPresent]=kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kHealerPresent]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kHealerPresent]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kHealerPresent]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kHealerPresent]=
kAttackWithMagic;
break;
}
if (Rnd(1,20)==1)
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedByBlade]=kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedByBlade]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedByBlade]=
kWearMetalArmor;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedByBlade]=
kWearMagicArmor;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedByBlade]=
kWearLeatherArmor;
break;
}
if (Rnd(1,20)==1)
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedByBlunt]=kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedByBlunt]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedByBlunt]=
kWearMetalArmor;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedByBlunt]=
kWearMagicArmor;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedByBlunt]=
kWearLeatherArmor;
break;
}
if (Rnd(1,20)==1)
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedByProjectile]=
kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedByProjectile]=
kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedByProjectile]=
kWearMetalArmor;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedByProjectile]=
kWearMagicArmor;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedByProjectile]=
kWearLeatherArmor;
break;
}
if (Rnd(1,20)==1)
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackedByMagic]=
kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackedByMagic]=kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackedByMagic]=
kWearMetalArmor;
break;
case 4:
ai_Creature[i].chromosomes[kAttackedByMagic]=
kWearMagicArmor;
break;
case 5:
ai_Creature[i].chromosomes[kAttackedByMagic]=
kWearLeatherArmor;
break;
}
if (Rnd(1,20)==1)
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kAttackerWearingMetalArmor]=
kAttackWithMagic;
break;
}
if (Rnd(1,20)==1)
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kAttackerWearingLeatherArmor]=
kAttackWithMagic;
break;
}
if (Rnd(1,20)==1)
switch (Rnd(1,5)) {
case 1:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kRetreat;
break;
case 2:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kHide;
break;
case 3:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kAttackWithBlade;
break;
case 4:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kAttackWithBlunt;
break;
case 5:
ai_Creature[i].chromosomes[kAttackerWearingMagicArmor]=
kAttackWithMagic;
break;
}
}Example 15-20 will reassign chromosomes randomly. Each trait has a 5% chance of randomly mutating. This is accomplished with each conditional line if (Rnd(1,20)==1). Like the createIndividual function, there are limits to the values we can assign to each trait. We use the switch statements to ensure that only legitimate values are assigned to each trait.
You can incorporate genetic algorithms into a multiplayer role-playing game in other ways as well. The previous example focused mainly on changing behavior in response to player actions; however, other areas of game design can benefit from genetic algorithms. For example, role-playing games typically categorize character abilities and assign a point level to each. A troll might have 100 opportunity points to divide over several attributes, such as strength, magical ability, dexterity, and a magic resistance. Instead of assigning the same values to each troll in the population, it might be better to use some diversity. For example, some would be physically stronger while others would have a greater resistance to magic. Varying the point distribution and then ranking the fitness of the population would help determine the best balance of point distribution. Successive generations of trolls then could evolve into more challenging adversaries for the players.
Further Information
As we stated earlier, many strategies are available for implementing crossover and mutation. Further, many other game problems besides the ones we’ve discussed could use genetic algorithms effectively. If you’re interested in pursuing genetic algorithms further and would like alternative strategies and additional examples, we encourage you to check out the following references:
AI Application Programming (Charles River Media)
AI Techniques for Game Programming (Premier Press)
AI Game Programming Wisdom (Charles River Media)
Mat Buckland’s book, AI Techniques for Game Programming, covers both genetic algorithms and neural networks and even shows how to use genetic algorithms to evolve, or train, neural networks. This is an interesting alternative to the back-propagation training method we discussed in Chapter 14.