Roguelike Intelligence - Genetic Algorithms and Evolving State Machine AIs

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
 
(Wikified ;-))
Line 1: Line 1:
<pre>
+
== Roguelike Game AI, part 3A ==
Roguelike Game AI, part 3A:
+
        Genetic Algorithms and evolving stateless AIs.
+
  
    Now we're going to get to the first technique that
+
Genetic Algorithms and evolving stateless AIs.
 +
 
 +
Now we're going to get to the first technique that
 
I'd refer to as "Artificial Intelligence" rather than
 
I'd refer to as "Artificial Intelligence" rather than
 
"Pseudointelligence."  The difference between these two
 
"Pseudointelligence."  The difference between these two
Line 14: Line 14:
 
merely pedantic.
 
merely pedantic.
  
    Keep in mind that from this point onward, we are
+
Keep in mind that from this point onward, we are
 
going "above and beyond the call" as far as implementing
 
going "above and beyond the call" as far as implementing
 
roguelike monsters.  I do this kind of engineering for a
 
roguelike monsters.  I do this kind of engineering for a
Line 20: Line 20:
 
own game.
 
own game.
  
    The fundamental algorithm for most kinds of
+
The fundamental algorithm for most kinds of
 
artificial intelligence, when boiled down to first
 
artificial intelligence, when boiled down to first
 
principles, is disarmingly simple:
 
principles, is disarmingly simple:
  
        1. Develop some structure capable of complicated
+
# Develop some structure capable of complicated behavior that's also capable of being adjusted or tweaked just about infinitely.
          behavior that's also capable of being adjusted or
+
# If it doesn't do what you want, make small changes in it in a way that's expected to improve its behavior.
          tweaked just about infinitely.
+
# If it does do what you want, stop the program.
 
+
# goto 2.
        2. If it doesn't do what you want, make small
+
      changes in it in a way that's expected to improve
+
      its behavior.
+
 
+
        3. If it does do what you want, stop the program.
+
 
+
        4. goto 2.
+
 
+
  
    In this article, I'm going to first give a general
+
In this article, I'm going to first give a general
 
introduction to genetic algorithms and then talk about how
 
introduction to genetic algorithms and then talk about how
 
to apply them to the kind of stateless and state-machine
 
to apply them to the kind of stateless and state-machine
Line 49: Line 41:
 
the ones whose behavior is not improved."
 
the ones whose behavior is not improved."
  
    Here is how a genetic algorithm, in general, works.
+
Here is how a genetic algorithm, in general, works.
 
You have a "population" of individuals.  Each individual is
 
You have a "population" of individuals.  Each individual is
 
judged according to a fitness function that says how good it
 
judged according to a fitness function that says how good it
Line 59: Line 51:
 
about that individual at random.
 
about that individual at random.
  
    There are an infinite number of variations on this
+
There are an infinite number of variations on this
 
general theme.  The parameters that the engineer has to work
 
general theme.  The parameters that the engineer has to work
 
with are population size, mutation rate, fitness function,
 
with are population size, mutation rate, fitness function,
Line 69: Line 61:
 
out and avoid some of the more popular mistakes.
 
out and avoid some of the more popular mistakes.
  
        Population size is the number of individuals in the
+
Population size is the number of individuals in the
 
population.  If it's too big, your genetic algorithm will
 
population.  If it's too big, your genetic algorithm will
 
take a long time to converge on a solution.  If it's too
 
take a long time to converge on a solution.  If it's too
Line 75: Line 67:
 
but it may not be a very good one.
 
but it may not be a very good one.
  
    The fitness function is absolutely critical. What
+
The fitness function is absolutely critical. What
 
you're going for is that, in most cases, small changes in
 
you're going for is that, in most cases, small changes in
 
the individuals should map to small changes in the overall
 
the individuals should map to small changes in the overall
Line 99: Line 91:
 
up with, but I'll talk more about that later.
 
up with, but I'll talk more about that later.
  
    The mutation rate has to be considered in
+
The mutation rate has to be considered in
 
combination with the mutation types and the fitness
 
combination with the mutation types and the fitness
 
landscape.  If you imagine that the fitness landscape has
 
landscape.  If you imagine that the fitness landscape has
Line 138: Line 130:
 
have very similar (about as good as there is) fitness.
 
have very similar (about as good as there is) fitness.
  
    The degree of elitism expresses how much of a
