Bill DeSmedt and Don Loritz
The Amber Consortium, Inc.
13306 Point Pleasant Drive
Fairfax, Virginia 22033
What will it take to get non-player characters talking in computer games? Its not just parsing any more! Heres a preview of the next wave of authorable, knowledge-based conversational agents, and what itll take to get there.
At the Amber Consortium we see conversation as the next wave in the confluence of AI and game development.
This is not to say that AI will cease contributing advances in the tools for fabricating ever more lifelike bodies, behaviors, and movements. But games themselves (and gamers, too) are evolving beyond their early fixation with non-stop action and eye-catching 3D graphics, in the direction of greater depth and involvement. And as game developers grapple with the challenge "to give people the widest possible means of exploring that you can get" (as Roberta Williams puts it ), they are increasingly turning to modes of interaction beyond the (virtually) physical to "a dimension, not of sight or sound, but of mind..."
Thats because endowing non-player characters (NPCs) with more, well, character in the sense of possessing and expressing memories, beliefs, and opinions turns out to be one of the most cost-effective ways to meet players demands for a more immersive experience. Scott Watson of Walt Disney Imagineering reports [Watson, 1996] that one of the star attractions (unexpectedly so) of the Aladdins Magic Carpet ride was a conversation between two NPC rug merchants haggling in the street. Surrounded by millions of polygons worth of expensive, labor-intensive eye-candy far as the eye could see, patrons still stopped to listen to this (canned) dialogue.
Imagine what it would be like if the users were able to take part in the conversation as well. Their involvement in the characters "inner space" would not only make possible a new kind of gaming experience, it might even reach the point where game developers could ease up on the 3D animation at least for the duration of the dialogue!
Its Mostly About About
What does it take to generate that degree of user involvement? What, in other words, does it take to build a conversational agent: software that can carry on a coherent, consistent conversation with human users?
For starters, an ability to manipulate natural language, of course: large-vocabulary full-sentence parsing, metasentential discourse analysis, extemporaneous response generation the whole nine yards of Computational Linguistics. Weve described the baseline requirements elsewhere in some detail [DeSmedt 1997]. Here, wed like to take a different tack, and look at the issues that arise once the formal aspects of language processing are well in hand. Because no matter what level of abstract linguistic competence a conversational agent achieves, it still cant aspire to (a reasonable facsimile of) conversation unless its prepared to converse about something.
On the analysis side, parsers grind to a halt in the face of ambiguous input like "time flies like an arrow." What we are talking about here the second law of thermodynamics, perhaps? or a fly species (Drosophila chronologicus?) with a fondness for archery equipment? or maybe were just responding to the question: "Whats the best way to time flies?" makes a big difference to the parse tree. And even bolting on a topicality-tracking discourse manager doesnt help much with input like "the puppy pressed its nose against the window so hard it broke it". Determining what all those its refer to requires knowing something about the world: namely, that puppies have noses and windows dont, and that those noses are less fragile than glass is. In short, the ambiguities inherent in human languages are such that the problem of formally interpreting an arbitrary input string is fundamentally insoluble without some reference to what that string is about.
By the same token, some sense of the meaning behind the words of the world those words describe is equally essential on the output side. If an agent hasnt a clue what its talking about, even perfectly grammatical language generation and perfectly articulated speech synthesis wont disguise the fact. Real discourse presupposes at least a minimum level of coherence and consistency. If an NPC fails to meet this expectation, it wont be able to hold a conversation, much less an audience. Once its initial fascination wears off, random chatter ceases to be interesting in order to involve us, conversation has to be about something.
How we go about imparting that "about-ness" to an agents conversational capabilities with special reference to the opportunities and challenges afforded by game development is what the rest of this paper will be "about".
Knowledge Representation: How Much is Enough?
At this juncture, however, the pursuit of linguistic competence for our conversational system leads us out of the domain of computational linguistics altogether, and into that of knowledge representation (KR).
KR focuses on how reality as a whole might best be reflected in an internal "mental model," and what operations on that model are needed in order to draw valid conclusions from known facts. As this implies, knowledge representation is industrial-strength technology, with concerns and applicabilities far beyond those of constructing NPCs.
Perhaps the best-known KR project in the world is Cyc [Lenat & Guha 1990]. Begun some fifteen years ago, Cyc (short for Encyclopedia) is only just beginning to approach, if that, the point of commercial viability. In the meantime, the RAM footprint of an executable has burgeoned to between 150 and 250 megabytes [Whitten 1997], the fundamental representational schema has thrashed back and forth between competing paradigms a couple of times and, after its first decades worth of knowledge input, Cyc still hadnt learned that the sky is blue [Pratt 1994].
Thats no reflection on Doug Lenat and the rest of the crew at Cycorp. Endowing a computer with common sense is one of AIs well-known "hard problems," and their multi-generational commitment to solving it is an inspiration to the rest of us toilers in the vineyard.
At the same time, even if Cycorps efforts were to be crowned with success before the millennium is out (and Doug himself seems to be thinking in terms of another quarter century), dont look for a "CycBot" to appear on a game console near you anytime soon.
Its not just those RAM and machine-cycle requirements, either. Rather, the real problem is that a KR that "only" represents the real world may well prove inadequate when it comes to a counterfactual games universe. For instance, one would hardly expect a traditional KR to support such pseudo-scientific principles as the Law of Contagion or the Law of Similarity, yet these are essential to constructing a reality where magic works. It gets worse: if the KR models relativistic physics too rigorously, you can kiss faster-than-light travel goodbye but no FTL means no Star Wars, no Star Trek, no Star anything!
So, mainstream Knowledge Representation offers game developers both too much and too little. On the one hand, it eats too much of the bandwidth budget. On the other, it narrows the scope of what can be represented and reasoned about to a single, humdrum real world the very world so many gamers are trying to escape.
As opposed to this kind of Knowledge with a capital "K," what our conversational agent really needs is just enough in the way of memories, beliefs, expertises, and reasoning ability to hold its own in normal conversation about topics relevant to its role in a game. One way to think about whats required is to draw a distinction between the amount of medical knowledge it takes to function as a physician and how much it takes to portray a doctor in a hospital soap opera. So what if Richard Chamberlain didnt know the difference between an esophagus and a duodenum? Dr. Kildare wasnt going be slicing anybody open to find out and neither will our conversational characters.
Even these somewhat scaled-down expectations involve more in the way of implementation issues than we can hope to address in the allotted space-time, but here is a sort of "One-Minute Epistemologist" version:
* Our knowledge model (which, for convenience, we will refer to here as a "mindset") begins with an ontology [Noy & Hafner 1997] that is, a catalogue of all the things in the world that we want our agent to be able to converse about (its "universe of discourse").
* Next we specify how the things (more properly, the "concepts") in the ontology are related to one another. We do so by embedding them in a so-called "IS-A" hierarchy, not unlike the class hierarchies used in object-oriented programming. IS-A linkages will capture the fact, for instance, that an elephant is-a mammal, that a mammal is-a vertebrate, that a vertebrate is-a[n] animal, etc.
* The rationale for the IS-A hierarchy in KR is the same as for the class hierarchy in C++: inheritance of properties and functionalities. If we install the proposition "mammals breathe oxygen" into our embryonic mindset, then elephants, being mammals, will automatically inherit this attribute, freeing us from the necessity of further asserting that "elephants breathe oxygen," not to mention dogs, cats, and so on.
* The kind of knowledge we are capturing and encoding with such efficiency here is called, following Carnap , intensional knowledge propositions that are true of a class (and its subclasses) in general. And the kind of reasoning it affords is an extension of set theory called First Order Predicate Calculus (FOPC). Much of the inferencing (the drawing of conclusions from a body of known fact) which our agent will be called upon to perform in imitation of human reasoning boil down to theorem-proving operations in this propositional calculus.
* The underlying inheritance scheme gets into trouble, though (and FOPC along with it) when we try to extend it from classes of things to the individuals belonging to those classes. If an agents mindset posits both that "elephants have four legs" and that "Clyde is an elephant," then if asked "How many legs does Clyde have?" the agent should answer "four." Oops! We forgot to mention that poor Clyde, victim of a freak gardening accident, only has three legs.
* Such extensional knowledge as the propositions specifying the properties and behaviors of individuals (as opposed to classes) are collectively known represents a speed bump in the otherwise smooth top-down propagation path of inheritance logic. Particular assertions made at this level can, as Clyde amply demonstrates, override universal intensional truths handed down from on high. And, unlike C++, FOPC does not look kindly on "method overriding."
The fact that extensional knowledge does not play nicely with others has led more than a few KR researchers to exclude it from their representations entirely. This is, to say the least, unfortunate, since it is at the level of individual entities and incidents that all the really interesting things there are to talk about must be encoded. Lamentable as it may be to the logicians among us, conversations made up entirely of statements like "a mallard is a kind of duck" or "bread is made of flour" get old pretty quick compared with discourse about what Harry and Sally did last night.
An ability to subvert the monotonous validity of first-order truth-testing KRs becomes even more crucial when it comes to game design. Lacking an extensional override, our conversational agent would be bereft of one key element of characterization: it would be incapable of lying. Characters in games seldom if ever tell the whole truth and nothing but the truth: even the simplest murder mystery presupposes that at least some of the suspects arent telling us everything they know.
Yet even those knowledge representation systems that give extensional knowledge its due still fall short of what we need in a conversational agent. The point about knowledge of specifics is that its, well, specific every conversational character in an interactive fiction, while sharing a baseline knowledge of generalities with the rest of the dramatis personae, is going to need its own individual mindset as well. Lacking at least some personalized facts, memories, beliefs, etc. its hard to see how an agent could portray a personality.
The problem of crafting all those individual mindsets, however, brings us up against the authorability issue: In a word, how easy is it going to be to make lots of these individualized conversational characters, on a schedule, on a budget? For what game developers need are not just mindsets, but mindsets that can be tailored to order as part and parcel of the content-creation process.
Mindset Authoring: They Told Me I Was Gullible And I Believed Them!
The builders of large knowledge bases seem at times almost to take pride in how difficult these beasties are to author and edit. Programming PARKA was said to require "teams of programmers" [Spector et al 1992], while Cycs creators are adamant that no "naive editors" need apply for the challenging job of engineering its ontology [Lenat & Guha 1990]. In all this chest-thumping, one senses an unvoiced concern for the fragility of such all-encompassing knowledge bases: one false move (or one false proposition) and the whole edifice could crash to the ground in a heap. Its a valid concern, especially in light of the uses being contemplated for the ultimate end product automating the life-and-death decisions of air traffic controllers, or brain surgeons, or Polaris submarine commanders.
In the world of games, we can be sure that any mayhem resulting from a corrupted knowledge base will remain strictly virtual. Consequently, it becomes possible to dispense with the "zero-defect" mentality, relax a little, and open up mindset authoring to more than the chosen few. From his work on Toy Story, Tom Porter drew the lesson that, ideally, the technician should get out from in between the director and the content creator [Porter 1996]. Were suggesting that the way to do that is to apply to our conversational agent the liberating insight of another of Pixars luminaries in Woodys words: "Youre just a toy!"
It may seem as if were prematurely mulling over the implications of a technology we have yet to describe. Thats because weve really been describing it all along. Whats it going to be like to author a conversational character? You guessed it its going to be like a conversation! (After all, why should the users have all the fun?)
... A special sort of conversation, though. An appropriate metaphor might be the sort of sessions where an undercover operative is given and then grilled on his or her "legend," or an improvisational actor is coached in his or her "backstory." Another way to think about the authoring exercise is to liken it to a conversation with an extremely gullible person. From that perspective, authoring an agent means putting its knowledge base into "pillow mode," where it takes the shape of the last head its come in contact with. Then, one just talks to it.
To an external observer, the ensuing coaching dialogue might at times wax bizarre:
AUTHOR: Youre an only child...
AGENT: Oh, uh-huh, okay...
AUTHOR: ...and an axe murderer.
AGENT: What the hey, why not?
... but it will get the job done. Once the agent has absorbed enough of such backgrounding, the author resets its "gullibility index" back into the normal range, and quizzes it to see if the newly imparted content has had the desired conversational results.
Implicit in all this is the commercial availability of plugn play mindsets: component knowledge bases representing all the memories and beliefs that go with having been an only child (or an axe murderer). Arduous as it may be to author these building blocks, the job only has to be done once. We envision a thriving industry of virtual "talent agencies" offering stock-model backstories which furnish the bare bones of a characterization, leaving the author free to add the nuances that will transform a stereotype into a living personality performing in a particular game-space.
The Talkies Are Coming!
Clearly, this is not going to happen all at once. Full-motion video stars will not become an endangered species overnight. Conversational agents will begin as bit-players, enlivening street scenes, doing the grunt work on battlefields, vending hotdogs at sporting events, and chattering tipsily at cocktail parties. Even in such walk-on roles, though, they will have the effect of extending the dramatic reach of computer games. And, if populating a virtual environment with virtual conversationalists does come to require no more effort than overlaying a few quick brushstrokes of characterization on off-the-shelf characters, then maybe the economics of production will drop to where it can hope to keep pace with the game industrys insatiable appetite for content, and the gamers lust for unbounded experience.
Looking a little further out, though, we foresee a day when some shy, unassuming conversational-agent understudy in a big Broadband show suddenly whips off its virtual hornrims, unpins its simulated hairdo, and a star is born!
In short, we think the game industry is in for a paradigm shift on the same tectonic order as the one that hit Hollywood in the late twenties. Then as now, storytelling was hampered by the absence of one whole channel of interactivity. Now as then, the advent of the "talkies" will not just enhance our existing stories, they will alter the nature of the stories we can tell.
Carnap, Rudolf. 1947. Meaning and Necessity: A Study in Semantics and Modal Logic. U. Chicago.
DeSmedt, William. 1997. The Talkies Are Coming. In Proceedings of the Computer Game Developers Conference. San Clara, CA, April 25-29.
Evett, M., J. Hendler, and L. Spector. 1990. PARKA: Parallel Knowledge Representation on the Connection Machine, UMIACS TR 90-22. University of Maryland.
Lenat, D. B. and R. V. Guha. 1990. Building Large Knowledge-Based Systems. Addison Wesley.
Noy, Natalya Fridman and Carole D. Hafner. 1997. The State of the Art in Ontology Design: A Survey and Comparative Review. AI Magazine, vol. 18, no. 3:53-74.
Porter, Tom. 1996. Creating Lifelike Characters in Toy Story. In Working Notes of the Lifelike Computer Characters 96 Conference. Snowbird UT, October 8-11.
Pratt, Vaughan. 1994. CYC REPORT (April 16/19, 1994). http://retriever.cs.umbc.edu/~narayan/proj/cyc-critic.html
Spector, L. B. Andersen , J. Hendler, B. Kettler, E, Schwartzman, C. Woods, and M. Evett. 1992. Knowledge Representation in PARKA Part II, UMIACS TR 92-16. University of Maryland.
Watson, Scott. 1996. Realtime Characters in Aladdins VR Adventure. In Working Notes of the Lifelike Computer Characters 96 Conference. Snowbird UT, October 8-11.
Williams, Roberta. 1997. Sierras Queen Is Still on Top of Her Game. Newsweek, 31 March:80-81.
Whitten, David J. 1997. The Unofficial, Unauthorized CYC Frequently Asked Questions Information Sheet. http://www.mcs.net/~jorn/html/ai/cycfaq.html.