March 1, 2006

Turner’s Minstrel, part 1

by Noah Wardrip-Fruin · , 9:33 am

As mentioned in my previous post, the first publication about Minstrel appeared in the mid-1980s. The system was brought to completion over the course of a decade, resulting in Turner’s 1994 publication of The Creative Process: A Computer Model of Storytelling and Creativity. Over the first few years of Minstrel‘s development, some of the ideas at its foundation continued to evolve. Particularly, in Schank’s lab the model of dynamic memory and its adaptations was extended into the idea of “Case-Based Reasoning” (CBR). The basic idea of CBR is in some ways quite close to that of scripts: in the main people do not decide what to do in each situation by reasoning from first principles, but rather by drawing on previous knowledge. However, rather than suggesting that each of us has a “restaurant script” and a “sports event script” and so on, case-based reasoning assumes that we remember many cases, and reason from them — much as the learning of previous cases is formalized in legal and business education. (I’m adapting this account from 1989’s Inside Case-Based Reasoning.)

According to CBR theory, humans have three major types of cases we work with. There are “ossified cases” that have been abstracted to the point where they are essentially rules, such as proverbs. There are “paradigmatic cases,” each of which turns out to be the only experience we have that is relevant to a particular current situation, and which we adapt in order to understand the new situation. Finally, the most complex structures are “stories,” which Schank and Riesbeck characterize as “unique and full of detail, like paradigmatic cases, but with points, like proverbs.” The continuing reinterpretation of stories is described as the “basis of creativity in a cognitive system” (p. 14).

Over the decade of work on Minstrel Turner also further developed his position on how story generation systems should be designed — and, in particular, what relationship such designs should have to the way that human authors go about their work. In Turner’s conception, the relationship should be one of simulation. As he writes in The Creative Process:

Authors craft stories to achieve a wide variety of complex and often competing goals. To understand why storytelling is so difficult, we must understand what an author is trying to achieve. To build a computer program to tell stories, we must understand and model the processes an author uses to achieve his goals. (p. 3)

In other words, much as Meehan sees the key to story construction in Tale-Spin as the accurate simulation of the goal-directed behavior of people as characters, Turner sees the key to story construction in Minstrel as the accurate simulation of the goal-directed behavior of people as authors. Given that Turner remained, at the time of this work, committed to the view of human behavior articulated by Schank and his colleagues, there was only one option for the design of Minstrel. As Schank and Riesbeck put it, “Case-based reasoning is the essence of how human reasoning works” (p. 7). Therefore, as Turner writes, “Minstrel is a type of case-based reasoner” (p. 11).

Creating stories from stories

Minstrel begins storytelling much as some human authors might: with a theme to be illustrated. The audience can request a particular theme, or Minstrel can be “reminded” of a story with a similar theme. However, Minstrel isn’t reminded by doing a search through the hard drive of the machine where it resides, or by monitoring the content of recent email delivered to the user of the machine, or by any other happenstance. Instead, Minstrel is reminded by being given a pool of fragments structured according to the internal schema representations it uses for characters and scenes. Matching fragments against stories in memory will result in one story being selected, and then Minstrel will have the goal of telling a story on the same theme.

Minstrel uses case-based reasoning to meet its goals, including this one. But goals also need to be organized. And here we can see the first tension emerging between Turner’s goals of simulating human behavior and creating a successful system for telling stories. Though there’s no assertion made that human authors operate in this way, Minstrel‘s goals are organized as an internal agenda. Planning proceeds in cycles, with each cycle attempting to accomplish the goal that currently has the highest priority on the agenda. If a goal fails it can be put back on the agenda at a lower priority, with the hope that later circumstances will make it possible to achieve. Turner describes the agenda this way:

Minstrel begins storytelling with an initial goal to “tell a story.” This goal breaks down into subgoals including selecting a theme, illustrating a theme, applying drama goals, checking the story for consistency, and presenting the story to the reader. At each cycle, Minstrel selects the author-level goal with the highest priority from the goal agenda and passes it to the problem solving process. Problem solving finds a plan for that goal and executes it.

Two important actions that Minstrel‘s plans can take are to create and add new scenes to the story, and to create and add new author-level goals to the planning agenda. As new scenes are created, they are added to the current story. As new goals are created they are added to the goal agenda. Storytelling finishes when the goal agenda is empty. (p. 77-78)

Minstrel‘s themes are also represented in its schema system. Each theme is actually a piece of advice about planning, and represents the kinds of characters, plans, and outcomes necessary for illustrating the theme. Though Minstrel is designed to tell stories in the domain of King Arthur’s knights, its “planning advice themes” (PATs) are drawn from Romeo and Juliet, It’s a Wonderful Life, and proverbs. For example, one of the PATs drawn from Romeo and Juliet is PAT:Hasty-Impulse-Regretted, based on Romeo killing himself upon discovering what he believes is Juliet’s lifeless body — though, if he had waited a moment longer, she would have awakened from her simulated death. Oddly, Turner summarizes his schema representation of this as follows:

Decision: &Romeo believes something (&.Belief.1) that causes a goal failure for him (&Goal.1). This and his hasty disposition motivate him to do something irreversible (&Act.1).

Connection: &Romeo learns something new (&State.4) that supersedes the evidence for his earlier belief (&Belief.1).

Consequence: &Romeo now has a different belief, which motivates him to retract his earlier goal (&Goal.2) but he cannot, because his earlier action (&Act.1) is irreversible. (p. 104)

Of course, as Turner notes, this isn’t actually what happens in Shakespeare’s play. Romeo kills himself, and never knows that Juliet wasn’t actually dead — much less regrets his decision. This is perhaps another artifact of the tension between building an operational system and simulating human authorship. In Minstrel, character-level goals and plans are represented in the schema, and so can be transformed (as outlined in my next post). Author-level plans, on the other hand, are each structured, independent blocks of LISP code — presumably for reasons of authoring and execution efficiency. Therefore, author-level plans are opaque to Minstrel‘s transformation procedures, which operate on the schema representations. As a result, if PATs are going to be transformed, which is Minstrel‘s primary engine for producing new stories, then they must be represented at the character level, rather than at the authorial level.

In any case, once a theme has been selected, this adds a set of goals to the agenda: instantiating examples of the decision, connection, consequence, and context of the PAT. Once transformation plans succeed in creating the sequence of story events that accomplish these goals, other goals can come into play. One set of secondary goals are called “drama goals” and include suspense, tragedy, foreshadowing, and characterization. A characterization goal, for example, would add a story scene illustrating that a character has an important personality element (e.g., makes decisions in haste) before the section of the story that illustrates the PAT. Another set of goals, “consistency goals,” fill out elements that aren’t the bare-bones illustrations of the PAT. For example, if a knight kills another person, consistency goals makes sure that he is near the person first, and makes sure that he has an emotional reaction afterward. Finally, presentation goals make the final selection of the scenes that will be in the story, their ordering, and how they will be expressed in English.

I hope this makes sense so far. In my next post I’ll talk about how Minstrel‘s transformations operate, about the kinds of stories that result, and about some further context that may be helpful as we seek to understand these two systems.