Genetic Programming for Artificial Intelligence

Genetic Programming is an automated method of generating code by leveraging processes similar to the ones which are in effect in reality, namely natural selection.  Essentially what you do is create a bunch of components, mix them up in various ways, and measure the result of each.  Initially it’s very likely they don’t do what you want at all.  You cut out the worst of each generation, recombine them (programmatically, using some technique), and try again.  The idea is that eventually you will programmatically generate a technique that works as well or better than something that you would engineer from scratch.  It’s a very interesting technique, and I encourage you to read about it if you’re so inclined, but what I’d really like to talk about is the limitations of it.

When applying Genetic Algorithms, the key factor is that you need to have some kind of fitness criteria to measure each iteration with.  In the real world, the ‘fitness criteria’ is ability to survive long enough to breed, and it is enforced by the universe itself (which kills you off it you don’t make the cut, so to speak).  When employing this technique, you generally need to be more specific, and have a goal in mind that you’re trying to accomplish.  In generally this is HIGHLY specific, (e.g. a circuit which raises the output of the input signal to the third power) but this is mostly because determining the fitness criteria is one of the hardest parts about Genetic Programming.  And so far, we’re not very good at determining fitness for vague things.

This is an area of active research, and there’s probably a lot of room in this field to get yourself a PhD if you’re interested.  One of the possible uses for GP which always immediately comes to mind is to develop AI.  Efforts at doing this have met with little success so far, certainly none that are commercially viable.  Part of the problem is that AI is designed to be flexible, and many of the GP techniques are designed to solve specific problems.  What I propose is that instead of developing a general AI, we confine the problem a little bit, and attempt to develop a better AI for computer games. 

While GP is often used to develop parts of the AI, it’s usually the more esoteric parts which are really Optimization problems such as Path-finding.  The type of AI I suggest is more of a “Strategic AI”.  Video Games, like all games, are defined by what are called a “Possibility Spaces”.  This possibility space is structured around the rules imposed by the designer of that game, and thus creates a world with limits.  Playing a game is fundamentally about exploring the possibility space, and there are all sorts of ludological theories about the mechanisms that occur when you do that (If you’re interested in that sort of thing, I might recommend Daniel Cook’s Blog at Lost Garden, or an except from a talk with Will Wright).  Because these possibility spaces are in most games very highly defined and structured, it means the AI only needs to understand how to operate within the context of that space, and to come up with strategies in which to operate depending on which ‘area’ of that space it is currently occupying.

My suggestion for how to implement this is to start by making the basic building blocks of the AI atomic bits of code that represent verbs.  “Move forward” “Move back” “Look for X”, “Hide”, “Shoot”.  Mix these in with various inputs that the character motivated by the AI would encounter, these being the other tokens in the game, including the human player.  These objects can then be programmatically combined and used to generate a more complex AI through the process of GP.  The trick comes in when it comes to defining the fitness function for the AI. 

This is the more tricky part.  It depends on what the character behind the AI is trying to do.  Let’s say we were talking about a FPS, in which case it’s fairly simple.  Kill the people on the other team, don’t get myself killed, protect people on my team.  Almost every FPS on the planet has mechanisms to determine this kind of data built in.  If you had a sample population that were reasonably intelligent, you could just have them play off at random against each other, and continue the process that way.  You could, in fact, continue to do this after release and offer AI patches perodically when you had major improvements in your AI behaviour.

But how to seed the populations of AIs in the first place?  Simple answer:  XBox Live.  Take several thousand copies of your AI, and work with Microsoft to set them up with XBL accounts, and just dump them in the player pool.  Offer free beta testing for regular users, and let them kill off your AI population.  Every couple of days during the beta period, while the rest of the team is responding to non-AI issues, the AIs can be regenerated and use the same accounts they had before.

It may be the case that an insufficient number of iterations would go by in the time period to get a successful AI.  Typically the fitness function is very simple and it takes thousands of iterations to get a reasonable result.  In this case the fitness function is replaced by real human players and the performance of the AI against those players, which takes several minutes.  On the other hand, by having many games going in parallel, the time it takes to run through an entire generation may only be those minutes.  If the regeneration process only took an hour or so, one could do several generations in a day.  Additionally, by seeding the population with heavier verbs in the first place it may be possible to get a reasonable result in only a few hundred generations.  It would be an interesting experiment to try with a simpler game, perhaps in flash, online.  If that game were played by thousands of people online, we would be able to get a feel for how many generations would be required, based on a feeling of the complexity of the possibility space in question.  Anybody interested in pursuing such a project might be well advised to check out this site for some resources on GP and Game AI.