Meaningful choice has often been identified as a key component in a player's engagement with an interactive narrative, but branching stories require tremendous amounts of hand-authored content, in amounts that increase exponentially rather than linearly as more choice points are added. Previous approaches to reducing authorial burden for computer RPGs have relied on creating better tools to manage existing unwieldy structures of quests and dialogue trees. We hypothesize that reducing authorial burden and increasing agency are two sides of the same coin, requiring specific advancements in two related areas of design and technology research: (1) dynamic story management architecture that represents story events abstractly and allows story elements to be selected and re-ordered in response to player choices, and (2) dynamic dialogue generation to allow a single story event to be revealed differently by different characters and in the context of dynamic relationships between those characters and the player. This paper describes SpyFeet, a playable prototype of a storytellingsystem designed to test this hypothesis.

In this paper, we are considering advanced pathplanning problems that feature finding paths for multiple units subject to rich path constraints. Examples of richer constraints are the following of other units or to stay out of sight of a specific unit. Little attention has so far been given to richer pathplanning problem where the objective is more than reaching a specific destination from a starting point such that the path length is minimized. Richer pathplanning problems occur in many complex real-world scenarios, ranging from computer games to military movement planning. In this paper, a novel way to formally specify such problems and a new local-search strategy to solve such problems are proposed and demonstrated by a prototype implementation. Among the design goals are real-time computability as well as extendibility for new constraints and search heuristics.

A growing issue in the development of realistic and entertain-ing interactive games is the need for mechanisms that support ongoing natural language conversation between human players and artificial non-player characters. Unfortunately, many methods for implementing natural language generation(NLG) induce a significant burden on the author, do not scale well, or require specialized linguistic knowledge. We formalize the notion of typed-templates, an extension of standard structures employed in template-based NLG. We further provide novel algorithms that, when applied to typed-templates, ameliorate the above issues by affording computational support for authoring and increased variation in utterance and scenario generation. We demonstrate the efficacy of typed-templates and the algorithms through a user study.

In this work, we look at the challenge of learning in an action game,Infinite Mario. Learning to play an action game can be divided intotwo distinct but related problems, learning an object-relatedbehavior and selecting a primitive action. We propose a framework that allows for the use of reinforcement learning for both ofthese problems. We present promising results in some instances of thegame and identify some problems that might affect learning.

This paper presents a search-based approach to generating game content that satisfies both gameplay requirements and user-expressed aesthetic criteria. Using evolutionary constraint satisfaction, we search for spaceships (for a space combat game) represented as compositional pattern-producing networks. While the gameplay requirements are satisfied by ad-hoc defined constraints, the aesthetic evaluation function can also be informed by human aesthetic judgement. This is achieved using indirect interactive evolution, where an evaluation function re-weights an array of aesthetic criteria based on the choices of a human player. Early results show that we can create aesthetically diverse and interesting spaceships while retaining in-game functionality.

Probabilistic models were fit to logs of player actions in the card game Dominion in an attempt to find evidence of personality types that could be used to classify player behavior as well as generate probabilistic bot behavior. Expectation Maximization seeded with players' self-assessments for their motivations was run for two different model types — Naive Bayes and a trigram model — to uncover three clusters each. For both model structures, most players were classified as belonging to a single large cluster that combined the goals of splashy plays, clever combos, and effective play, cross-cutting the original categories — a cautionary tale for research that assumes players can be classified into one category or another. However, subjects qualitatively report that the different model structures play very differently, with the Naive Bayes model more creatively combining cards.

Hiding and seeking is a cognitive ability frequently demonstrated by humans in both real life and video games. We use machine learning to automatically construct the first computational model of hide/seek behavior in adult humans in a video game like setting. The model is then run generatively in a novel environment and its behavior is found indistinguishable from actual human behavior by a panel of human judges.  In doing so the artificial intelligence agent using the model appears to have passed a version of the Turing test for hiding and seeking.

In this paper, we apply the idea of testing games by learning interactions with them that cause unwanted behavior of the game to test the competition entries for some of the scenarios of the 2010 StarCraft AI competition. By extending the previously published macro action concept to include macro action sequences for individual game units, by adjusting the concept to the real-time requirements of StarCraft, and by using macros involving specific abilities of game units, our testing system was able to find either weaknesses or system crashes for all of the competition entries of the chosen scenarios. Additionally, by requiring a minimal margin with respect to surviving units, we were able to clearly identify the weaknesses of the tested AIs.

Massive Multiplayer Online Strategy games present several unique challenges to players and designers. There is the need to constantly adapt to changes in the game itself and the need to achieve a certain level of simulation and realism, which typically implies battles involving combat with several distinct armies, combat phases and diferent terrains; resource management which involves buying and selling goods and combining lots of diferent kinds of resources to fund the player's nation and cutthroat diplomacy which dictates the pace of the game. However, these constant changes and simulation mechanisms make a game harder to play, increasing the amount of effort required to play it properly. As some of these games take months to be played, players who become inactive have a negative impact on the game. This work pretends to demonstrate how to create versatile agents for playing Massive Multiplayer Online Turn Based Strategy Games, while keeping close attention to their playing performance. In a test to measure this performance the results showed similar survival performance between humans and AIs.

Conflict is an essential element of interesting stories, but little research in computer narrative has addressed it directly. We present a model of narrative conflict inspired by narratology research and based on Partial Order Causal Link (POCL) planning. This model informs an algorithm called CPOCL which extends previous research in story generation. Rather than eliminate all threatened causal links, CPOCL marks certain steps in a plan as non-executed in order to preserve the conflicting subplans of all characters without damaging the causal soundness of the overall story.