Post news Report RSS Why Evolutionary Computation is the Future of Game AI

After several years experimenting with the application of a genetic algorithm to the AI for a physics-based sports game, I'm convinced that evolutionary computation is the future of video game AI. Here's why.

Posted by on

Diversity of Play Styles

The most direct benefit of an evolutionary approach is the richness of play that arises when every player is a unique individual. If properly implemented, a genetic algorithm can explore a vast behavior-space, focusing its attention on just the feasible regions. As evolution proceeds, the programmer can select representative individuals from the population to serve as the final players to ship with the game.

Game Balance

For established games and sports, the best overall approach to the game is gradually refined through a process of trial and error. But for a programmer designing the AI for an entirely new game, the "best overall approach" is not obvious (unless the game is very simple) and can only be guessed at. A genetic algorithm by its nature can hone in on the ideal overall style of play while still maintaining a diversity of individual styles. The coevolving players essentially act as automated play-testers, both balancing the game and, as a side benefit, uncovering any simplistic exploits that might exist.

Natural Parallelism

The obvious drawback of an evolutionary approach is that evolution is slow. The good news is that a genetic algorithm can be parallelized in a straightforward way, by assigning a separate population to each processing core. The cores can thus be conceptualized as islands or continents, with periodic migrations between them. It's easy to imagine a distributed, massively parallel implementation where every installation of the game constitutes an island, and migrations travel through the Cloud.

Variety of Events

The last benefit is subtle, closely related to the first two, and perhaps the most important. It is the tendency of a co-evolutionary system to maximize the variety of events that unfold within the environment. To understand how, consider the relationship between goalies and shot-takers. When a goalie plays close to the goal, it's to the shot-taker's advantage to take the shot from a distance; but if the majority of shots are taken from a distance, then there is selective pressure on the goalies to play further out.

Intuitively, it's easy to see how the population will tend towards an equilibrium, with the goalies playing at some intermediate distance. And that's the key; because the goalies have "split the difference", opportunities remain on either side of the split. On some occasions, goals will be scored from a distance, and on other occasions, from close-in. This principle applies across the board to all types of interactions: players will sometimes cut back, sometimes not; sometimes play the ball, sometimes the ball-carrier; sometimes push up the middle, sometimes go around the ends, and so on.

Here's some sample gameplay from Thetaball, the game I've been working on. All players are AI-controlled.

Post comment Comments
keevee
keevee

This is really cool to watch the video and see how graceful and almost human like a lot of the AI movements are, as well as them predicting where things will be. The fact that they block shows some really cool thought happening AI wise. I've been looking for an excuse to dive into some genetic algorithm building, as well as neural networks. It definitely is the future.

Reply Good karma Bad karma+1 vote
tim_ps Author
tim_ps

Thank you! It's been a fun project -- watching different behaviors emerge & evolve is just a very cool thing. Definitely a fruitful thing to pursue.

Reply Good karma+2 votes
Post a comment

Your comment will be anonymous unless you join the community. Or sign in with your social account: