Transcript A Genetic Algorithm Approach to Interactive

A Genetic Algorithm Approach To
Interactive Narrative Generation
TeongJoo Ong and John Leggett
Texas A&M University
Introduction



Stories are used to convey information, cultural
values, and experiences
New technologies have constantly provided
increasingly sophisticated means to tell stories
Recent trend is the convergence of technology,
entertainment, and art in the computer
Background


Interactive storytelling is a major research area
Many overlapping approaches have been used:

AI community (Narrative intelligence):





Immersive storytelling
Emergent storytelling
Plot-based systems
Interactive authoring of stories
Character-based systems
Background (cont.)

Hypertext community:
Hypertext narratives
 Adaptive hypermedia
 Sculptural hypertext


Partial listing of related work from these areas:
CHOROS (N. M. Sgouros)
 Façade (M. Mataes, A. Stern)
 Card Shark and Storyspace (M. Bernstein)
 Metalinear Cinematic Narrative (K.M. Brooks)
 StoryBeads (B. Barry)

Motivation





The HEFTI storytelling engine attempts to merge
results and ideas from both communities
Recombination, mutation, selection of authored
story elements with Genetic Algorithm (GA)
Generate, remove and traverse links in the story
elements as the story unfolds using the author’s
predefined rules
Story elements and rules are encoded in XML
Provides a small drag-and-drop tool and tree-view
tools for authors to create their stories
Definitions




Story elements – Smallest units in HEFTI’s
story search space
Story template – Describes combinations of
various story elements at a particular stage in
the story
Template sequences – Subdivision of story
template to depict time-based relationships
among story elements
Story component – Combination of story
elements, agent scripts and variables generated
by HEFTI based on the given set of story
templates and elements
Generating a Story




A story is divided into multiple time steps
Chromosomes represent a story component
Genes represent a collection of story elements
pertaining to a template sequence within a story
template
Genes are encoded as floating point numbers for
convenience of manipulation (as shown later)
Generating a Story (cont.)



A gene is generated by constructing valid story
element sets based on the current state of the
story and various conditions and rules imposed
by the author (Encoding)
The encoding process is sequential due to
dependencies and ordering of story elements
The encoding process is repeated several times
to generate individuals in the GA population
Generating a Story (cont.)



After the evolution process, the decoding
process steps through each of the genes,
decoding each gene based on its story context
The end result is a story component that
describes the next story sequence
The process is repeated to generate subsequent
story sequences
Generating a Story (cont.)
Operations on Story Components


The original genetic operators are modified to
handle authored ordering of story elements
Chromosome level operators:
Single point crossover
 Multi point crossover


Gene level operators:
Crossover operators
 Mutation

Chromosome Operators
Chosen offsets for multipoint crossover


Chromosome A
…
…
Chromosome B
…
…
Chromosome A*
…
…
Chromosome B*
…
…
The offsets are chosen to share similar starting
conditions and consequences
The operator generates permutations of the
template sequences
Chromosome Operators (cont.)

An example from The Three Little Pigs …

Given two chromosomes (A and B) with:
Starting conditions:
Wolf shows up in front of Angela Pig’s house
Consequences:
Wolf eats Angela Pig

If the state of the story is the same for both, the
intermediary stages can be swapped between A and B
Gene Operators
Gene A*
(After
mutation)
1
3


…
…
Gene A
(Before
mutation)
1
Chosen offset
for mutation
1
6
6
4
4
…
…

Alter selection of story elements
Crossover operators are the same
as at the chromosome level
except they crossover story
elements instead of genes
Mutation operator changes the
offset into a list of possible story
elements
Story Threads


Authors create potential story threads
Story thread is an indicator for:
1.
2.
3.
4.
5.
Length of story
Choice of story elements from a story template
Sets of story templates to be used at certain story
time steps
Rules that change the flow of the story
Evaluation criteria for chromosome fitness
Fitness Evaluation




HEFTI is free to generate stories that adhere only so
closely (within a threshold) to a story thread
Fitness evaluation takes place on the chromosomes
of a story thread
Authors can indicate preference, indifference, or
dislike towards certain story elements by assigning
positive or negative values to the story elements
The existence of certain story elements in story
components are influenced accordingly through the
selection mechanisms of GA
Story Thread with
Fitness Evaluation
<timestep order="4" name="wolf's plan"
loop="{isPigStillAvailable.value} == true
AND {isWolfDead.value} == false">
<set type="wolf's plan" >
<element name="act_13" addfitness="0.8"/>
</set>
</timestep>
Scenarios of Use



Interactive fiction: A murder mystery with
multiple dynamically generated story threads
Sub-module of a computer game engine that
dynamically combines various story and agent
scripts from existing story elements
An educational environment that can present
new concepts in various forms while preserving
the goals of the story
Conclusions




HEFTI needs a large enough set of story
elements and templates for it to create the story
components
Authoring a story from scratch can be tedious
Story templates allow authors to create story
elements at different granularities
Story elements can be reused in similar story
settings
Future Work



Genetic programming might be used to generate
agent scripts given the starting and ending agent
actions
Evaluation of fitness data on all of the story
variants that HEFTI is capable of generating
Better support for user interaction and control
of the story