You’re following a gloomy corridor into a large boiler room, dimly lit by a flickering fluorescent lamp and echoing with the rhythms of unseen machinery. Three enemy soldiers suddenly appear on a catwalk high above the floor. They split up, one of them laying down suppressive fire, which forces you to take cover. Although you shoot back, the attackers still manage to creep forward behind a curtain of smoke and flying debris.
Moments later, a machine gun rings out, and you are cut down in a shower of bullets. Then, as you lie dying, you glimpse the soldier who flanked you from behind while his two buddies drew your attention.
Thankfully, it was only a video game, so in fact you’re not mortally wounded. Still, your ego might well be bruised, because you were not only outgunned but also outsmarted by artificial intelligence (AI).
The game is called F.E.A.R., short for First Encounter Assault Recon, and its use of AI, along with its impressive graphics, are its prime attractions. The developer, Monolith Productions of Kirkland, Wash., released it in 2005 to rave reviews, including the GameSpot Web site’s Best Artificial Intelligence award. Such recognition means a lot to the game’s creators, who face stiff competition in what has become a multibillion-dollar industry.
The game is a far cry from the traditional diversions that AI researchers like ourselves have long studied, such as chess and checkers. Whereas the goal in the past was to write computer programs capable of beating expert players at such board games, now the metric of success for AI is whether it makes video games more entertaining.
Because a high fun factor is what sells, the video-game industry has become increasingly keen to make use of developments in AI research—and computer scientists have taken notice. A watershed came in 2000, when John E. Laird, a professor of engineering at the University of Michigan, and Michael van Lent, now chief scientist at Soar Technology, in Ann Arbor, Mich., published a call to arms that described commercial video games as ”AI’s killer application.” Their point was that research to improve AI for such games would create spin-offs in many other spheres.
The main challenge is to make computer-generated characters—dubbed bots—act realistically. They must, of course, look good and move naturally. But, ideally, they should also be able to engage in believable conversations, plan their actions, find their way around virtual worlds, and learn from their mistakes. That is, they need to be smart.
Today many video games create only an illusion of intelligence, using a few programming tricks. But in the not-so-distant future, game bots will routinely use sophisticated AI techniques to shape their behavior. We and our colleagues in the University of Alberta GAMES (Game-playing, Analytical methods, Minimax search and Empirical Studies) research group, in Edmonton, Canada, have been working to help bring about such a revolution.
The AI of F.E.A.R. is based loosely on an automated planner called STRIPS (for STanford Research Institute Problem Solver), which Richard E. Fikes and Nils J. Nilsson, both now of Stanford University, developed way back in 1971. The general idea of STRIPS was to establish one or more goals along with a set of possible actions, each of which could be carried out only when its particular preconditions were satisfied. The planning system kept track of the physical environment and determined which actions were allowed. Carrying out one of them in turn modified the state of the environment, which therefore made other actions possible.
The designers of F.E.A.R. gave its soldiers such goals as patrolling, killing the player’s character, and taking cover to protect their own virtual lives. The makers of the game also gave each kind of bot a set of possible actions with which to accomplish each of its goals. One advantage of this approach is that it saves the developers the burden of trying to specify a response to every situation that might arise. Further, it allows seemingly intelligent behaviors to appear almost magically—such as the maneuver described above.
In that instance, the three attackers were carrying out two types of basic actions. One is to move to covered positions that are as close as possible to the player’s character. The other is simply to move around obstacles. The combination creates something that was not explicitly programmed into the game at all: a devastating flanking maneuver.
The spontaneous emergence of such complex behaviors is important because it provides a sense of deeper intelligence. That’s really what gets your heart pounding when you play the game. But you’d also like your adversaries to become more cunning over time, and F.E.A.R. has no mechanism for accomplishing that.
Why do bots need to get smarter? Imagine a game of badminton in which your opponent always reacts to your serves in the same way, always falls for your drops, and never attempts to anticipate your smashes. It would be a boring match. Up until recently, AI had been able to offer video gamers no better: the imps of Doom, released in 1993, never shoot their fireballs preemptively, and the civil-protection officers in Half-Life 2 (2004) always take the nearest cover while reloading their weapons—to mention just a couple of things players experience with two well-known releases.
The standard solution is to add an element of randomness to the code that controls a bot’s decision making. Doing so varies a player’s experience, but the result does not necessarily come across as being intelligent.
A better approach is for the computer to learn about the player and to adapt a bot’s tactics and strategy appropriately. Of course, you don’t want the bot to become so good that it will win all the time; you just want it to give the human player a good run for the money. This capability, known as machine learning, is found in very few commercial games: Creatures, from the now-defunct Creature Labs, employed machine learning as early as 1997, as did Black & White, developed by the UK-based Lionhead Studios a few years later. But most video games are not able to ”learn” on the fly or otherwise adapt to the person playing. Our group is hoping to push things forward in this regard using a system we’ve created for research purposes called PaSSAGE, which stands for Player-Specific Stories via Automatically Generated Events.
PaSSAGE, as its name implies, is all about storytelling, which has long been a staple of various role-playing games. But video games of all types rely to some extent on engaging storytelling. You can categorize such games by the way they vary their repertoire to appeal to different people.
Some games— Half-Life (2001), for example—are immensely popular even though they feature just a single linear story. So good scriptwriting can clearly go a long way. Other games, such as Star Wars: Knights of the Old Republic (2003), offer several alternatives to the main plot. This gives you the impression that you can shape your virtual fate—what psychologists call a sense of agency. That feeling of being in control is usually limited, however, because the branching plot lines often merge later on.
Titles like The Elder Scrolls IV: Oblivion (2006) and S.T.A.L.K.E.R.: Shadow of Chernobyl (2007) work similarly, taking one main story and complementing it with episodes drawn from a library of side quests. Other games, such as The Sims 2 (2005), go a step further by dispensing with a scripted plot altogether and creating an open-ended world in which players can effectively design their own happenings.
Although each of these techniques has enjoyed success, they all force the designer to make a trade-off between scriptwriter expressiveness and player agency. The approach we’ve taken with PaSSAGE avoids that conundrum by having the computer learn players’ interests and preferences and mold the story to suit them as the game progresses.