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.
Rebel Moon Rising
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.
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.
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.
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.
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 firstname.lastname@example.org