March 5, 2008

EP 7.2: Universe

by Noah Wardrip-Fruin · , 6:11 am

Michael Lebowitz began work on Universe at around the same time that Scott Turner began his work on Minstrel, and the two systems bear a number of similarities.2 Both focus on the importance of authorial actions, rather than simply character actions. Both emerge from the scruffy AI tradition — Lebowitz had recently written his dissertation at Yale under Schank’s supervision, contributing to Schank’s model of dynamic memory, especially in relation to story understanding.3 Descriptions of both also emphasize the importance of the “point” or “theme” that the system is working to communicate through each act of generation (Lebowitz, 1984, 175).

But, in addition to its similarities with Minstrel, Universe also has an unusual feature in common with Tale-Spin. Just as the most famous stories attributed to Tale-Spin are actually hand transcriptions of early errors, the most famous story attributed to Universe has a somewhat more tenuous connection to the project than one might assume. Here is the story:

Liz was married to Tony. Neither loved the other, and, indeed, Liz was in love with Neil. However, unknown to either Tony or Neil, Stephano, Tony’s father, who wanted Liz to produce a grandson for him, threatened Liz that if she left Tony, he would kill Neil. Liz told Neil that she did not love him, that she was still in love with Tony, and that he should forget about her. Eventually, Neil was convinced and he married Marie. Later, when Liz was finally free from Tony (because Stephano had died), Neil was not free to marry her and their trouble went on.

Though a number of prominent authors4 provide this as an example of Universe’s output, in fact this is a summarization of a plot from Days of Our Lives. It appears in a paper about Universe as “an illustration of the kind of plot outlines we would like to generate” (Lebowitz, 1985, 172). Unfortunately, Universe was never able to display the level of mastery achieved by the authors of Days of Our Lives — a remarkably popular and long-running daytime television melodrama, or “soap opera.” However, this story does nonetheless point to a number of important ways in which the goals of Universe are significantly different from those of systems such as Tale-Spin and Minstrel.

First, Universe is designed to to generate continuing serials: stories that never end. Second, Universe is working in one of the world’s most popular story forms (television melodrama) rather than the somewhat archaic (and more difficult for contemporary audiences to judge) forms of Aesop-style fables and tales of Arthur’s knights. Third, Universe’s goals are defined in terms of what kinds of story and character structures it will generate, rather than in terms of the model of human cognition that the system’s operations will simulate.

The last of these is, I believe, the most significant. While ideas such as scruffy AI’s “memory organization points”5 are important in the conception of Universe, the system is not presented as a simulation of a model of human cognition. Rather, it is presented as a means of generating a universe of characters and an ongoing plot that interconnects them. In fact, in lieu of any cognitive science theory, Lebowitz writes: “Our methods are based on analysis of a television melodrama” (Lebowitz, 1985, 483). This allows Universe to be designed specifically for the generation of stories, and of a particular style of stories, rather than for the simulation of the behavior believed to generate stories.

The Universe system is organized in two parts. One creates the interconnected sets of characters and histories that will form the background for the generated fiction. The other generates an ongoing fiction. Universe’s model of authoring also falls into two parts. One part of the authoring effort is the creation of basic processes for generating the background world and the ongoing fiction. The other is the creation of the data that these processes employ, such as character stereotypes and story fragments.

Universe’s characters

A Universe story begins with the creation of characters, much as happens in Tale-Spin. But rather than a small number of characters who seem to come into existence at the moment the story begins, Universe creates an interconnected group of characters with somewhat detailed histories. This is accomplished through a character creation cycle. As outlined in Lebowitz’s 1984 paper, the cycle begins with a few characters in a queue, soon to become the universe’s (m/p)atriarchs, who need the details of their lives fleshed out. One character at a time is removed from the queue, and a simple simulation of that character’s life is carried out — focusing on the gaining and losing of spouses, the birth of children, and the possibility of death — until the present is reached. Any new characters created through this process are added to the queue. New characters aren’t created for each marriage, however, because the system may select an already existing eligible character (defined as single at the time of the marriage, of appropriate age and sex, and not directly related to the character). This begins to create interconnections between the families.