+
The degree of elitism expresses how much of a
 
reproductive advantage an individual in this population has
 
reproductive advantage an individual in this population has
 
as a result of being more fit.  The classic "newbie mistake"
 
as a result of being more fit.  The classic "newbie mistake"
Line 152: Line 144:
 
it to the next generation.
 
it to the next generation.
  
    What I usually do is pick three individuals at
+
What I usually do is pick three individuals at
 
random, order them from best to worst in fitness, then
 
random, order them from best to worst in fitness, then
 
assign chances to breed and chances to be replaced for each
 
assign chances to breed and chances to be replaced for each
 
depending on their ranking within the three.  For example:
 
depending on their ranking within the three.  For example:
  
      "normal" elitism  "small" elitism  "slight" elitism
+
        "normal" elitism  "small" elitism  "slight" elitism
        %breed %replace  %breed %replace  %breed  %replace
+
        %breed %replace  %breed %replace  %breed  %replace
best        50    20        40  25          35    32
+
best        50    20        40  25          35    32
medium      30    30        35  35          34    33
+
medium      30    30        35  35          34    33
worst      20    50        25  40          31    35
+
worst      20    50        25  40          31    35
  
 
+
A high degree of elitism will eliminate potentially
    A high degree of elitism will eliminate potentially
+
 
valuable genetic material before that material gets
 
valuable genetic material before that material gets
 
considered in combination with other things it could be
 
considered in combination with other things it could be
Line 187: Line 178:
 
notes but often just wandering.
 
notes but often just wandering.
  
    The gene map and the method of combination also have
+
The gene map and the method of combination also have
 
to be considered together.  The gene map is usually a vector
 
to be considered together.  The gene map is usually a vector
 
or sequence of values, and the values control different
 
or sequence of values, and the values control different
Line 207: Line 198:
 
together in the gene map.
 
together in the gene map.
  
 
+
Now how do we apply this technology to developing
 
+
 
+
    Now how do we apply this technology to developing
+
 
AI's for roguelike monsters?  Well, it's hard.  Some
 
AI's for roguelike monsters?  Well, it's hard.  Some
 
problems I can answer, like what would be a good gene map.
 
problems I can answer, like what would be a good gene map.
Line 216: Line 204:
 
can discuss a couple approaches to them.
 
can discuss a couple approaches to them.
  
    First of all, let's talk about evolving
+
First of all, let's talk about evolving
 
stateless-AI's of the sort I talked about in article 1.
 
stateless-AI's of the sort I talked about in article 1.
 
Each of these is, basically, a nested set of if-then
 
Each of these is, basically, a nested set of if-then
Line 228: Line 216:
 
         / \      /  \        where leftchild(n) = 2n and
 
         / \      /  \        where leftchild(n) = 2n and
 
     act3 act4  act5 act6    rightchild(n) = 2n+1.
 
     act3 act4  act5 act6    rightchild(n) = 2n+1.
 
+
test1 test2 test3 act1 test4 act2 test5  act3 act4 act5 act6
+
test1 test2 test3 act1 test4 act2 test5  act3 act4 act5 act6
1      2    3    4    5      6    7      10  11  14  15
+
1      2    3    4    5      6    7      10  11  14  15
  
 
For example test5 is found at index 7.  its leftchild is
 
For example test5 is found at index 7.  its leftchild is
Line 237: Line 225:
 
nor 12 and 13.
 
nor 12 and 13.
  
    This remapping trick with trees is valuable; it lets
+
This remapping trick with trees is valuable; it lets
 
you code with just a number what the relationships of nodes
 
you code with just a number what the relationships of nodes
 
are within the tree.  You get isomorphic structure between
 
are within the tree.  You get isomorphic structure between
Line 244: Line 232:
 
convergence happens.
 
convergence happens.
  
    Also, you get the ability to use subtree swapping
+
Also, you get the ability to use subtree swapping
 
for your combination function, which preserves entire
 
for your combination function, which preserves entire
 
behavioral complexes from one parent to the next.  That is,
 
behavioral complexes from one parent to the next.  That is,
Line 260: Line 248:
 
the test's subbranches end in actions.
 
the test's subbranches end in actions.
  
    Certain things you'll want to telescope into this
+
Certain things you'll want to telescope into this
 
structure.  Remember that in the handwritten stateless-ai's
 
structure.  Remember that in the handwritten stateless-ai's
 
