Genetic Algorithms and Video games

A couple of months ago I started a short series of blog posts about genetic algorithms, which I originally intended to develop quickly, but never found the time to do so. Finally, here's the next chapter.

During my time at the Computer Science institute (ISTI) of the University of Urbino, immediately after my graduation, my friends Alessandro, Piervincenzo and I dedicated some time to find possible applications of genetic algorithms to video games. A field that of course we did (and still do) find very interesting. We spent some time coming up with prototypes and developing them - one of which, "Genetic RTS", you'll see in a future post - and our work culminated with a seminary at the university and a short paper published at SECEVitA 2007.

So, GA and Video games?

GAs can also be used to generate nice abstract wallpapers.

In the previous posts about GAs I - somewhat blurrily, but nonetheless - showed that they often provide a viable solution for many generic optimization problems, where finding an efficient solution is not possible. This is done assuming that the algorithm is able to "encode" a solution in some form, generate a large number of such solutions for the given problem and then efficiently test each one of them and evalute their "goodness".

Those same points are the main problems with GAs in video games: generally speaking, none of them can be done easily in the context of a video game. Let's see one point at a time.

Encoding the solution

While encoding the solution for a "find the max of a function" or "solve a XOR logical gate" is very easy, encoding the behavior of an IA player in a standard video game is way too complex. For instance, the code that determines the movement of a bot in Unreal Tournament has tons of parameters and small routines that decide how the bot moves, how it tracks adversaries, when and how it shoots, how it chases or flees, etc... To find a format capable of encoding such a wealth of information would require a huge amount of memory, composed of non-orthogonal information bits (that is, chunks of "genetic information" with interdependencies, i.e. whose influence on the final behavior is constrained or influenced by one or more other chunks of information, which of course can change and mutate on their own).

An Unreal Tournament bot is an incredibly complex problem to be formulated and solved by a genetic algorithm.

The problem we are trying to solve must be suitably reduced to a simpler one, perhaps only at the strategic level, which can then be encoded in a concise manner.

Generate and evaluate tentative solutions

If we are able to find an encoding of our IA "solution", we still must be able to create a large number of them and evaluate them quickly. The problem here is that you have only 3 different ways to do so (which I can think of):

1. Simulation: you throw your tentative solutions into a simulator, where each of them is evaluated and rated based on its success. But, the game itself already is a simulation: we are just pushing the problem around. In this case, you'd essentially would need a simple version of your game that can be used to test the behavior of your IA before deploying it into the game. Goes without saying that this is extremly complex to get right and also requires a lot of time.
2. Arbitrary evaluation: you rate each single tenative solution agains a set of arbitrarily defined rules, which represent a behavior you deem "correct" for your game. In this case you are reducing the problem to the construction of an "expert system" which requires a well defined set of parameters to evaluate what is good and what is bad. The genetic algorithm might still come up with interesting "ideas", but you essentially have no dynamic way to determine its goodness.
3. Challenging the user: you deploy the tentative solution in the real game and let it play. After a certain interval of time you can then measure its performance against a set of rules which determine the "success" achieved by the tentative solution. This must be done for each solution and requires a huge amount of time (compared to the two other ways mentioned above), but on the other hand this is the only way to measure whether a solution works or not against a particular player.

Which one of those solutions works best depends on the kind of video game you are implementing. For example, if you're programming a game of chess you can't let each genetic solution play against the player and could instead use a simulation of all possible moves. If you're creating the AI for Unreal Tournament bots, you might generate a large number of bots randomly and let them play. Once the player kills them you can evaluate their performance (in terms of damage inflicted, etc.) and evolve them.

Level of abstraction

As mentioned above, even very simple AI engines in video games have a lot of work to do. Just moving the simulated enemy through the scenery of the game and aiming (for instance) require a lot of computation that serioulsy impact the overall impression of the IA (an enemy might look extremely dumb if it gets stuck in doors and geometry, even if its moves are perfect from a strategical point of view).

The best thing to do is to implement everything that can be solved deterministically with known AI algorithms: pathfinding is a complex problem that can be solved by a GA, but using A* should always yield better (and consistent) results. Other "problems" might be better not solved: for instance, aiming is best left to standard approximation algorithms. Even if a GA could solve the aiming problem, you'd sooner or later end up with a deadly sniper with perfect aiming which isn't very fun to play against ("perfect aiming" is a far too easy problem, geometrically speaking).

Overall, only high level strategic reactions of the AI should be "solved" by a genetic algorithm. For example, the reactions of a single bot to various actions by the player can be easily encoded in a simple genome and a GA can be used to progressively select individuals that show the best reactions and offer a better challenge. At the same time, the exact workings of all those reactions still should be implemented using traditional methods: a video game player can be made to think that a wrong strategy is a realistic depiction of confusion or "humanity" by the AI, but not the same if the bot runs against a wall or blows itself up all the time.

Killer AI

At good last, another important point about GAs in video games is that, since they tend to improve very quickly under favorable conditions, the adversaries of the player get very good in little time. This can be frustrating in some games: a stealth game that adapts to your tricks and forces you to find new ways to approach the game is great, but an FPS bot that becomes practically invincible is not.

Note that genetic algorithms only improve solutions based on a predefined scheme (the encoding) and evaluate them on an equally arbitrary and synthetic "goodness" scale (the fitness function). This means that in the end, all results that can be obtained through a GA still are limited to a finite set of alternatives (there is no real creativity and everything is constrained to the bounds set by the developer, who must choose a good level of expressiveness for his genome). Moreover, the only objective "goodness" scale that can be used is the effectiveness of the AI: using "gamage inflicted", "points made", etc. as metric also means that the individuals will always be selected in order to maximize their efficiency and not their realism, nor how "fun" they are.

A good example of this problem might be the AI director from Left 4 Dead. This AI most likely is not implemented using a GA, but works to maximize the fun and excitement of the players and not the lethality of the zombie hordes. Like I said before: generating a perfectly deadly bot is easy. The difficult part is to make him credible and - even more important - fun to play against. Unfortunately, "fun" is an incredibly volatile value which hardly can be evaluated by the AI.

Therefore? Are GAs useless in games?

Not at all. Even if you can't optimize your AI for fun, you still can provide and ever-growing and ever-improving challenge to the player. In some cases such an adversary could be very desirable, for instance in strategy games which usually must resort to cheating in order to stand up against very capable players. An AI that can react to the player's behavior and adapt to unforeseen strategies can be extremely fun in those cases.

Also, games where the player's defeat is unavoidable (his/her survival merely determines the amount of points collected, like for example in Defense Grid) could be made progressively more difficult using a genetic algorithm.

The prototype I will show in the next post about genetic algorithms is based exactly on such a system: the game cannot be won. The challenge for the player is to survive to the computer's attack for as long as possible, while the AI progressively finds out the weaknesses in the player's strategy and improves his own tactic. When it works, it surprisingly looks like a cunning adversary... which hopefully is fun.

UPDATE: the paper published at SECEVitA 2007 mentioned above can be downloaded here (in italian).