Role of Drama Management in Interactive Narrative 

A review of “Declarative Optimization-Based Drama Management in Interactive Fiction”

Interactive Storytelling or Interact Narrative is one of the digital entertainment products of Artificial Intelligence which has been in practice for quite a long period of time(almost a 40-year history, as quoted in Wikipedia) though it has not been very famous as the other facets of AI till now. To briefly introduce, it’s a genre of intelligent games in which the player interacts with the system by writing in his moves and the outputs and the scene is also shown to him as a description of what’s happening. Due to it’s inherent complexity in understanding human language and typical style of having more than one definite ending of the story, it becomes increasingly complex to design such games as the size of the story explodes. Most of the earlier research in this field greatly failed to deliver on it’s promises and most of them got abandoned in the swirling waves of technology. However, a notable amount of research has been devoted to this field and with the new emerging NLP techniques like Deep Convolutional Neural Networks, we can now look forward to this field in a new direction and with a higher hope. In the aforementioned work of Mark J. Nelson and his co-authors, they have explored some of the aspects of Interactive Narrative related to it’s storyline controlling and evaluation testbeds. One of the most important aspects of such system is controlling the interactions between the system and the player and suggest corresponding storyline branching as accurately and efficiently as possible. Traditionally, this is done using condition-action rules and local triggers which are very inefficient when we scale up the storyline to a larger extent. It also has difficulties capturing the bigger pictures relating to the full control over the gameplay dynamics. In their paper, they explored the concepts of a special approach for storyline controlling called Drama Management(DM), which helps the system to adapt to the player’s moves by changing and reconfiguring the world as the story progresses. This drama management is formally encapsulated under the bigger umbrella of Declarative optimization-based drama management(DODM) which according to him guides the player by projecting possible future stories and reconfiguring the story world based on those projections. One subset of DODM is search-based drama management(SBDM), which is kind of the principle focus of his paper. The authors very carefully and comprehensively describe almost all of the aspects of SBDM in Interactive Storytelling and also provides an elaborate test bed for evaluation of such implementations. Finally, he also shows some interesting shortcomings he discovered for the SBDM paradigm and tried solving this using some Reinforcement Learning approaches, which gives a very useful and strong platform for future research as we are slowly moving towards Reinforcement Learning approaches in many of the AI related domains.

Approaches and the game under experiment: 

The principle idea behind DM is very similar to almost all kinds of Machine Learning models, i.e. to modify the world of the story according to player moves which maximize a particular evaluation function. The authors argue that this typical constraint bases optimization paradigm is very effective for the problem domain under consideration. SBDM, which is a special approach for DODM as already mentioned, uses a search based optimization approach using a traditional game tree search variant. 

The game this paper explores is a horror fiction piece named “Anchorhead” authored by Michael S. Gentry. The original game is quite large and spans over a gameplay of almost 5 days which the researchers under discussion modified to suit their own needs for initial experimentation. In a nutshell, the final modified game had two main subplots, each leading to a different ending based on player actions. We refrain from providing any more details about the game due to space constraints here. As a connection to previous works, a scientist named Weyhrauch did some initial experimentations on all the aspects of DODM in general in a game called “Tea for Three”. Matias and Stern used beat based Drama manager in their game “Faaçde”. However, according to the authors of our paper, all the previous works were done on games of relatively lower scale than “Acnhorhead” and they argue that to what extent previous results could be generalized or scaled was not clear. We feel that the authors pretty much proved their arguments in their work as they very successfully formalized their notions throughout the paper which we will see in the next sections.

Authorial tasks of Drama Management:

The main authorial task of DM is to discretize the continuous story stream of the narrative and project it into an abstract space of something called “plot points” which is the basic parameter on which all the optimizations take place. The authors describe how they had adapted the previous architecture of using directed acyclic graphs introduced by Weyhrauch and extended it further. They very cleverly describe the AND-OR planning graph architecture for the same with relevant examples and drilled into the details of the granularities of the plot points mapping and its effects. Apart from deciding on the level of details, they also talked about maintaining the model of the player and how it can help in providing more efficient hints and storyline control for the DM.

