March 6, 2006
Lebowitz’s Universe, part 2
This is the last in my series (1 2 3 4) of posts about two story generation systems that were first published about in the mid-1980s: Minstrel and Universe. I think they’re not just interesting in themselves, but also in the lessons they give us for how we might approach story generation today (including interactive story generation). In fact, I think they’re interesting in helping us think about how we might design any system meant to exhibit behaviors we consider “intelligent” — behaviors meant to be interpretable to a human audience as similar to things we do ourselves.
Universe‘s stories
The model of planning in Universe is somewhat different than in systems like Tale-Spin and Minstrel. 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, on the other hand, plans based on “character goals” and “author goals.” Character goals are monitored to maintain consistency, while the primary impetus for story generation comes through author goals. And the author has goals for keeping things going, rather than bringing them to conclusion. The result is 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.” 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 quite 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. (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 husband, the husband 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.
Below is an example of an actual Universe output for a forced marriage storyline (1985, 491), using the same characters as the Days of Our Lives plot summary in my first post about Universe. 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.
*(tell ‘(((churn liz neil)(together renee neil))))
working on goal — (CHURN LIZ NEIL)
Several plans to choose from FORCED-MARRIAGE LOVERS-FIGHT JOB-PROBLEM
— using plan FORCED-MARRIAGEworking 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
Possible candidates — MARLENA JULIE DOUG ROMAN DON CHRIS KAYLA
Using MARLENA for WORRIER>>> MARLENA is worried about NEIL
working on goal — (TOGETHER * NEIL)
Several plans to choose from SEDUCTION DRUNKEN-SNEAK-IN SYMPATHETIC-UNION JOB-TOGETHER
Possible candidates — DAPHNE RENEE
Using RENEE for seducer>>> RENEE seduces NEIL
working on goal — (ELIMINATE STEPHANO)
Several plans to choose from ATTEMPTED-MURDER EXPOSE
— using plan ATTEMPTED-MURDER
Using ALEX for KILLER>>> 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 at this time only contained 65 plot fragments, it was already enough to generate stories with more variety than Minstrel and more structure than Tale-Spin in their completed states. Further, its fictional worlds were much more complex and complete than those of either system, despite the fact that Minstrel was not finished until significantly after this point in the development of Universe. In short, eschewing the simulation of human cognitive processes was a demonstrably powerful outlook, from the perspective of fiction — but where did it leave the AI researcher?
What kind of author?
Though it is clear that Universe isn’t designed to simulate a human author through its internal processes, at the same time, the main processes it uses for storytelling are referred to as “author goals.” This may lead one to wonder, “Which author is that?”
Also, 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.
It is understandable that, less than a decade out of Schank’s lab, Lebowitz was unable to entirely drop cognitivist language in discussing his AI projects. In fact, to some extent, publication in AI journals and at AI conferences may have demanded it. In Lebowitz’s last paper on Universe, at the 1987 conference of the Cognitive Science Society, he even suggests that case-based reasoning may be a future direction for Universe‘s plot generation (p. 240).
But the next year Lebowitz left Columbia’s faculty, and by the publication of Ray Kurzweil’s book The Age of Intelligent Machines (1990) Lebowitz was riding out the AI winter outside academe. In the book, accompanying a capsule description of Universe, he is listed as a vice president of the Analytical Proprietary Trading unit at Morgan Stanley and Company (p. 390).
And it was only a few years later, in the early 1990s, that a set of AI techniques with no pretense to modeling human intelligence would rocket into the public consciousness: statistical techniques. For generating stories, however, better results are still achieved by processes that are specified explicitly by humans, rather than learned through the statistical examination of large pools of data. And the tools of traditional AI — both scruffies and neats — are powerful formulations for specifying such processes. Given this, such tools remain in use, but in a different environment. The successes of statistical AI, hard on the heels of “Good Old-Fashioned” AI’s (GOFAI’s) winter, have shaken to the core the belief that these tools can claim a special status. They are now simply ways of building a system, almost like any other. And, in this environment, people have begun to regard the task of story generation quite differently. We see this, for example, with projects like Michael’s Terminal Time.
March 6th, 2006 at 5:50 am
tale spin and the others come not from some fixation on planing but from the fact that I had little kids at the time so I was making up stoires and trying to see how i did it; joe bear was an idea that comes from the fact that I made up stories on the fly; I do not believe that that is how real authors work and, if I wanted to build such a program today i would do something very different; in fact I proposed that darpa sponsor a program that wrote movie plots that could win an academy award (they were looking for signs of success in aten year project) but, of course this was not what they had in mind’ I thought this was do-able because there really are only so man y plots — they keep writing the same movies after all
March 6th, 2006 at 7:40 am
Roger – thanks for stopping by!
In Meehan’s dissertation he doesn’t say much about your contributions to Tale-Spin‘s conception (specifically as a storytelling program, rather than the higher-level cogsci contributions), or about motivation from telling stories to kids. I’d be fascinated to hear more.
Also, I heard that a friend of mind from high school — Natalya Preiser — ended up working with you in Chicago. Is this true? I tried searching the web, but there were no traces.
March 6th, 2006 at 8:50 am
I find that it is a widely held belief among computer scientists who are trying to build systems that are meant to be able to generate stories that “they [= the Hollywood screenwriters] keep writing the same movies.” It is also very wrong. It seems to me that the belief is based on the assumption that “plot = story”, which is completely insufficient when used as a fundament for storytelling.
While many in the Entertainment business don’t even think they ever think in mathematical terms when doing creative work, there are storytellers, producers, directors &c who consciously work with equalities/inequalities as tools for generating and/or refining stories. But I don’t think that the equation “story = plot” can generate even a mediocre story, and nobody else seems to think so, because it’s never used by anybody to produce anything.
I think that one of the first things students of Creative Writing are told (or at least should be) is: “Whithout character, there is no plot. Without plot, there is no character.” I think that most researchers in Story Generation have yet to “get” the concept of “character”, and the complex ways in which “character” interacts with “plot”. So the minimal equation that I would think is useful for, and is acually used by, storytellers is “story = character + plot”.
There are much more elaborate equations and other mathematical representations which are used by storytellers today, but no generative model on the market fails to feature “character” as a fundamental value to be generated. In contrast, AI researchers working at story generation never seem to ask themselves: “What is character? How can my system express character? How can my system recognize character? What makes one character different from another character? What does my system know about these differences?” &c &c.
To put it bluntly, I don’t think you’ll make much progress at story generation until you start investigating these questions, and follow the trail that will emerge for you from there.
March 6th, 2006 at 9:11 am
Dirk, thanks for your comment. It’s good to have someone turning our attention to character.
Can I ask you to say a bit more about what’s lacking in the Universe conception of character? (After all, the system’s guiding assumption is that you shouldn’t generate any plot until you have a cast of characters.) Also, I don’t know if you have any thoughts about the model of the Oz Project, but it would be good to hear how/if you think that model of character is lacking.
March 6th, 2006 at 11:19 am
I have no idea about what’s lacking in the Universe conception of character, because I don’t understand it. If the “guiding assumption” is “you shouldn’t generate any plot until you have a cast of characters”, it’s way to broad for me to work with. It doesn’t even define what “character” is supposed to be doing in a story. What does it mean to the system to “generate a cast of characters”? What does the system know about any one character it generates? What methods does the system use to “grow” its characters (you wouldn’t believe what we do in search of inspiration; e.g. one prominent screenwriter and director, Dalton Trumbo, used to write best when sitting in the bathtub and smoking).
Here’s what Hendrik Ibsen had to say about character generation:
This is how character generation done by humans works. Following this procedure, the character generator generates a text string, with the goal of this text string being unique, in that the character that it represents is unique. Uniqueness of character requires uniqueness of text string.
And there is a point at which the generator knows that the string is unique; there is a final draft to finish, after which the generator is sure that “A Doll’s House” or “Hedda Gabler” will be a smashing success. In computational terms: the program halts, at the point where it assumes that the text string that it has produced will be successful with the audience. Only if the audience is able to identify with Nora, Hedda, or whoever the character is, and applauds, the computation can be said to have been successful.
Now for the 55 billion dollar question: is this process of character generation formalizable? This could only be done if it were a discreete process, which I think it isn’t. Thoughts?
March 6th, 2006 at 11:31 am
So, Dirk, this means that you’re convinced that a story generation system has to act as an author, and operate like a human author (the guiding assumption of Minstrel)? I think that’s probably an unproductive path, given all the failed projects we see strewn along it. I think we’re better off viewing the human system creator(s) as the author(s). Something more like Michael’s concept of “Expressive AI.” But certainly your point of view (if I understand it correctly) has a long and distinguished tradition behind it.
The Universe approach to character generation, by the way, was summarized briefly in my previous post. There’s a lot more detail in Lebowitz’s 1984 paper.
March 6th, 2006 at 12:13 pm
To quote myself, Noah:
So no, I don’t think that I, or anybody else, can write a program that does what writers do. Therefore, I don’t think that programs can generate characters. And because programs cannot generate characters, programs cannot generate stories, in any “strong” sense, i.e. in any sense that involves human creativity. I don’t accept that programs can be “imaginative”, or “creative”, or even “generative” in storytelling, in the sense in that human storytellers are these things.
The reason why I don’t accept this is a mathematical one: for me, the impossibility of “strong” story generation follows from Algorithmic Information Theory, which proves that the random string is computationally incompressible, i.e. there can be no formal representation (= generative program) shorter in length than the string itself. Since the best human authors not only produce unique – that is, random – strings on purpose, but even can predict with high probability just when such a string has some quality that will make it a success with the audience, this, to me, means that the string as a result of creativity cannot be based on a formal representation, i.e. a program.
For more than 50 years now, mathematicians and computer scientists working in AI have failed to show how the generative set can be formalizable, and always, the Incompleteness Theorem turns out to be the fundamental obstacle. I tell you, this won’t work. The best I think I can do is to forget about character generation, and concentrate on how I can make human-generated characters interactive.
March 6th, 2006 at 12:34 pm
Dirk — oddly enough, I think we seem to be agreeing but speaking past each other.
We both seem to think that the task isn’t to get the computer to be creative, but rather to get it to do some interesting procedure with the results of human creativity.
You think that interactivity is a possibility for this interesting procedure (though many people don’t). I think configuring the storyline is a possibility for this interesting procedure (though it appears you don’t).
In either case, we both agree that the start of an interesting system is somewhere in the neighborhood of smoking in the bathtub.
March 6th, 2006 at 12:48 pm
meehan had the idea to write tale-spin before I arrived at yale; when I took over as his advisor I pushed him into thinking about what I was thinking about: how I made up stories
the real issue at that time was to get computers to do anything at all that would look like intelligence; I had the idea that if you wanted to do that you might think about what people did, which anyway was a subject I cared (and still care) more about; AI folks always took themselves too seriously; arguing whether computers can think is irrelevant; can people think? a more interesting question (to me); my vote: NO; that is why I think movies can be written by a computer; I think the procedure is much more straightforward than “artists” want to admit
as for natalya — yes she did work for me — we were good friends in fact; then she went to harvard for an MBA and I lost track of her
March 6th, 2006 at 5:38 pm
Whether I think that configuring the storyline is a possibility seems to depend on what you mean by “configuring the storyline”, Noah. I wouldn’t want to try using an Oz Project-style Drama Manager to configure anything in a story, since I wouldn’t know how to identify with my character through such a module.
I think that a character should be autonomous, not dependent on being managed from the outside. To minimize compression-induced loss of meaning, I only use carefully hand-encoded string transformations; no numerical abstractions, except for loop counting (the results of which are easy to re-translate into natural language: “I already told you twice that […]”). Wherever possible, I push context information towards the substring/program fragment, instead of away from it, as one tends to do when using larger “management” modules: let the individual word or phrase “decide for itself” which output sentence it should be in, by giving it enough information.
I don’t even think that I have anything any more that could be called a “storyline”; it’s more like configuring an abstract story “space”, where the constraints of the underlying technology appear in the content as character traits, putting plausible, and therefore narratable, bounds on any character interaction.
And Roger: the idea that computers can write movies is now like, 30 years old or so. But did you ever sell a script?
March 6th, 2006 at 7:06 pm
ideas like that would have been 3000 years old if there had been computers or movies; you miss the point; 30 years ago no one knew how to do it; I am just saying it could be done now; perhaps this is irrelevant in an abstract conversation like this one, but I like to know how to do something before i say it can be done
March 6th, 2006 at 7:09 pm
Excuse me, but how could it be done now?
March 7th, 2006 at 12:19 pm
Apologies for dropping out of the conversation yesterday afternoon. I had a rather non-direct flight from Rhode Island to California that consumed 12 hours or so of the day.
Roger, I think it’s great that you might be getting back into the story generation game. I’m sorry to hear that DARPA didn’t go for it — but I hope someone does.
I’m sure that your plans can’t be outlined in a blog comment, can you point us to any related information for what you’re thinking of for the movie plot generator?
As for Natalya, last I heard she was getting married — I believe to one of the writers for “That 70s Show.” She and I also become friends through common work, though I’m sure our high school mock trial team was a rather humble operation compared to what you two were pursuing.
Dirk, I think I feel sympathy with the goals you outline above, but I feel that I lack context. Is there a relatively up-to-date overview of your architecture available online?
March 7th, 2006 at 4:06 pm
I put a 7-page PDF online, Noah. I wrote it in June last year, so it’s a fair bit behind what the code now does – especially the vague description of how I planned to implement Turing degrees has a concrete and working implementation in the form of a type system now -, but the basic ideas are unchanged.
March 8th, 2006 at 2:08 pm
Noah, I’ve found these posts to be very interesting, would it be possible to provide some more examples of the three programs output for illustrative purposes?
March 8th, 2006 at 7:51 pm
Dirk, thanks for the pointer. I’ll try to post some thoughts about your writeup at some point, and I’d be curious to hear the thoughts of others.
Mike, I don’t know if I will have time to type in outputs from the systems any time soon. You can certainly find more in Meehan’s dissertation (chapter 11 is a complete run-through of an example generation) and Turner’s book (which provides a similar generation walk-through). Unfortunately, there aren’t as many published examples of Universe‘s output as I’d like, so I’m not sure what to suggest in that case. Maybe we could find Lebowitz’s email somewhere and ask him?
March 15th, 2006 at 12:21 pm
One thing I’m rather interested in is the set of author goals that Universe uses. Do you know what the basis for these goals was? If you had a complete language of plot elements and tropes for any particular genre, it seems that Universe could easily generate a typical example of any genre. For instance, in traditional (romantic) comedic plays (the genre who’s conventions I’m most familiar with), tropes such as “Woman discovers legitimate parents” or “misunderstanding about suitor’s identity” would be such authorial goals.
What was the basis for Universe’s authorial goals? (Essentially, is there a grammar for constructing stories out of plot elements?)
Has anybody attempted to apply different sets of authorial goals to mimic different genres of story?
March 17th, 2006 at 5:46 am
Noah, thanks again for posting these great descriptions and analyses.
While Universe at this time only contained 65 plot fragments, it was already enough to generate stories with more variety than Minstrel and more structure than Tale-Spin in their completed states. Further, its fictional worlds were much more complex and complete than those of either system, despite the fact that Minstrel was not finished until significantly after this point in the development of Universe. In short, eschewing the simulation of human cognitive processes was a demonstrably powerful outlook, from the perspective of fiction
As I suggested in my comments on Minstrel, I’d argue that Universe‘s greater variety and completeness of story generation versus Minstrel is because Minstrel didn’t have enough raw knowledge, as well as polishing of such knowledge, to be as successful in its output. Yes that could be because Minstrel was closer to simulating human cognitive processes, and therefore was more complex, which requires more time and effort to engineer the needed knowledge. But I’d be careful of drawing much more of a conclusion than that.
I like Lebowitz’s work; it reminds me a lot of Chris Crawford’s, or even the The Sims with its generic characters. (I’m planning a top level post describing what Chris is up to these days, btw.)
Echoing Dirk’s sentiments, it’s not the initial approach I would take (or have taken) to interactive story though; IMO high-level plot generation is not interesting if it lacks getting very grounded in dialog, i.e., in specific characters and their language. Specific characters are more interesting to me than generic plot; let’s let plot come after character, or emerge from character, not the other way around.
March 17th, 2006 at 1:06 pm
Hey – sorry I can’t keep up on this thread right now. A big deadline looms over me. But I’m very interested in the thoughts folks are posting, and hope the conversation can keep some momentum even without me.
May 19th, 2006 at 4:53 pm
[…] ion… Pontification at Terra Nova on the future of MMOGs. In light of Noah’s series of posts on creative systems for narrative: a new book by generative […]