I had a test to "flight check" every action.  In this
 
I had a test to "flight check" every action.  In this
Line 277: Line 265:
 
stateless-AI that you're trying to improve.
 
stateless-AI that you're trying to improve.
  
    So, we have a gene mapping and a combination
+
So, we have a gene mapping and a combination
 
function.  I'd make a decision that the "individuals" never
 
function.  I'd make a decision that the "individuals" never
 
got more than 1024 nodes (for animals) or more than 4096
 
got more than 1024 nodes (for animals) or more than 4096
Line 290: Line 278:
 
function.
 
function.
  
    Fitness functions are hard to find in RPG game
+
Fitness functions are hard to find in RPG game
 
opponents. Sad but true, the fate of most monsters in a
 
opponents. Sad but true, the fate of most monsters in a
 
roguelike game is to be on screen for about twenty seconds
 
roguelike game is to be on screen for about twenty seconds
Line 304: Line 292:
 
injuries.
 
injuries.
  
    About the best you can do before we cover modeling
+
About the best you can do before we cover modeling
 
the player in the fourth section of this series of articles
 
the player in the fourth section of this series of articles
 
is a fitness function that evaluates, over a monster's
 
is a fitness function that evaluates, over a monster's
Line 324: Line 312:
 
meets and see which ones did better or worse.
 
meets and see which ones did better or worse.
  
    Since there'd be a huge level of variance due to just
+
Since there'd be a huge level of variance due to just
 
plain luck, I'd use a very high degree of elitism on the
 
plain luck, I'd use a very high degree of elitism on the
 
principle that I'm just compensating for getting noisy
 
principle that I'm just compensating for getting noisy
 
measurements anyway.//
 
measurements anyway.//
  
    But, the real-time test of interacting with the
+
But, the real-time test of interacting with the
 
player simply doesn't conclude enough experiments fast
 
player simply doesn't conclude enough experiments fast
 
enough to make a GA approach work really well.  You could
 
enough to make a GA approach work really well.  You could
Line 340: Line 328:
 
to provide the data.
 
to provide the data.
  
    Basically, a genetic algorithm allows you to say
+
Basically, a genetic algorithm allows you to say
 
what goals to try to achieve without specifying the solution
 
what goals to try to achieve without specifying the solution
 
-- but you have to be able to state those goals, and usually
 
-- but you have to be able to state those goals, and usually
Line 358: Line 346:
 
are pathetic, silly, or too embarrassing to talk about.
 
are pathetic, silly, or too embarrassing to talk about.
  
        But don't despair; there is a worthwhile fitness
+
But don't despair; there is a worthwhile fitness
 
function that can be successfully applied to a roguelike
 
function that can be successfully applied to a roguelike
 
game monster AI.  I'll explain it, but we can't actually do
 
game monster AI.  I'll explain it, but we can't actually do
 
it until after part 4, Modeling the Player.
 
it until after part 4, Modeling the Player.
  
    The only worthwhile approach to a fitness function
+
The only worthwhile approach to a fitness function
 
for monsters is run plus status evaluation.  Basically, this
 
for monsters is run plus status evaluation.  Basically, this
 
takes a monster and its situation and tries to project it
 
takes a monster and its situation and tries to project it
Line 379: Line 367:
 
player is going to do for the next few rounds.  And that is
 
player is going to do for the next few rounds.  And that is
 
hard.
 
hard.
 
  
 
Ray Dellinger
 
Ray Dellinger
</pre>
 
 
  
 
[[Category:Articles]][[Category:AI]]
 
[[Category:Articles]][[Category:AI]]

Revision as of 05:19, 15 September 2006

Roguelike Game AI, part 3A

Genetic Algorithms and evolving stateless AIs.

Now we're going to get to the first technique that I'd refer to as "Artificial Intelligence" rather than "Pseudointelligence." The difference between these two terms, colloquially, is that when you're working with an Artificial Intelligence technique, you can be genuinely surprised by the results, where a pseudointelligence simply does what you tell it. But, as far as most people are concerned, if it's what decides monster actions in a game, they're happy to call it "AI" and such distinctions are merely pedantic.

Keep in mind that from this point onward, we are going "above and beyond the call" as far as implementing roguelike monsters. I do this kind of engineering for a living, and I'm not using it (at least not yet) even in my own game.

