Alexander Zook. Automated Iterative Game DesignPh.D. Dissertation, Georgia Institute of Technology, 2016.

    Iterative game design is a process for refining the design of a game through a process of: (1) creating a base game; (2) playtesting the game to gather examples of people playing the game; (3) evaluating playtest outcomes to assess how well the game meets design goals; and (4) choosing a way to iterate on the game design to better achieve desired design goals. Developing computational models of this process holds great potential value for informing our understanding of iterative game design and automating aspects of this practice. In this thesis I develop a set of systems to automate the iterative game design process.

    The central statement of this thesis is:

      Explicitly modeling the actions in games as planning operators allows an intel- ligent system to reason about how actions and action sequences affect game- play and to create new mechanics. An intelligent system facilitates human iterative game design by learning design knowledge about gameplay and re- ducing the number of design iterations needed during playtesting a game to achieve a design goal.
    I demonstrate general game generation through developing a modular, mechanic-centric representation for games across genres that allows a system to reason about how players are able to achieve a variety of outcomes. This approach enables a system to generate games given only a specification of success and failure criteria for a genre and a modu- lar specification of the mechanics for a genre. To enable general game playing I apply Monte-Carlo Tree Search (MCTS) as a domain-agnostic game playing algorithm, using the computational bounds of the search as a proxy for varying human capabilities to play games. To evaluate the space of play in games I develop a taxonomy of four types of met- rics for actions taken in games, showing how these metrics reveal strengths and defects in the design of two games to support differentiation among the general game playing agents using MCTS. These evaluations showcase how these metrics can reveal where games support differentiation of player skills through design, in turn demonstrating their utility for design evaluation. This evaluation approach for design iteration is further supported with evaluation of the design space of a game by generating a range of game design variants and evaluating hypotheses about how different design choices influence player behavior in terms of the action metrics. The range of design variants supports direct optimization to choose the best design variant to achieve a design goal. A system is also able to learn pre- dictive models for how changes to game design features in a card game result in changes in how actions are used, as measured by the previous action metrics. Finally, I apply tech- niques from optimal experimental design to show how a system can choose new design variants sequentially to balance the trade-off between optimizing the quality of a design against a design goal and exploring alternative designs to seek out the generally best de- sign. By comparing a variety of techniques across two design optimization goals I illustrate the general applicability of this approach to enabling efficient design iteration.

Hong Yu. A Data-Driven Approach for Personalized Drama Management. Ph.D. Dissertation, Georgia Institute of Technology, 2015.

    An interactive narrative is a form of digital entertainment in which players can create or influence a dramatic storyline through actions, typically by assuming the role of a character in a fictional virtual world. The interactive narrative systems usually employ a drama manager (DM), an omniscient background agent that monitors the fictional world and determines what will happen next in the players’ story experience. Prevailing approaches to drama management choose successive story plot points based on a set of criteria given by the game designers. In other words, the DM is a surrogate for the game designers.

    In this dissertation, I create a data-driven personalized drama manager that takes into consideration players’ preferences. The personalized drama manager is capable of (1) modeling the players’ preference over successive plot points from the players’ feedback; (2) guiding the players towards selected plot points without sacrificing players’ agency; (3) choosing target successive plot points that simultaneously increase the player’s story preference ratings and the probability of the players selecting the plot points.

    To address the first problem, I develop a collaborative filtering algorithm that takes into account the specific sequence (or history) of experienced plot points when modeling players’ preferences for future plot points. Unlike the traditional collab- orative filtering algorithms that make one-shot recommendations of complete story artifacts (e.g., books, movies), the collaborative filtering algorithm I develop is a sequential recommendation algorithm that makes every successive recommendation based on all previous recommendations. To address the second problem, I create a multi-option branching story graph that allows multiple options to point to each plot point. The personalized DM working in the multi-option branching story graph can influence the players to make choices that coincide with the trajectories selected by the DM, while gives the players the full agency to make any selection that leads to any plot point in their own judgement. To address the third problem, the person- alized DM models the probability that the players transitioning to each full-length stories and selects target stories that achieve the highest expected preference ratings at every branching point in the story space.

    The personalized DM is implemented in an interactive narrative system built with choose-your-own-adventure stories. Human study results show that the personalized DM can achieve significantly higher preference ratings than non-personalized DMs or DMs with pre-defined player types, while preserve the players’ sense of agency.

