Developing By Me

Project Development and Design

Genetic Algorithms

Genetic Algorithms [GA] are rarely used within the gaming environment because the results can be unpredictable if each of the generations are not properly controlled. A GA is not as difficult to implement as some advanced concepts, however, the ability to predict the results can make it impractical. In order to understand how GA could be used within a game environment. It is important to know what is involved in creating a GA. There are two functions required for a proper GA to work correctly. They are genetic representation and fitness. The representation function handles the current state of each member in the population as individuals, groups or a whole. The fitness function explains how each member is suited to the current state of the world. These functions are the basic requirements however they can be broken down in to smaller sections.

The best way to explain these concepts is by example. Since the actual code can be quite complex the explanations of the functions, statistics and methods will be as general as possible to provide an overview of the concept. To facilitate this, the following tables will describe some information about the members or Actors in the population. The tables show the current Status and Statistics that will be used in the examples.

Statistics Description
Health Number of Hit Points
Defense Reduces damage taken
Accuracy Ability to hit the target
Dodge Ability to deflect an attack
Damage Number of life taken on a successful attack
Status Current state of the Actor
Gender Male, Female, Unic

 

Status Description
Killed Actor is dead
Reset Actor was reset by server
Young First age group
Juvenile Second age group
Adult Third age group
Old Fourth age group
Ancient Fifth age group
Died Final age group

 

The population is described by 7 Statistics [Stats] (first table). The first five are required for any game to be successful since they deal with combat. The sixth is the current status or state of the Actor (second table). The seventh and final is the gender of the Actor. The last stat is important when working with populations and generations which will be covered shortly. But first it is necessary to explain how the different stats relate to the genome of the Actor. Each stat represents a genetic state that the Actor has and will influence future children.

The genetic representation function of an actor can be shown in a table or collection of rows which can be described as an associative array or as members of a class. The following table shows the test population during the first generation of the population. This is a subset of the actual population that can be used to explain how a GA works. The first five stats are represented on a scale of 1 to 10 where 1 is the weakest and 10 is the strongest. The last two will be enumerated in the function and represented as a string.

Name Health Defense Accuracy Dodge Damage Status Gender
Bob 4 1 2 1 1 Young Male
Sally 8 3 5 3 3 Adult Female
Jim 6 4 6 3 3 Killed Male
Dan 3 1 1 1 1 Young Unic

 

After reviewing the table it is obvious that the majority of the statistics are not very strong since the population is first generation. In this example any Male or Female can reproduce in the next generation however a unic cannot reproduce. The genetic reproduction model will determine how many children each female can have and how the attributes will be carried on to the next generation. For this example, the female to child ratio will be 1:1 for simplicity but the reproduction rate can be of any range. In order to reproduce the female (Sally) must select a mate. Each mate will be rated by the GA however this pool will use the status column in order of importance the ages from young to Ancient are preferred, followed by died, killed and reset and unic is ignored. In this example, there is a higher chance that Sally will take Bob over the Jim since he is still alive. But there would still be a chance that Sally mated with Jim before his death, so he must be considered. The chance of reproduction with a killed, died, or reset will be 5% (15% total). There is a 15% chance that she will mate with any living age (75% total) and a 10% of no mate found. With the current population Sally is 75% likely to mate with Bob, 15% with Jim, and 10% none found. At this point a random number is rolled for Sally to determine the mate followed by the child’s stats. For simplicity the stats will be an average of the parents attributes and the new child’s gender will be random. Also after all new children are added the old population members will be aged one bracket and all stats will be improved 1 point. The new population might look like the following table.

Name Health Defense Accuracy Dodge Damage Status Gender
Bob 5 2 3 2 2 Juvenile Male
Sally 9 4 6 4 4 Ancient Female
Kim 6 2 4 2 2 Young Female
Dan 4 2 2 2 2 Juvenile Unic

 

In this generation there are now 2 females and 1 male that can breed. This means the next generation will have two children. Based on this method eventually all Actors in the population will have all statistics near or at 10 even with deaths and childless generations. So how can this be prevented or controlled? Well in a game the player will typically kill the Actors faster than they can repopulate so there is the need for spontaneous generation of Actors. When this happens the new Actor will be created with the base stats of the age group rolled and a gender is selected to balance the population. However, at any time by birth or generation a unic can be born which will slow down the growth of the population. The actual population would have one more member to replace the one who died previously.

