MEXICA-Impro: a Computational Model for Narrative
Improvisation
Rafael Pérez y Pérez, Santiago Negrete, Eduardo Peñalosa, Rafael Ávila, Vicente
Castellanos, Christian Lemaitre
División de Ciencias de la Comunicación y Diseño
Universidad Autónoma Metropolitana - Unidad Cuajimalpa
México
{ rperez, snegrete, eduardop, ravila, vcastellanos,
clemaitre}@correo.cua.uam.mx
Abstract.
This paper describes a system that dynamically generate narratives through
improvisation. MEXICA-impro is based on a cognitive account of the creative
process called engagement-reflection. Its architecture defines a framework
where two agents participate in a simulated improvisation session to generate
the plot of a story in which each one draws knowledge from two different
databases representing cultural backgrounds. A worked example is explained in
detail to show how this approach produces novel stories that could not be
generated before.
1 Introduction
Storytelling has a relatively long history in computational creativity research.
Some well known models of storytelling include: TALESPIN (Meehan 1981),
MINSTREL (Turner 1994), FABULIST (Riedl 2004). Improvisation is a means by
which creativity can be exercised in storytelling. Two or more participants (agents)
intervene in a session where each contributes pieces of stories that are combined with
those of the others as time passes, until a whole story is constructed. The intervention
of each individual agent in the process, with a certain degree of unexpectedness and a
personal point of view, makes the whole process interesting and different from a
creative process where only one agent participates.
Once several agents participate in a process where their beliefs (rules) are tested by
exposure to those of other agents, we enter the realm of social interaction. Here, the
notion of creativity acquires a new meaning, namely the creative process is seen as a
social process where a cultural clash might result in something new for both
originators. The interaction among computational agents represents a metaphor of the
processes of communication in a socio-cultural context, given that, when under
controlled observation and with clear parameters, we can shed light on the
understanding that characterizes the starting up of human systems of meaning.
90
Social cognition processes have an especially important role in a model such as
MEXICA-Impro. We identify some important components of this kind influencing
the collaborative improvisation of narratives. We consider three important elements of
social cognition in our model: 1) communication resources, including the
understanding of symbolic systems such as languages and key meanings facilitating
mutual comprehension (Clark & Brennan, 1991); 2) availability of pieces of
knowledge shared by agents, such as concepts, principles, procedures or strategies,
conforming a convergent (shared) knowledge base in the agents’ minds (Jeong & Chi,
2007), and 3) multiple perspectives, including an amount of divergent knowledge
pieces (not shared by agents), leading to flexible ways of analyzing the same
phenomena.
In a creative collaborative goal such as constructing narratives, the agents: first,
interact and generate a common ground, or mutual understanding space, while
directing their efforts to achieve a common goal; second, in order to construct new
stories, they rely on their common knowledge base, which should contain the minimal
knowledge schemas or mental models to allow discussing the topics under analysis;
and finally, according to cognitive flexibility theory (Scott, 1962), they make
associations from multiple representations of the same information, such as their own
representations compared to other agent’s ideas of the same phenomenon, a process
allowing the mental scaffolding necessary to consider novel applications of
knowledge, or the emergence of new ideas.
There needs to be a balance between what both agents know (common knowledge)
and what they know individually (unique knowledge) to construct creative stories:
when both agents’ knowledge bases share an important amount of knowledge pieces,
the plots generated by both agents are very similar; otherwise, when agents have an
important amount of divergent pieces of knowledge, plots generated by both agents
would be completely different (Jeong & Chi, 2007).
2 MEXICA-impro: a computer model of narrative
improvisation
Mexica (Pérez y Pérez & Sharples 2001, 2004) is a computational model of
plot generation on top of which our system is built. It was inspired by the
engagement-reflection (E-R) cognitive account of writing as creative design (Sharples
1999). So, MEXICA-impro is a computer model of narrative improvisation. It is
formed by two mexica agents working together to develop as a team a story plot.
Agent 1 is also called the leader, and agent 2 is also called the follower. The leader
starts the improvisation and decides when it finishes (although in future versions both
should be able to decide when to finish). The leader generates material through one
complete E-R cycle and then cues the follower to continue the narrative. Then the
follower takes the material generated so far and progress the story through one
complete E-R cycle and then cues the leader to continue the narrative, and so on.
Each agent in MEXICA-impro is formed by two main modules: the
construction of knowledge structures (the K-S module) and the generation of plots
through engagement-reflection cycles (the E-R module). The K-S module takes as
input two text files defined by the user: a dictionary of valid story-actions and a set of
91
stories known as Previous Stories. The dictionary of story-actions includes the names
of all actions that can be performed by a character within a narrative along with a list
of preconditions and post conditions for each. The Previous Stories are sequences of
story actions that represent well-formed narratives. With this information the system
builds its knowledge base with structures known as atoms. Atoms represent (in terms
of emotional links and tensions between characters) potential situations that can
happen in the story-world and have associated a set of possible actions to be
performed when that situation occurs. For example, an atom might represent the
situation where a knight is in love with the princess, and it might have associated the
action “the knight buys flowers to the princess” as a possible action to be performed
by the lover. In MEXICA-impro each agent has different story-actions and/or
different set of previous stories. Thus, the same situation might lead each agent to
perform different actions.
The E-R module takes two main inputs: the knowledge-base and an initial
story-action provided by the user of the system (e. g., the princess heals jaguar knight)
that sets in motion the E-R cycle. During engagement, an agent generates sequences
of actions guided by rhetorical and content constraints; during reflection, the agent
breaks impasses, evaluates, and, if necessary, modifies the material generated so far.
It works as follows: the system starts in engagement; the post conditions of the initial
action are triggered, generating a story-world context; the story-world context is
employed as cue to probe memory and match an atom; then, the system retrieves the
actions associated to the atom, selects one at random and updates the story-world
context; After that, the engagement cycle starts again; the system attempts to match
an atom that is equal to the current story-world context; if it fails the agent looks for
an atom that is similar to the current story-world context; after generating three
actions (this number can be modified by the user), the system switches to reflection.
During reflection the system verifies that all actions’ preconditions are satisfied; if it
is necessary, the agent inserts actions to satisfy them; then, it evaluates the material
generated so far. At this point, a E-R cycle ends.
3 Generating narratives via improvisation
The MEXICA-impro project has an important goal: the stories generated by the
collaborative agents cannot be developed by any one of them alone. If, furthermore,
the story produced by the collaborative agents cannot be found within their
knowledge bases, we refer to it as a collectively-creative story. Collectively-creative
narratives are produced by providing each of our agents with different computational
representations of culture, experience (knowledge-base) and personality. Let us
elaborate this idea. For example, when one talks about knowledge bases in the context
of the MEXICA-impro project, it is possible to describe at least three possible
situations. The first one has to do with providing both agents with the same
knowledge base. In this case the stories generated by them cannot be classified as
collectively-creative because each agent can develop the same story alone. The
second one consists of providing both agents with completely different knowledge
bases. In this case we might be able to produce collectively-creative stories; however,
92
there is a high risk that our agents cannot progress the story as a team due to the lack
of shared experiences. The third possibility involves providing both agents with
partially different knowledge bases. In this case, we expect to produce collectivelycreative
stories through a fluid collaboration between agents. This is the case we are
interested in. In this paper we report some tests that we have performed employing
partially different knowledge-bases. There are several issues related to dissimilar
knowledge bases that should be discussed: how the dissimilarity between two
knowledge bases can be measured? What is the best ratio similarity/dissimilarity
between two knowledge bases to generate the best collectively-creative stories? And
so on. However, due to space limitations, in this document we focus exclusively on
explaining the core characteristics of our examples.
As explained earlier, the knowledge base is built from the dictionary of storyactions
and the set of previous stories. For this example, both agents employ the same
actions; only the previous stories are different. From now onwards, the file of
previous stories of agent 1 will be referred to as PH1 and the file of previous stories of
agent 2 will be referred to as PH2. PH1 includes seven previous stories; PH2 includes
six previous stories. Each story in PH1 shares a similar plot with at least one story in
PH2. Sometimes they are very similar and sometimes they only share few elements.
Tensions between characters
0 1 2 3 4 5 6 7 8
0 1-0
1 1-1-(2) 1-0 1-0-(1)
2 2-2-(1) 1-2 1-1 1-0 1-1
3 1-2-(1) 3-1 2-1 0-1 0-1 1-0 1-0
4 1-0 2-2 3-4 2-0 0-1 1-1 0-1 0-1 0-1
5 0-1 0-2(1) 0-2 2-3 1-0 1-0 0-1
6 0-1 0-3 1-0 0-1-(1) 1-2
7 1-1 1-0 1-0 0-1 0-1 0-1
8 1-0 0-1 (1) (1) 1-0 1-0 1-0
Emotional Links
Figure 1. Partial map of atoms. The first digit in each cell indicates the
numbers of atoms in the knowledge base of agent 1; the second digit indicates the
numbers of atoms in the knowledge base of agent 2; numbers in parentheses
indicate the shared atoms.
For example, story four in PH1 and story three in PH2 only differ in their first
action; the rest of the actions and the characters participating in the story are alike.
However, story one in PH1 only shares few actions with story 1 in PH2. The
knowledge bases built from PH1 and PH2 are partially represented in figure 1(for
reasons of space we only show half of the map). This map allows comparing each
93
agent’s atoms in terms of the number of components it has. All atoms are comprised
by emotional links and tensions between characters (see Pérez y Pérez 2007 for
details on how atoms are built). The horizontal axis indicates the number of tensions
and the vertical axis indicates the number of emotional links that each atom contains.
Each entrance in the map has figures that indicate the number of atoms in that
position. The first digit in each cell indicates the number of atoms that belong to the
knowledge base of agent 1; the second digit in each cell indicates the number of
atoms that belongs to the knowledge base of agent 2; numbers in parentheses indicate
those atoms that are equal in both knowledge bases. For example, the position (0
tensions, 2 emotions) shows that both agents share one identical atom, and that each
agent has 2 unique atoms. As the reader can observe, agent 1 and agent 2 only share
nine identical atoms. Those atoms located in the same position or located close to
each other in the map share some characteristics; therefore, they are similar but no
identical. Finally, we have few atoms that are very different to the rest. In this way,
we are able to have two knowledge bases that are similar but not identical.
4 A story generated by MEXICA-impro
MEXICA-impro is set to produce three actions during engagement and then switch
to reflection. From now on agent 1 is referred to as the leader and agent 2 is referred
to as the follower. The user provides the following first action:
(0) princess cured jaguar knight
The number on the left indicates that this action was produced at Time = 0. The
leader starts an E-R cycle; during engagement the following actions are retrieved
from memory:
(0) princess cured jaguar knight
(1) enemy kidnapped princess
(2) enemy attacked princess
(3) jaguar knight looked for and found enemy
At time = 1 the enemy kidnaps the princes, at time = 2 the enemy attacks her and at
time = 3 the knight decides to look for the enemy. Now, the leader switches to
reflection.
(4) jaguar knight is introduced in the story
(5) princess is introduced in the story
(7) hunter is introduced in the story
(9) hunter tried to hug and kiss jaguar knight
(8) jaguar knight decided to exile hunter
(10) hunter went back to Texcoco Lake
(6) hunter wounded jaguar knight
(0) princess cured jaguar knight
(1) enemy kidnapped princess
(11) enemy got intensely jealous of princess
94
(2) enemy attacked princess
(3) jaguar knight looked for and found enemy
The system introduces the princess and the jaguar knight into the story. Then, the
system requires to justify why the princess healed the knight and inserts the action
where the hunter injured the knight at time = 6. Since there is a new actor, the system
introduces the hunter into the story (time = 7). The leader now requires to justify why
the hunter wounded the knight; so, it inserts the action where the knight exiled the
hunter (time = 8). Why did the knight do that? Because the hunter attempted an
excessive demonstration of love on the knight (time = 9). However, because the
hunter was exiled, it changed his position inside the story-world. Therefore, in order
to wound the knight, first it had to move back to the lake (where the knight is
located). The system detects this situation and moves back the hunter to the Texcoco
Lake (Time = 10). Finally, MEXICA-impro requires justifying why the enemy
decided to attack the princess. So, it inserts action at time = 11. At this point, all
preconditions are satisfied and the leader ends its first E-R cycle and cues the follower
to continue the story.
The follower starts its E-R cycle and during engagement generates two actions:
(12) jaguar knight had an accident
(13) enemy decided to sacrifice jaguar knight
So, after the knight finds the enemy the follower continues the story inserting an
action where the knight suffered an accident (time = 12) and the enemy decides to kill
him (time = 13). The follower cannot match an atom in memory to continue the story
and an impasse is declared. Thus, the system switches o reflection.
Jaguar knight is introduced in the story
princess is introduced in the story
hunter is introduced in the story
hunter tried to hug and kiss jaguar knight
jaguar knight decided to exile hunter
hunter went back to Texcoco Lake
hunter wounded jaguar knight
princess cured jaguar knight
enemy kidnapped princess
enemy got intensely jealous of princess
enemy attacked princess
jaguar knight looked for and found enemy
(12) jaguar knight had an accident
(13) enemy decided to sacrifice jaguar knight
(14) hunter found by accident jaguar knight (breaking
impasse)
All preconditions are satisfied, so the system inserts at the end of the story in
progress the action where the hunter found accidentally the knight (time = 14) to try
to break the impasse. The E-R cycle ends and the follower cues the leader to continue
the story.
95
The leader attempts to match an atom in memory; however, it fails and an impasse
is declared. This is not surprising because none of the leader’s previous histories
includes a scene where a hero goes to rescue a victim and instead suffers an accident.
Now the leader switches to reflection. All preconditions are fulfilled and the system
inserts the action where the hunter killed the knight to try to break the impasse.
(15) hunter killed jaguar knight (breaking impasse)
This produces an interesting situation. One would expect that the enemy killed the
knight; however, the hunter, who hated the knight, is reintroduced in the story and
performs the murder. There is not a similar precedent in the previous stories of both
agents. The leader cues the follower to continue the story.
The follower tries to match an atom but again an impasse is declared during
engagement; the system switches to reflection to try to break the impasse and inserts
the action where the hunter killed himself.
(16) hunter committed suicide (breaking impasse)
The follower evaluates the story in progress and decides that the story is
completed. So, the follower cues the leader to continue the story and informs the
leader about its decision of finishing the story.
The leader receives the information and nevertheless tries to advance the story.
During engagement it cannot match an atom in memory and an impasse is declared.
During reflection it cannot break the impasse. So, the leader decides to finish the
story. This is the plot that both agents built together:
*** Final Story
(4) jaguar knight is introduced in the story (l)
(5) princess is introduced in the story (l)
(7) hunter is introduced in the story (l)
(9) hunter tried to hug and kiss jaguar knight (l)
(8) jaguar knight decided to exile hunter (l)
(10) hunter went back to Texcoco Lake (l)
(6) hunter wounded jaguar knight (l)
(0) princess cured jaguar knight
(1) enemy kidnapped princess (l)
(11) enemy got intensely jealous of princess (l)
(2) enemy attacked princess (l)
(3) jaguar knight looked for and found enemy (l)
(12) jaguar knight had an accident (f)
(13) enemy decided to sacrifice jaguar knight (f)
(14) hunter found by accident jaguar knight (f)
(15) hunter killed jaguar knight (l)
(16) hunter committed suicide (f)
What makes this story original is its conclusion: a hero goes to rescue a victim but
instead suffers an accident that leads to his murder, not by the enemy, but by an old
96
resented rival that suddenly is reintroduced in the plot. There is no similar story in
either PH1 or PH2.
The letter on the right side indicates if the action was generated by the leader (l) or
by the follower (f). Actions in italics were generated during reflection. In this example
the leader performed three E-R cycles while the follower performed two. The leader
contributed with 12 actions while the follower contributed with 4. This difference
arouse because the initial action provided by the user required that the leader inserted
several actions during reflection to satisfy preconditions. During its first E-R cycle the
leader produced 11 actions; so, almost its whole contribution to the narrative was
generated during its first participation (i.e. during its first E-R cycle). During its
second participation the leader inserted one action to try to break an impasse and
during its final participation the leader was not able to contribute to the story. The
follower contributed with three actions during its first participation and with one
during its final participation. Both agents were able to generate more actions during
its first E-R cycle because as the narrative unravelled the story-context became more
complex and novel and it was more difficult to match an atom. The sequence of
actions generated by the leader during its first participation (actions time = 1 to 11)
produced a context that was novel to both the leader and the follower. That is, neither
the leader’s knowledge-base nor the follower’s knowledge-base contained an atom
that was equal to the current story-world context. This novelty arouse as a result of
the heuristics employed to satisfy preconditions. The production of novel contexts is a
normal and necessary situation when MEXICA generates stories: novel contexts arise
and MEXICA looks for atoms similar to the current story-world context and then
retrieves its associated actions to unravel the narrative in progress. In this way
MEXICA is able to create novel narratives. However, in MEXICA-impro the follower
receives unknown material (in this case produced by the leader) that must be
progressed coherently: the actions chosen to continue the story must connect with the
previous ones, the relation between characters must be kept, and so on. This is a
difficult task. The E-R model provides the necessary elements to achieve this goal.
We hypothesized that if the knowledge bases of the two agents were similar
enough, the agents would interact without problems. However, in this case, the
sequence of actions generated at times 1 to 11 produces a novel context for both
agents. This characteristic is positive because the system is generating original
situations to push the story forward instead of just copying the content of its
knowledge base. However, if the context is “too novel”, the system is not capable of
matching an atom in memory and an impasse is declared. In this case, the follower
was able to retrieve an action during engagement to continue the narrative. Due to
lack of space, it is not possible to explain the details of how the follower matched the
atom and retrieved the action at time 12. But it is important to mention that the atom
matched only satisfied the minimum requirements to be considered similar to the
current story context. That is, because the context was pretty novel the follower was
close to declaring an impasse. Nevertheless, agent 2 was able to continue the story.
Would the leader be able to match an atom employing the same story-context? This
question leads to a more important question: would the leader be able to generate the
same story alone? In order to answer these questions we ran a second test. We forced
agent 1 to generate exactly the same initial first 11 actions and see if it could continue
97
the story alone. The result was that, after generating again the first eleven actions,
agent 1 was not capable of matching any atom in memory. Thus, an impasse was
declared and the system switched to reflection to try to break the impasse. Employing
the heuristics designed for this purpose, the system inserted an action where Jaguar
Knight made the enemy a prisoner. Then, the system considered that the story was
completed and decided to finish it. In this way, the story generated alone by agent 1 is
shorter and its conclusion is not as original as the conclusion in the story generated by
both agents (one could easily expect that the knight would make the enemy a
prisoner). Because its knowledge base does not include the necessary knowledge, the
leader could never produce alone the same tale produced by MEXICA-impro.
Would agent 2 be capable of generating alone the first same 11 actions and then
continue the story? To answer this question we attempted to forced agent 2 to produce
the same initial sequence of actions. However, the content of its knowledge base
made it impossible. Agent 2 could not come out with the proposal that, after the
princess cured the knight, something logical to happen was that the enemy kidnapped
her. Thus, this agent could not generate the desired sequence of actions.
As mentioned earlier, collectively-creative narratives are produced by providing
each of our agents with different computational representations of culture, experience
and personality. In our current version of MEXICA-impro, these characteristics are
represented in the system’s knowledge base. This way, because the story produced by
MEXICA-impro is novel and could not be produced by any of the agents alone, we
consider it as a collectively-creative narrative. This is a nice example of how the
cooperation between both agents allowed producing a novel story.
5 Conclusions
MEXICA and other systems have explored in the past how narratives can be
created automatically according to different cognitive models and ideas. MEXICA
has been successful in representing in computer terms the engagement-reflection
account of the human creative process, especially through its capability to ‘reflect’
about partial stories and adjust generation cycles thereafter. One of the main
characteristics of creativity, however, one accounted for by many authors (e.g. Boden,
1990), is that products of the process need to be novel to a community, either in a
particular group, or in society at large. This particular constraint for some product to
be deemed ‘creative’, takes the problem of building models and systems of creative
processes into the realm of the social: not only the outcomes need to be sound and
interesting but also new to the community. Creative agents then, need to take into
account the community’s knowledge when trying to come up with something new.
Our project explores an approach to creativity, namely the use of improvisation in
story generation as a metaphor of social reproduction. We believe that creativity is
achieved by confronting established local (or global) lore with new, different
knowledge and practice. Improvisation is a well known creative experimental medium
where two or more different worlds collide in an organised environment to establish
the ground for innovative, amusing and relevant knowledge, art work or otherwise.
MEXICA-impro has provided a good starting point for our endeavour since it allows
98
us to redefine the creative process as a dialog between two improvising agents that
draw their information from different databases considered as cultural contexts for
different cultures. From the methodological point of view, our project establishes
right from the onset a multidisciplinary approach to a multidisciplinary subject. What
creativity is and how it can be modelled and studied can only be investigated by
involving all the relevant disciplines. Our system possesses an architecture that
provides all members of the group with a clear knowledge of all the relevant
mechanisms and parameters at stake, in such a way that everyone can participate
almost right from the start in discussions about future design and experiments.
MEXICA-impro simulates the interaction between two agents with separate
cultural backgrounds. The resulting system has become an experimental zone at the
crossroad of several disciplines. The members of the group developing it come from
backgrounds as diverse as A.I., Film Studies, Sociology and Psychology. We believe
that we, ourselves, have set out in an engagement-reflection journey to explore in a
multidisciplinary way the possibilities of creativity.
<references_biblio/>
6 References
Boden, Margaret. The Creative Mind. Abacus. London, U.K. 1990, p32.
Clark, H. H., & Brennan, S. A. (1991). Grounding in communication. In: Resnick, L.B., J.M.
Levine, and S.D. Teasley (Eds.). Perspectives on socially shared cognition. Washington:
APA Books.
Jeong, H., & Chi, M. T. H. (2007). Knowledge convergence and collaborative learning.
Instructional Science, 35, 287-315.
Meehan, J. (1981). Tale-spin. In R. C. Shank & C. K. Riesbeck (Eds.), Inside computer
understanding: Five programs plus miniatures. Hillsdale, NJ: Erlbaum Press
Pérez y Pérez, R. (2007). Employing Emotions to Drive Plot Generation in a Computer-Based
Storyteller. Cognitive Systems Research. Vol. 8, number 2, pp. 89-109. DOI information:
10.1016/j.cogsys.2006.10.001
Pérez y Pérez, R. & Sharples, M. (2004) Three Computer-Based Models of Storytelling:
BRUTUS, MINSTREL and MEXICA. Knowledge Based Systems Journal. Vol. 17, number
1, pp. 15-29.
Pérez y Pérez, R. & Sharples, M. (2001) MEXICA: a computer model of a cognitive account
of creative writing. Journal of Experimental and Theoretical Artificial Intelligence. Volume
13, number 2, pp. 119-139.
Riedl, M. (2004). Narrative planning: balancing plot and character. Ph.D. dissertation,
Department of Computer Science, North Carolina State University, Raleigh, NC
Scott, W. (1962). Cognitive Complexity and Cognitive Flexibility. Sociometry, 25 (4), 405-414
Sharples, M. (1999). How we write? Writing as creative design. London: Routledge.
Turner, S. R. (1994). The creative process: A computer model of storytelling. Hillsdale, NJ:
Lawrence Erlbaum Associates.
99