The fundamental algorithm for most kinds of artificial intelligence, when boiled down to first principles, is disarmingly simple:

  1. Develop some structure capable of complicated behavior that's also capable of being adjusted or tweaked just about infinitely.
  2. If it doesn't do what you want, make small changes in it in a way that's expected to improve its behavior.
  3. If it does do what you want, stop the program.
  4. goto 2.

In this article, I'm going to first give a general introduction to genetic algorithms and then talk about how to apply them to the kind of stateless and state-machine AI's I've talked about in the first couple of articles. The stateless-AI's and state-machine AI's constitute a structure capable of complicated behavior and also capable of being tweaked or adjusted a lot; For a genetic algorithm, the process of "adjusting it in a way that's expected to improve its behavior" means "adjusting members of a population randomly and then biasing survival vs. reproduction against the ones whose behavior is not improved."

Here is how a genetic algorithm, in general, works. You have a "population" of individuals. Each individual is judged according to a fitness function that says how good it is. You then pick a couple of the "better" individuals, and make a new individual by combining their sequences in some way. You replace one of the "worse" individuals with this new individual, and the cycle repeats. Every so often, you pick some individual in the population and change something about that individual at random.

There are an infinite number of variations on this general theme. The parameters that the engineer has to work with are population size, mutation rate, fitness function, gene map, degree of elitism, and method of combining individuals. Many systems change one or more of these parameters during the run. Some discussion of what these parameters are and how they influence the runs (read: guidance at troubleshooting) will help you figure stuff out and avoid some of the more popular mistakes.

Population size is the number of individuals in the population. If it's too big, your genetic algorithm will take a long time to converge on a solution. If it's too small, your genetic algorithm will quickly find a "solution" but it may not be a very good one.

The fitness function is absolutely critical. What you're going for is that, in most cases, small changes in the individuals should map to small changes in the overall fitness, and similar values at similar locations in the genomes should usually mean similar things. But it's often very hard to visualize in advance exactly how the fitness function will map things. For an extreme case, consider a fitness function for finding a key in a modern cipher system; basically, if the individual is the key, its fitness is perfect and if it's anything at all else, its fitness is perfectly wrong. A genetic algorithm can get no "traction" here, because there's nothing to base fitness decisions on. For another extreme case, consider a fitness function that looks at one number in the genome, takes four minus the number, and squares it, regarding the lowest numbers as the best fitness. This presents a simple fitness landscape with one "valley" centered on four. Every change to that number will map to a change in the fitness, and every change that makes an individual more fit will bring it closer to the global optimum. The first system will never converge except by blind luck; The second will converge trivially. Roguelike-AI fitness functions are particularly hard to come up with, but I'll talk more about that later.

The mutation rate has to be considered in combination with the mutation types and the fitness landscape. If you imagine that the fitness landscape has broad curves and few local optima, you'll want a high mutation rate with mutations that make smallish changes; this is called an "exploitation" or "hill climbing" strategy, because it "exploits" the area that the individual is in, making new individuals very near it in the expectation that those with higher fitness scores (those "higher on the hillside") will survive to the next generation, until the optimum is reached. If you imagine that the fitness landscape is very complex, you'll want a lower mutation rate because the changes it makes will necessarily be large. This is called an "exploration" strategy, because it makes individuals that are further away from its parent. Early in a run, lots of these will find themselves at a better level of fitness than their parent, and will in turn become parents themselves; late in the run almost all mutants die. This is the factor that is most commonly twiddled during a run. In a tactic called "simulated annealing", there are periodic 'cataclysms' during the run where the mutation rate is raised far above its normal level to put individuals out there all over the fitness landscape, then returned to a low level so that the unfit ones die out over succeeding generations. You also get a lot of workers who start with a sustained, high mutation rate and then gradually reduce it during the run. What you need to know about mutation rate is not where to set it, but rather what indicates that it's too high or too low. If the mutation rate is too low, then you'll get convergence, but usually on some local optimum. Successive runs will find "solutions" of significantly differing quality. If the mutation rate is too high, you'll get non-convergence; you'll have some highly fit individuals in your population, but the proportion of highly-fit to other individuals won't be increasing as generations pass. When it's just right, you'll get solutions in different runs that have very similar (about as good as there is) fitness.

