Game AI: The State of the Industry

Since the birth of the videogame market, artificial intelligence (AI) has been a standard feature of games - especially with developers' emphasis on single-player games, which represented the vast bulk of released titles up until fairly recently. Although the recent support for multiplayer capabilities (especially via the Internet) and free online gaming services such as Battle.net and Microsoft's Internet Gaming Zone may have prompted some developers to downplay the need for good computer opponents, good AI is needed more than ever.

At the 1996 Computer Game Developer's Conference (CGDC), I attended a number of excellent technical discussions on game AI. Everything from formal university techniques to better pathfinding was presented to standing-room-only crowds. As a result, developers Eric Dybsand, Neil Kirby, and I thought the time might be right to begin a series of CGDC roundtables on game AI, both as a forum for developers to exchange ideas and as a venue for gauging the industry's use of AI techniques. This article discusses what was discussed in those roundtables, details some industry trends, highlights some recent games that use interesting and innovative AI techniques, and examines how the impact of offloading 3D graphics processing onto hardware may affect AI. I'll wrap up with the thoughts of various game developers on the future of game AI.

Historically, game AI has been one of the last maidens to join the dance during the development process. Emphasis was placed on other aspects of the game, from tuning 3D engines to integrating last minute sound effects. Design and coding the computer opponents was often deferred to the final phase of the project, when it was dumped on whichever hapless developer happened to be least busy at the moment. There was little planning beyond "Get it done by the shipping date," and little design beyond "Don't lower the frame rate."

In part, this can't be helped. For obvious reasons, most testing and tuning of computer opponents can't really be done until large portions of the game are already complete. Since this doesn't usually happen until close to the shipping date, it can be difficult if not impossible for developers to correct any major deficiencies in the AI if anything pops up at the last minute. That's one reason why patches are issued a mere week or so after a game hits the streets.

This state of affairs seems to be changing, however. More developers are becoming involved in the design and implementation of the AI at an earlier stage, and more resources are being dedicated to AI processing. Table 1 (below) shows the results of two questions we asked all developers who attended the CGDC AI roundtables in 1997 and 1998. While these figures and others from the roundtables shouldn't be considered statistically accurate and cannot necessarily be applied across the entire industry, they do show some encouraging trends.

The number of projects with developers dedicated to game AI increased sharply from the roundtables of 1997 to 1998, from roughly 24 percent of all projects represented to nearly 50 percent. A handful of developers reported that there were "two or more" programmers dedicated to working AI, and one developer at the 1998 session reported a whopping three programmers wholly dedicated to game AI and scenario development. AI is still taken care of by a small subset of the programming staff, and these developers often have other duties as well, but this situation seems to be rapidly changing.

The average number of CPU clock cycles reportedly dedicated in some fashion to AI processing also jumped from the 1997 to 1998 roundtables, from an overall average of 5 percent to around 10 percent. When broken out between real-time action games and turn-based games, we noted that the biggest gains were made by developers who were responsible for the former. This jibes with the fast evolutionary pace of the real-time action game genre. On the other hand, gauging AI advances in turn-based games is necessarily tenuous: many of those present who were working on turn-based projects said that they basically received all of the CPU power they needed when it was the AI's turn.

Significantly, developers overall reported that AI was becoming a more important factor in game design than it had been in the past, often being assigned an equal priority with graphics and sound in the initial game design and allocation of resources. Those responsible for game AI (whether or not it is their sole task on the project) are getting involved earlier in the design and development cycle, smoothing the way for better integration between the AI and game engine. Fewer developers reported having the AI dumped on them in the last month of development, although everyone cited the crunch of the shipping date as a major factor in the tuning of any game AI.

A handful of developers in the roundtables noted that working on a sequel to a successful game, or building on a licensed 3D engine technology, often gave them greater freedom to pursue development of more capable computer opponents. In such instances, this growing emphasis on AI seems as much feature-driven as technology-driven, as companies look to differentiate products in the marketplace.

An interesting side effect of the rapid advances in the 3D hardware acceleration market is that the CPU has been freed up for more AI-related tasks. While some developers at the roundtables felt that the trend towards more glitz in games was stealing CPU cycles away from other portions of the game engine, most developers were of the opinion that offloading 3D processing to 3D hardware was gradually giving them CPU cycles that could be used for deeper AI processing. All the developers felt that offloading 3D processing was a positive trend, especially with today's powerful CPUs (such as the Pentium II and the AMD-K6-2 with 3DNow!) providing orders of magnitude more processing power than were available just a few years ago.

