=Paper=
{{Paper
|id=Vol-2862/paper18
|storemode=property
|title=Toward Example-Driven Program Synthesis of Story Sifting Patterns
|pdfUrl=https://ceur-ws.org/Vol-2862/paper18.pdf
|volume=Vol-2862
|authors=Max Kreminski,Noah Wardrip-Fruin,Michael Mateas
|dblpUrl=https://dblp.org/rec/conf/aiide/KreminskiWM20
}}
==Toward Example-Driven Program Synthesis of Story Sifting Patterns==
https://ceur-ws.org/Vol-2862/paper18.pdf
Toward Example-Driven Program Synthesis of Story Sifting Patterns
Max Kreminski, Noah Wardrip-Fruin, Michael Mateas
University of California, Santa Cruz
{mkremins, nwardrip, mmateas}@ucsc.edu
Abstract human interactor’s perspective enables the narrative system
Unlike in strong story narrative systems, where the creation of to present the interactor with offers of various ways in which
narrative is orchestrated from the top down by a drama man- the story might be further developed (Louchart et al. 2008).
ager or similar agent, stories in emergent narrative systems As a result, it’s often desirable to provide emergent narrative
emerge bottom-up from the behavior of autonomous charac- systems with more sophisticated ways of understanding the
ters in a simulated storyworld. As a result, emergent narrative stories they’re creating.
systems do not always know what stories they’re telling, and Story sifting (Ryan, Mateas, and Wardrip-Fruin 2015;
a perennial challenge for these systems involves recognizing Ryan 2018) is one way to build narrative systems that un-
and showcasing emergent stories as they unfold. Story sifting derstand emergent stories. So far, implementing story sifting
technologies can enable a narrative system to automatically has involved hand-writing lots and lots of small story sifting
recognize emergent stories that match certain sifting patterns,
but hand-authoring these sifting patterns can be difficult and
patterns that recognize certain kinds of interesting emergent
time-consuming. To support users in authoring these sifting microstories. While this approach has its advantages, think-
patterns, we present an interactive example-driven program ing up and writing these sifting patterns can be both time-
synthesizer that can generate realistic sifting patterns given a consuming and error-prone. The Felt system (Kreminski,
few examples of target event sequences and refine the result- Dickinson, and Wardrip-Fruin 2019) attempts to mitigate
ing patterns based on further user feedback. some of the difficulties of authoring sifting patterns by intro-
ducing an approachable domain-specific language intended
Introduction to improve authorial leverage and open up the authoring of
sifting patterns to writers as well as dedicated narrative sys-
In emergent narrative systems, story emerges organically
tem programmers, but substantial difficulties remain.
from interaction between characters in a simulated sto-
ryworld (Louchart et al. 2015). Past research in player In order to partially address the difficulties of hand-
retellings of their play experiences in simulation-driven writing sifting patterns, we propose an approach to synthe-
emergent narrative games has shown that these games of- sizing sifting patterns from user-provided examples of target
ten function as storytelling partners for the player (Eladhari event sequences: an interactive, domain-specific example-
2018; Kreminski and Wardrip-Fruin 2019; Kreminski et al. driven program synthesizer for story sifting patterns repre-
2019). To support this style of play, we would like to make sented as Datalog-equivalent queries in the Felt story sifting
these games better at mixed-initiative co-creative (Liapis et DSL. Our system leverages inductive logic programming,
al. 2016) storytelling. along with other program synthesis techniques, to gener-
One difficulty in doing this is that it’s hard to get emergent ate plausible story sifting patterns from few examples and
narrative games to understand the emergent stories they’re present these patterns to the user for interactive refinement.
producing. Unlike in strong story narrative systems (Mateas
and Stern 2000; Riedl and Bulitko 2013), where the creation Related Work
of narrative is orchestrated from the top down by a drama Our work draws on existing literature in program synthe-
manager or similar agent, emergent stories are not necessar- sis, and specifically the synthesis of Datalog programs, to
ily recognized by the system that produces them. However, which Felt sifting patterns are equivalent. Much past work
the more understanding the system has of the stories that are on synthesizing logic programs has been done under the ban-
emerging, the more effectively it can surface these stories ner of inductive logic programming (ILP). ILP systems—
to the player and support narrative development. In partic- including FOIL (Quinlan 1990), GOLEM (Muggleton and
ular, understanding of the story that is emerging from the Feng 1992), and Progol (Muggleton 1995)—attempt to learn
Copyright c 2020 for this paper by its authors. Use permitted un- a logic program that correctly characterizes the distinc-
der Creative Commons License Attribution 4.0 International (CC tion between a set of positive and a set of negative exam-
BY 4.0). ples (Muggleton and De Raedt 1994). Most existing ILP sys-
tems aspire to generality, limiting the extent to which they the string, number, or entity ID on the right. Parenthe-
can use domain knowledge about what kinds of programs sized clauses (such as (eventSequence ?e1 ?e2)
are likely wanted to avoid exhaustively searching a rela- and (contributingCause ?e1 ?e2)) denote
tively unrestricted space of potential programs. However, the invocations of domain-specific Datalog inference
Metagol system (Muggleton, Lin, and Tamaddoni-Nezhad rules, defined as part of the simulation. Clauses can
2015) compromises by allowing the user to provide a set of also be negated with the special not syntax, as in
meta-rules that encompass a sort of domain theory, render- (not [?e2 tag accidental]) here.
ing the problem of predicate invention more computationally From a program synthesis perspective, the problem of
tractable by cutting down the search space. generating story sifting patterns has several unusual aspects
More recently, a number of other techniques from the that informed our approach.
wider program synthesis literature have been applied to • Our past experience authoring sifting patterns has given
Datalog program synthesis, including constraint-based (Al- us a strong domain theory about which relations be-
barghouthi et al. 2017), syntax-guided (Si et al. 2018), and tween events, characters, and other storyworld entities are
provenance-guided (Raghothaman et al. 2019) approaches. worthwhile to explore when sifting, enabling us to aggres-
These newer systems have improved on both the perfor- sively prune the search space of candidate programs.
mance and the expressivity of classical ILP approaches to
logic program synthesis: they can either produce the same • We don’t want our synthesis algorithm to generate rela-
programs substantially more quickly than older systems; tions involving certain properties. For instance, in a sift-
produce programs that older systems could not have pro- ing pattern, relationships between the numeric IDs of in-
duced at all, for instance by introducing new predicate in- volved entities shouldn’t be considered, nor should re-
vention techniques; or both. lationships including characters who aren’t directly in-
To the best of our knowledge, program synthesis has not volved in the events under consideration. Further, because
yet been applied in an interactive or generative narrative re- we want to create interpretable sifting patterns that can be
search context. However, there has been some limited use of presented to an end user directly, to explore these irrele-
program synthesis in the adjacent procedural content gen- vant relationships would run the risk of overwhelming the
eration and game generation communities. For instance, the user with extraneous information.
ILP system Leda (Summerville 2018) synthesizes AnsPro- • Ideally, for easy interoperability with other tools (includ-
log inference rules describing the relationship between low- ing Felt), we want our synthesis algorithm to be fast
level game mechanics and higher-level aspects of player ex- enough to run interactively in a web browser—a task
perience. Meanwhile, Butler, Siu, and Zook (2017) apply for which state-of-the-art general-purpose ILP systems, in
non-ILP program synthesis techniques to the generation of spite of their significant performance improvements in re-
boss monster behaviors for digital games. cent years, are still not well-suited.
• We don’t need to tackle the difficult ILP problem of in-
Background venting reusable intermediate predicates ourselves, as we
Our goal is to synthesize Felt sifting patterns. As back- can generally rely on the authors of the simulation domain
ground, to showcase the features of the Felt sifting DSL, we to have provided relevant intermediate predicates for us.
first present a complete hand-authored Felt sifting pattern,
For these reasons, instead of leveraging an existing off-
adapted from the arson-revenge pattern documented in
the-shelf ILP system or other synthesizer, we elected to build
(Ryan 2018):
a small domain-specific ILP system of our own, intended for
(eventSequence ?e1 ?e2) interactive use as a human-in-the-loop authoring tool.
[?e1 eventType hatchRevengeScheme]
[?e2 eventType setFire] Approach
(contributingCause ?e1 ?e2) Given a database of storyworld events, we first present the
[?e1 actor ?arsonist] user with an interface for selecting positive examples: se-
[?e2 actor ?arsonist] quences of events that the synthesized sifting pattern should
(not [?e2 tag accidental]) match. Initially, each positive example is represented as a se-
This pattern matches a sequence of two events: a quence of one or more numeric event IDs. Once the user has
hatchRevengeScheme event, followed by a non- selected a set of positive examples, we enrich each exam-
accidental setFire event with the same protagonist and to ple with background information by running several queries
which the first event was a contributing cause. Tokens begin- against the database to fetch and cache information about
ning with a question mark, such as ?e1 and ?arsonist, the events and characters that are directly involved in this
denote logic variables, whose values are unified with one example. What background information needs to be fetched
another across the whole sifting pattern. Square-bracketed depends on how events and characters are represented in the
clauses (such as [?e2 eventType setFire] and simulated storyworld at hand; for the simple storyworld we
[?e1 actor ?arsonist]) indicate assertions of used to evaluate this technique, the information fetched by
the form [entity attribute value], which this process includes the type and tags of each event in the
can be read as stating that the entity on the left has an sequence, as well as the numeric IDs of the characters that
attribute with the name in the middle whose value is participated in each event as an actor or target.
We then pick an example at random and generate a set and we’ve already asserted that the target of the first event
of properties for this example. As in Odena and Sutton is friends with the protagonist of the first event, we don’t
(2020), a property is a small program that takes in an ex- need to reassert the same relationship between the target of
ample and returns a boolean value indicating whether this the first event and the target of the second.) Then we prune
property holds for this example. Intuitively, a property can properties that are fully logically subsumed by other prop-
be thought of as a straightforwardly answerable yes/no ques- erties. For instance, in our test simulation, an event’s tags
tion about the example: for instance, “Does the first event in are always dependent on its type; therefore, we eliminate all
the sequence have event type betray?” or “Is the protago- properties of the form eventTag_eN_TAG if a property of
nist of the first event the same person as the target of the last the form eventType_eN_TYPE is also present.
event?” Once a set of properties intended to be applied to all At this point, we can synthesize a story sifting pattern (i.e.
of the user-provided examples has been generated, we can a Datalog-equivalent query in the Felt story sifting DSL) and
test these properties against an example to produce the ex- run it against the storyworld state database to get any other
ample’s property signature: the subset of all generated prop- matches that might exist, besides the user-selected positive
erties that hold for this example. examples, and show these to the user.
Our current approach generates two kinds of proper- If the user thinks the pattern shouldn’t match one or more
ties, based on the most commonly used features in an ex- of these examples, then they can add these examples as neg-
isting library of sifting patterns developed for the emer- ative examples. We generate properties for each negative ex-
gent narrative game Why Are We Like This? (Kreminski ample in the same way as before, and identify which proper-
et al. 2020a; 2020b). First, we examine the distinguish- ties are consistently true for all negative examples and con-
ing attributes of each event in the example sequence and sistently untrue for all positive examples. Then we refine the
generate event attribute properties. In our test simula- synthesized sifting pattern to exclude these negative proper-
tion, events are distinguished by their eventType and ties and re-present the matches to the user.
tag attributes, so we generate properties of the form
eventType_eN_type for each event’s type and prop- Usage Examples
erties of the form eventTag_eN_tag for each tag on Story sifting can be applied to event sequences from a va-
each event. For instance, if the first event in the example se- riety of sources. At one end of the spectrum, sifting tech-
quence is an insultDismissively event with the tags niques are sometimes used to extract narrative from se-
unfriendly and highStatus, the example’s property quences of game events that were initially generated with-
signature would include the following properties: out regard for narrativity, as in many sports games (Rhodes,
• eventType_e1_insultDismissively Coupland, and Cruickshank 2010). At the other end of the
spectrum, sifting can also be applied to the output of sophis-
• eventTag_e1_unfriendly ticated narrative simulations like Talk of the Town (Ryan
• eventTag_e1_highStatus et al. 2015) and Dwarf Fortress (Bay 12 Games 2006;
Garbe 2018), which employ high-fidelity models of char-
Next, we generate entity relationship properties based acter motivation and other narrative-relevant concerns at the
on a simulation-specific library of Datalog inference level of event generation, before sifting is applied. Because
rules relating involved entities to one another. These these event sources vary widely in the baseline level of nar-
rules include character/character relationships, e.g. likes, rative structure and sophistication they provide, we want our
dislikes, and ancestor; character/event relationships, approach to testing to assume minimal narrative structure
e.g. eventAdvancesHeldValue; and event/event rela- in the storyworld database. This allows us both to stress-
tionships, e.g. indirectCause. These rules form a sig- test the generality of our synthesis approach (ensuring that
nificant part of the domain theory about which relationships it doesn’t implicitly depend on regularities in a particular
might be relevant to story sifting in a particular simulation, simulation) and to place the primary authoring affordance
and our system is able to translate these rules directly into on example specification (rather than spreading it between
properties, allowing the domain theory to evolve as new example specification and simulation authoring).
rules are defined. Therefore, in order to test our system, we first gener-
Once we’ve generated a complete property signature for ated a simple storyworld containing five characters and 200
the first example, we test these properties against the second random events. To establish a rudimentary social graph, a
example and remove any that don’t hold. We then iteratively handful of directed likes and dislikes relationships
repeat this process for all the other examples, winnowing and a handful of symmetric coworkers relationships were
down the set of properties to just those that hold for all pos- added between some pairs of characters at random. Addi-
itive examples. tionally, from a pool of eight values (such as authority,
The resulting set of properties may need to be pruned to communalism, and comfort), each character was ran-
eliminate redundancies. First, we prune properties that log- domly assigned two values that they support and one value
ically duplicate other properties, for instance by asserting a that they oppose.
relationship between two logic variables representing char- For each event, we randomly selected one of 35 possi-
acters for which the same relationship has already been as- ble event types, then randomly assigned two different char-
serted. (If the protagonist of the first event and the target acters to be the actor and target of this event. Events were
of the second event are known to be the same character, also assigned a handful of tags based on their event type; the
storyworld as a whole contained 12 total distinct event tags, (eventSequence ?e1 ?e2 ?e3)
with each individual event having between one and four tags. [?e1 actor ?e1actor]
Events of certain types were also marked as supporting or [?e2 actor ?e2actor]
opposing some of the values held by characters: for instance, [?e3 actor ?e3actor]
a rejectSuperiority event might be marked as oppos- [?e1 tag negative] [?e1 tag romantic]
ing the authority value. The resulting storyworld was [?e2 tag negative] [?e2 tag romantic]
then used as background for the following examples. [?e3 tag positive] [?e3 tag romantic]
[(= ?e1actor ?e2actor ?e3actor)]
Simple Positive Examples The eventSequence setup clause here ensures that
We attempted to synthesize sifting patterns for several recur- all of its arguments are database entities of type event,
ring, emergent patterns of events that we found narratively and that all of these events occurred in chronological order
compelling. First, we attempted to synthesize a sifting pat- from left to right (potentially interspersed with arbitrarily
tern for the microstory “romantic failure followed by roman- many other events). Meanwhile, setup clauses of the form
tic success”, which we chose to operationalize as a sequence [?eN actor ?eNactor] are used to bind characters in-
of two romantic failures for the same character, followed by volved in these events to temporary logic variables, so that
a romantic success for that same character. We provided the they can be referenced in later clauses.
system with one positive example of this pattern: Besides the two provided positive examples, the resultant
1. Sarah tried to flirt with Mira, but was rejected. sifting pattern also matched 41 other event sequences in the
database, all of which fulfilled the intended requirements.
2. Sarah tried to ask Mira out on a date, but was rejected. Many of these matches included some, but not all, of the
3. Sarah tried to ask Emin out on a date, and succeeded. events provided in the positive examples.
Given only this example, our system generates 35 proper- Adding Negative Examples
ties. 3 of these (one per event in the example) involve event
types; 10 involve event tags; 4 involve statements about Building on the same “romantic failure followed by roman-
the same character being involved in two different roles, tic success” microstory, we next attempted to refine the syn-
for instance as the target of both the first and the second thesized sifting pattern to specifically require that the first
events. The remaining 18 properties involve various charac- event in the sequence is not a major romantic failure (such
ter/character relationships, for instance indicating that Mira as a breakup or failed proposal). Some events in our test sim-
dislikes Sarah; Mira likes Emin; and that Emin and Sarah ulation had the major tag, but there was no corresponding
are coworkers. minor tag for non-major events, so this had to be accom-
We then provided another positive example for the same plished through the use of negative properties.
pattern: From the set of matches for the previous sifting pattern,
we added the following match as a negative example:
1. Zach tried to ask Emin out on a date, but was rejected.
1. Mira tried to propose to Emin, but was rejected.
2. Zach tried to rekindle a romantic relationship with Sarah,
but was rejected. 2. Mira tried to ask Zach out on a date, but was rejected.
3. Zach tried to flirt with Mira, and succeeded. 3. Mira tried to flirt with Zach, and succeeded.
This second example was sufficient to reduce the set of The system initially proposed several candidate negative
common properties between both examples down to just properties, all of which were true for the single negative ex-
nine: ample but false for both of the positive examples:
• eventTag_e1_negative • eventType_e1_propose_rejected
• eventTag_e1_romantic • sameCharacter_e2target_e3target
• eventTag_e2_negative • likes_e1actor_e1target
• eventTag_e2_romantic However, the first of these three properties was too spe-
cific (targeting the event type, rather than the tags, of the first
• eventTag_e3_positive event in the sequence), while the latter two were incidentally
• eventTag_e3_romantic applicable, but unrelated to our intent. To further refine the
pattern, we then provided a second negative example:
• sameCharacter_e1actor_e2actor
• sameCharacter_e1actor_e3actor 1. Emin broke up with Vincent.
2. Emin tried to flirt with Vincent, but was rejected.
• sameCharacter_e2actor_e3actor
3. Emin tried to ask Sarah out on a date, and succeeded.
By prepending a set of static setup clauses and pruning
setup clauses that introduced unused logic variables, these This enabled the system to further filter down the set of
properties were then translated into the following complete candidate negative properties, resulting in the addition of the
Felt sifting pattern: following (correct) clause to the sifting pattern:
(not [?e1 tag major]) same town resident character. A naı̈ve implementation of
this sifting pattern might look like this:
Note that this negative clause was initially subsumed by
the more specific eventType constraint when only a sin- (eventSequence ?e1 ?e2 ?e3)
gle negative example was provided. A second negative ex- [?e1 eventType enterTown]
ample was needed to show the system that it was the event [?e1 actor ?guest]
tags (rather than the event type) of the first event in the se- [?e2 eventType showHospitality]
quence that we actually intended to restrict. [?e2 actor ?host] [?e2 target ?guest]
[?e3 tag harm]
Incorporating Entity Relationships [?e3 actor ?host] [?e3 target ?guest]
Next, we attempted to synthesize a sifting pattern for a mi- However, this sifting pattern would also match event se-
crostory in which a character’s ideological rival calls them quences like the following, in which the intended interpreta-
out on a hypocritical action. An example of this pattern tion of the matched events is invalidated by the traveler leav-
might look something like the following sequence of events: ing the town before the final event of the intended sequence
1. A performs an action opposed to one of their own values. plays out:
2. B criticizes A. 1. Yann enters town.
2. Yann is shown hospitality by Ema.
...where B is a character who holds a value to which A
is opposed, or vice versa. Although this sequence of events ∗ Yann leaves town.
is short, matching instances of this microstory requires the 3. Ema pickpockets Yann, getting away with all their money.
synthesis of a pattern that includes both a character/character To address this problem, an additional clause might be
relationship (i.e. that characters A and B hold opposed val- appended to the end of the sifting pattern, taking advantage
ues) and a character/event relationship (i.e. that the first ac- of the not-join syntax (inherited from the DataScript li-
tion in the sequence harms a value held by A, or advances a brary atop which the Felt sifting pattern DSL is built) to
value to which A is opposed). specify that the traveler must not leave town between the
We first provided the system with two positive examples. first and last events of the sequence. This clause essentially
This was sufficient to produce the following nearly-correct states that there must not exist any event with the specified
sifting pattern: characteristics (?eMid) between ?e1 and ?e3:
(eventSequence ?e1 ?e2) (not-join [?e1 ?e3 ?guest]
[?e1 actor ?e1actor] (eventSequence ?e1 ?eMid ?e3)
[?e2 actor ?e2actor] [?eMid eventType leaveTown]
[?e2 target ?e2target] [?eMid actor ?guest])
[?e2 eventType criticize]
[(= ?e1actor ?e2target)] However, the search space of possible compound negative
(likes ?e2actor ?e1actor) event clauses for any given set of user-provided examples is
(opposedValues ?e1actor ?e2actor) very large. The first difficulty lies in identifying which event
(eventHarmsHeldValue ?e1 ?e1actor) or events that aren’t part of the provided negative example
are somehow disqualifying the negative examples from con-
We then had to provide one more positive example to sideration. We could narrow down the search space some-
eliminate the spurious (likes ?e2actor ?e1actor) what by considering only events that occurred between the
clause, introduced by a property that incidentally happened start and the end of the provided negative example, and that
to hold for the first two examples we provided but that was involved at least one of the characters involved in the exam-
not part of our intent. Alternatively, an attentive user might ple events directly, but this could still include prohibitively
notice that this clause was not part of their intent and man- many events. And the second difficulty lies in determining
ually eliminate it from the sifting pattern without giving the what aspects of the disqualifying event are responsible for
system any further examples. the disqualification: is it the event type, the tags, the actor,
the target, one of the relationships between these entities to
Currently Unsupported Negative Constraints one another (or to other entities in the example), or some
Besides the constraint types illustrated here, there exists one combination of these factors?
other type of constraint that’s fairly common in existing Perhaps the most promising way to cut down this search
Felt sifting patterns, but that our system currently doesn’t space is to ask the user for further guidance as to which in-
make any attempt to synthesize. These are compound nega- terceding events are responsible for disqualifying each neg-
tive event constraints, which (among other uses) allow sift- ative example. This guidance could then allow the system
ing patterns to avoid matching candidate event sequences to suggest reasonable combinations of negative properties
that are interrupted by events with certain attributes. For in- involving these events. However, presenting the user with
stance, suppose you want to write a sifting pattern to match an interface that allows them to easily identify the relevant
a “violation of hospitality” microstory, in which a traveling events may be difficult due to the sheer volume of events
character enters a town, is shown hospitality by a resident of generated by many emergent narrative systems. For the time
this town, and then experiences harm at the hands of this being, we leave this problem to future work.
Figure 1: A screenshot of the system’s current user interface. On the left sits a scrolling, filterable log of all events that have
occurred in the storyworld so far, allowing the user to select event sequences to use as examples. On the right sits an editable
view of the current synthesized sifting pattern; the sets of positive and negative examples the user has provided; and the set of
additional matches for the current candidate sifting pattern, which the user can add as positive or negative examples.
Discussion guage sentences, so even a relatively naı̈ve user can figure
Our approach avoids many of the difficulties associated with out which clauses of the synthesized sifting pattern make
general program synthesis by encoding a lot of information sense and which ones don’t. In this sense, program synthe-
about the domain, especially in the form of hand-authored sis serves as an on-ramp that teaches users about the DSL
Datalog rules about relationships between characters and used to define sifting patterns and the set of features that
events. We don’t need to try to discover these rules gener- this DSL supports, so that users can move from exclusively
ically if we’ve been provided with a good set of special- defining sifting patterns via examples toward modifying ex-
case rules up front, so we don’t have to do the actually-hard isting sifting patterns and maybe even constructing new sift-
part of Datalog program synthesis (i.e. trying to invent these ing patterns from scratch via the textual DSL.
potentially-recursive rules ourselves given just the concrete We consider our approach to be an example of human-
examples.) centric program synthesis (Crichton 2019), which deals with
We avoid some of the other difficulties by including a “what applications [of program synthesis] open up when a
human in the loop and building our synthesized programs user has the programming skills to express specifications at a
out of relatively straightforward, individually comprehensi- level beyond examples”. For us, synthesis functions partly as
ble building blocks. Individual Datalog clauses can be pre- a teaching tool for introducing users to the textual language
sented to the human user as short, declarative natural lan- in which sifting patterns are expressed and making them
aware of what affordances this language provides. Our syn- Felt sifting DSL, given several user-provided examples of
thesized programs aren’t treated as black boxes, but exposed narratively interesting event sequences. Our system is in-
to the user for editing, and it’s our hope that users will com- tended for interactive use with a human user in the loop. We
bine the programming-by-example features that this tool af- avoid or mitigate some of the difficulties of general-purpose
fords with direct manipulation of generated sifting patterns program synthesis (especially the problem of intractably
to modify, add, and remove constraints. large search spaces) by encoding a lot of domain knowledge
Moreover, our tool remains useful even for experienced into the architecture of the synthesis algorithm. Our system
sifting pattern authors, who might not immediately notice features several key limitations, especially around the syn-
all of the properties they intend the sifting pattern they’re thesis of complex negative constraints, but is nevertheless
writing to contain. In addition, since the set of relationships able to synthesize useful, realistic sifting patterns from a
that might exist between characters is likely to evolve over small number of example event sequences.
the course of developing a complex simulation-driven emer- Potential future work includes extension of the user in-
gent narrative game, even experienced sifting pattern authors terface and synthesis algorithm to better support complex
might benefit from the existence of a system that can surface negative constraints; incorporation of the synthesizer into a
new clause types to them as new Datalog rules are imple- more full-featured and user-friendly sifting pattern author-
mented by other developers. ing tool; evaluation of the resulting tool with a larger num-
ber of potential users; and a more detailed comparison of
Limitations our hand-rolled domain-specific synthesizer against existing
general-purpose Datalog program synthesizers, to determine
As discussed previously, our current system makes no at- whether we could feasibly re-encode the problem in a way
tempt to synthesize compound negative event constraints. To that makes it more amenable to attack by a general-purpose
support synthesis of these clauses will likely require further synthesizer.
work on both the core synthesis algorithm and the user inter-
face to provide the user with a way to explain why negative References
examples are negative by pointing out the specific interced-
ing events that invalidate them. Albarghouthi, A.; Koutris, P.; Naik, M.; and Smith, C. 2017.
Currently, our approach enforces an implicit total order- Constraint-based synthesis of datalog programs. In Interna-
ing constraint on the events matched by the synthesized sift- tional Conference on Principles and Practice of Constraint
ing pattern. All examples provided for a single sifting pattern Programming, 689–706. Springer.
(positive and negative) must be of the same length, and it’s Bay 12 Games. 2006. Dwarf Fortress. bay12games.com/
assumed that the Nth event of each example event sequence dwarves.
is intended to play the same role in the target microstory as Butler, E.; Siu, K.; and Zook, A. 2017. Program synthesis
the Nth event of every other example. This strict constraint as a generative method. In Proceedings of the 12th Interna-
may not always be intended or desirable; for instance, it’s tional Conference on the Foundations of Digital Games.
sometimes preferable to construct a sifting pattern in which Crichton, W. 2019. Human-centric program synthesis. In
the middle events (between the first and last events of the PLATEAU Workshop @ UIST.
matched sequence) are permitted to occur in any chrono-
Eladhari, M. P. 2018. Re-tellings: the fourth layer of narra-
logical order. However, assuming an implicit total ordering
tive as an instrument for critique. In International Confer-
constraint allows us to simplify our approach to generating
ence on Interactive Digital Storytelling, 65–78. Springer.
both properties and setup clauses. In the future, we may seek
to relax this constraint, but to do so would require significant Garbe, J. 2018. Simulation of history and recursive narrative
modification to our current approach. scaffolding. project.jacobgarbe.com/simulation-of-history-
Like many learning approaches, our approach may overfit and-recursive-narrative-scaffolding.
when few examples are available. In preliminary testing with Kreminski, M., and Wardrip-Fruin, N. 2019. Genera-
an even smaller simulated storyworld, the system was prone tive games as storytelling partners. In Proceedings of the
to including properties in synthesized patterns that were in- 14th International Conference on the Foundations of Digi-
cidentally true of all examples but not part of our intent. tal Games.
This can be mitigated by users reviewing the synthesized Kreminski, M.; Samuel, B.; Melcer, E.; and Wardrip-Fruin,
sifting patterns and removing unintended clauses. Addition- N. 2019. Evaluating AI-based games through retellings.
ally, we may be able to help users debug overfitted patterns In Proceedings of the AAAI Conference on Artificial Intel-
by procedurally relaxing each clause of the pattern and pre- ligence and Interactive Digital Entertainment, volume 15,
senting the user with “almost matches”, inspired by Writing 45–51.
Buddy’s “almost actions” (Samuel, Mateas, and Wardrip- Kreminski, M.; Dickinson, M.; Mateas, M.; and Wardrip-
Fruin 2016). This could help users diagnose which clause Fruin, N. 2020a. Why Are We Like This?: Exploring writ-
of a synthesized pattern is responsible for overfit. ing mechanics for an AI-augmented storytelling game. In
Proceedings of the Electronic Literature Organization Con-
Conclusion ference.
We present a domain-specific inductive logic programming Kreminski, M.; Dickinson, M.; Mateas, M.; and Wardrip-
system capable of synthesizing story sifting patterns in the Fruin, N. 2020b. Why Are We Like This?: The AI archi-
tecture of a co-creative storytelling game. In Proceedings of ternational Conference on Interactive Digital Storytelling,
the Fifteenth International Conference on the Foundations 14–26. Springer.
of Digital Games. Ryan, J. 2018. Curating Simulated Storyworlds. Ph.D. Dis-
Kreminski, M.; Dickinson, M.; and Wardrip-Fruin, N. 2019. sertation, UC Santa Cruz.
Felt: a simple story sifter. In International Conference on Samuel, B.; Mateas, M.; and Wardrip-Fruin, N. 2016. The
Interactive Digital Storytelling, 267–281. Springer. design of Writing Buddy: a mixed-initiative approach to-
Liapis, A.; Yannakakis, G. N.; Alexopoulos, C.; and Lopes, wards computational story collaboration. In International
P. 2016. Can computers foster human users’ creativity? Conference on Interactive Digital Storytelling, 388–396.
Theory and praxis of mixed-initiative co-creativity. Digital Springer.
Culture & Education 8(2):136–153. Si, X.; Lee, W.; Zhang, R.; Albarghouthi, A.; Koutris, P.; and
Louchart, S.; Swartjes, I.; Kriegel, M.; and Aylett, R. 2008. Naik, M. 2018. Syntax-guided synthesis of Datalog pro-
Purposeful authoring for emergent narrative. In Joint In- grams. In Proceedings of the 2018 26th ACM Joint Meeting
ternational Conference on Interactive Digital Storytelling, on European Software Engineering Conference and Sympo-
273–284. Springer. sium on the Foundations of Software Engineering, 515–527.
Louchart, S.; Truesdale, J.; Suttie, N.; and Aylett, R. 2015. Summerville, A. 2018. Towards inductive logic program-
Emergent narrative, past, present and future of an interac- ming for game analysis: Leda. In Workshops at the Thirty-
tive storytelling approach. In Interactive Digital Narrative: Second AAAI Conference on Artificial Intelligence.
History, Theory and Practice. Routledge. 185–199.
Mateas, M., and Stern, A. 2000. Towards integrating plot
and character for interactive drama. In Working notes of the
Social Intelligent Agents: The Human in the Loop Sympo-
sium, 113–118. Menlo Park: AAAI Fall Symposium Series.
Muggleton, S., and De Raedt, L. 1994. Inductive logic pro-
gramming: Theory and methods. The Journal of Logic Pro-
gramming 19:629–679.
Muggleton, S., and Feng, C. 1992. Efficient induction of
logic programs. Inductive logic programming 38:281–298.
Muggleton, S. H.; Lin, D.; and Tamaddoni-Nezhad, A. 2015.
Meta-interpretive learning of higher-order dyadic datalog:
Predicate invention revisited. Machine Learning 100(1):49–
73.
Muggleton, S. 1995. Inverse entailment and progol. New
generation computing 13(3-4):245–286.
Odena, A., and Sutton, C. 2020. Learning to represent pro-
grams with property signatures. In International Conference
on Learning Representations (ICLR).
Quinlan, J. R. 1990. Learning logical definitions from rela-
tions. Machine learning 5(3):239–266.
Raghothaman, M.; Mendelson, J.; Zhao, D.; Naik, M.; and
Scholz, B. 2019. Provenance-guided synthesis of datalog
programs. Proceedings of the ACM on Programming Lan-
guages 4(POPL):1–27.
Rhodes, M.; Coupland, S.; and Cruickshank, T. 2010. En-
hancing real-time sports commentary generation with dra-
matic narrative devices. In Joint International Conference
on Interactive Digital Storytelling, 111–116. Springer.
Riedl, M. O., and Bulitko, V. 2013. Interactive narrative: An
intelligent systems approach. AI Magazine 34(1).
Ryan, J. O.; Summerville, A.; Mateas, M.; and Wardrip-
Fruin, N. 2015. Toward characters who observe, tell, mis-
remember, and lie. In Eleventh Artificial Intelligence and
Interactive Digital Entertainment Conference.
Ryan, J. O.; Mateas, M.; and Wardrip-Fruin, N. 2015. Open
design challenges for interactive emergent narrative. In In-