Once this basic framework of marriage, birth, and death is filled in, each character is further fleshed out. This begins by giving each character a set of traits, some of which are inherited from their parents (if known), and selecting a set of stereotypes that work well to explain those traits. Stereotypes include many familiar character elements (e.g., lawyer, doctor, gangster, big-eater, swinger, video-game-player) and have normal values for some traits and not others (e.g., “lawyer” has normal values for intelligence, guile, and self-confidence, but not for religion, promiscuity, or moodiness). Following this, the system adds further detail to the characters’ pasts by creating simplified versions of the sorts of events it will create in the present (once story generation begins).

Universe’s stories

Because Universe is not aimed at producing stories that end, but rather serial melodramas on the model of Days of Our Lives, its plans are never aimed at bringing things to completion. In Tale-Spin, and most AI work on planning, the focus is on achieving goals: Joe Bear is hungry, and the planning process tries to get some food and ingest it so that his hunger will go away. In Minstrel the plans are to flesh out a PAT schema, meet the other goals, and complete the story. Universe plans, on the other hand, are based on “character goals” and “author goals” that do not lead toward conclusions. Character goals are monitored to maintain consistency, while the primary impetus for story generation comes through author goals. The author has goals for maintaining an interesting story — Lebowitz talks about goals such as preserving romantic tension and keeping the story moving — with the result that Universe’s plans can never specify a complete course of action, only one that seems appropriate given the current circumstances in the story’s universe.

High-level author goals are carried out by lower-level goals, and planning for both takes place through “plot fragments.” These fragments are a primary type of data in the Universe model of authoring. They are both events themselves and means toward authorial goals. For example, a higher-level goal to which Lebowitz gives particular attention is “churning” lovers, keeping them separated by new obstacles each time the previous set is cleared up. The forced marriage of Liz and Tony, on Days of Our Lives, is by Lebowitz regarded as a fragment that achieves (among other possible goals) the “churning” of Liz and Neil. This makes it apparent how character goals are treated quite differently in Universe as opposed to systems such as Tale-Spin. As Lebowitz writes about “churning”:

Obviously this goal makes no sense from the point of view of the characters involved, but it makes a great deal of sense for the author, and, indeed, is a staple of melodrama (“happily ever after” being notoriously boring in fiction, if not in life). Universe has a number of other plot fragments [besides forced marriage] for achieving this goal, such as lovers’ fights and job problems. (Lebowitz, 1985, 488)

Universe maintains a representation of outstanding author and character goals. The storytelling cycle begins with choosing an author goal that has no unmet preconditions. A plot fragment is selected that will achieve that goal, with preference given to fragments that also achieve other goals that are current. This is plot fragment is then made part of the story — producing new characters, events for output, and new goals as appropriate. Even “forced marriage” is a relatively high-level plot fragment, which needs to be filled out with lower-level fragments for the woman dumping her lover, the lover getting together with another woman, the threat from the parent being eventually eliminated, and so on. The potential choice of a number of different fragments and characters for each of these elements increases the variability of the story structures Universe produces.

As this process takes place, Universe doesn’t simply choose characters and plot fragments randomly. First, the personalities and plans of characters constrain which can play roles in the fragments (and, further, some fragments require the participation of characters that have particular stereotypes). Second, with each fragment Universe tries to select events and include characters that will help meet other active authorial goals. This helps create complexly interwoven plots, such as those of serial melodramas, in which events often contribute to several active storylines.

Table 7.1 is an example of an actual Universe output for a forced marriage storyline, using the same characters as the Days of Our Lives plot summary above (Lebowitz, 1985, 491). Those lines of the output that begin “>>>” represent low-level events, whereas other text provides a trace of the planning process. The system begins with two active goals: to churn Liz and Neil, and to get Neil together with Renee.

