Evolutionary Algorithms used to make better videogame AIs

There was an interesting blurb in New Scientist about evolutionary algorithms in videogames:

The team used evolutionary algorithms to generate characters for the game Quake3 and then multiplied them by producing random mutations in each character’s behavior. Each of these mutants then took on the standard computer opponent. Those that performed well were "mated" to create a new selection of mutants, while the rest were discarded. The team repeated the process a number of times, finally creating characters that were able to beat the conventional computer bad guys and were much tougher for humans to play against.

This is the first time I’d heard of evolutionary algorithms being used in videogames, but it makes sense. If they can compute the shortest way to connect a bunch of points, or other complex math problems, and if they can evolve complex behaviors, then why not make more difficult videogame AIs? Evolutionary algorithms can produce a stunning number of different results, which would mean more distinct AIs, which creates more realistic and more difficult gameplay. Not only could it produce a multitude of different styles, it could also produce the best ones.

Traditionally, as difficulty level increases, enemies simply have more health, deadlier and more accurate weapons, and find you faster; behavioral modification is slight (at least in the games I’ve played). However, now they could actually behave more effectively, more like a real player would, with strategies and tactics. Evolutionary algorithms routinely surprise their designers with how much they can produce from little input, and the same would be true of game AIs: very complex situation-dependent behaviors would emerge. Even in advanced games, even on the highest difficulties, AIs are still pretty dumb. By evolving characters, game designers could change that.

An even more dramatic improvement would be characters that evolve based on how you play. Over the course of the game, you kill thousands of characters. The game knows characters are easiest for you to kill, and can play less of them. But you also die dozens of times, so it would also know which ones kill you best, and could play more of them. In this way you’d find yourself up against the most vexing opponents for your style. Not only could the game change the frequency of the characters, it could change the strategies themselves. As you progress and get better at the game, the characters adapt to your style, and you have to counter-adapt. In evolutionary terms, this is an arms race, and it ends with you as a better player. Or losing and throwing the controller at the screen, whichever comes first.

I have yet to play a videogame where the AI is harder than another player, and with evolutionary algorithms it could soon happen. I look forward to the day when the computer is better than my roommate (that bastard can really kick ass at Halo).