 14
March
2002
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.
Issues
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.
The definitive genetic algorithm
manual:
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 |