Once we decide on the plot points and the corresponding graphs, next thing we have to do is specifying the different actions the Drama manager can take on. These are the modifications the DM does at runtime to control the execution sequence of the story. We see it as one of the most crucial aspects of DM as they control the main gameplay mechanics of the Game. Authors talked about mainly 5 kinds of DM actions namely permanent deniers, temporary deniers, causers, hints and game endings. All these different set of actions are very well described in the paper with relevant examples from “Anchorhead” and gives a strong foundation for the upcoming discussions. We feel, anyone who is working on DM must have a very clear understanding of these actions and the authors did a great job by introducing them in a fine tuned and concise manner. They also describe some issues they ran into while using DM actions in Anchorhead and how they tackled those. One example which we feel worth mentioning here is the introduction of constraints like “must-follow” and “must-follow-location” in DM actions which helped them overcome the location dependency issues due to bigger size of Anchorhead as compared to earlier experimental games like Tea for Three. By this point of the paper, the readers get a very clear overview of a DM and the authors carefully proceed to the next sections where he talks about the evaluation functions. These functions are defined at each plot point of the story and those are used by DM to decide on the best course of action during the gameplay. This approach is often more effective in action as compared to the author manually specifying all possibilities of the gameplay in advance. The runtime scoring and decisions taken on the basis of those scores can project the decision making in a higher dimensional and complex space which a human can never foresee while writing the story. The authors conclude the sections with some very brief introduction to the general properties of the stories and issues related to multiple endings. At this point, we felt that the description of multiple ending related aspects was little incomplete and leave lots of potential for more explanations. Driving the game climax is one of the most crucial functionalities these systems must handle, so a little more elaborate description would have been gold. Finally, he wraps up with impact of choices and manipulatively in DM.

Experiments and Final thoughts:

The game tree search used by SBDM is essentially similar to traditional Minimax implementation with a small difference that here the player doesn’t act as an absolute adversary to the DM, rather it is more of a random in nature. The author describes two different approaches of evaluation which Weyhrauch used for evaluation DM on Tea for Three and shows the comparisons and other aspects connecting to Anchorhead. The first approach was to search the whole tree with a memoized algorithm which was easy in the case of Tea of Three as it was a relatively small game. But for Anchorhead, it was almost impossible due to it’s much bigger search space. The second method deployed was called Sampling Adversarial Search(SAS) which performs a search on a smaller version of the main game tree. Overall they saw that the results for Anchorhead were not very much promising. In a particular scenario, he even observed that incorporating DM was giving a worse result as compared to no DM. This was primarily dependent on the course of the story and some storyline paths being dominated by a particular kind of DM actions which contributed to these results. Apart from these, they also tried some reinforcement learning approaches which relies on offline computational power rather than banking everything on runtime calculations. The used something called Temporal Difference Learning(TD) which the authors have very vaguely described and if anyone is interested in knowing more about this approach, they must dig into the other relevant literature of the same. They also show the similarities and differences between the search based methods and reinforcement learning methods and argues that reinforcement learning consistently performed well to the extent they tested. However, they explored very little about the latter approaches and humbly describes room for future exploration. All the experiments performed on Anchorhead were tuned to the step-down version of the game, a real world exposure to the game will be another great future direction of research. Also, the paper didn’t exploit much on the player modeling aspects. Finally, we feel that in the very beginning of the paper, there should have been a little introduction to the Interactive Narrative in general so that the absolute beginners can get a rough overview of the genre. Overall, we must say that it’s a great piece of work considering the meticulous details of the subject matter presented and it’s depth of explanations, and is definitely a must read for anyone diving into this field.

NB: The article is a critique on Roberts, D. L., & Isbell Jr, C. L. Declarative Optimization-Based Drama Management in Interactive Fiction.