The degree of elitism expresses how much of a reproductive advantage an individual in this population has as a result of being more fit. The classic "newbie mistake" in genetic algorithms is to always breed the very most fit individuals -- absolute elitism. This doesn't work. Selection entirely at random also doesn't work, as it confers no advantage to the more fit individuals. When you're selecting individuals to breed, or individuals to eliminate, or both, fitness has to influence the decision, but it can't dominate it. Even the "worst" individual in the population should have some chance of having offspring, and even the "best" should have some odds of failing to make it to the next generation.

What I usually do is pick three individuals at random, order them from best to worst in fitness, then assign chances to breed and chances to be replaced for each depending on their ranking within the three. For example:

       "normal" elitism   "small" elitism  "slight" elitism
        %breed %replace   %breed %replace  %breed  %replace
best        50    20         40   25          35    32
medium      30    30         35   35          34    33
worst       20    50         25   40          31    35

A high degree of elitism will eliminate potentially valuable genetic material before that material gets considered in combination with other things it could be combined with; a low degree of elitism will preserve and experiment with genetic material in different combinations, gradually eliminating it only as it finds absolutely no use for it. The more complicated the problem you're trying to solve (the more complex the fitness function and the more complexity-rich the combinations of genes are), the lower the degree of elitism you want. You need to give the system time to make its experiments. Elitism has to be considered in combination with mutation rate; mutation introduces new genes, and if mutation is high and elitism is low new genes will be introduced faster than the experiments with different combinations can play themselves out. A very low degree of elitism requires a low mutation rate to work in your favor. If elitism is too low for the current mutation rate, you'll get non-convergence; however, unlike the situation where the mutation rate is too high in general, the fitness of even the most-fit individuals in the population will fluctuate wildly, sometimes hitting high notes but often just wandering.

The gene map and the method of combination also have to be considered together. The gene map is usually a vector or sequence of values, and the values control different things. The more those things influence each other's value in the fitness function, the more likely you want it to be that they are transferred *together* to an offspring. This is not actually essential, and it doesn't mean the difference between convergence and nonconvergence; but it can make the convergence process significantly faster. The most common method of combination for a vector is "crossover," which means that a copy is made of one of the parents, and then, values from the other parent are copied over them from a randomly selected "beginning" point to an "ending" point. The result of this is that values closest to each other in the gene map are also most likely to be transferred to offspring together. And what that means in practical terms is that you want to put values that form a particular strategy or behavior that's important, close together in the gene map.

Now how do we apply this technology to developing AI's for roguelike monsters? Well, it's hard. Some problems I can answer, like what would be a good gene map. Others, like finding a good fitness function, are hard but I can discuss a couple approaches to them.

First of all, let's talk about evolving stateless-AI's of the sort I talked about in article 1. Each of these is, basically, a nested set of if-then statements. That is, they have a tree structure:

        test1              at left is an example of a
        /   \              a stateless AI, each node of the
    test2  test3           tree is a test or an action.
     / \     |  \
 act1 test4 act2 test5       below is this tree as a vector,
       / \       /  \        where leftchild(n) = 2n and
    act3 act4  act5 act6     rightchild(n) = 2n+1.

test1 test2 test3 act1 test4 act2 test5  act3 act4 act5 act6
1      2     3    4    5      6    7      10   11   14   15

For example test5 is found at index 7. its leftchild is found at index 7x2=14, and its rightchild is found at 7x2+1 = 15. Note that there is nothing at vector indexes 8 and 9, nor 12 and 13.

This remapping trick with trees is valuable; it lets you code with just a number what the relationships of nodes are within the tree. You get isomorphic structure between different individuals, which means the same gene will usually means the same thing in different individuals as convergence happens.

Also, you get the ability to use subtree swapping for your combination function, which preserves entire behavioral complexes from one parent to the next. That is, you just cut a branch off one parent tree and substitute a branch randomly selected from the other parent tree. That preserves complexes of behavior that work together. A good mutation function is one that picks a node and replaces it with a different node. You'd even have access to "small" mutations, since you can replace actions or tests with self-similar actions or tests having different parameters or different implementations. In practice, you'll want a mutation that frequently picks "small" mutations and occasionally picks "large" mutations. Just make sure that if the mutation function substitutes a test for an action, all the test's subbranches end in actions.

