This document summarises my research in the area of Real-Time Strategy (RTS) video game Artificial Intelligence (AI). The main objective of this research is to increase the quality of AI used in commercial RTS games, which has seen little improvement over the past decade. This objective will be addressed by investigating the use of a learning by observation, case-based reasoning agent, which can be applied to new RTS games with minimal development effort. To be successful, this agent must compare favourably with standard commercial RTS AI techniques: it must be easier to apply, have reasonable resource requirements, and produce a better player. Currently, a prototype implementation has been produced for the game StarCraft, and it has demonstrated the need for processing large sets of input data into a more concise form for use at run-time.

The problem of optimal planning under uncertainty in collaborative multi-agent domains is known to be deeply intractable but still demands a solution. This thesis will explore principled approximation methods that yield tractable approaches to planning for AI assistants, which allow them to understand the intentions of humans and help them achieve their goals. AI assistants are ubiquitous in video games, mak- ing them attractive domains for applying these planning techniques. However, games are also challenging domains, typically having very large state spaces and long planning horizons. The approaches in this thesis will leverage recent advances in Monte-Carlo search, approximation of stochastic dynamics by deterministic dynamics, and hierarchical action representation, to handle domains that are too complex for existing state of the art planners. These planning techniques will be demonstrated across a range of video game domains.

Narrative Intelligence (NI) can help computational systems interact with users, such as through story generation, interactive narratives, and believable virtual characters. However, existing NI techniques generally require manually coded domain knowledge, restricting their scalability. An approach that intelligently, automatically and economically acquires script-like knowledge in any domain with strategic crowdsourcing will ease this bottleneck and broaden the application territory of narrative intelligence. This doctoral consortium paper defines the research problem, describes its significance, proposes a feasible research plan towards a Ph.D. dissertation, and reports on its current progress.

My research involves creating and evaluating adaptive gameenvironments using player models created using data-driventechniques and algorithms. I hypothesize that I will be able tochange parts of a game to elicit certain behaviors from players,and that these changes will also result in an increase ofengagement and/or intrinsic motivation.

The field of game AI is largely industry driven, lacking an agreed upon formalism for AI representation. Ad-hoc scripting languages, simple finite state machines, behaviour trees, and planners are employed, but not in a fashion adhering to any standard. As a result, reuse is sparse between games and formal analysis techniques are undeveloped. As research for a Ph.D. thesis, we propose to show that a layered Statechart-based AI is a suitable formalism for Game AI, enabling the use of model-driven development techniques such as reuse and high-level analysis including model-checking. The fundamentally modular nature of this approach leads naturally to reuse as a fundamental component of the design process. Supported by a clearly defined formalism, useful behavioural analyses become possible, such as testing reactions to various inputs at design time. We also explore transformations at the modelling level to enable procedural generation, allowing rapid deployment of varying AIs. Additionally, such a model allows for the generation of efficient code that can be directly inserted into games. Tool support for reuse, generation, and analysis will be developed, then employed in creating an industrial scale AI, proving that this formalism is appropriate for industrial use.

Most systems for generating cinematic shot sequences for virtual environments focus on the low-level problems of camera placement. While this approach will create a sequence of camera shots which film individual events in a virtual environment, it does not account for the high-level effects shot sequences have on viewer inferences. There are systems which are based on well known cinematography principles such as the rule of thirds and other framing principals, however these usually utilize schemas or predefined shots and do not reason about the high level cognitive effects on the viewer. In this paper a system is proposed which can reason directly about these high-level cognitive and narrative effects of a shot sequence on the viewer’s mental state.

Authoring narrative content for interactive digital media can be both difficult and time consuming.The research proposed here aims at enhancing the capabilities of content creators through the development of a computational model that improves the quality of automatically generated stories, potentially decreasing the burden placed on the author. The quality and believability of a story can be significantly enhanced by the presence of compelling characters. To achieve this objective, I aim to develop a choice-based computational model that facilitates the automatic generation of narrative that includes characters that are made more compelling by the presence of distinct personality characteristics.

In this demo we present a visualization of formalized representations of story. Introducing the interactive to storytelling requires the management of experiences that a user creates by their decisions. These sorts of variations can have impact on not only the user, but also the retrievable content appropriate to present to the user. The overall contribution of this work is to identify the player impact of story variation by modeling supplementary variations, and systematically responding to player interaction through supplementary variation, while respecting the author’s intentions by maintaining the integrity of the core story skeleton.

KGoldrunner is a puzzle-oriented platform game with dynamic elements. This paper describes Goldspinner, an automatic level generation system for KGoldrunner. Goldspinner has two parts: a genetic algorithm that generates candidate levels, and simulations that use an AI agent to attempt to solve the level from the player's perspective. Our genetic algorithm determines how "good" a candidate level is by examining many different properties of the level, all based on its static aspects. Once the genetic algorithm identifies a good candidate, simulations are performed to evaluate the dynamic aspects of the level. Levels that are statically good may not be dynamically good (or even solvable), making simulation an essential aspect of our level generation system. By carefully optimizing our genetic algorithm and simulation agent we have created an efficient system capable of generating interesting levels in real time.

In this paper, we present adaptive quests, an extension to the dominant quest model that guides and motivates gameplay in MMORPG shared worlds. The standard model has proven effective, but is significantly incompatible with the desire for player driven change in the world. We present an incremental step to increasing player impact, discuss the problems it creates with the quest model, and show how adaptive quests can help reconcile the two. We present simulation experiments supporting not only that adaptive quests help mitigate those problems, but that they can actually improve them over the standard model.