ARTIFICIAL INTELLIGENCE
They fight. They flock. They have free will. Get ready for game bots with a mind of their own.
It is the year 2002. After an explosion of R&D funded by software giants and startups, more than a third of US households are populated by sophisticated artificial intelligence bots - their decisionmaking guided by complex neural nets and simulated emotions, their perceptual systems honed to detect subtle changes in their environment. Every day millions of Americans interact with these creatures, encountering advanced technology from nuanced natural language routines to gesture recognition to machine learning. Perhaps most impressive: As the AIs have grown smarter, they have begun to communicate among themselves, sharing new ideas and collaborating on group tasks.
This is not some hopelessly optimistic sci-fi scenario from 20 years ago. It is reality. Consumer-grade artificial intelligence is alive and well in the world of games.
If you've played a videogame released in the past year, you probably know the feeling: the eerie, ghost-in-the-machine sense of interacting with a semi-intelligent creature existing somewhere on the other side of the screen. It's what happens when a lone sentry in Metal Gear Solid 2 tracks your bloody footprints straight to your hiding place, calls in reinforcements, and then launches a sophisticated group assault on your position. It's when your fellow marines seamlessly coordinate a flanking maneuver around an alien squad, while navigating the rocky, uneven terrain of Halo. Or when a small riot suddenly breaks out in Grand Theft Auto III after your carjacked SUV crashes into a pedestrian. It's a world of spontaneous, adaptive, sometimes even smarter-than-you behavior, a million light-years from the one-dimensional assault of Space Invaders.
You can measure the flowering of game AI in a number of ways. Start with CPU cycles: All game development is a struggle over this most precious of resources. Historically, games made graphics a priority over everything else, often leaving AI routines for the spare cycles. But most complex games today devote extensive processor time to AI code: One recent poll of developers showed a sevenfold increase in CPU time used for AI in the average game since 1997. Hardware advances are accelerating this trend. Today's game machines and game-ready computers have two processors, nearly equal in power: The 3-D chip handles the graphics, and the CPU is increasingly devoted to artificial intelligence. It's no surprise that there are at least six AI PhDs now working in the game industry, and that MIT's Marvin Minsky, the elder statesman of modern artificial intelligence, lectures at game developer conferences. Almost all games now include an AI designer credit, and some AI wizards - like Black & White's Richard Evans - have become minor celebrities among hardcore gamers.
The newfound stature of game AI is readily visible to ordinary players. The Sims features a button on its preferences screen that lets you toggle "free will" on and off. Turn it off, and the characters become hapless puppets, relying on your instructions at every turn. Turn it on, and the Sims take on a life of their own: dancing, swimming, shooting pool, showering - all dictated by their ever-changing moods.
It's tempting to trot out that old standby of AI research and ask whether today's games have passed some kind of Nintendo-era version of the Turing test, but in a way, the question is too easy. (The computer-controlled bots in a first-person shooter like Unreal Tournament can easily pass for human opponents.) What's more striking about the latest generation is the appearance of unscripted, emergent behavior - the AI stumbling on new ways of responding to the world, strategies and behaviors that weren't deliberately planned by the designers. You can see this most clearly in Peter Molyneux's landmark Black & White. A kind of artificial pet, your creature in B&W can take the form of about a dozen mythological animals and can be trained to interact with the objects and inhabitants of the game world through a simple feedback system. Tear up some forests or shower rain on a local village, and your pet will start to mimic your actions. If you like his mimicry, you reward him by petting him gently; if he's bad - setting fire to villages instead of watering them, say - you can give him a quick slap across the face. Over time, the creature learns, based on your tutelage.
Fans of the game have created sites to share anecdotes about the bizarre or uncanny deeds they've coaxed out of their creatures. Consider this post from The Creature Stories Archive:
"My creature is still pretty young - age 8, and I'm only in level 2 up to now. Anyways, while I was in level 1 I got the healing spell. So I thought, it would be pretty neat to teach my little ape this spell. Since Adiz wants to be always kind and generous to the people, he ran to the village to try his new spell. He looked around and I guess there was no one to heal. He got pretty upset about that. So he just picked up a guy and threw him as hard as he could against a mountain. The man rolled down, and - for some reason - survived. He was hurt pretty bad though, screamed like hell, and was trying to get back to his house as quick as possible. My ape of course saw that, and healed him. After that he looked at me all happy and smiling."
There are hundreds of these stories, lined up one after another, recounting behavior that may well be unique to each creature. Blur your eyes as you scan them, and you might think you were looking at a parenting site, rife with excited accounts of junior's latest breakthrough.
Five years ago, when games like Myst began to be taken seriously as cultural forms - not unlike the period in the mid-'60s when the highbrow music critics started reviewing rock albums - one persistent gripe revolved around their lack of psychological depth. (Think of the horrific faux-British accents of Myst's "actors" or the character-less drones of Doom.) Those early critics had a point, but they were using the wrong criteria: That generation of games was interesting largely for architectural reasons - they had environments to explore, not relationships to develop. The art of playing them was the art of movement, not psychology. Much has changed in the half decade since: While the worlds conjured up by today's games are even more vividly realized than before, the biggest shift has been psychological. Consider the mental toolbox of a computer-controlled character (also called an NPC, for "non-player character") in Microsoft's flagship Xbox game, Halo. NPCs in Halo have real-time perceptions about the world around them (aural, visual, and tactile); knowledge about the "state of the world" as they've perceived it (memories of enemy sightings, weapon locations); an emotion system that changes based on events (growing more fearful during enemy onslaughts); and a decisionmaking system that consults the other three systems to decide whether to attack, run for cover, or initiate another behavior.
The specialized modules of Halo's artificial brains mirror what we now understand about the human mind's architecture. Instead of a single general intelligence, the brain is more like a Swiss army knife of task-specific tools - face recognizers, syntax decoders, memory subsystems - that collectively create our varied and adaptable intelligence. As game AI has moved from crude if-then decision trees to the parallel, distributed intelligence of today's computer-controlled characters, it has become a kind of testing ground for the modular theory of the mind. At a recent game developer conference, MIT's Bruce Blumberg demonstrated an even more advanced simulation of a modular mind: a virtual dog called Duncan, whose mental routines included an advanced memory and object recognition system that enabled it to make commonsense predictions about the world around it.
The artificial minds of today's games have also become better at collaborating with one another. One recent trend in game design - facilitated by state-of-the-art collaborative AI - is flocklike behavior, where dozens of NPCs will follow the player around an environment, dutifully helping out with tasks where appropriate. This can be visually stunning, much like the elaborate group choreography of an ant colony. In the flagship GameCube title Pikmin, designed by Mario creator Shigeru Miyamoto, your onscreen character leads a herd of all-too-cute creatures (called Pikmin) across a trippy garden-floor landscape. The effect is immediately startling: The Pikmin trail behind you like a band of arthropod groupies. But that kind of behavior can be fiendishly difficult to model. After all, getting single characters to traverse a landscape in a convincing fashion - without getting trapped in a corner or moving through walls - is a taxing enough problem. (It's no accident that the first generation of game AI was largely devoted to pathfinding routines.) Trying to usher a band of 30 characters through a doorway without creating an artificial-looking assembly line is significantly harder.
In Munch's Oddysee, the latest installment in the Oddworld series, up to several dozen NPCs can accompany the primary character. Oddworld lead designer Lorne Lanning considers the success of those group interactions to be one of the most essential AI achievements of the title. "These seem like really mundane tasks," he says, "but it's more like navigating a big class of preschool kids." Those navigations are coordinated by the game's new Alive 2 engine, short for Aware Lifeforms In Virtual Entertainment. During a complicated attack sequence, the Oddworld bots have an uncanny knack for protecting the main player, while negotiating dozens of simultaneous challenges presented by the environment: "They're running all these different series of checks, while still maintaining the sense of life," Lanning explains. "They're thinking: 'Wait a minute, I can't go into the water; also, there's an invisible barrier over here that I'm not supposed to get past because it will get my collision code into trouble; and I've got to keep track of the distance I'm trying to keep from all the other characters. And at the same time, I'm trying to avoid enemies and protect the main character.'"
The computer-controlled marines that accompany you as you explore Halo have a complex and fluid communication system that enables them to adopt dynamic military strategies on the fly. Playing, you'll sometimes find yourself ushering the marines into a particular formation; on other occasions, you'll find yourself following their lead. That parity exists behind the scenes, too. "One of the things that makes Halo's AI interesting is the sense that the AI doesn't cheat. It doesn't regard you, the player, as anything special, nor does it know special things about where you are," explains Halo AI engineer Chris Butcher. "The NPCs all have their own unique knowledge model, which means that any given character in the world doesn't know where the player is. All they know is where they last saw him."
The limitations of the NPC perspective are a measure of how advanced today's AI truly is. In the old days, you had to make your virtual characters omniscient to make them believable; today's bots can learn about the world on their own, usually employing a neural net system that strengthens or weakens associations between objects or other players based on their experience in the game. The creatures in Black & White, for instance, use the binary feedback from the player to develop an ever-more refined behavioral model. If you punish your creature after he devours a villager, you may find him refraining from eating altogether for a while, because he will have established a connection between your negative feedback and the act of eating. But if you reward him after he dines on some harvested grain, he'll start to recognize that eating the villager is what got him into trouble the last time, not the act of eating itself. With a slap or a cuddle from the player, the creature's relationship to the world grows more nuanced, and more distinctly his own.
Virtual organisms aren't the only ones doing the thinking. Today's game AI also revolves around objects that think - sometimes called smart environments. Ironically, the virtual people in the most influential AI implementation to date - The Sims - aren't very smart at all. Their intelligence derives as much from the world around them as from their own innate cleverness. Items in the game (refrigerators, pool tables, chairs) effectively contain their own "instructions for use." The Sims themselves are like little wondering processors executing programs embedded in the objects around them. The question that Will Wright and his team grappled with early in the design process was how to create a convincing system for satisfying desires. In a house full of potential activities, how does a Sim decide to do one thing over another? Wright calls the solution they came up with a "happiness landscape," borrowing from evolutionary theory's concept of a "fitness landscape," in which organisms climb ever-higher peaks of adaptive fitness as natural selection runs its course.
"Rather than traversing a genetic landscape of fitness," Wright explains, "you're traversing a spatial landscape of happiness. We had a little cheat that you could turn on: You could graph the happiness values, and when a character assumes a given spot, it starts climbing gradients of happiness. So if I'm hungry, the happiness landscape changes, and things that are providing food will have a higher peak in that landscape. And if I happen to be on the slope of a fridge, I'll start climbing that slope until I get to the fridge. After I eat, all of a sudden the peak will collapse." The graph dramatizes how the Sims' movements are guided by the intersection of their desires and the objects that cross their paths. The slope of the bed extends all the way across the house, while the pinball machine extends only a few feet. A fatigued character will start climbing the slope toward the bed no matter where she is; if she needs some entertainment, she'll migrate to the pinball machine but only if it's nearby.
"The biggest problem we had was formally describing happiness for it to work," Wright says. "I literally went around my house looking at all the crap and tried to figure it out: What was the justification I had for buying this thing? What did I think it was going to help me do? So we had to come up with the smallest number of needs that we could use to justify the largest number of objects."
The happiness landscape may be the ultimate example of why game AI is such a fascinating space right now. In what other creative field do you find an artist borrowing from consumer psychology, evolutionary theory, and software pathfinding models - not to mention home decorating - all to create a title that sells millions of copies and is almost demonically fun to play?
The intellectual energy associated with game AI has tightened the connection between the academic AI community and the game developers. That connection will grow stronger in the coming years, according to John Laird, who's served as a liaison between the two worlds. In early 2000, Laird, a professor of computer science at the University of Michigan, coauthored a manifesto of sorts for the research AI community, arguing that games provide a perfect environment for experiments in human-level AI - and offer a better career path than creating smart software for more traditional clients like the Department of Defense. "What we're now seeing is a generation of grad students who grew up playing videogames," Laird says. "In the next five years or so, we're going to see a lot more people going to grad school wanting to focus on AI and games, and then going into the industry. It's sort of a mantra of technology transfer in the computer sciences: You don't transfer ideas, you transfer people."
As optimistic as Laird is about all the possibilities, he has clear ideas about where the field needs to go next. "I would like to see independent, autonomous characters that you have genuine social interactions with," Laird says. "So when you're thinking about moving through the game, it's not solving jumping puzzles or figuring out how to shoot someone - it's figuring out, how can I get this person to work with me in order to solve my problems? Or, what can I do for them so that they then want to help me?" Laird and his colleagues have launched a research project at Michigan to explore the possibilities of this social interaction: an Unreal Tournament mod called Haunt 2, in which the player controls a ghost in a house inhabited by NPC "humans." Unable to handle most physical objects directly, the ghost must, in Laird's words, "entice, cajole, threaten, or frighten the AI characters into manipulating the objects in the world."
To be sure, the subtleties of Laird's social interactions are not yet commonplace in today's game AI, which still largely revolves around creating better military bots and training them to hunt down enemies in more believable ways. In a sense, there's something strangely appropriate in that shortcoming: Early artificial intelligences are devoting themselves to the very same problems - hunting, pathfinding, foraging, traversing simple happiness landscapes to satisfy their desires - that wrestled with our ancestors at the dawn of man. Given the progress we've made since those robotic Space Invaders first appeared on our screens, can anyone doubt that more nuanced artificial minds, with a more sophisticated emotional repertoire, lie ahead?
Or maybe it's here already. Every now and then - after a successful harvest or the building of a new temple - the villagers in Black & White will spontaneously break out into an elaborate group dance, their bodies linked together in ever-changing patterns. If you've trained him properly and he happens to be nearby, your creature may join in the festivities, gyrating along with the Dionysian throng of villagers. Watching those sprites dance on the screen, you can't help but think that these simulated minds are displaying emotions - joy, solidarity, love for life - that are unfathomable in a videogame: That the life in question is artificial might actually be beside the point.