Another trend is the rise of the AI specialist - an external developer who focuses solely on creating the game AI. (Full disclosure requires me at this time to note that I'm just such an individual myself.) This can be a low-risk approach for companies that are interested in providing more challenging AIs in their games, but which lack the in-house experience to develop it. Several developers also noted that their companies are in the process of setting up their own internal teams to handle all AI development across multiple games, which is something that simply didn't happen just a couple of years ago.

A handful of people from development studios stated that they were also attempting to find developers with knowledge of both AI and general writing/story-telling expertise. This trend was most evident among groups working on RPGs, especially online products, and likely reflects some of the lessons learned from Origin's Ultima Online experiences. Developers working on these projects felt that by hiring AI developers experienced in writing and story telling, they could build more realistic worlds that would interact with players more consistently with what the games' producers had in mind.

Exploring the AI technologies used in games has been popular in the CGDC roundtables. As the importance of good game AI increases, developers have been turning to academia and defense research for information on more exotic technologies and better methods than the brute force approaches often used in the past. Here are some AI technologies that have been employed recently.

Rules-based AI
Rules-based AI, characterized by the heavy use of the almighty finite state machine (FSM) and its close cousin, the fuzzy state machine (FuSM), remain the technologies of choice for AI development. Every game on the market uses rules-based AI to some degree or another and with good reason: these methods work. Rules-based AI remains the foundation of opponent intelligence in most games for three simple reasons:

Yosemite Entertainment's S.W.A.T. 2, on the other hand, demonstrates some of the capabilities of FuSMs, which were heavily used for the tactical AI in that game. This approach was driven by the game's design: the developers wanted set scenarios that could play out in any number of plausible, yet different ways. Similar games often use scripting to lay out a scenario, but this can lead to predictability and limits replayability. S.W.A.T. 2 gets around this by building FuSMs. Each possible decision is run through a bit of code they call a "fuzzy decider," which weights the possible responses of any given unit based on its health, personality, and so on, and then chooses one of these randomly. The result is a series of actions that are perfectly believable and realistic, but which vary from any previous game so the player is never quite sure what will happen. FuSMs also provide more of an "analog" feel to the AI, allowing a spectrum of realistic behaviors that might not be expected by the player.


One nice side effect demonstrating the intrinsic power of such a straightforward approach to AI can be seen in something called "emergent behavior." A developer faced with coding a complex AI can instead break it down into smaller pieces. Rather than having to code thousands of rules for every conceivable situation that could arise in a game, lower-level behaviors are coded individually and then linked in a decision-making hierarchy. The interaction between these low-level behaviors can cause higher-level, more "intelligent" behaviors to emerge without any explicit programming. This is the basis behind flocking, an AI technology that seeks to emulate the behavior of large groups of animals, such as flocks of birds or schools of fish. No one member of a flock actually knows anything about the motion of the flock, and yet through individual actions their motions are coordinated and fluid. Flocking has found its way into a number of first-person shooters and RPGs as the basis of sort of artificial life, another form of AI technology seeing more use in games.

A number of game developers have started investigating the use genetic algorithms (GAs) in their games. Genetic algorithms, which you can read about in Swen Vincke's article on page 36 of this issue, are something of a rules-based approach to AI, but focus on using digital analogs of biological DNA that allow an AI, in effect, to rewrite itself in response to its environment.

Cyberlife's Creatures makes heavy use of a combination of chemistry-based GAs and neural networks to control virtual pets (called Norns), which learn how to speak, feed themselves, and interact with the player in a variety of ways. These creatures live in a virtual world filled with unexplored areas, beginning the game in nearly total ignorance of their environment. Every aspect of an individual Norn is encoded in a form of digital DNA and can be passed down to descendants over time, allowing players to selectively breed Norns with desired characteristics. A sophisticated mutation engine forces new characteristics to pop up from time to time. Norn DNA can be exchanged online with other players, adding to the gaming experience, and the game's creators have a web site dedicated to assisting in these exchanges.

This ability to create new characteristics has proven to be one of the most popular and interesting parts of the game, and has led to developments in the Norns that have surprised even the programmers at Cyberlife. At one of the 1997 CGDC roundtables, Creatures producer Toby Simpson reported that they had received a DNA strand from a player whose Norn seemed "smarter" than the others in the player's world. Examination of its "brain" showed that it had indeed mutated, spontaneously developing additional "lobes" (processing centers) for its AI to work with.

Oidian System's Cloak, Dagger, and DNA is another game making use of GAs, using them to produce smarter opponents. A Risk-like game of world conquest, the heart of CDDNA uses GAs to guide the computer opponent's decisions. The game comes with four different AI opponents, each of which has a strand of digital DNA containing rules governing its strategy in the game. As each AI plays, a record is kept on how well it did in every battle. Between battles, the user can pit the AIs against each other in a series of tournaments; the winners survive to provide stronger and more capable computer opponents over time. The player can edit a given AI's DNA if so desired, ultimately building a library of opponents that are theoretically adapted to each player's unique playing style.

It's worth noting that the natural adaptive abilities of technologies such as GAs are giving developers a tool that can help them tune an AI during development. Several developers in our CGDC roundtables either mentioned that they had used genetic algorithms to help tune their AIs, or were considering it.

AI tuning is always somewhat problematic; by the time a game is near enough to completion that tuning can be done meaningfully, there can be hundreds of parameters that can affect the AI's style of play. Testing every combination is an impossible task, especially given the often short amount of time that, by that point, remains in the development cycle. Using GAs to tune an AI involves making hundreds of runs of a game using various parameters for the computer opponents, and then using genetic algorithms to tweak those parameters from run to run to favor those AIs that perform better. Over time, this method can test out many more AI variations than an individual developer ever could, allowing him or her to focus on particular configurations that work poorly and to select a more capable suite of AIs for the final product.

The drawback to using GAs and neural networks in games is that they require a considerable amount of time to converge to any significant degree. Both Creatures and CDDNA demonstrate this. Each requires dozens or hundreds of AI generations of evolution before the player begins to see significant behavioral changes. CDDNA solves the problem by providing the player with an offline testbed in which AI strains can wage war against each other in a batch-processing mode. Players can interrupt the process at any point and move the current champions into a stable of computer opponents. Creatures makes the convergence and training process part of the game itself, involving the player in the breeding, raising, and education of the Norns. In this way, the enormous load that a neural network places on the CPU can be handled without adversely impacting graphics or game play. (Cyberlife states that each Norn requires roughly five percent of a CPU's cycles.)

A-life is more a description of a desired result - a realistic emulation of biological behavior - than of a technology, per se. A-life is nothing new. The classic showcase in this field is the well-known Life computer program, but only recently have developers begun looking to A-life to build better game AI. The aforementioned flocking behavior is an example of A-life that was implemented using a simple rules-based approach, while Creatures uses genetic algorithms to achieve its organic behavior.

A-life technologies offer a way to build a better and more believable environment for games. They're particularly powerful when used to control the actions of NPCs in online role-playing games. For instance, very few of Ultima Online's paying customers want to play a village blacksmith when they could choose to be powerful knights and sorcerers, and yet village blacksmiths are an essential part of the gaming experience. Ultima Online also uses A-life to control the spawning, migration, and activities of wandering monsters and other wildlife. Parameterized characteristics allow different species to behave differently, so wolves have a predisposition to hunt in packs in forest regions while dragons tend to be solitary and dwell around mountains. This ecological system leads to a relatively realistic environment in which players can adventure freely. (To some extent, this realism was later compromised in the interests of game play, but that's a topic for another article.)

Flocking, mentioned earlier as an A-life technology, has found its way into some of the more recent game releases. Half-Life and GT Interactive's Unreal both use flocking to control the movement of groups of fish, birds, and monsters to create a more realistic and natural environment. Players, in return, have noticed and commented on the fact that these games don't feel as canned as previous first-person shooters. Players feel as though they're interlopers in a living, dynamic environment, rather than stalkers going from room to room slaughtering monsters.

While many games over the years have allowed users to modify various game-related parameters, only recently have developers begun to let players alter and extend their computer opponents in a more direct fashion through scripts and code plug-ins. The most common example of this is, of course, the Quake's Bot phenomenon. When id introduced the world to the Quake scripting language, Quake C, it radically changed the level of interactivity expected in games. Players were able not only to build their own levels and fill them with monsters, but actually to specify how the monsters would act in some situations. If players didn't like the monsters that came with the game, they could build their own - and they did. A whole subculture of Bot builders sprang up on the Web, and players have developed a surprising variety of highly capable computer opponents.

More recently, Unreal was released with Unreal Script, a robust programming environment that allows extensive customization of the game by the players. Developed by Tim Sweeney, Unreal Script provides a higher-level interface to the API controlling the computer opponent. This obviates the need for detailed programming statements in favor of more general directives such as, "Run forward two seconds, fire a weapon, find a new attack spot, run to it and evaluate, and create a new attack strategy," Players, in turn, have been using this capability to develop a wide variety of Bots, from deadly Terminator NPCs to companions who assist the player in various ways.

Grimmware's Wisdom of Kings - The Twilight War take this concept one step further. Due to be released towards the end of this year, WoK (a real-time strategy game in the Age of Empires vein) will break out the AI for each unit type into stand-alone .DLL files that players can rewrite or replace. The developers intend to expose the API completely to the player, providing the source code for the AI shipped with the game so would-be AI developers will have the option to start with the factory-built opponents or build their own from scratch. Grimmware will provide documentation and support via the company's web site. Activision plans a similar approach to its upcoming title Civilization: Call to Power.

Providing hooks in a game to support an extensible AI isn't easy, however, and while the trend is growing, developers at our roundtables agreed it's not likely to become widespread. The groups were split on whether extensible AI is even worth the effort, and with good reason. Significant technical challenges are involved (Do we provide hooks through raw code or a scripting interface? How much control do we give players? How do we prevent hackers from writing AI module viruses that can wipe out a hard drive?), which require careful design from the beginning of the game's development cycle. The development costs of such an AI engine can quickly approach the level of the 3D engine, with arguably less significant impact on sales. Building in this level of interactivity and extensibility also presents developers with another dilemma: they risk exposing proprietary technologies to the scrutiny of competitors.

What technologies are on the horizon that might be useful in games? Will good AI continue to increase in importance, or will multiplayer eventually render it moot for all but the most disconnected players? Do consumers really care about good game AI, or are they more interested in the latest 3D special effects? Would dedicated hardware (a la 3D hardware accelerators) be useful?

As might be expected, these topics elicit heated debates. Developers at the roundtables weren't sure where the next big advance in game AI might come from, though they did offer their opinions. Most people felt that they would slowly move away from a hard-coded, rules-based approach toward more flexible AI engines based on fuzzy logic and neural networks. While these technologies are presently prohibitively expensive for most kinds of games, widespread opinion was that learning from and adapting to the players' style would become a more important feature over the next few years.

One technology that many developers agreed would be a significant advancement is speech recognition. Until recently, speech recognition was largely the subject of academic and military biometrics research, but lately speech recognition APIs have begun to trickle down to PCs and are now attracting the attention of game developers. Already in limited use in a couple of flight simulators, speech recognition will be an option in a handful of first- and third-person shooters and real-time strategy games in development for late 1998.

One of these is Fenris Wolf's up-coming Rebel Moon Rising, a third-person real-time action game in which the player is the leader of a squad of space-suited marines. A key element of its AI technology will be the use of speech recognition as an interface between the players and the other members of their fireteams.

Robotics research was also cited as an interesting area of technology that might have applicability to game AI. Researchers at NASA and Carnegie-Mellon University have been working with autonomous robot designs for a number of years now, finding ways to integrate navigation, learning, and limited decision making for probes intended for planetary exploration. Because the distances are too great to permit real-time control by technicians on Earth, researchers have had to develop techniques that allow these robots to make their own decisions. There are some striking parallels between this work and what could be accomplished with unit AIs in real-time strategy games, NPCs in massive multiplayer RPGs, and so on.

In general, AI developers as a group felt that game AI would continue to see incremental and slow evolutionary advances, rather than revolutionary changes. We will continue to be CPU- and design-bound for the foreseeable future.

Finite State Machines
The FSM is probably the single most common AI technology in use, though many developers may be unaware of it. Simply put, an FSM is a logical hierarchy of rules and conditions that can only be in a fixed number of possible states. The inputs and outputs of each state are identical, and there's no choice of the sequence in which states are visited.

An example of an FSM might be the logic controlling the doors on the USS Enterprise. When one approaches them, they open; when one clears them, they close. In Red Alert conditions, only authorized personnel can use them. A few simple conditions (authorization and proximity) control a limited set of actions (opening and closing). Sequencing is maintained by the fact that a door can't be closed if it's not open, and vice versa.

Fuzzy State Machines
The FuSM is much like its FSM brother, with a twist: rather than a given set of inputs mapping to a specific output, they map instead to a "membership" to a set of possible responses. These potential responses are each given a weight based on their membership. Developers then use a variety of methods to select a given response - the weights might be used as a simple probability, or they may be accumulated and matched against some threshold value to see which one is triggered. The result is a state machine that can generate a variety of different, yet plausible, responses to a given set of stimuli. Keeping with our example of the USS Enterprise, where the doors might be controlled by FSMs, we would probably want a Klingon warship controlled by an FuSM, so that it could react flexibly to changing battlefield conditions.

Artificial Life
A-life is the name given to a particular discipline that studies natural life by attempting to recreate biological phenomena from scratch within computers and other artificial media. A-life emulates biological life by building systems that behave as living organisms. Depending on the design, one can use hard-coded rules, genetic algorithms, or a variety of other methods for this emulation.

Genetic Algorithms
GAs are an approach to machine learning that derive their behavior from the processes of natural evolution. This is done by creating within a machine a population of individuals represented by chromosomes - in essence a set of character strings that are analogous to the chromosomes that we have in our own DNA. The individuals in the population then go through a process of evolution in which they are tested against some fitness criteria. Those that fail are discarded, while those that score highest are allowed to breed - essentially, creating a new individual using a combination of two or more individuals' chromosomes. Mutation is often allowed to prevent things from settling into a steady state. The result is a population of individuals that gradually adapt themselves to the constraints of their digital environments, in effect evolving over time.

Why Do So Many AI Technologies Seem Similar?
The astute reader might notice that a lot of AI technologies seem as though they're variations on a theme. Genetic algorithms, neural networks, and even FSMs can all modify themselves; GAs, neural networks, and A-life are all biologically-based, and so on. One might well wonder, therefore, why AI experts bother to make distinctions between them.

It's a good question, and unfortunately a good answer might take more space than allowed by this article. Suffice it to say that various AI technologies have a lot in common with each other, and can be viewed as variations on a theme. (For example, a neural network that is nonlearning is basically just a big set of rules and can be reduced to a series of cascaded FSMs.) Adding to the confusion is the fact that there are different names for some AI technologies depending on what field of engineering is using them.

The following is a very short list of resources for developers interested in digging more deeply into game AI technologies and research.

Books and Periodicals
Precious few books really discuss AI from a gaming perspective. Most are more academic-oriented texts that go into theory more than practice. Probably the best single comprehensive reference at present is Artificial Intelligence: A Modern Approach by Stuart J. Russell and Peter Norvig (Prentice Hall, 1995).

Additionally, author Bryan Stout ("Smart Moves: Intelligent Pathfinding," Game Developer, October/November 1996) is working on a book dedicated to game AI due out in early 2000. It's tentatively titled Adding Intelligence to Computer Games and will be published by Morgan Kaufmann.

Newsgroups
Several Usenet newsgroups focus on artificial intelligence in general and game AI in particular. A few of the better ones in terms of noise-to-content ratio are comp.ai.games, comp.ai, and rec.games.programmer.

Web Sites
There's probably no better resource for researching AI technology than the Web. Some sites I recommend include:

http://www.concentric.net/~swoodcoc/ai.html - The author's page, dedicated to all things related to game AI. It includes links to other AI resources, archives of various Usenet threads, and a page focusing on games making use of particularly interesting AI technologies.

http://hmt.com/cwr/boids.html - Craig Reynolds is the Father of Flocking. His page is the best place on the Web to start research into the theory and technology behind flocking and similar A-Life technologies.

http://www.aracnet.com/~wwir/j&p.html - Nova Genetica is one of the best online references for all things related to genetic algorithms and genetic programming.

http://ai.iit.nrc.ca/ai_point.html - The Artificial Intelligence Resources page is maintained by the NRC/CNRC Institute for Information Technology; it's an excellent starting point for AI research.

http://www-cs-students.stanford.edu/ ~amitp/gameprog.html - Amit's Game Programming Page is crammed with information on path-finding algorithms and pointers to other AI resources.

Steve's background in AI comes from a decade of SDI-related work building massive real-time distributed wargames for the Air Force. When he's not saving the world, he's busy doing AI development on a contract basis and target shooting when he gets the chance. Steve lives in gorgeous Colorado Springs, Colo., with a very understanding wife and an indeterminate number of ferrets. His e-mail address is [email protected]