Towards Managing Epistemic Complexity in Narrative Games Jennifer Wellnitz Chris Martens mawellni@ncsu.edu martens@csc.ncsu.edu POEM Lab North Carolina State University Raleigh, North Carolina, USA Abstract Interactive narrative experiences can get complex: authors create combinatorial, generative play spaces that can grow to involve a number of states exponential in the number of story-world variables. When character beliefs are a key as- pect of game state, authoring and debugging are especially onerous, leading to game bugs in production. We explore this problem in the context of the interactive narrative game Elsi- nore. We present an application of Dynamic Epistemic Logic to model character belief update in Elsinore with the goal of controlling epistemic complexity. In principle, an epistemic logic engine should offload some of the manual effort in man- aging the knowledge effects of information sharing between characters. In practice, we find that our encoding fails to sig- nificantly reduce authoring complexity and bug-prone com- Figure 1: Screenshot of Elsinore’s primary interface for plexity from character belief management. We discuss why moving through the environments and observing conversa- this turns out to be the case and potential future directions. tions. INTRODUCTION nothing. Because some surprising behaviors are desirable Interactive narratives are a growing genre of published when creating emergent narrative experiences, we differen- games and an interesting area for games and AI research. tiate this kind of bug from unplanned event sequences that Many interactive narratives, as they become more complex, do not violate the rules of the world. feature a vast number of possible result states for any action, In this paper, we present our first steps towards this goal, based on a number of factors and decisions from elsewhere a case study of the game Elsinore. Elsinore (Golden Glitch in the story. These states can become difficult to manage, re- Studios 2019) is an interactive narrative game in which the quiring long chains of complicated preconditions and many player takes the role of Ophelia in the Shakespearean play versions of similar states that reflect the current state of the Hamlet. The story begins with the plot of Hamlet as writ- game in all of its detail. Manually authoring these states, ten, but then Ophelia is murdered instead of her canonical their associated actions and transitions, and their precondi- death by suicide. She then wakes up in her bed, realizing tions can be onerous, and can create bugs in the code. These that she is in a time loop that resets on her death. The player problems can be exacerbated in games where not all charac- is then tasked with manipulating the events of Hamlet to ters share the same information, vastly increasing the num- create a more favorable outcome for Ophelia and break the ber of factors to keep track of. time loop. Ophelia’s means of changing the story is an infor- In the long term, we want to minimize errors related mation exchange mechanic: as Ophelia moves through the to manual authoring of complex character belief changes. world, she can observe conversations and events (see fig- Specifically, we are interested in mitigating narrative logic ure 1), which are logged in a record the player can access bugs, in which the presence of behavior or the advance- (see Figure 2). She can then participate in conversations and ment to a game state is not permitted by the (often implicit) share certain elements of knowledge she has learned, called rules of the story world defined by the author, e.g. disabling Hearsay, with other characters—who in turn may change a player action that should be possible, performing an ac- their actions in response to new information (see Figure 3). tion that should be impossible, or learning information from A positive feedback loop is created by the fact that the Copyright c 2020 for this paper by its authors. Use permitted un- more information the player learns, the more ways they can der Creative Commons License Attribution 4.0 International (CC change the story, generating new events that reveal new in- BY 4.0). formation. Figure 2: Screenshot of Elsinore showing how the game reports knowledge updates for the player and NPC characters. mental model of that character’s knowledge. This is not an isolated instance; another tweet by Connor Fallon reads: So, @elsinoregame bug of the day: Polonius would pre- emptively arrest himself under certain conditions, go- ing to sulk in his jail cell before anyone actually locks him up. He’d still leave his cell to do errands, though. This bug also exemplifies problems in character beliefs — Polonius updates his behavior due to the beliefs and actions of other characters, but before the event that would logically change his character’s beliefs. Finally, in a tweet by one of the developers of Elsinore, Katie Chironis, says Figure 3: Screenshot of the hearsay mechanic in Elsinore, where topics in white can be shared with the NPC, and it would be a slight exaggeration to say that elsinore is greyed out topics are unavailable 9 billion if/else statements duct taped together, but only slightly. so... we’ll just keep adding more. This game meets our criteria as a large and intricate in- We refer to the complexity that creates character belief teractive narrative with a number of bugs arising from that update bugs such as these as epistemic complexity. Because complexity. Issues relating to the management of character of Elsinore’s epistemic complexity, we decided to try con- beliefs are particularly prevalent within Elsinore. Searching structing a model of the game in which the belief update me- Twitter for player bug reports reveals several, such as this chanics are managed with Dynamic Epistemic Logic (DEL), tweet by Amanda Gentzel: a formalism for reasoning about how agent beliefs change @elsinoregame Loving the game so far, but I think I over time in the presence of imperfect information and com- found a bug. It is Saturday night ( 11pm), and when I municative actions. DEL seems like a good fit for reason- selected to ask Horatio about my father’s murder, I told ing about Elsinore, not only because of the game’s reliance him I feared Hamlet ’may’ kill my father, and Horatio on belief update, but also because of how it conceptualizes said it was impossible. But my father is definitely dead time in terms of possible worlds, computing which events are possible or not in the current timeline. As such, the aim This bug deals with characters having inconsistent beliefs. for this project is to investigate DEL as a tool for manag- Whether it was in the writing of the dialogue or a bug in what ing epistemic complexity in Elsinore, testing the hypothesis conditions were being checked for that scene to play out, the that common bugs in the Elsinore game could be avoided by actions of the player’s character do not reflect the player’s using Dynamic Epistemic Logic to handle character beliefs. RELATED WORK APPROACH This research focuses on the potential use Dynamic Epis- Little work has been done to determine the efficacy of Dy- temic Logic for character belief management in the field of namic Epistemic Logic as basis or component for computa- interactive narrative. Dynamic Epistemic Logic is a logical tional and interactive narratives. However, other techniques system which represents imperfect information. It incorpo- have been employed to model narrative games, manage large rates actions that effect the genuine state of the world, as sets of characters in interactive narrative, and to reduce au- well as actions that reveal or obfuscate pieces of that world, thorial burden in these games. For example, Claire Wolf’s changing the beliefs of agents about which worlds they view The Teeny Tiny Mansion (TTTM) (Wolf 2017) is a simple as possible. model of an adventure game which is formally verified to be To represent Dynamic Epistemic Logic programmati- solvable. The aim of this project is not to create a playable cally, and in the context of a multiagent game, this project experience per se, but to prove that adventure games are able uses the Ostari language. Ostari is a language meant to fa- to be formally verified to be solvable. Though questions of cilitate multiagent interactions centering around incomplete solvability are not the aim of this paper, the genres of adven- knowledge and changing belief states (Eger and Martens ture games and interactive narrative are closely related, and 2017). Ostari is a computational implementation of the for- this project strives to do something similar to TTTM in cre- mal mathematical language Alexandru Baltag used to de- ating a model of an engine for character beliefs rather than a scribe Dynamic Epistemic Logic (Baltag 2002). This lan- fully playable experience. guage allows for agents to maintain a set of worlds they be- Other work into managing complex stories may focus lieve possible, and for actions to be defined that control the on different aspects of NPC interaction to improve upon, flow of information to those agents, revealing information rather than belief and knowledge management. Ware et al. to some and obfuscating it to others, causing those agents to frame the problem of managing NPCs in complex narrative consider more possible worlds from the uncertainty. as a story graph pruning problem (Ware et al. 2019). The This language is perfect to model the dynamics surround- aim presented by Ware is similar to the aim of this paper, ing information and belief in the Elsinore narrative. For ex- to manage complex narratives programmatically by using ample, Ophelia will continue to be murdered every loop un- a system to simplify some aspect of the NPCs that would til she finds a way to prevent it. When she discovers who otherwise have to be manually authored. However, where the murderer is, she will still continue to die until she alerts this paper does not address NPC actions in emergent narra- the guard captain and has him apprehend the killer. This is tive, Ware’s specifically simplifies the concept of NPC be- because the knowledge the player (and Ophelia) have is not lief states, showing that these methods of addressing similar the same as the knowledge that each character has. If the problems both have their limitations. guard captain doesn’t know who the killer is, he can’t act Much work has already been done to effectively man- on that information, even if the player does. Thus, the game age character beliefs in complex story environments that must keep track of varying levels of knowledge and beliefs doesn’t leverage Dynamic Epistemic Logic. For example, for each of the characters, something Ostari was built to do. Farrell proposed a system where character beliefs are han- Ostari alone, however, is primarily useful in simulating dled abstractly as action histories in the domain of story interactions between digital agents, not in interfacing with graph pruning (Farrell 2018). Although the intended domain those agents directly, and having a player become one the is different from that of this project, the underlying moti- characters. Thus this paper also makes extensive use of work vation is quite similar — to develop a method of managing done by Henry Mohr in using Ostari as an engine to facil- epistemic complexity in interactive narratives. This project itate player interaction within a narrative (Mohr, Eger, and focuses on offsetting the problem of managing belief states Martens 2018). Mohr’s work deals with using Ostari in tan- through the use of Dynamic Epistemic Logic and trigger- dem with Python to create mysteries that a player interacts ing distinct events in a story without tracking a full history, with to solve. Thus, the work done to interface with Ostari while Farrell’s project focuses on abstracting away from be- was instrumental in the ability to have a player take part in lief management through the use of action history as an anal- the narrative for this project. ogous but more efficient metric. The bulk of this research was done by building a model Finally, one of the main goals of this research is to limit of a small section of Elsinore using both Ostari and Python. the number of bugs introduced into an interactive narra- Python functions as a wrapper for Ostari and is charged with tive game by managing NPC belief states. Thus, this project both running the Ostari code and managing certain metadata seeks to simplify the authoring task for these games. While and world state information for the game itself. Ostari, on we present one method to do so, many others have been em- the other hand, defines the actions of the game, and man- ployed. James Thomas presents a novel system for interac- ages events — their effects and preconditions — as well as tive narrative authoring which employs a collaborative ap- character beliefs. proach to planning agents, giving some manual control to The majority of the functionality of the game is handled the author but otherwise streamlining the authoring task sig- by the Python layer, and the specific functionality of each nificantly (Thomas and Young 2006). While the system de- component is detailed in Figure 4. This includes handling scribed in this paper is significantly different, both belong player input, scheduling, and running the Ostari code on to a growing body of literature concerning assisted or pro- each ”turn” of the game. Essentially, time is stagnant ex- grammatic authoring of narratives. cept in relation to player action, so each turn is composed of Figure 4: Diagram of the overall system the player executing an action, and the game resolving the ing our system, all of these actions — except for wait — effects of that action. Depending on the action itself, new ac- are instantaneous. The only way to advance time is through tions may be put on the schedule or time may be advanced. the wait function. Further, no actual dialogue is displayed The Python code interfaces with Ostari by taking a template and hearsay is shared using specific codes to represent each of the Ostari code for the game, and replacing the list of ac- piece of information. These choices were made primarily tions to execute with the list of actions that have occurred because, although this model is fully playable, playing the thus far in the game. The Python layer then runs the Os- game through it does not facilitate the story in much detail. tari as a sub-process, and captures and interprets the output. Rather, this model is a simplified version of the game meant Thus, the Python code maintains a list of actions that have to help evaluate it, rather than a playable potion of the game occurred and reruns the Ostari on every player turn. itself. There are five gameplay actions available. The player may wait, tell hearsay to another character, view an event, go to another location, or query the status of another character (mostly for the purpose of experimentation rather than game Further, the design of this project was split into two stages play). These actions are described in more detail in Table 1. — skeleton and content. The skeleton makes up the me- For example, Figure 3 illustrates how player information chanics of the game, which could potentially be translated to and information sharing is handled in Elsinore. The image other games of a similar type. The content is an implementa- depicts the hearsay sharing mechanic in Elsinore, which is tion of a subset of the content within the Elsinore game such primarily how the player affects the game. Here the player that the mechanics of the skeleton can be tested in a genuine can see all of the pieces of information they have learned game and so the results can compared. While Elsinore con- throughout the game by observing events and talking with tains many locations and characters, for the purpose of this various NPCs. They can share certain pieces of this infor- paper some locations were collapsed into each other (result- mation with the character they’re speaking with to influence ing in the composite locations: Grounds/Docks, Lower Hall, the information that character knows, learn new information Upper Hall, Main Hall, and Courtyard) and only the char- from the resulting conversation, and possibly change that acters (Bernardo, Brit, Polonius, Laertes, and Hamlet) and character’s actions further down the timeline. All of this hap- events necessary such that the player can solve their mur- pens in the interface shown in Figure 3 and in the resulting der were included. This was to give a small cross section of conversation, and is played out directly in the game. the game for comparison while still focusing mainly on the By way of comparison, in the model of Elsinore built us- design of the mechanics. Action Ostari Elsinore Effect Wait User specifies an amount of time User holds a button while the Time fast forwards to wait, instantaneous shift in world speeds up time Tell User specifies a character and a User approaches a character and Character reacts to hearsay and Hearsay piece of hearsay chooses a piece of hearsay new events are scheduled/new hearsay is learned Observe User indicates that they want to User clicks on an icon above an Player may learn hearsay Event observe an event, event ends im- event, witnesses it play out in mediately real time Move Instantaneous travel Real time travel Player moves Query User specifies a character Information about characters is Player learns about a character seen in journal and map screens and sees their location Table 1: Action Comparison from Elsinore to Ostari Character Beliefs each of the characters’ beliefs and the state of the world, and The main purpose of Ostari in this project is to manage the may or may not involve the player. As events are often both beliefs of the game characters. In fact, the main purpose of the cause and effect of changes in the world, and the prod- this project is to see if managing character beliefs using Dy- uct of character beliefs, it was important to show how events namic Epistemic Logic is a viable alternative to hand author- were affected by the changes to belief representation. Within ing states and transitions in narratives which make heavy use this model, events are dealt with both on the Python and on of character beliefs. The Ostari code, dynamically generated the Ostari side. The Python layer contains metadata about by the Python layer, executes a series of actions which rep- the events like what time they take place and in what loca- resent all of the events that have happened from the start of tion. It also is responsible for deciding which events have the game to the present. Each of these actions are defined in occurred and adding them to the action queue to be run in the Ostari code, and executing them in the order that they Ostari. Ostari, on the other hand, has actions that represent occurred in the game results in a world states representing the preconditions and effects of each event, and when the each character’s beliefs at the current moment in the game. Python layer tells the Ostari to run an event, Ostari is what Python does pattern matching against the current state of the deals with the effects of that event occurring. world to determine which actions have their preconditions For each event, there are two actions in Ostari: one which met, but the tracking of agents beliefs about themselves and contains only the preconditions for the event and sets a pred- other agents is all internal to Ostari. icate indicating to the Python layer to schedule the event, Character beliefs had to be specifically authored to fit the and one that contains the effects of the event, and is sched- mechanics of Elsinore. Specifically, NPC characters have uled by the Python layer to execute the event. These pre- beliefs and goals, which represent their knowledge about conditions are typically a mix of character beliefs and world the world and their current drive respectively. Ophelia, the state information (who has died or left the castle and so on). main character, on the other hand, has pieces of information The effects set character beliefs, change the world state, and called hearsay which she can potentially share with NPCs to can give the player, should they be observing the event or be change their behavior and knowledge to advance the game. otherwise involved, new hearsay. These functionalities are Thus character beliefs are represented as objects of those split into two actions such that the Python can schedule an three categories: beliefs, goals, and hearsay. This was sim- event in advance of running it, rather than having to execute pler than representing the ideas in each of these beliefs using the full action when the preconditions for the event are met complex relationships (for example, defining primitive ac- (but before the time it was supposed to take place) or having tions within Ostari and expressing each belief as a conjunc- to check if each action was valid at every time step to avoid tion of these primitives), as the original games treated them missing one. as simple Boolean variables in terms of triggering events. Events in Python, on the other hand, contain all the infor- As such, the character beliefs are primarily used as pre- mation needed for the Python layer to schedule and eventu- conditions for scheduling events. Beliefs are formatted as ally execute the event. This includes a start time, stop time, Boolean variables and events use beliefs as preconditions to location, all of the characters involved, whether or not the mimic the original design philosophy of Elsinore. The aim player is inherently involved in the event, whether or not the of this research is to determine if managing these beliefs event results in a reset (player death), and the name of the with Dynamic Epistemic Logic cuts down on errors, and this event in Ostari. This data must be contained in Python be- section of functionality is the core addition of this research. cause timekeeping is handled in this layer and because all of that information is necessary to add the event dynami- Events cally to the Ostari code. However, as Python layer needs to The main building block of the narrative in Elsinore are pattern match against the current World state to determine events. Events are situations that arise due to the current state which events to schedule, Python must also maintain a list of preconditions for each event. Ostari not being compatible with the method of interactivity required for a game of this style, even much of the work sur- Scheduling rounding character beliefs was pushed to the Python layer. As stated earlier, the game runs off of a turn based model Determining which actions were now valid and scheduling where the player takes some action and the world responds should have, ideally, been in the domain of the Ostari layer, to it. Each response causes the Ostari layer to be rerun and but the capability simply wasn’t there. a new world state to be generated. From this world state, the On a different note, the narrative structure of Elsinore Python layer finds whichever events have not been sched- was not as compatible with the ideas of Dynamic Epistemic uled, completed or cancelled, and finds among them those Logic as initially thought. Though the story and gameplay events who’s preconditions have also been met and adds were largely dependent on the idea of incomplete infor- them to the schedule. mation and possible worlds, the actual story itself was too After each run of the Ostari layer, the Python layer iter- strictly authored to make full use of actions in Ostari as gen- ates through each of the possible events. Each event that is eral rules and not simply triggers for a structured sequence. not already scheduled, cancelled, or completed, and that has Initial plans included expressing each belief of characters all of its preconditions met, is added to the schedule. Fur- as some combination of generic predicates (kills(player, ther, this is also the stage where events are cancelled. If an player), etc), but because the original game used these be- event on the schedule is deemed impossible (mostly by the liefs as more of boolean triggers, and because events are al- presence of the impossible(event) predicate set by some ways structured and pre-authored rather than emergent, this other event), that event is removed from the schedule. This approach was quickly scrapped — it would simply make is only one way that events may be cancelled, the other is by preconditions needlessly laborious while not giving any real conflicts. benefit. In a game that focuses more on a generic or emer- To deal with the scheduling of events, the Python layer gent narrative, especially one that is procedurally generated, keeps track of a current master schedule. Events are added this approach is likely to be much more effective. and removed from this schedule as the game progresses and One of the key aims of this process was to determine if events are executed when observed by the player or when it helps to mitigate bugs. Unfortunately, it did not. Because the current time passes their end time on a wait action. Fur- events are so definite in this game, they essentially had to ther, when events conflict over resources, particularly over- be authored in Ostari much as they are in the original code lapping in time and requiring some of the same characters — with long chains of preconditions. As such, many of the present, the scheduling algorithm simply defaults to can- potential errors come from improper preconditions and im- celling the older event in lieu of the new. This behavior is proper effects, both of which are still distinctly possible in present in the original game as well and represents one’s this system. In fact, with two separate code bases and with plans being changed with new information. preconditions authored in both, inconsistencies may be more likely. CONCLUSIONS AND FUTURE WORK While this system may not work well for Elsinore, that Overall, the results of this research were inconclusive, but is partly the product of the type of game Elsinore is. Refer- this specific approach yielded little to no improvement over ring back to the bug found by Amanda Gentzel, where Ho- the original design. These results were partially caused by ratio’s dialogue doesn’t accurately reflect the current state the limitations of the interactivity of Ostari, but, beyond of the world or his current knowledge, that issue could be technical limitations, this project uncovered a significant in- caused by not checking the right preconditions in decid- compatibility between the structure of Elsinore and the ideas ing what scene plays when the player brings up that topic of Dynamic Epistemic Logic. with him, or it may be that dialogue for that specific situ- Although a similar approach to Henry Mohr’s work was ation did not exist at the time. The latter option highlights used to allow the player to interface with Ostari, the Os- an important limitation for our system — even if it handled tari language is still not particularly suited to complex user knowledge and preconditions perfectly, in a game like Elsi- interaction. This mostly is a result of the fact that Ostari nore, where the scenes are heavily scripted and pre-authored, cannot be interfaced with at runtime, but only have the re- the authors themselves still have to write all of the dialogue sults fetched after the program finishes. An early planned for every conceivable scene. Our system would not be able approach involved querying Ostari to determine which ac- to help prevent this bug. As such, our system would work tions are currently possible. This would have replaced hav- best in less story rich environments, where characters react ing Python track prerequisites and pattern match to schedule based on their beliefs but only from a pool of generic actions events. Would this functionality been possible, Ostari would rather than scripted scenes. A prime example of these types have been able to be responsible for more of the functional- of games would be The Sims series. ity of the game as a whole. Though this project was ultimately not successful, ele- Further, the Python layer ended up being responsible for ments of it have led to other potential avenues for research. a large proportion of the functionality of the game. The pur- One such avenue is an expansion of Ostari to incorporate pose of this project was to model the dynamics of informa- runtime intervention. Specifically, adapting Ostari to both tion amongst the characters solely through Ostari to deter- allow for user input (in the form of specifying actions to mine the efficacy of Dynamic Epistemic Logic in represent- be executed) and querying of world state, possible actions, ing those ideas in a narrative, but with the functionality of and so forth during runtime, between actions would suffice. These alterations would give more fine tuned control in ex- ecuting Ostari code, as well as open up a whole new type of game to be viable under the Ostari language. Finally, though the content portion is specific to modelling Elsinore, the skeleton used to adapt the content is suitably generic to be useful in other similar, albeit a bit less struc- tured, narratives. This skeleton could serve as a tool to both interface with Ostari and to design more emergent narratives which could make use of Ostari’s unique system of charac- ter beliefs. Hopefully, this tool could be used to do further research into how Dynamic Epistemic Logic pairs with in- teractive narratives. References Baltag, A. 2002. A logic for suspicious players: Epistemic actions and belief–updates in games. Bulletin of Economic Research 54(1):1–45. Eger, M., and Martens, C. 2017. Practical specification of belief manipulation in games. In Thirteenth Artificial Intel- ligence and Interactive Digital Entertainment Conference. Farrell, R. 2018. Experience management with beliefs, de- sires, and intentions for virtual agents. In Fourteenth Artifi- cial Intelligence and Interactive Digital Entertainment Con- ference. Golden Glitch Studios. 2019. Elsinore. Published online. Mohr, H.; Eger, M.; and Martens, C. 2018. Eliminating the impossible: A procedurally generated murder mystery. In AIIDE Workshops. Thomas, J. M., and Young, R. M. 2006. Author in the loop: Using mixed-initiative planning to improve interactive nar- rative. In Workshop on AI Planning for Computer Games and Synthetic Characters. Ware, S. G.; Garcia, E. T.; Shirvani, A.; and Farrell, R. 2019. Multi-agent narrative experience management as story graph pruning. In Proceedings of the AAAI Conference on Artifi- cial Intelligence and Interactive Digital Entertainment, vol- ume 15, 87–93. Wolf, C. 2017. The teeny tiny mansion (tttm). Technical report, University of Applied Arts Vienna.