Certain things you'll want to telescope into this structure. Remember that in the handwritten stateless-ai's I had a test to "flight check" every action. In this structure, you don't want the flight checks to ever be separated from the actions, so you'd make all actions have a "left child" which could be another test or another action. The child node would be executed if the specified action couldn't be performed. Now, that implies that these trees are infinitely deep, which is not actually possible. So you'll need some "default behavior" that happens when they go off the bottom of the tree. You can go simplistic and pick "wait," relying on the GA to develop every bit of the smarts on its own, or you can use the GA to amplify handcoding by just having the "default" behavior be executing the handwritten (and guaranteed terminating) stateless-AI that you're trying to improve.

So, we have a gene mapping and a combination function. I'd make a decision that the "individuals" never got more than 1024 nodes (for animals) or more than 4096 nodes (for "intelligent" monsters) in them and that the index number of any node simply is not allowed to exceed MAXINT. I'd include code in the branch-swap function to truncate any branch that wanted an index number higher than that. I'd pick a population size around 150, a "normal" or "small" rate of elitism, restrict the range of tests and behaviors to things I considered "appropriate and possible" for that monster type, and then I'd be looking for a fitness function.

Fitness functions are hard to find in RPG game opponents. Sad but true, the fate of most monsters in a roguelike game is to be on screen for about twenty seconds and then get slaughtered. Now, you could take "survival time" as your fitness criterion, but all you would teach your monsters is to be very good at running away. If they got good enough at it, the player would never even see them. And that's probably not what you want. You could take "hits of damage inflicted on the player" as the measure of monster worth, but you run into another problem in that most monsters don't inflict any damage at all, and some of the most fun ones do their stuff in a form other than physical injuries.

About the best you can do before we cover modeling the player in the fourth section of this series of articles is a fitness function that evaluates, over a monster's lifetime, what it has cost the player. A few hitpoints? One- tenth of a charge off a fireball wand? Six charges from a rod of illumination? A round of sword swinging? A speed potion? Food and time spent digging? Whatever it is, you have to assign credit for getting the player to use it to one or more monsters, and then try to decide its value to the player. Remember that the last hitpoint has infinite value and the first has a very small value, so the monster who hits a player for 4 damage when he's low on HP should get more rewarded than the monster who hit for 4 damage when he was full up. Add it all up and assume that the monster who cost the player the most was probably the one with the best AI. You'd need to build this directly into your combat code; having selected the next three "kobold AI's" to test in its GA, the system would have to wait and use them in the next three kobolds the player meets and see which ones did better or worse.

Since there'd be a huge level of variance due to just plain luck, I'd use a very high degree of elitism on the principle that I'm just compensating for getting noisy measurements anyway.//

But, the real-time test of interacting with the player simply doesn't conclude enough experiments fast enough to make a GA approach work really well. You could do it, but it would take a lot of games to develop good monster AI's. A "nice" fitness function, ideally, should be something you can calculate without player input, so you can leave the GA chewing on a problem overnight (or for a week) and see what it comes up with, instead of waiting for hundreds of games by dozens of playtesters, per run, to provide the data.

Basically, a genetic algorithm allows you to say what goals to try to achieve without specifying the solution -- but you have to be able to state those goals, and usually the goals are hard to precisely define. What normally happens is that the first six or eight runs show you what's wrong with the ways you've formulated your fitness function by "raping" it in various ways with the simplest (and least interesting) possible behavior that gets a good fitness score in a way you didn't think of. After that you start getting results that point out subtle errors in your conception of how the monsters' actions and tests worked, or point out exploitable bugs in your combat code. And once you work through all of those, you'd start getting usable, novel results and you start runs where you do a lot of tweaking of your GA parameters such as mutation rate, elitism, etc. A lot of GA runs will result in things that are pathetic, silly, or too embarrassing to talk about.

But don't despair; there is a worthwhile fitness function that can be successfully applied to a roguelike game monster AI. I'll explain it, but we can't actually do it until after part 4, Modeling the Player.

The only worthwhile approach to a fitness function for monsters is run plus status evaluation. Basically, this takes a monster and its situation and tries to project it some number of rounds into the future with different AI's. At the end of that time, the status of the different "virtual monsters" (one for each AI) is evaluated, and the one with the most improved (or least degraded) status is regarded as the best for purposes of this test. It's much easier to write a status evaluation function than it is to write an AI evaluation function, so this is a method of leveraging what you can do relatively easily to get what is much much harder to do. The big problem with this approach is, since you're mainly interested in situations that involve the player, this requires you to guess what the player is going to do for the next few rounds. And that is hard.

Ray Dellinger

Personal tools