Table 7.1: Universe Output:

*(tell ’(((churn liz neil)(together renee neil))))

working on goal — (CHURN LIZ NEIL)

working on goal — (DO-THREATEN STEPHANO LIZ “forget it”) — using plan THREATEN

>>> STEPHANO threatens LIZ: “forget it”

working on goal — (WORRY-ABOUT-NEIL) — using plan BE-CONCERNED

>>> MARLENA is worried about NEIL

working on goal — (TOGETHER * NEIL)
Possible candidates — DAPHNE RENEE

>>> RENEE seduces NEIL

working on goal — (ELIMINATE STEPHANO)
Several plans to choose from ATTEMPTED-MURDER EXPOSE — using plan ATTEMPTED-MURDER

>>> ALEX tries to kill STEPHANO

working on goal — (DO-DIVORCE TONY LIZ) — using plan DIVORCE

>>> LIZ and TONY got divorced

working on goal — (TOGETHER LIZ NEIL)
no acceptable plans

Other plot fragments that Universe can use for churning include LOVERS-FIGHT, JOB-PROBLEM, PREGNANT-AFFAIR, ACCIDENT-BREAKUP, STEAL-CHILD, COLLEAGUE-AFFAIR, and AVALANCHE-ACCIDENT. The variations on these depend on the characters involved. For example, in Lebowitz’s 1987 paper he shows output from churning Joshua and Fran. Given their jobs, they can experience the job problems of BUREAUCRAT and SLEAZY-LAWYER. Given other aspects of their characters, they can fight about IN-LAWS, MONEY, SECRETS, FLIRTING, and KIDS.

While Universe was never completed (at the time of Lebowitz’s 1987 paper it only contained 65 plot fragments) it was already able to generate stories with more consistency than Minstrel and more structure than Tale-Spin. But its very consistency raises a question: In what sense is Universe a story generation system? Sequencing plot fragments doesn’t sound nearly as impressive as the creative adaptation of Minstrel’s TRAMs or the simulation of intelligent behavior in Tale-Spin.

Authoring Universe

It is precisely the elements that make Universe an important early model of pursuing story generation from an authorial perspective that also open it to questions as to its significance. The system is explicitly limited to combining and sequencing hand-authored story data, rather than attempting to somehow generate new data. This means that important human knowledge about stories can be encoded into the data. It provides a role for authors and a route to shaping the audience experience. But the same can be said of a Choose Your Own Adventure book, each of which is structured as a set of pathways through plot fragments.

One difference, of course, is that a Choose Your Own Adventure book provides even greater opportunities for encoding authorial knowledge — down to the level of language, not just the comparatively abstract level of character stereotypes and plot fragments. But the more significant difference lies in the pre-defined pathways that structure a Choose Your Own Adventure. This is a close parallel to a difference described earlier, between character actions driven by finite-state machines and by the Strips-derived planning processes of F.E.A.R. In all these operational logics, the possible action fragments are hand-created by human authors. But in one set the connections between fragments are pre-determined during the same authoring process, while in the other set actions are dynamically sequenced, according to rules, based on the current state of the fictional world. This produces a vast difference in both the tractability of the authoring process and the dynamism of the audience experience.

However, when systems are designed in this way, a risk presents itself. A system designed to dynamically sequence hand-authored elements of a fiction may embody a flexible, powerful approach to generating a variety of fictions — or it may simply be an elaborate manner of breaking a particular story into chunks and providing a means for a computer to reassemble them. The only way to be sure that a software author hasn’t created an inflexible system (while fooling her- or himself into thinking it is a general, flexible one) is to have enough data to produce a variety of complete audience experiences. Universe seems like a powerful and flexible model, but only further development of its data could have demonstrated this convincingly.

