Game Intelligence Design

 [Up] [Map] [Prior] [Robot Wisdom home page]

 IF, AI, and the confabulating-arranger model of interactive fiction

 by Jorn Barger (jorn@mcs.com)

 September 26, 1994

      Abstract: One plausible design-paradigm for interactive fiction
      might be to supply IF authors with an extensive library of
      intelligent objects that 'know' how to interact realistically,
      including a rich model of human behavior. Doug Lenat's Cyc
      project is already attacking this task from a traditional AI
      perspective, but for IF this knowledge may be more simply
      collected in the form of stories-- in fact, a new mailinglist on
      the Internet is devoted to compiling such a story-library. If
      this library also tags all the most interesting possible
      plot-lines, the computer's task might be extended to
      "confabulating" the player's reality, on the fly, simultaneously
      arranging both past and future so as to open as many interesting
      plot-directions as possible.

 A couple of issues ago (IED 7.4), Chris Crawford discussed the basic known
 'topologies' for interactive fiction (IF)-- each of which he showed to
 contain intractable fatal flaws. Basically, interactivity implies that the
 user is making choices, which implies that the story is branching into a
 tree-like topology. But Chris showed that storytrees must either be folded
 back on themselves in a very limiting way, or have most of their branches
 trimmed to (violent) dead-ends. If they don't, they'll necessarily expand
 exponentially... so consequently, within these design paradigms, even
 high-budget efforts are doomed to produce only simplistic and uninvolving
 games....

 The fantasy for the distant future, of course, is that the computer should
 offer an infinitely-various Virtual Reality, full of objects and characters
 whose behavior mimics 'real life' in great detail. In the ideal future, one
 should be able to step into the pages of a Dickens or Tolstoy novel and
 interact with its characters as freely as in 'real' life....

 But how do we get there from here What sorts of design strategies might
 make these new forms of IF possible?

 Certainly, one step in the right direction will be to teach computers the
 basic laws by which real objects interact, which is one of the traditional
 challenges of artificial intelligence (AI). In this article, I'll first
 explore the AI-world's leading contender for a truly intelligent program--
 the Cyc project. Then I'll look at how Cyc's models overlap with those of
 traditional text-adventure games. I'll discuss a potentially-simpler
 strategy for compiling a 'Cyc' for IF, using a text format called a
 "meta-story", and offer some examples of how these can capture knowledge in
 an intuitive way. And finally I'll explore a new paradigm for IF-- the
 confabulating-arranger model.

 The Cyc project as a universal knowledgebase

 The last thirty years of academic AI research have produced very little
 that computer-game designers would find useful. The problems they've chosen
 to research have been too limited, and the programming structures they seem
 to favor are impossibly slow for realtime gameplay. So the world of gaming
 has pretty much had to invent its own styles of AI, as it's needed them.

 But for the last ten years, a highly ambitious (and surprisingly
 low-profile!) effort has been underway in Austin, Texas, to spell out the
 entire range of human commonsense knowledge. The goal of this Cyc (for
 enCYClopedia) project is a program that can read a newspaper, and
 'understand' what it has read, well enough to detect violations of common
 sense, just as human readers can. But to the extent that it succeeds at
 this, it should be equally useful, at least in theory, for maintaining
 internal consistency in a virtual world....

 The Cyc team, led by Doug Lenat, has been trying to break down human
 understanding into thousands of subdomains that they call "micro-theories",
 like ailments, food-preparation, communication, and corporate behavior, and
 then trying to translate the basic 'rules' of each such domain into the
 language of symbolic logic. When they need to say, "If someone is
 asphyxiating, they cannot breathe," for example, they write:

 (LogImplication
   (LogAnd
      (allInstancesOf $AIL Asphyxiation)
      (bodilyInvolved $AIL $AGT))
   (holdsIn $AIL
     (LogNot (behaviorCapable $AGT Breathing bodilyInvolved))))

 where $AIL and $AGT are the variables for ailment and agent,
       LogAnd, LogNot, and LogImplication are simple logical connectives
 and "holdsIn" defines the context within which this 'axiom' holds.

 According to the Cyc model, if an adventure game needed to know
 what-happens-next at any particular point-- say, when a person drops a
 delicate vase-- it would send a query to Cyc and in a matter of seconds,
 Cyc should return with the news that vases dropped on hard surfaces usually
 shatter...

 Unfortunately, if you multiply that plausible retrieval-time times the
 thousands or hundreds of thousands of deductions that would be needed to
 keep an interactive fiction realistic from moment to moment, you're forced
 to the conclusion that Cyc just isn't going to be fast enough to support
 IF, anytime soon.

 Probably the worst problem here is that Cyc-- unlike any other largescale
 project in history-- didn't evolve by starting with a simpler version of
 the whole, and gradually filling in the less-important details. Rather, Cyc
 is being built by the much riskier strategy of accumulating detailed
 subsections, one by one, with no known overall pattern... and later
 streamlining it down to a "core knowledge base". To make that streamlined
 enough for IF may turn out to be the hardest challenge of all!

 So Cyc offers a good startingpoint for IF-theory, with regard to the
 knowledge it hopes to embody, but perhaps not so good a model with regard
 to the performance constraints of realtime IF. But we know for certain that
 some level of realtime IF is possible-- Zork and Hitchhiker's Guide (etc)
 have proven that! But is there a way to build an "IF engine" that includes
 something more like Cyc?

 Text-adventure development languages

 The enduring popularity of text adventures, especially the Infocom games of
 the early 1980s, has led a number of talented enthusiasts to create
 programming languages especially for text-adventure development. Many of
 these are available free on the Internet, where the newsgroup
 rec.arts.int-fiction supports a thriving subculture of text-adventure
 designers working in these formats. (The newsgroup has its archives at
 ftp.gmd.de in /if-archive/.)

 TADS (The Text-Adventure Development System) by Michael J. Roberts is
 probably the most popular environment, because games created in TADS can be
 run on almost every major hardware platform. TADS offers a modest range of
 predefined object-types that have at least a minimal level of intelligence
 about their own behavior. Containers and vehicles, for example, understand
 that objects placed within them will move with them, and will be invisible
 unless the container or vehicle is transparent. Characters automatically
 grow hungry if they don't eat, and even eventually die.

 TADS is object-oriented, with the objects themselves containing most of the
 code embodying such "story elements":

 class openable: container
     contentsReachable = { return( self.isopen ); }
     contentsVisible = { return( self.isopen ); }
     isopenable = true
     ldesc =
      { caps(); self.thedesc;
        if ( self.isopen )
        { " is open. ";
          pass ldesc;}
        else " is closed. "; }
 [etc]

 The TADS object-hierarchy is firmly grounded in story-telling pragmatics:

 Thing
   Item: vehicle, surface, lightsource, key, food, container, clothing
   FixedItem: switch, dial, button, decoration, actor, chair
   Room

 Cyc, by contrast, offers at the highest level the following, rather less
 pragmatic, partial object hierarchy:

 Thing
   Intangible
   IndividualObject
     Event
     Stuff
       Process
         SomethingExisting
           TangibleObject

 The Wisdom-FAQ mailinglist

 If a knowledgebase like TADS's could be gradually extended, ultimately even
 to the full extent targeted by Cyc, this would surely be a major step
 towards better IF. So with this in mind, a group of us from
 rec.arts.int-fiction (and elsewhere) have spun off a new mailinglist to
 investigate the possibility of building a sort of public-domain 'Cyc' for
 IF.

 The name for the mailinglist-- Wisdom FAQ-- is derived from the Internet
 tradition of Frequently-Asked-Questions files (FAQs), which try to
 condense, into the most accessible format possible, all the most useful
 information on any given topic. The "Wisdom FAQ" can be seen as a (rather
 grandiose!) image of a FAQ that tries to contain all the wisdom of the
 world, on every topic... starting, of course, with those truths most useful
 for interactive fiction. (To subscribe to the list, send me a request at
 wisdom-request@mcs.com. The accumulated archives can be ftp'd from
 ftp.mcs.com in mcsnet.users/jorn/wisdom/. If you need me to email them to
 you, let me know how many kilobytes your emailbox can handle at once.)

 The mailinglist is grappling simultaneously with the task of simply
 accumulating 'story elements' or axioms, and the more difficult task of
 agreeing on a standardized way of expressing them. Because the latter task
 is more technical and less interesting to many people, it will likely be
 spun off into a second list of its own sometime soon.

 The task of enumerating story-elements, though, is not so much a question
 of technical as of storytelling expertise. For this reason, the Wisdom-list
 eagerly welcomes non-technical contributors who nevertheless have a knack
 for spinning out plotlines, or a gift for clever plot twists...

 Every object tells a story... don't it?

 The obvious way to keep these collections of story-elements organized is
 according to which objects in the object-hierarchy they require. It's not
 that hard, for any object in a game (or in the world), to rattle off the
 basic rules of its behavior. One strategy for 'priming your pump' might be
 to ask:

    * Where does this object come from?
    * How does a person come into relationship with it?
    * How might the person use the object?
    * How might they change it?
    * How might they be changed by it?
    * How might their relationship with it end?
    * How might it cease to exist?

 One convenient format for compiling the answers to these questions might be
 called a "meta-story":

 The food meta-story: A person tended a garden or farm raising plants or
 animals to eat or sell. They harvested the food when the time was right and
 sold it or preserved it or prepared it and ate it or fed it to friends or
 family. If it was well-prepared, their hunger was satisfied and they were
 happy. The food travelled thru their intestines and had to be excreted. If
 they didn't get enough good food, they got thin and died. Maybe the person
 preparing the food put poison in it to injure the person who ate it. They
 might have to disguise the flavor of the poison. Maybe they prepared it
 poorly and it tasted bad.

 The bottle meta-story: A person heated up some sand in an oven and blew air
 into it with a straw until it became a bottle. When it cooled, they could
 pour liquids into it and put a cork or cap on it to keep the liquids from
 spilling or evaporating. They could also fill it by dipping it into a
 larger body of liquid. When they took the cork out they could pour out the
 liquids, or drink from the bottle. Two or more people could pass the bottle
 around and share the drink. If they dropped the bottle on something hard,
 it probably broke, and any liquid in it spilled out. The broken glass could
 cut a person when they touched it, if they weren't careful. It could make a
 car tire flat. If a barefoot person stepped on it they would get cut. The
 broken base might act like a lens to focus light and start a fire, or
 magnify something tiny. (The bottle with clear liquid in it might also be a
 lens.) The person could knock someone unconscious by breaking the bottle
 over their head. They could use the bottleneck to make their guitar play
 better. They could roll dough flat by using the bottle like a rollingpin.
 (etc)

 So one approach the Wisdom-list may use could be to accumulate a sort of
 'children's encyclopedia' of these meta-stories, elaborating each of them
 to whatever level of detail our creativity allows.

 But simply enriching the supply of intelligent objects won't necessarily
 make the IF-author's job easier. For one thing, the more pre-existing
 behavior that's been supplied for the game's objects, the harder it will
 become for the author to anticipate every possible solution to the game's
 puzzles. In fact, the farther we move in this direction, the less
 attractive the whole idea of puzzle-oriented IF begins to seem...

 IF and 'psychology objects'

 Cyc has been circling closer and closer to the task of representing human
 dramas, and claims already to have a working model of emotions and
 motivations, but the Wisdom-list won't stand a chance if it doesn't
 directly confront the problem of encoding literary plots.

 The classic analysis of literary plots is George Polti's "Thirty-Six
 Dramatic Situations". Polti analysed a huge range of classic plotlines in
 literature, and declared these to be the basic ones: Supplication,
 Deliverance, Revenge, Vengeance by Family upon Family, Pursuit, Victim of
 Cruelty or Misfortune, Disaster, Revolt, Daring Enterprise, Abduction,
 Enigma, Obtaining, Familial Hatred, Familial Rivalry, Murderous Adultery,
 Madness, Fatal Imprudence, Involuntary Crimes of Love, Kinsman Kills
 Unrecognised Kinsman, Self Sacrifice for an Ideal, Self Sacrifice for
 Kindred, All Sacrificed for Passion, Sacrifice of Loved Ones, Rivalry
 Between Superior and Inferior, Adultery, Crimes of Love, Discovery of
 Dishonor of a Loved One, Obstacles to Love, An Enemy Loved, Ambition,
 Conflict with a God, Mistaken Jealousy, Faulty Judgement, Remorse, Recovery
 of a Lost One, Loss of Loved Ones

 Only a few of these will normally turn up in the course of applying the
 meta-story approach to story objects, because the most important 'objects'
 in literary plots tend to be psychological ones, like emotions and
 motivations.

 The meta-story approach can still work fine as a way of accumulating
 story-elements, though, even if you choose a totally arbitrary
 startingpoint (for example, hypnosis), so long as you're comfortable with
 the storytelling aspect of things:

 The 'hypnosis' meta-story: Once a person learned they could control others
 by hynosis. So they hynotized others into giving away their money and power
 and their health and their self-respect. And these people didn't even
 realize what had happened to them. Eventually things got so bad they were
 desperate to discover the source of their situation. Then one person got a
 glimpse of the truth, and then lost it, and then saw it again, and tried to
 tell others, and got dismissed as crazy, and attacked, but finally figured
 out how to lead others to see the truth, and they rose up together and
 overthrew their oppressors.

 The intuitive familiarity of the story-format allows almost any topic to be
 productively explored...

 Reverse-engineering emergent-behavior

 While the artificial-life theorists have been hoping to discover a few
 simple laws that will result in a vast payoff of interesting stories, via
 the principle of 'emergent behavior', the meta-story approach might be
 thought of as an attempt to outdo them by 'cheating'-- first you spell out
 the stories you want to see 'emerge', and only then do you analyse them and
 try to 'reverse engineer' the set of simpler laws that will produce them.

 So even something as simple as Maslow's hierarchy of needs (physiological,
 safety, belongingness and love, esteem, cognitive, aesthetic, and
 self-actualization needs), which might seem like a plausible startingpoint
 for a simple set of a-life laws, leading to emergent behavior, reveals some
 extremely inobvious patterns (at least from a mathematical point of view),
 when analysed for meta-stories:

 The physiological-needs meta-story: Every so often, a person gets a craving
 to consume food and drink. They usually arrange to have a source of these
 nearby, that they can rely on for purity. They may prepare the food and
 drink, cooking things, cutting them up, mixing them together, adding
 flavorings to make the experience pleasant. Or maybe they expect another
 person to do that for them. Usually, a group of people who live together
 will sit down together to eat, at a table with plates and silverware and
 glasses. Afterwards, someone must clean up. Sometimes they may eat at
 restaurants, or in a vehicle as they travel. They may carry a container of
 water to drink (perhaps flavored or mixed with nutrients or stimulants or
 intoxicants), or stop at a vending machine or drinking fountain or coffee
 machine. If a person's daily calories consumed don't equal their calories
 burned, they lose weight. If they consume more, they gain weight. If they
 lose too much weight, or fail to drink enough, they can die.
 Water-plus-wastes is excreted by urination, food-after-nutrient-absorption
 by defecation.

 The safety-needs meta-story: A person felt unsafe, and they didn't like it.
 Maybe there were other people or animals around, untrustworthy ones, and
 their home wasn't secure. Maybe they had to leave the safety of their home
 during the day, and risked being attacked. Maybe it was nature that
 threatened them, in the form of high cliffs, deep holes, quicksand,
 dangerous bodies of water, weather that's too cold, hot, or violent, etc.
 Maybe it was poorly maintained technology that was the danger. The person
 changed the environment or changed their behavior so that the danger was
 lessened and they felt safer.

 The belongingness-and-love-needs meta-story: A person felt lonely. They
 sought out others' company and acted charming so they would be welcome. Or
 they acted domineering so that others would be afraid to reject them. Or
 they acted hurt so that others pitied them.

 The esteem-needs meta-story: A person felt that no one respected or
 appreciated them. So they tried to do something admirable, and then made
 sure that others knew about it. Or maybe they lied about doing something
 admirable.

 The cognitive-needs meta-story: A person needed to know something, or was
 just curious. They sought out a book and read it, or a teacher and took a
 class or asked them questions. Or they just observed the thing they didn't
 understand, and thought deeply about it, maybe doing experiments. If they
 discovered something new they probably published their findings.

 The esthetic-needs meta-story: A person was oppressed by a boring or ugly
 environment, so they made or acquired or sought out objects that were
 pleasing to their senses. Maybe they recorded the process of creation, so
 that it could be reexperienced later, by others. Maybe they positioned
 these creations within their environment so they could experience them
 often. Maybe they grew bored with them after a time.

 The self-actualization-needs meta-story: A person had everything they
 needed, but didn't feel fulfilled. So they looked within themselves to
 discover what their heart wanted most, and followed their bliss...

 "SimNormal"

 Given the ambitious scope of the Wisdom list, there's a serious risk of
 getting bogged down in such a mass of story-content, that one loses any
 sense of a startingpoint, and so also any chance of actually building a
 working IF program!

 One way to keep these meta-stories somewhat 'grounded in reality' is to
 visualize them as being acted out on a computer screen, using even the
 fairly primitive existing standard for graphics adventures like King's
 Quest and its ilk. If your stories are too abstract for this technology,
 you probably haven't thought them through in enough detail!

 I like to imagine a sort of SimCity-like environment where a community of
 little NPC's go through their daily routines of life, in a completely rote
 fashion, with no emergent behavior expected or desired. (In honor of
 Normal, Illinois, I call this world "SimNormal".)

 Looking again at the belongingness-needs meta-story above, it's clear that
 before you can visualize it as a SimNormal animation, you have to break it
 down further, according to certain typical patterns of how these needs are
 satisfied:

 The casual-acquaintance meta-story: A person gets to know another by being
 introduced, or by introducing themselves, or by crossing paths
 occasionally. When they meet they exchange mild greetings and smalltalk
 about weather, news, gossip, entertainment they've seen. If nothing
 divisive turns up, they may gradually open up and trust each other more.

 The simplest way to encode this might be to give each person an
 intimacy-level toward each other one. Zero would mean total strangers, but
 each time they noticed a given person it might increase by one. When it
 reached five, say, they'd shift to casual-acquaintance mode, and greet each
 other. If they're introduced, on the other hand, they might reach five
 right away. As this number continues to grow, their greetings should become
 more extended in time, stopping to chat if they're not in a hurry. (There
 could be a chatting animation that's designed to be cycled continually, for
 whatever duration they've reached.) Discovering common interests may cause
 the intimacy-level to skyrocket. Discovering incompatibilities, or failing
 to see each other for a long time, can cause the intimacy-level to drop.

 The best-friend meta-story: A person gradually gets to know someone else,
 and enjoys spending time with them. (Or maybe it's a sudden strong
 connection.) They arrange to spend time together, do things together, maybe
 talk on the phone. They tell each other their private worries, and try to
 help each other. These exchanges make them feel better. Sometimes they
 fight, and reconcile or not. Maybe one of them gets an S.O. and that causes
 them to break apart. Maybe it just stops being so fun, and they drift
 apart.

 A person may maintain a 'short list' of those with the highest intimacy
 rating, and when they're bored or upset they'll look to these for support.
 A person-soothes-person2 story could be very simple-- time is consumed and
 person2 feels better. (Person1 may or may not feel worse-- if they do, it
 bodes ill for the friendship!) There may be a certain potential for
 conflict at each point, which should depend on the sorts of personalities
 they are, and whether they're in competition for scarce resources.

 The pals meta-story: A person has one or more best friends, and that group
 grows larger as others are allowed to join their get-togethers. Maybe
 they're invited or maybe they just show up and tag along. If someone
 doesn't like them they may be driven off. Several times a week, at least,
 they arrange to meet together. Maybe there's a power struggle between two
 who both want to lead. Maybe one by one they drop out; maybe others take
 their places.

 The planning-logistics of getting a group of free-thinking individuals
 together are a lot more complex than for just two. Maybe any of them can
 invite the others-- there'll need to be be a 'get-together meta-story' to
 handle this.

 The housemates meta-story: A person moves into a living-place with one or
 more housemates, sharing common areas. Usually, the housemates play the
 role of friends to some degree, listening to each others' daily stories.
 Some housemates are neater than others, and this will lead to conflicts.
 When bills arrive, they sometimes have to be split up unevenly and this may
 cause tensions. One person is probably the most responsible, signing the
 checks, etc. Each probably has one or more annoying traits that try the
 patience of the others. Maybe one by one they move away, and are replaced
 by others, or maybe they all leave at once.

 The co-workers meta-story: A person gets a job at a workplace, with others.
 Some of these become friends, others maybe casual acquaintances. Some
 become enemies. Even when they fight, they still have to work together, or
 quit, or ask for a transfer. Their enemies may try to make them look bad to
 their bosses.

 The confabulating-arranger model of IF

 So if we continue to pursue these directions of research, what sorts of IF
 might become possible? How do you give the player an infinite world, and
 still keep enough control to involve them in especially interesting
 stories?

 If the computer 'knows' all the most interesting sorts of dramas in
 literature, one strategy could have it be continually, unobtrusively
 revising the virtual world behind the scenes, so as to open up as many
 interesting plotlines as possible.

 So the game might open with a person in their apartment, waking up in the
 morning, and if they go outdoors they may be presented with a series of
 neighbors whose dramas they can become involved in... but none of these
 dramas needs to have been worked out in detail beforehand. Rather, the
 computer will continually improvise new possibilities based on the player's
 choices, and the view of reality they've been allowed thus far. If the
 player chooses not to follow up any given opening, that's no problem...
 there will be many other options to explore.

 This way, the past is as undetermined as the future, and can be molded to
 any extent, limited only by what the player has already been shown and
 told. So the computer is actively arranging that new developments will be
 as interesting as possible-- "confabulating" reality, to use a psychiatric
 term.

 And in this, the "confabulating-arranger" model perhaps most closely
 resembles the activity of the brain, during dreams...!
 ---------------------------------------------------------------------------

 Bibliography

    * Chris Crawford, "Flawed Methods for Interactive Storytelling" IED 7.4,
      April 1994.
    * Douglas B. Lenat and R.V. Guha, "Building Large Knowledge-Based
      Systems" Addison-Wesley 1991.
    * Michael J. Roberts, "TADS: The Text-Adventure Development System" Palo
      Alto, High-Energy Software, 1992.
    * George Polti, "The Thirty-Six Dramatic Situations" Boston, The Writer,
      1977 (originally published 1900).

 Some journal references for more on Cyc:

    * "CYC" AI Magazine 7(1), 1986
    * "When will machines learn?" Machine Learning, Dec 1989
    * "Cyc: Toward Programs With Common Sense" CACM, Aug 1990
    * "Knowledge and Natural Language Processing" CACM, Aug 1990
    * "Common Sense and the Computer" Discover magazine, Aug 1990
    * "Cyc: A Mid-Term Report" AI Magazine, Fall 1990
    * "The commonsense reviews" Artificial Intelligence, 61(1), 1993
    * "CYC-O" Wired magazine, Apr 1994
    * "Enabling agents to work together" CACM, 37(7), 1994

 [Up] [Map] [Next] [Robot Wisdom home page]

 [BACK] Back