Players begin games at different skill levels and develop their skill at different rates—so that even the best-designed games are uninterestingly easy for some players and frustratingly difficult for others. A proposed answer to this challenge is Dynamic Difficulty Adjustment (DDA), a general category of approaches that alter games during play, in response to player performance. However, nearly all these techniques are focused on basic parameter tweaking, while the difficulty of many games is connected to aspects that are more challenging to adjust dynamically, such as level design. Further, most DDA techniques are based on designer intuition, which may not reflect actual play patterns. Responding to these challenges, we have created Polymorph, which employs techniques from level generation and machine learning to understand level difficulty and player skill, dynamically constructing levels for a 2D platformer game with continually-appropriate challenge. We present the results of the user study on which Polymorph's model of level difficulty is based, as well as a discussion of the unique features of the model. We believe Polymorph creates a play experience that is unique because the changes are both personalized and structural, while also providing an example of a new application of machine learning to aid game design.

Team coordination of non-player characters can create a deeper sense of immersion in real-time games by allowing characters to work together to produce better tactics and strategy. Achieving multi-agent coordination can be a difficult problem, and can incur substantial computational costs. Our goal with this work is to produce a reactive method for coordinating game characters that will allow computationally inexpensive team coordination. Reactive teaming creates teams of agents through the use of simple constant-time agent interactions without increasing the difficulty of authoring game characters.

We have developed and demonstrated an experimental authoring and run-time tool, called Disco for Games, that supports the creation of games in which dialogue and action are integrated without the need for changing modes. This tool is based on collaborative discourse theory and hierarchical task networks, in which utterances are treated as actions, and has a number of additional benefits including better modeling of interruptions, automatic dialogue generation, plan recognition and automatic failure retry.

Game environments are becoming more and more mutable from the actions of both Players and Non Player Characters (NPCs). However, current generation AI agents do not take advantage of the tactical abilities these mutable worlds provide. We propose a method to make the game agents aware of the mutability of the world by extending their repertoire of abilities to include world alteration commands and some evaluation functions, which determine when and where to alter the world for the greatest tactical gain. Primarily, our work focuses on the Adversarial Navigation Mesh Alteration (ANMA) algorithm, which evaluates potential changes to the map in adversarial environments from an attacker and defender point of view. We present an empirical evaluation of the ANMA algorithm in a Capture The Flag (CTF) simulation environment with several teams of agents. One group of agents (adaptive) lacks the ability to initiate world deformations, but they can respond and re-plan to take advantage of world modifications. The second team of agents (builders) can only generate additional paths through the world using the attacker portion of ANMA. The third team of agents (universal) is able to fully deform the world by generating new paths or removing existing paths using both the attacker and defender sections of ANMA. We evaluated these teams and observed that builder agents beat adaptive agents at a rate of 1.33 to 1. The more advanced universal agents beat adaptive agents at a rate of 2.75 to 1 and builder agents 1.4 to 1.

Massively Multiplayer Online Games (MMOGs), in their aspect as online communities, represent an exciting opportunity for studying social and behavioral models.  For that purpose we have developed Cosmopolis, a free MMOG containing several key research-oriented features.  First, Cosmopolis consists of an outer game for larger-scale social modeling, as well as a set of subgames suitable for tightly-controlled sandbox-style experiments, all allowing a high level of data logging configuration and control by researchers.  Also, Cosmopolis’s world model incorporates configurable, AI-driven non-player character communities, as a means of researching interactions between individuals and societies

One of the main challenges in game AI is building agents that can intelligently react to unforeseen game situations. In real-time strategy games, players create new strategies and tactics that were not anticipated during development. In order to build agents capable of adapting to these types of events, we advocate the development of agents that reason about their goals in response to unanticipated game events. This results in a decoupling between the goal selection and goal execution logic in an agent. We present a reactive planning implementation of the Goal-Driven Autonomy conceptual model and demonstrate its application in StarCraft. Our system achieves a win rate of 73% against the built-in AI and outranks 48% of human players on a competitive ladder server.

Artificial intelligence is frequently used to control virtual characters in movies and games. When these characters appear in crowds, controlling them is called crowd simulation. In this paper, I suggest that crowd simulation could be accomplished by multi-agent reinforcement learning, a method by which groups of agents can learn to act autonomously in their environment. I present a case study that explores the challenges and benefits of this type of approach and encourages the development of learning techniques for AI in entertainment media.

Real-time pedestrian simulation for open-world games involves aggressive behavior simplification and culling to keep computational cost under control, but it is diffficult to predict whether these techniques will become unrealistic in certain situations. We propose a method of perceptually simulating highly realistic pedestrian behavior in virtual cities in realtime. Designers build a highly realistic simulation, from which a perceptually identical "perceptual simulation" is generated. Although the perceptual simulation simulates only a small portion of the world at a time, and does so with inexpensive approximations, it can be statistically guaranteed that the results are perceptually indistinguishable from those of the original simulation.

Most games being shipped today use some form of high-level abstraction such as a navmesh or waypoint graph for path planning. These structures can generally be represented in a form which is compact enough to meet the tight memory constraints in a game. But, when such a graph grows too large, finding paths can still be a complex task. This challenge was faced in Dragon Age: Origins and solved by adding an additional level of abstraction.In the last few years a variety of novel approaches have been developed for finding optimal paths through graphs with specific design applications for road networks. Currently these techniques cannot be feasibly applied to the lowest detail of movement possible in a game map, but can be applied to the high-level abstractions which are commonly found in games.In this paper we describe the pathfinding challenge faced before shipping the title Dragon Age: Origins and perform a postmortem analysis on the extended abstraction that was used in comparison to building more advanced heuristics or the use of contraction hierarchies. We show that contraction hierarchies and abstractions have similar overhead and performance and are both useful approaches for high-level planning in games.

Our goal is to enable Non Player Characters (NPC) in computer games to exhibit natural behaviors. The quality of behaviors affects the game experience especially in story-based games, which rely on player-NPC interactions. We used Reinforcement Learning to enable NPC companions to develop preferences for actions. We implemented our RL technique in BioWare Corp.’s Neverwinter Nights. Our experiments evaluate an NPC companion’s behaviors regarding traps. Our method enables NPCs to rapidly learn reasonable behaviors and adapt to changes in the game.