Similarly, given the lack of attention given to surface generation in Universe, it is impossible to know how well its model serves the challenge of expressing its underlying model for the audience. Some might argue that meeting this challenge is entirely a matter of the design of the system for presenting the work’s surface — that almost any model can be effectively presented in the desired manner. Perhaps this is true, but it is strongly reminiscent of a position that has proven problematic in the field of human-computer interaction (HCI).

In the HCI field it is relatively common to suggest that a software system’s interaction surface can be abstracted from the underlying processes. The processes can be specified up front and implemented in a “waterfall” fashion, working linearly from a detailed initial specification, which may be efficient from an engineering standpoint. Meanwhile, the interface can be developed iteratively, perhaps with participation from those who will actually use it. Finally, another software layer can be used to map between the waterfall-produced processes and the iteratively-developed interface.

It is here, however, that we see the limitations of the model of authoring systems introduced at the start of this chapter. While it is true, theoretically, that layers of software abstraction make it possible to create software systems that relatively arbitrarily make some tasks easy and others difficult, it is also true that the underlying layers inevitably exert their influence. In the field of software development, Bonnie E. John and Len Bass have called this “We can’t change That!” (Bass and John, 2001; John and Bass, 2002, 2003, 2004). If the model of the underlying activity embedded in the software processes is too far from the imagined interface, then the amount of work required to support that interface is simply not entertained. In the field of digital media, Nick Montfort and Ian Bogost have coined the phrase “platform studies” to name scholarly work that takes the specifics of underlying hardware and software layers into account.

I believe that, given this, we simply cannot know how well suited Universe is to surface realization, and the same holds true for the many story generation projects that focus solely on the generation of story structures. Fortunately, the next two systems I will discuss — Brutus and Terminal Time — make surface realization an important element of their systems. I will dedicate a separate section to considering how they address this challenge; focusing first on a close, critical reading of their models of authorship.


2Lebowitz’s work on Universe was carried out while a faculty member at Columbia University, during which time (according to the acknowledgments in Lebowitz’s 1984 and 1987 papers) work by Paula Langer and Doron Shalmon made significant contributions to the project and Susan Rachel Burstein helped develop many of the ideas.

3Lebowitz’s dissertation was “Generalization and Memory in an Integrated Understanding System,” filed December 1980.

4Including Marie-Laure Ryan (1992, 246) and Janet Murray (1997, 201).

5Also known as “memory organization packages.”