Name Health Defense Accuracy Dodge Damage Status Gender
Bob 5 2 3 2 2 Juvenile Male
Sally 9 4 6 4 4 Ancient Female
Kim 6 2 4 2 2 Young Female
Dan 4 2 2 2 2 Juvenile Unic
Smith 3 1 1 1 1 Young Male

 

By using this method the population remains balanced and there are enough Actors for the player to interact with. Through the process of birth and generation; it is possible to maintain a variety of Actors while still maintaining a balance of practical Actors in the game. There are other types of Actors that might occur which can create different scenarios for the player. These unusual actors are nearly always unics so that they do not disrupt the gene pool. Often they are higher level mobs such as elite, boss, mutant or other variations on a theme.

There are many different ways to handle the reproduction and generation of the different actors. The design of the GA is based on the game design itself. The examples shown are very simple however other stats might be considered when designing the actors for the genetic pool. Some other statistics might include Magic Points, Energy, Resistances, Attack Type, Critical Rate, Critical Damage or any other attribute that is appropriate for the game. The additional statistics can produce truly interesting results within the genome pool.

So how will experience change by including deaths? The additional stats are needed because more information is necessary to change the playable experience. Remaining with the simplistic concept an attack type stat will be added. There are two different attacks the actors can have they are either attack in melee or ranged combat. If the majority of the actors that dying use melee then the next generation will use more ranged weapons. This is a method of genetic learning. Genetic learning can be used to change the behavior of the actors in a way that will challenge the player. Since ranged actors will run if the player gets to close. He must switch to a ranged attack in order to fight them. However, if he uses ranged attacks to often then the population will revert to using melee weapons in order to render the players ranged attack ineffective. This method can be used for magic, resistances, damage type, weapon type, and other aspects of the population. Since they can be easily changed from one generation to the next the changes can be controlled to prevent over balancing the environment in any particular direction.

The last thing to consider is constraints. Different communities or gene pools may have a maximum or minimum setting per attribute. The current example uses 1 and 10 as the normal constraint. However another group may have different levels for each individual stat. The minimums and maximums keep the pool within the reasonable expectations of the player. If the area the player is in is a low level zone then the variation should be quite small. However, in a high level area there might be a wide variation of ages and higher statistics since the actors are expected to be harder to kill.

In the higher level areas the more unique environments may occur. For example, the population is being killed by fire attacks constantly. To combat this in an attempt to survive the next generation of actors will have a higher resistance to fire. If the player continues to use fire based attacks then the population will be harder to kill over time. This will force the player to change strategies and use a different kind of attack. By using this method and other possible ideas each genetic pool can use the GA to produce different results and customize the personalities of each group even though different groups came from the same original stock when the game launched.

A GA within the game will produce a constantly changing environment that requires players to think on their feet. This creates a more tactical game and can prevent the player from focusing on a single aspect in combat. Most games expect the player to use brute force to defeat opponents. But by using this method, the game can produce different scenarios within the same game world depending on what tactics the player chooses. Because of this, it is possible for two players to have a completely different experience when playing the same game. If done properly a GA improves the replay value of the game while providing a mental component that is currently lacking. Finally, it is important to know that if the game changes to fast or too often players may find the game too hard to adapt to because of the negative aspects of game play such as frustration or annoyance, however it can be interesting when handled properly. If the GA is properly designed with reasonable constraints then most players will not find the system to be a turnoff. This is because the game will challenge them in more the one way by augmenting the theme or story that the developer is telling.

 

Related pages

  1. Finite State Machines
  2. Neural Networks for a Single Mob
  3. Neural Networks for Groups
powered by Related Pages WP plugin

2 Responses to “Genetic Algorithms”

  • Wilber Hertweck says:

    I simply want to mention I am just new to blogging and site-building and certainly enjoyed you’re blog. Very likely I’m want to bookmark your site . You actually have fabulous posts. With thanks for sharing your web page.

  • Wayne Longworth says:

    I simply want to mention I am very new to weblog and really savored your web-site. Probably I’m going to bookmark your blog post . You amazingly have superb articles and reviews. Appreciate it for revealing your web-site.

%d bloggers like this: