Planning for Individualized Experiences with Quest-Centric Game
Adaptation
Boyang Li and Mark O. Riedl
School of Interactive Computing
Georgia Institute of Technology, Atlanta, GA, USA
boyangli@gatech.edu, riedl@gatech.edu
Abstract
Planning has been extensively used to build competent
opponents in games for human players. In this paper, we
focus not on winning strategies but on creating an enjoyable
overall gaming experience by adapting human-authored
game narratives and customizing them to the players’
motivation, tastes and needs. We discuss the benefits of
modeling game narratives as plans and analyze causal
structures to build novel computational models of narrative
coherence. A planning approach to the narrative adaptation
problem is presented. The planner takes a complete
storyline comprised of several quests and iteratively
searches for modifications, deleting and inserting quests and
events, until it meets the user’s preferences. A user study
strongly suggested the proposed notion of narrative
coherence has positive influences on story aesthetics.
Introduction
Much research efforts on planning in games have been
devoted to creating competent opponents that win as much
as possible for human players. Various planning techniques
have been applied in the context of real-time and turn-
based strategy games (Chung, Buro, and Schaeffer 2005;
Sánchez-Ruiz et al. 2007; Balla and Fern 2009), first-
person shooters (Orkin 200), and contract bridge (Smith,
Nau, and Throop 1998), to name just a few. These works
focused on planning strategies for an AI player, and have
achieved success to some extent.
However, relatively few works have focused on
optimizing gaming experience of players. As pointed out
by Roberts, Riedl and Isbell (2009), the player’s overall
experience may be more important than the expected
payoff. For instance, a hard-fought battle that is lost may
be more fulfilling than an easy victory. One aspect of the
overall experience of the player is the perception of
narrative arc, which can be dynamically generated or
adapted with planning techniques.
Indeed, the narrative arc is a crucial aspect of most
modern computer games. Game designers use a storyline
to lead players through dramatically engaging sequences of
events. Role-playing games and other types of
contemporary video games usually consist of a series of
challenges, or quests, that a player is asked to complete.
Rollings and Adams (2003) define gameplay as “one or
more causally linked series of challenges in a simulated
environment.” To overcome these challenges, players have
to perform required gaming activities, such as combat or
puzzle-solving, in a virtual world. The story elements
provide motivation, set contexts for gaming activities, and
propel the game narrative forward. In short, game
storylines are used to plan for player experience.
We suggest that optimization of player’s experience
consists of presenting the right story to the right person at
the right time. The significance of this claim is twofold.
Firstly, game players usually possess diverse motivation,
tastes, and needs (Crawford 1984; Yee 2006). A one-size-
fits-all script might not be ideal. Secondly, the preferences
of players can change over time. After playing one story,
they may demand a new one. Therefore, the ability to
generate different stories may enhance replayability and
improve player experience. Finally, by addressing the first
two implications, we are working toward the potential of
games that continuously grow and change with the player
over a long period of time.
As the cost of labor to write individualized storylines can
be prohibitively expensive, AI technologies, specifically
planning, can be used to plan for player experience by
dynamically generating or adapting storylines in games. In
this paper, we concern ourselves with the problem of
customizing game narratives for role-playing games while
simultaneously maintaining the quality of the aggregated
storyline. We acknowledge that computer systems are not
capable of the same levels of creativity as humans.
Consequently, we aim to automatically adapt human-
authored game narratives, thereby leveraging human
authoring skills and creativity while at the same time
scaling up the ability to deliver unique, customized game
experience to individual players.
In this paper, we justify our stance of representing game
narratives as plans, and discuss the notion of narrative
coherence as heuristic features of the plan structure. We
then present a technique to adapt and customize human-
authored game narratives consisting of game quests. A
refinement search algorithm is used to iteratively modify a
pre-existing storyline plan until it more closely matches the
motivation, tastes, and needs of the target user. Our system
is capable of (1) generating a large variety of quest
combinations to suit the need of each individual player and
enhance re-playability (2) maintaining story quality by
maintaining narrative coherence in addition to soundness
and (3) balancing the preservation of the original stories
and the adaptation to leverage human creativity. The
storyline is adapted by adding, deleting or replacing quests.
In addition, quests themselves can be altered in content and
structure to fit the aggregated storyline.
The remainder of the paper is organized as follows: We
discuss the theoretical aspects about narratives, the
adaptation problem and the notion of narrative coherence
in the next section. After that, we deal with the practical
side of narrative adaptation and present the planning
algorithm and a detailed example. The fifth section
analyzes the theoretical authorial leverage our system
empowers game designers with. The last section concludes
this paper.
Planning and Narrative
We focus on the narrative aspect of experience, a sequence
of events with continuant subject and that constitutes a
whole (Prince 1987). In the case of our work, the narrative
is a description of the expected sequence of events that will
occur in a virtual environment. Following others (c.f.,
Young 1999; Riedl and Young 2004; Riedl 2009), we
computationally represent narratives as a plan. The plan
representation provides a formal framework to explicitly
represent causal relationships between events and reason
about them on first principles (for example, we can ask if a
narrative is sound). Further, plans closely resemble
cognitive models of narrative. Graesser et al. (1991) and
Trabasso and van den Broek (1985) in particular highlight
the importance of causalities in stories.
Cognitive science and neuroscience suggests that
planning may be a very appropriate computational means
for narratives. Young and Saver (2001) note that
dorsolateral prefrontal injuries simultaneously impair
behavioral planning and the ability to produce “narrative
account of their experience, wishes and actions” while
many other cognitive abilities remain intact. This
coincidence seems to hint on the functional similarity of
planning and narrative generation in the human brain.
Rattermann et al. (2001) suggested adult human performs
planning in an analogous manner to partial-order planning.
In summary, planning, especially partial-order planning,
seems to bear some resemblance to narrative processing
and generation mechanisms utilized by human beings.
Given the above evidence, we represent narrative as
partially ordered plans. A partial-order plan consists of
actions and temporal and causal relations. Actions encode
preconditions – conditions that must be true for the action
to be executable – and effects – conditions that become
true once the action completes. Causal links, denoted
a
1
→
c
a
2
, indicate that the effects of action a
1
establish a
condition c in the world necessary for action a
2
to execute.
Temporal links indicate ordering constraints between
actions.
We use additional representational structure provided by
decompositional partial order planning (DPOP) (Young
and Pollack 1994). In DPOP, abstract actions are
decomposed into more primitive actions using
decomposition recipes. Figure 1 is an example of nested
decomposition recipes. Rounded rectangles are abstract
actions and ordinary rectangles are primitive actions.
Encapsulation represents decomposition recipes and
arrows represent causal links. For clarity, no temporal links
are shown. Primitive actions outside the decompositions
are not part of the definition of the decomposition recipe,
but are necessary for causal soundness.
The Narrative Adaptation Problem
The conventional planning problem is to find a sound
sequence of actions that transforms the world from an
initial state into one that satisfies a goal situation. The
soundness guarantees correct execution in the absence of
uncertainty. The narrative generation problem, in
comparison, can be defined as finding a sound and
coherent sequence of events that narrates the
transformation of the world, which involves events, or
sequences of events, of significant interest to the audience.
Narrative generation contrasts with conventional planning
in that the entire experience replaces the final outcome as
the primary concern. For example, a tragedy or thriller
relies more on relationships between actions in the
narrative plan and less on its outcome.
This paper deals with a problem that is slightly different:
the adaptation of narratives. Instead of generating a
narrative from scratch, adaptation starts with a sound and
coherent narrative and modifies it to meet the user’s
requirements. In this paper, we start with a human-
authored game narrative. Our algorithm preserves as much
as the original narrative as possible to minimize the chance
any handcrafted aesthetic or intuitive elements are broken
because the algorithm is incapable of understanding them.
Quest-centric game adaptation applied narrative
adaptation to computer games in which the main storyline
is comprised of one or more challenges. Quests capture the
Figure 1 An Example Quest
d
r
F
a
i
n
N
W
o
g
o
m
t
o
n
t
h
c
m
s
r
s
c
e
o
s
s
s
t
h
o
s
p
C
o
t
h
h
r
e
o
i
n
H
t
o
r
i
n
D
i
n
s
d
e
r
d
ifferent types
r
ecipes. We
r
F
igure 1 show
s
a
nd an award,
w
n
to a larger st
o
N
arrative C
o
W
e believe pa
r
o
f stories. Ho
w
g
eared toward
s
o
r most effici
e
m
ost coherent
o
maintain the
Trabasso an
d
n
arrative cohe
r
h
e story. A
c
ontributes sig
n
m
ain outcome.
s
een as a di
r
r
epresented as
s
oundness is
a
c
hains back to
e
ach event has
o
utcome state.
s
tory flaws th
a
s
uperfluous e
ff
s
ound plan. T
h
h
e abstrac
t
ca
u
o
ther words, t
h
s
tory domain,
p
reconditions
a
C
ore Set. Firs
t
o
f special inte
r
h
an others. T
h
h
uman designe
r
evolve about
e
vents form th
e
o
n the applica
t
n
clude only
p
H
owever, dep
e
o
choose oth
e
r
epresent co
m
n
termediate g
o
D
ead Ends. A
n
n
a meaningf
u
s
e
t
. It is beli
e
d
irectly harms
e
xample, whe
n
r
ich, the event
Fi
g
u
r
of challenges
r
epresent que
s
s
a quest. Que
s
w
hich allows
q
o
ryline.
o
herence
r
tial-order pla
n
w
ever, conven
t
s
maximum e
f
e
nt sequence o
story. Therefo
coherence of
t
d
van den Bro
e
r
ence as a pro
p
narrative is
n
ificantly to t
h
On each hie
r
r
ected acyclic
vertices and c
a
chieved if al
l
the initial stat
e
at least one
e
In this sectio
n
a
t break narrat
i
ff
or
t
s. These
f
h
e definitions
o
u
sal structure
h
e flaws are
although the
y
a
nd effects of
a
t
, we suggest
t
r
est to the aud
h
e significance
rs and audien
c
and eventuall
y
e
core set of t
h
t
ion. In this p
a
p
ropositions i
n
e
nding on the
e
r events for
t
m
plex authori
a
o
als (Riedl 20
0
n
event is a de
a
u
l way to the
u
e
ved that the
the perceptio
n
n
the player is
i
where treasur
e
r
e 2 Schemati
c
in a library o
f
s
ts as decom
p
s
ts are decom
p
q
uests to be re
c
n
s are effectiv
e
t
ional plannin
g
f
ficiency wher
f actions is r
a
re, special car
e
t
he story gene
r
ek
(1985)
p
rop
p
erty of the ca
u
coherent wh
h
e causal ach
i
r
archical level
graph (DA
G
a
usal links as
l
p
recondition
s
e
, coherence i
s
e
ffect on a ca
u
n
, we distingu
i
i
ve coherence
:
f
laws can ha
p
o
f the two fla
w
and
p
erforme
r
d
efined indep
e
y
are depend
e
a
ctions are def
i
t
hat some eve
n
ience and are
of events can
c
e. Other even
t
y
lead to thes
e
h
e story. The
c
a
per, we defin
e
n
the goal st
a
circumstances
,
t
he core set.
F
a
l inten
t
a
p
0
9).
a
d end if it do
e
u
nfolding of e
v
presence of
d
n
of narrative
i
nterested in b
e
e
s are obtaine
d
c
of dead-end
f
decompositi
o
p
osition recipe
p
osed into a ta
s
c
onfigured to
f
e
representatio
n
g
algorithms a
r
eas the shorte
a
rely the best
o
e
must be tak
e
r
ated.
osed the idea
o
u
sal structure
o
en each eve
n
i
evement of t
h
, a
p
lan can
b
G
) with actio
n
edges. Where
a
s
are on caus
a
s
achieved wh
e
u
sal chain to t
h
i
sh two types
o
:
dead ends a
n
p
pen even in
w
s rely purely
o
r
s of actions.
I
e
nden
t
ly of t
h
e
nt on how t
h
i
ned.
n
ts in a story a
r
more importa
n
be perceived
b
t
s set context f
o
e
events. The
s
c
ore set depen
d
e
the core set
t
a
te of the
p
la
n
,
one may wa
n
F
or example,
t
p
lan may ha
v
e
s not cont
r
ibu
t
v
ents in the co
r
d
ead-end even
coherence. F
o
e
coming filthi
l
d
is crucial, a
n
events
o
n
s.
s
k
f
it
n
s
r
e
st
o
r
e
n
o
f
o
f
n
t
h
e
b
e
n
s
a
s
a
l
e
n
h
e
o
f
n
d
a
o
n
I
n
h
e
h
e
r
e
n
t
b
y
o
r,
s
e
d
s
t
o
n
.
n
t
t
o
v
e
t
e
r
e
ts
o
r
l
y
n
d
other
magi
c
then
t
Figur
e
end,
w
repre
s
dead
e
Fo
r
v ∈
V
only
p
reco
n
fact t
h
Give
n
defin
e
In ge
n
that t
h
storyl
i
Supe
r
coher
e
then
r
swor
d
drago
n
super
f
swor
d
(top)
s
p
urpo
(botto
that r
e
is re
q
p
erfo
r
Fo
r
super
f
• S
• t
h
s
u
e
d
• ¬
W
h
of th
e
heuri
s
chara
c
exha
u
impo
r
coher
e
coher
e
Fi
g
events should
c
sword that is
t
he event of o
b
e
2 for an illu
s
w
here a box
s
ents a causal
l
e
nds are labele
r
mally, in a s
t
V
represents e
v
if any effec
t
n
dition of ev
e
h
a
t
there is a
n
a core set S
C
e
d by:
∀
u
∈
V, v
∈
S
n
eral, it is reco
m
h
ere are no d
e
i
ne.
r
fluous Effo
e
nce occurs
w
r
estore world
s
d
to a strange
r
,
n
with i
t
.
T
f
luous if, befo
r
d
, no other eff
e
s
hows superfl
u
se other than
m) shows no
n
e
-establish co
n
q
uired that act
i
r
med by the sa
m
r
mally, a subs
e
f
luous effort i
f
is (weakly) c
o
h
e set of con
d
u
bset of the
s
d
ges.
∃a ∈V, (∃b, c
h
ereas, dead e
n
e
autho
r
, sup
e
s
tic guard agai
n
c
ters. The lis
t
u
stive, but th
e
r
tant and co
m
e
nce. We bel
i
e
nce is import
a
g
ure 3 Schem
a
non-su
p
be subordinat
not necessary
b
taining the s
w
s
tration of
t
he
represents a
n
l
ink. The initi
a
d.
t
ory DAG G
=
v
ents in the pl
a
t
of event u
e
nt v. We use
path from ve
r
⊆ V, the set
o
S
C
,
(
¬
p
ath(u,v
)
m
mended the
c
e
ad ends in th
e
rts. Another
w
hen even
t
s
u
s
tates. For ex
a
,
and then has
T
he action o
f
r
e the conditio
n
e
cts contribute
u
ous effort
b
e
c
re-establishin
n
-superfluous
e
n
dition p serve
i
ons in the s
u
m
e character.
e
t of vertices
S
f
o
nnecte
d
.
d
itions annota
t
s
et of conditi
o
∈ S, path(b,
a
n
ds prevent int
e
rfluous effor
t
n
st interferenc
e
t
of coherenc
e
e
two exam
p
m
plimentary
a
i
eve that the
p
a
nt for any typ
e
a
tic of superfl
u
p
erfluous effo
r
e. If the playe
for finding th
e
w
ord is a dea
d
causal struct
u
n
action and
a
l state, core
e
=
(V, E) whe
r
a
n and (u, v)
∈
satisfies at
path(u, v) to
r
tex u to vert
e
o
f dead end a
c
)
⇔ u ∈ S
D
)
c
ore set be de
s
e
original ha
n
b
reach of
u
nnecessarily
n
a
mple, the pla
y
to steal it bac
f
giving the
n
of the player
to the core s
e
c
ause the even
t
g condition p
e
ffort because
an additional
u
perfluous eff
o
S
⊆ V \{initial
,
t
ing outgoing
o
ns annotatin
g
a
)∧ path(a, c))
erference wit
h
t
s can
b
e co
n
e
with intenti
o
e
flaws is
b
y
p
les illustrate
a
spects of th
e
p
reservation o
e
of story ada
p
u
ous efforts (t
r
ts
(
bottom
)
.
r obtains a
e
treasures,
d
end. See
u
re of dead
an arrow
e
vents, and
r
e a vertex
∈
E if and
least one
denote the
e
x v in G.
c
tions S
D
is
(1)
s
igned such
n
d-authored
narrative
n
egate and
y
er gives a
k to slay a
sword is
having the
e
t. Figure 3
t
s serve no
. Figure 3
the events
purpose. It
o
rts are all
,
goal} is a
edges is a
g
incoming
h
intentions
n
sidered a
o
ns of story
no means
two very
e
narrative
f narrative
p
tation.
op) and
T
t
h
p
c
h
r
s
s
r
t
h
C
r
s
p
a
e
d
t
w
1
2
t
h
r
D
c
1
2
3
r
e
D
Plann
i
T
o optimize a
p
h
e main storyl
p
layer’s intere
s
c
an also produ
c
h
uman-crafted
r
eplayability.
s
ystem. The
s
toryline, a lib
r
r
equirements.
T
h
e player him
C
urrently, we
r
equirements.
Our storylin
e
s
earch for t
h
p
reconditions,
a
bstract action
s
e
ach flaw, a
c
d
oing so, deco
w
o assurances
1
) All abstr
a
actions.
2
) Preconditi
o
other acti
o
links are
n
causal cha
i
N
evertheles
s
h
e narrative a
d
r
etaining the
r
D
POP with th
e
c
apabilities (2-
3
1
) Modify pl
a
As playe
r
these requ
i
2
) Delete ev
e
links to a
p
to delete
q
longer nec
3
) Ensure n
a
technique
s
causal c
h
Narrative
c
on causal
outcomes.
The algori
t
r
epresent ques
t
e
xperience. D
e
D
eletion of ac
t
Fi
g
ure
4
i
n
g
Al
g
orit
h
p
layer’s exper
i
ine of the ga
m
s
ts, needs, an
d
c
e numerous
v
storylines, r
e
Figure 4 sh
game adapt
a
r
ary of quest
s
T
he player re
q
or herself or
allow playe
e
adaptation al
h
e sound p
elimina
t
es ca
u
s
until a sou
n
c
hoice from s
e
mpositional
pa
:
a
ct actions a
r
o
ns of action
s
o
ns or the ini
t
n
ot threatene
d
.
i
n beginning
w
s
, standard D
P
d
aptation prob
l
r
efinement se
a
e
following pr
e
3
):
a
n goals. Plan
r
s’ requireme
n
i
rements must
e
nts. While D
P
p
lan, the adap
q
uests and w
o
essary or that
c
a
rrative coher
e
s
only ensure
h
ains leading
c
oherence req
u
leading to
t
hm must d
e
t
s that are not
e
letion of ac
t
t
ions, followe
d
4
The Stor
y
lin
e
h
m for Ada
p
i
ence in a gam
m
e should be c
u
d
motivations.
I
ariations of a
f
e
sulting in g
r
o
ws the arc
h
a
tion process
s
tructures, an
d
q
uirements can
derived from
rs to directl
y
g
orithm exten
d
lan, DPOP
u
sal threats,
a
n
d plan is con
s
e
veral strategi
e
a
rtial order
p
l
a
r
e decompos
e
s
are satisfied
t
ial condition,
Indeed, ever
y
w
ith the initial
s
P
OP is not su
f
l
em as describ
e
a
rch paradig
m
e
processing st
e
goals reflect
a
n
ts change,
g
change accor
d
P
OP can only
tation algorit
h
o
rl
d
-level eve
n
c
ause the plan
n
e
nce. Conven
t
actions’ prec
o
back to th
e
u
ires that acti
o
important a
n
e
lete actions
desired as par
t
t
ions can ca
u
d
by addition
o
e
Adaptation
p
tation
e, we argue th
a
u
stomized to t
h
I
n doing so,
w
f
inite number
o
r
eatly improv
e
h
itecture of o
u
takes a ma
i
d
a set of play
e
be provided
b
a player mod
e
y
specify th
e
d
s DPOP. In t
h
satisfies op
e
a
nd decompos
e
s
tructed. To f
i
e
s is made.
B
a
nning provid
e
e
d to primiti
v
with effects
o
and the caus
a
y
action is on
s
tate.
f
ficient to sol
v
e
d above. Whi
l
m
, we empow
e
e
p (1) and ext
r
a
uthorial inte
n
g
oals satisfyi
n
d
ingly.
add actions a
n
h
m must be ab
l
n
ts that are
n
n
er to fail.
t
ional planni
n
o
nditions are
o
e
initial stat
e
o
ns’ effects a
r
n
d recognizab
l
because th
e
t
of the player
u
se dead en
d
o
f other actio
n
Pipeline
a
t
h
e
w
e
o
f
e
d
u
r
i
n
e
r
b
y
e
l.
e
ir
h
e
e
n
e
s
i
x
B
y
e
s
v
e
o
f
a
l
a
v
e
l
e
er
r
a
nt
.
n
g
n
d
l
e
n
o
n
g
o
n
e
.
r
e
l
e
e
y
’s
d
s.
n
s,
can r
effort
coher
e
Cu
s
modi
f
to the
quest
condi
t
goal
s
repair
satisf
y
effect
causi
n
p
lann
i
p
repr
o
De
l
p
rimi
t
simpl
y
order
i
then
a
delet
e
deco
m
deco
m
and d
deco
m
The a
d
evide
n
model
1. Te
r
p
lan i
s
2. Pla
n
flaw t
y
•
O
•
C
d
•
A
d
a
n
r
e
•
D
f
o
•
S
3. Re
c
esult in supe
r
must be perf
o
e
nce.
s
tomization o
f
f
ication of the
g
set of player
r
selection. W
h
t
ion quest‐
co
s
tate as a ques
t
ed, the quest
y
the goal. Wh
will be rem
o
n
g it to beco
m
i
ng. The go
a
o
cessing step
e
l
etion of event
s
t
ive event tha
t
y
removed al
o
i
ng constraints
a
ll other siblin
g
e
d and the pa
r
m
posed. The
r
m
position reci
p
eleting them
a
m
posed. If the
d
aptation algori
t
n
cing why the pl
a
consisting of u
n
r
mination If the
s
complete, retu
r
n
Refinement
C
y
pe:
O
pen Preconditi
o
Reusing an a
c
Adding a ne
w
Remove the
a
C
ausal Threat:
emotion, or del
e
A
bstract Acti
o
eterministically
n
d insert actio
n
e
use existing ac
t
D
ea
d
End: non-
d
o
llowing
Satisfy Prec
o
effects to a u
n
Replace Lin
k
p
recondition
w
Remove Acti
o
Do Nothing.
I
S
uperfluous Eff
o
Link effects
o
b
y actions in
t
Do Nothing.
I
c
ursion
Figure 5 Que
r
fluous effort
s
o
rmed to iden
t
f
the game
s
g
oal state of t
h
r
equirements.
h
en a quest is
o
mplete (qu
e
t
-level goal.
A
action will
b
en a quest is
n
o
ved from th
e
m
e a dead end
a
l-state modi
f
e
xecuted befor
e
s
is handled a
s
t
cannot be f
u
o
ng with any
c
. If the event
i
g
even
t
s in th
e
r
ent abstract
r
ationale is t
h
p
e are consider
e
a
ll allows the
event to be
t
hm takes a pla
n
a
n cannot be a s
n
-instantiated a
c
plan is inconsis
t
r
n.
C
hoose a flaw fr
o
o
n: non-determi
n
c
tion with a uni
f
w
action with a
u
a
ction with the
o
non-determinist
e
ting the action
t
o
n without
choose a deco
m
n
s in the deco
m
t
ions as part of t
h
d
eterministicall
y
o
ndition: Link o
n
ifying open pre
k
: Replace a
c
w
ith a link fro
m
o
n: Remove the
I
gnore the flaw.
o
rt:
o
f earlier steps
t
he superfluous
I
gnore the flaw.
st-Centric A
d
s
. Conseque
n
t
ify and restor
s
toryline start
s
h
e original pla
n
The player ca
n
added to the
e
st‐X) is ad
d
A
s open preco
n
b
e added to t
h
n
o longer desir
e
e
ques
t
-level
and be remo
v
f
ication is a
e
planning.
s
follows. If th
e
u
rther decom
p
c
ausal links an
d
i
s part of dec
o
e
decompositi
o
event is mar
k
h
at actions in
e
d having so
m
abstract actio
n
deleted is ab
s
n
s
tructure, a se
t
olution, and a
d
c
tions.
t
ent, fail. Other
w
o
m the plan. Sw
i
n
istically choos
e
f
ying effect
u
nifying effect
o
pen pre-conditi
o
ically choose
p
t
hreatening the l
i
Decompositi
o
m
position from
m
position into t
h
h
e decompositi
o
y
choose to do
ne of the dead
-
condition.
c
ausal link to
a
m
the dead end a
c
action from the
to pre-conditio
n
effort
d
aptation Pla
n
n
tly, extra
e narrative
s
with the
n
according
n
specify a
story, the
d
ed to the
n
ditions are
h
e plan to
e
d, its only
goal state,
v
ed during
one-time
e
event is a
p
osed, it is
d
temporal
o
mposition,
o
n are also
k
ed as un-
the same
m
e cohesion,
n
to be re-
s
tract, it is
t
of flaws
d
omain
w
ise, if the
i
tch on
e
o
n
p
romotion,
i
n
k
.
o
n: non-
the library
h
e plan, or
o
n
one of the
-
end action
a
unifying
c
tion.
plan.
n
s fulfilled
n
nin
g
removed along with all children in its decomposition.
The ability to delete and add actions creates
circumstances in which the planner revisits the same partial
plan in the search space. To preserve systematicity of the
search and prevent infinite loops, we mark every action
and causal link added during the adaptation as “sticky” and
do not allow them to be deleted henceforth. Note that
actions in the original plan to be adapted are not sticky.
The stickiness of actions is a hard constraint that cannot be
violated.
The planning algorithm itself is extended in order to
process existing plans. The algorithm is shown in Figure 5.
There are five types of flaws: (a) unsatisfied precondition
of an action, (b) un-decomposed abstract action, (c) causal
threats, (d) dead ends and (e) superfluous efforts. Here, we
only highlight the differences between our algorithm and a
typical partial-order planner. In our algorithm, an action
can be deleted due to an open precondition. It is necessary
in situations where the precondition cannot be satisfied due
to the deletion of other parts of the plan. Similarly, causal
threats can be resolved by deleting the action that threatens
the causal link. This can be handy in situations where
events that have become unnecessary are preventing plan
soundness. In both cases, deletion is used with caution.
Two new types of flaws, dead ends and superfluous
efforts, are introduced in order to maintain narrative
coherence. Normally, dead ends only occur as a result of
deletion or during repairing another dead end. We propose
four ways to fix a dead end, listed in decreasing order of
desirability. The planner can (1) link one effect of the dead
end to an open precondition in the plan. Alternatively, it
can (2) replace an existing causal link with a link from the
dead-end action, the two links satisfying the same pre-
condition. In this case, bookkeeping is necessary to prevent
infinite loops when two actions are competing for the same
link. In addition, the planner can (3) remove the dead end.
Finally, if all else fails, we (4) ignore the flaw and accept
that the final solution will have a dead end. We believe that
this is preferable to failing to return any solution.
Superfluous efforts can be generated by connecting
existing actions in an undesirable way, for example, in
order to repair a dead end. Also, it may be caused by the
removal of some actions the superfluous efforts lead to. To
repair a superfluous effort, the algorithm can replace
outgoing links from those actions in the superfluous effort
with effects from earlier actions. Extending earlier causal
effects to later links is a common technique used in
continuous planning (Russell and Norvig 2002). As with
dead ends, we ignore the flaw if there is no other way to
solve the problem, favoring a plan with superfluous actions
over no solution.
Example
In this section, we briefly explain the working of quest-
centric adaptation planning with an example of a simple
role-playing game. As shown in Figure 6, the original
game narrative consists of two quests. In the first quest, the
player kills the witch, arch-enemy of the king, by pouring a
bucket of water on her. In the second quest, the player
rescues the princess from a dragon and marries her.
However, suppose the player prefers treasures to marriage,
we can remove the rescue quest and add an escape quest
where the player is locked in a treasure cave and can only
escape by solving a puzzle. The original quest, an
intermediate step, and the final result are shown
respectively in Figure 6, 7 and 8. The order of operations is
denoted with numbers in circles. We do not intend to
explain every detail due to space constraints. For the sake
of simplicity, the search is assumed to be nondeterministic,
which always makes the correct choice at every decision
point. Backtracking will happen in real applications, even
though not shown here.
We begin with requirements from the user preferring
escape missions to rescues. The quest-level goal situation
is updated accordingly by removing
quest‐
complete(rescue)
and adding quest‐complete(escape).
The only outgoing causal link from the action
Rescue
Questis used to satisfy this quest-level goal. As a result,
this action becomes a dead end. The first step of planning
is to remove it together with all descendant actions and all
Figure 6 Original Game Narrative Before Adaptation
associated causal links. To fulfill the added goal quest‐
complete(escape)
, the abstract action RescueQuest is
added and subsequently decomposed. New actions in the
decomposition are added. They bring new open
preconditions. We then deal with world-level goals. In the
next few refinement iterations, dead ends, marked with
number 3, are removed and actions marked with number 4
and 5 are added to fulfilling open preconditions. After
these operations, we have obtained the plan in Figure 7.
The reward component of
Witch‐Hunt Quest is
modified as follows. The action
King Trusts You,
marked with 6, becomes a dead end and removed. Its
removal introduces two flaws: 1) the action
ShowShoes
toKing has become a dead end, and 2) the Witch‐Hunt
Reward abstract action now has no decomposition. The
relevance heuristic comes into play in resolving the dead
end. The action
ShowShoestoKing is determined to be
more relevant to the remaining quest than to the removed.
Hence, we prefer establishing an outgoing link
known‐
success(king,hero,witch‐hunt) for action number 5
to removing it. Finally, we need a new decomposition for
Witch-Hunt Reward, and we realize the decomposition can
reuse action number 5. Having fixed all flaws, we have a
complete and coherent narrative, shown in Figure 8.
Authorial Leverage
A direct motivation of this research is to scale up the
ability to deliver a large number of customized experiences
without significantly increasing the authoring effort. Chen
et al. (2009) defines authorial leverage as the quality of
experience per unit of domain engineering, where quality
is a function of complexity, ease of change, and variability
of experience. In this section, we focus on variability, or
the number of distinct stories.
Two components must be authored in the system: a
world domain model, containing specifications for
primitive event actions as well as a number of quests as
DPOP recipes. These constitute a one-time authoring cost
by a domain engineer. Next, one or more storylines may be
authored in the DPOP representation such that they consist
of some quests and other primitive events. This may
require additional effort on the part of the human author,
but the payoff for this extra effort is an exponential scaling
of the initial effort.
Theoretically, our adaptation process takes a single
narrative and produces as many adaptations as the size of
the power set of available quests. In practice, the number
of pragmatic adaptations will be lower because it’s likely
Figure 7 An Intermediate Snapshot in the Adaptation
Fi
g
ure 8 Com
p
lete, Coherent Narrative after Ada
p
tation
that a large fraction of the original is retained in each
adaptation request. It is possible, for example, that the
output story always contains more than 70% of original
quest. However, the scaling will still be exponential when
the fraction remains constant.
To manually achieve this scaling, one would have to
author n(n-1) transitions between quests (n-1 variations of
each quest so it can be paired with n-1 other quests).
However, as the planner can opportunistically discover
feasible transitions based on existing actions in the library,
the actual authoring effort required can be significantly less.
In either case, authoring efforts grows much slower than
distinct stories.
Future work is required to measure the pragmatic
authorial leverage of the system in terms of authoring
effort versus effective output. An evaluation of aesthetic
quality of generated storylines is also currently underway.
Related Work
As an offline procedure, storyline adaptation has a strong
connection with story generation. Story generation is the
process of automatically creating novel narrative sequences
from a set of specifications. The most relevant story
generation work is that that uses planning as the underlying
mechanism for selecting and instantiating narrative events
(c.f., Meehan 1976, Lebowitz 1987, Riedl and Young 2004,
Porteous and Cavazza, 2009). The distinction between our
storyline adaptor and story planning is that the storyline
adapter starts with a complete, sound narrative structure
and is capable of removing events.
Case-based reasoning (CBR) has also been used to
generate stories from scratch (c.f. Turner 1994; Peréz y
Peréz and Sharples, 2001; Gervás et al. 2005; Turner 1994.
Our system may also be compared with the revision stage
of transformational case-based planning (CBP), in which
old plans are reused and revised to solve new problems.
One important difference between CBP and quest-centric
adaptation is that planning is geared towards maximum
efficiency whereas the shortest or most efficient sequence
of actions is rarely the best or most coherent story.
Transformational CBP often tries to eliminate as many
actions as possible, but we always try to preserve the
original narrative and authorial intent if possible. Our
search heuristic always favors fixing plan flaws in
alternative ways before deleting any actions because
deletion of events may interfere with authorial intent.
In a parallel effort, the TACL system (Niehaus and Riedl
2009) is designed to adapt and customize military training
scenarios. Realistic military training is a highly rigorous
process. Any automatic adaptation must preserve
pedagogical correctness and the tolerance of modification
is low. Game quests, on the other hand, can be modified
extensively. In this paper, we apply the algorithm in the
novel context of quests and games. We demonstrate direct
modification of game quests.
Interactive storytelling systems demonstrate how players
or learners may interact with story and scenario content in
complex simulation environments. See Roberts and Isbell
(2008) for overviews of interactive storytelling and drama
management systems. The distinction between quest-
centric game adaptation and interactive storytelling is that
in interactive storytelling adjustments to the virtual world
occur at execution time in order to cope with the real-time
actions of the player. Our adaptation system, on the other
hand, rewrites the objectives of the virtual environment in
an offline process. In this light, quest-centric game
adaptation and drama management are complimentary: the
adaptation system configures the drama manager, which
oversees the user’s interactive experience.
While discussion of the execution of game narratives is
outside the scope of this paper, we envision using
planning-based interactive narrative systems such as the
Automated Story Director (Riedl et al. 2008) for dynamic
execution of game narratives within the game world.
Work on optimizing player experience in games have
been addressed in terms of interactive storytelling. Thue et
al. (2007) describe a player modeling approach to choosing
different trajectories through pre-authored branching story
structures based on player profiles. Hullett and Mateas
(2009) have investigated generation of game level floor
plans, and thus the narrative of moving through space,
using HTN planning. HTN planning requires complete
specification of how each task can be performed. In
comparison, our approach is capable of opportunistic
discovery of novel event sequences. Finally, others
investigating optimization of player experiences have
explored game world generation and other non-narrative
content generation using neural network models of players
and evolutionary computation (c.f., Togelius et al. 2010).
At this moment, we are ignoring the generation of
landscape and environment in games.
Conclusions
As game players possess different motivations, tastes and
preferences, adapting and customizing game content may
improve gaming experiences. In this paper, we presented a
planning technique that adapts game storylines consisting
of several quests in order to deliver customized narratives
for individual players. We proposed two plan structures
that break narrative coherence of a story and extend
decompositional partial-order planning to repair these
coherence flaws and delete actions to adapt existing plans.
Furthermore, we discussed design of search heuristics and
illustrated the algorithm with a concrete example. The user
study suggests the ability to repair dead end is useful in
generation of game narratives.
References
Balla, R.-K. and Fern, A. 2009. UCT for Tactical Assault
Planning in Real-Time Strategy Games. Proceedings of the
21st International Joint Conference on Artificial
Intelligence.
Chen, S., Nelson, M.J., Sullivan, A., and Mateas, M. 2009.
Evaluating the Authorial Leverage of Drama Management.
Proceedings of the AAAI Spring Symposium on Intelligent
Narrative Technologies II.
Chung, M., M. Buro, and Schaeffer, J. 2005. Monte Carlo
Planning in RTS Games. Proceedings of the 2005 IEEE
Symposium on Computational Intelligence and Games.
Crawford, C. 1984. The Art of Computer Game Design.
Berkeley, CA: Osborne/McGraw-Hill.
Graesser, A. Lang, K.L., and Roberts, R.M. 1991. Question
Answering in the Context of Stories. Journal of
Experimental Psychology: General, 120(3), 254-277.
Gervás, P., Díaz-agudo, B., Peinado, F. and Hervás, R.
2005. Story plot generation based on CBR, Knowledge-
Based Systems, 18(4-5), 235-242.
Hanks, S. and Weld, D. S. 1995. A Domain-Independent
Algorithm for Plan Adaptation. Journal of Artificial
Intelligence Research, 2, 319-360.
Hullett, K. and Mateas, M. 2009. Scenario Generation for
Emergency Rescue Training Games. In Proceedings of the
Fourth International Conference on the Foundations of
Digital Games.
Lebowitz, M. 1987. Planning stories. In Proceedings of the
9th Annual Conference of the Cognitive Science Society.
Meehan, J. 1976. The Metanovel: Writing Stories by
Computer. Ph.D. Dissertation, Yale University.
Niehaus, J. and Riedl, M. O. 2009. Scenario Adaptation:
An Approach to Customizing Computer-Based Training
Games and Simulations. In Proceedings of the AIED 2009
Workshop on Intelligent Educational Games.
Orkin, J. 2005. Agent architecture considerations for real-
time planning in games. Proceedings of the First Artificial
Intelligence and Interactive Digital Entertainment
Conference.
Pérez y Pérez, R. and Sharples, M. 2001. MEXICA: A
Computer Model of a Cognitive Account of Creative
Writing. Journal of Experimental and Theoretical Artificial
Intelligence, 13, 119-139.
Porteous, P. and Cavazza, M. 2009. Controlling Narrative
Generation with Planning Trajectories: The Role of
Constraints. Proceedings of the 2nd International
Conference on Interactive Digital Storytelling.
Prince, G. 1987. A Dictionary of Narratology. University
of Nebraska Press.
Rattermann, M.J., Spector, L., Grafman, J., Levin, H., and
Harward, H. 2001. Partial and Total-Order Planning:
Evidence from normal and prefrontally damaged
populations. Cognitive Science, 25, 941-975.
Riedl, M.O. 2009. Incorporating Authorial Intent into
Generative Narrative Systems. Proceedings of the AAAI
Symposium on Intelligent Narrative Technologies II.
Riedl, M.O., Stern, A., Dini, D., and Alderman, J. 2008.
Dynamic Experience Management in Virtual Worlds for
Entertainment, Education, and Training. International
Transactions on Systems Science and Applications, 4(2).
Riedl, M.O. and Young, R.M. 2004. An Intent-Driven
Planner for Multi-Agent Story Generation. In Proceedings
of the Third International Joint Conference on
Autonomous Agents and Multi Agent Systems.
Roberts, D.L. and Isbell, C.L. 2008. A Survey and
Qualitative Analysis of Recent Advances in Drama
Management, International Transactions on Systems
Science and Applications
, 3(1), 61-75.
Roberts, D.L., Riedl, M.O., and Isbell, C.L. 2009. Beyond
Adversarial: The Case for Game AI as Storytelling. In
Proceedings of the 2009 Conference of the Digital Games
Research Association.
Rollings, A. and Adams, E. 2003. Andrew Rollings and
Ernest Adams on Game Design. New Riders.
Russell, S. and Norvig P. 2002. Artificial Intelligence: A
modern approach. Prentice Hall.
Sánchez-Ruiz, A, Lee-Urban, S., Munoz-Avila, H., Diaz-
Agudo, B., González-Calero, P. 2007. Game AI for a Turn-
based Strategy Game with Plan Adaptation and Ontology-
based retrieval. In Proceedings of ICAPS 2007 Workshop
on Planning in Games.
Smith, S.J.J., Nau, D.S., and Throop, T. 1998. Computer
bridge: A big win for AI planning. AI Magazine 19(2).
Thue, D., Bulitko, V., Spetch, M., and Wasylishen, E. 2007.
Interactive Storytelling: A Player Modelling Approach.
Proceedings of the 3rd Conference on Artificial
Intelligence and Interactive Digital Entertainment.
Togelius, J. Yannakakis, G., Stanley, K., and Browne, C.
2010. Search-based Procedural Content Generation.
Proceedings of the EvoStar Conference.
Trabasso, T. and van den Broek, P. 1985. Causal Thinking
and the Representation of Narrative Events. Journal of
Memory and Language, 24, 612-630.
Turner, S. R. 1994. The Creative Process: A Computer
Model of Storytelling. Lawrence Erlbaum Associates.
Yee, N. 2006. The Demographics, Motivations, and
Derived Experiences of Users of Massively-Multiuser
Online Graphical Environments. PRESENCE:
Teleoperators and Virtual Environments 15(3), 309-329.
Young, K., and Saver, J.L. 2001. The Neurology of
Narrative. SubStance: A Review of Theory and Literary
Criticism, 30, 72-84.
Young, R.M. 1999. Notes on the Use of Plan Structures in
the Creation of Interactive Plot. In Working Notes of the
AAAI Fall Symposium on Narrative Intelligence.
Young, R. M. and Pollack, M.E 1994. Decomposition and
causality in partial-order planning. Proceedings of the
Second International Conference on Artificial Intelligence
and Planning Systems.