12 Responses to “EP 7.2: Universe”

  1. Richard Evans Says:

    There is a minor typo in “This is plot fragment is then made part of the story”…

  2. andrew Says:

    As an aside… The Facade architecture certainly falls in this camp. While we believe it is an expressive architecture for at least simplistic story generation (one of the requirements for high agency — agency being the primary design goal of the project), admittedly it’s not been demonstrated convincingly, since the only story we’ve built with it to date only has 27 high-level beats (plot fragments, each able to express its core content with some variation), plus ~20 smaller narrative progressions than can mix in to the beats.

    I’m curious, will you be doing a section at some point on “sandbox games”, e.g. The Sims or Grand Theft Auto, in regard to their story generation capabilities? (Since neither project has releaesd much technical detail about their implementation, perhaps you wouldn’t be able to, even if you wanted to.)

    I wonder, where would you draw the line between story “emergence” from sandbox style games (e.g., the types of emergent narrative fragments that I reported from Petz and Babyz), and story “generation”?

    Is paragraph 21 here essentially your answer? Meaning, “emergent” story falls out of a slightly flexible system, and “generated” story from a highly flexible one?

  3. noah Says:

    Thanks for the catch!

  4. noah Says:

    Andrew, I’m very happy your thoughts are running in that direction, at this point in the book. As it happens, the very next chapter is called “The SimCity Effect” and tries to get at some of these issues, though from a slightly different direction. In the next chapter I focus mostly on how sandbox games can be a satisfying way of interacting with human characters because the representation on the surface maps well to an interesting model below. But the surface experience isn’t what many people want for fiction. So then I talk about how projects like Oz, Improv, and Facade can help us think about the relationship between surface appearance and underlying model in something more like an enacted fiction than a sandbox. But it’s actually only in my discussion of Petz (also in the next chapter) that I come close to grappling with how we experience something like fiction in a sandbox. Going further might be a good thing for the conclusion, which I’m planning to use to address issues that come up in the two reviews (blog-based and blind).

  5. michael Says:

    While Universe doesn’t provide an explicit cognitive model, I would still classify it as an author modeling system. Unlike Tale-Spin, which models the goals of characters and their effect on the world (character and world modeling), or story grammars, which directly model story structure, Universe models authorial goals (e.g. churn the romantic lives of two characters) and plans for achieving authorial goals. I think this qualifies it as an author modeling system, though it is not as deep a model as Minstrel.

  6. michael Says:

    I’ve never fully understood what is meant in “choosing goals that have no unmet preconditions”. Typically preconditions are associated with plans rather than goals. It sounds like there’s some sort of precedence relationship maintained over goals, but it isn’t really described in his publications. In your researches, did you ever get more clarity on this?

  7. michael Says:

    Liebowitz proposes using a modified form of explanation-based learning to generalize the constraints in plot fragments. He gives one example (not clear if hand generated or not) of an explanation for the forced marriage plot fragment, and how the explanation can be used to generalize the constraints (standard EBL stuff). EBL of course requires a domain theory, which goes beyond simply authoring plot fragments; the author would have to provide a logical theory for how plot fragments achieve their author goals. Liebowitz does say that at the time of writing, his modified EBL is working. This is an example of something deeper than sequencing plot fragments.

  8. michael Says:

    Incidentally, Tale-Spin is sequencing character plans to accomplish character goals. At a high level, Tale-Spin and Universe are similar: they both sequence plans to achieve goals, where plans involve recursive subgoal pursuit. This is the basic loop for reactive planning (minus reactive conditions) as well. So it’s not clear to me that Tale-Spin seems more impressive than Universe.

  9. Noah Wardrip-Fruin Says:

    I think we get down to a distinction that may seem a little fine here — but I think it’s also a crucial distinction. It’s one thing to try to simulate what we think real authors do and it’s another to organize a story generation system to that it has an “author” level (without any commitment to whether what it does has any particular relationship to what human authors do).

    However, while I think this distinction is important, and I think Universe is an example of the latter (while Minstrel is an example of the former) it is true that Lebowitz’s writing creates some confusion. For example, while no cognitive science model of creativity is given as the basis of the system’s design, Lebowitz still gestures toward the cognitivist view of AI, writing in one paper that a goal of Universe is “to better understand the cognitive processes human authors use in generating stories” (1984, 172) and in another that we “can expect research into extended story generation to … give us insight into the creative mechanism” (1985, 484). Exactly how this will take place is never explained.

    I’ve added a footnote to this effect.

  10. Noah Wardrip-Fruin Says:

    I read the idea of a “goal with no unmet preconditions” relatively simply. For example, if churning lovers is a goal, there must be lovers to churn before it can be pursued.

    But I agree it would be great to get an expansion of the information on things like how Universe “maintains a precedence graph that records how the various pending author goals and plot fragments relate to each other and to events that have been told already” (and so on) in the 1985 paper. I don’t have more information (that I recall) but perhaps we might ask Lebowitz.

  11. Noah Wardrip-Fruin Says:

    Maybe there’s not enough emphasis, in the last sentence of this paragraph, on the “doesn’t sound” phrase. I mean to say that Tale-Spin‘s operations are presented using language that implies a simulation of intelligent action in the world, while Universe employs a less impressive-sounding rhetoric.

  12. Michael Mateas Says:

    Universe explicitly employs a rhetoric of authorship (the content of plot fragments depends on the story the author wants to tell, and are otherwise atheoretical), while Tale-Spin does use the rhetorical language of a theory of intelligent action. But of course, the truth is that Tale-Spin characters are just as “authored” as Universe plot fragments.

Powered by WordPress