Roguelike Intelligence - Genetic Algorithms and Evolving State Machine AIs
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:
- Develop some structure capable of complicated behavior that's also capable of being adjusted or tweaked just about infinitely.
- If it doesn't do what you want, make small changes in it in a way that's expected to improve its behavior.
- If it does do what you want, stop the program.
- 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 Dillinger