Boyang Li. Learning Knowledge to Support Domain-Independent Narrative Intelligence. Ph.D. Dissertation, Georgia Institute of Technology, 2014.

    Narrative Intelligence is the ability to craft, tell, understand, and respond appro- priately to narratives. It has been proposed as a vital component of machines aiming to understand human activities or to communicate effectively with humans. However, most existing systems purported to demonstrate Narrative Intelligence rely on manually authored knowledge structures that require extensive expert labor. These systems are constrained to operate in a few domains where knowledge has been provided.

    This dissertation investigates the learning of knowledge structures to support Nar- rative Intelligence in any domain. I propose and build a system that, from an corpus of simple exemplar stories, learns complex knowledge structures that subsequently en- able the creation, telling, and understanding of narratives. The knowledge representation balances the complexity of learning and the richness of narrative applications, so that we can (1) learn the knowledge robustly in the presence of noise, (2) generate a large variety of highly coherent stories, (3) tell them in recognizably different narra- tion styles and (4) understand stories efficiently. The accuracy and effectiveness of the system have been verified by a series of user studies and computational experiments.

    As a result, the system is able to demonstrate Narrative Intelligence in any domain where we can collect a small number of exemplar stories. This dissertation is the first step toward scaling computational narrative intelligence to meet the challenges of the real world.

Brian O'Neill. A Computational Model of Suspense for the Augmentation of Intelligent Story Generation. Ph.D. Dissertation, Georgia Institute of Technology, 2013.

    Narrative as entertainment plays a central role in many forms of entertainment media, including novels, movies, games, and theatre. One of the reasons for the prevalence of storytelling in human culture may be due to the way in which narrative is used as a cognitive tool for situated understanding. Expert storytellers who craft narratives for entertainment structure their narratives to be aesthetically pleasing to the audience. Computer scientists have tried for more than three decades to determine whether, and how, intelligent computational systems can create aesthetically pleasing narratives from scratch. One of the many tools that expert storytellers use to make stories aesthetically pleasing is suspense.

    In this dissertation, I present Dramatis, a computational human behavior model of suspense based on Gerrig and Bernardo’s definition of suspense. In this model, readers traverse a search space on behalf of the protagonist, searching for an escape from some oncoming negative outcome. As the quality or quantity of escapes available to the protagonist decreases, the level of suspense felt by the audience increases. The major components of Dramatis are a model of reader salience, used to determine what elements of the story are foregrounded in the reader’s mind, and an algorithm for determining the escape plan that a reader would perceive to be the most likely to succeed for the protagonist. I evaluate my model by comparing its ratings of suspense to the self-reported suspense ratings of human readers. Additionally, I demonstrate that the components of the suspense model are sufficient to produce these human- comparable ratings.

    Additionally, I present an approach for knowledge engineering based on qualita- tive methods. Dramatis is a knowledge-intensive system, requiring representations of actions in the world and readers’ genre knowledge. This qualitative knowledge engineering methodology allows for the conversion of a natural language corpus into a collection of knowledge structures in a way that mitigates engineer bias. Knowledge engineers annotate the corpus using an iterative coding process. These annotations then provide context for the creation of knowledge structures.

Mark O. Riedl. Narrative Generation: Balancing Plot and Character. Ph.D. Dissertation, North Carolina State University, 2004.

    The ability to generate narrative is of importance to computer systems that wish to use story effectively for a wide range of contexts ranging from entertainment to training and education. The typical approach for incorporating narrative into a computer system is for system builders to script the narrative features at design time. A central limitation of this pre- scripting approach is its lack of flexibility -- such systems cannot adapt the story to the user’s interests, preferences, or abilities. The alternative approach is for the computer systems themselves to generate narrative that is fully adapted to the user at run time.

    A central challenge for systems that generate their own narrative elements is to create narratives that are readily understood as such by their users. I define two properties of narrative – plot coherence and character believability – which play a role in the success of a narrative in terms of the ability of the narrative’s audience to comprehend its structure. Plot coherence is the perception by the audience that the main events of a story have meaning and relevance to the outcome of the story. Character believability is the perception by the audience that the actions performed by characters are motivated by their beliefs, desires, and traits.

    In this dissertation, I explore the use of search-based planning as a technique for generating stories that demonstrate both strong plot coherence and strong character believability. To that end, the dissertation makes three central contributions. First, I describe an extension to search-based planning that reasons about character intentions by identifying possible character goals that explain their actions in a plan and creates plan structure that explains why those characters commit to their goals. Second, I describe how a character personality model can be incorporated into planning in a way that guides the planner to choose consistent character behavior without strictly preventing characters from acting “out of character” when necessary. Finally, I present an open-world planning algorithm that extends the capabilities of conventional planning algorithms in order to support a process of story creation modeled after the process of dramatic authoring used by human authors. This open-world planning approach enables a story planner not only to search for a sequence of character actions to achieve a set of goals, but also to search for a possible world in which the story can effectively be set.

    The planning algorithms presented in this dissertation are used within a narrative generation system called Fabulist. Fabulist generates a story as a sequence of character actions and then recounts the story by first generating a discourse plan that specifies how the story content should be told and then realizing the discourse plan in a storytelling medium. I present the results of an empirical evaluation that demonstrates that narratives generated by Fabulist have strong plot coherence and strong character believability. The results clearly indicate how a planning approach to narrative generation that reasons about plot coherence and character believability can improve the audience’s comprehension of plot and character.