We examine the use of constraint propagation for populating indoor game levels with enemies and other objects.  We introduce a notion of path constraints , which bound some function over the possible paths a player might take, and show how to efficiently place objects while guaranteeing path constraints.  This allows the system to guarantee that power-ups are balanced to the number of enemies occurring in the level, that they’re placed early enough to be useful, that keys are not hidden behind the doors they are intended to unlock, and so on. We describe a constraint solver based on interval methods that allows natural processing of numeric constraints and show that it is efficient enough to be used even on very low-end platforms.

Monte-Carlo Tree Search (MCTS) is an online planning algorithm that combines the ideas of best-first tree search and Monte-Carlo evaluation. Since MCTS is based on sampling, it does not require a transition function in explicit form, but only a generative model of the domain. Because it grows a highly selective search tree guided by its samples, it can handle huge search spaces with large branching factors. By using Monte-Carlo playouts, MCTS can take long-term rewards into account even with distant horizons. Combined with multi-armed bandit algorithms to trade off exploration and exploitation, MCTS has been shown to guarantee asymptotic convergence to the optimal policy, while providing approximations when stopped at any time. The relatively new MCTS approach has started a revolution in computer Go. Furthermore, it has achieved considerable success in domains as diverse as the games of Hex, Amazons, LOA, and Ms. Pacman; in General Game Playing, planning, and optimization. Whereas the focus of previous MCTS research has been on the practical application, current research begins to address the problem of understanding the nature, the underlying principles, of MCTS. A careful understanding of MCTS will lead to more effective search algorithms. Hence, my two interrelated research questions are: How can we formulate models that increase our understanding of how MCTS works? and How can we use the developed understanding to create effective search algorithms? This research summary describes the first steps I undertook in these directions, as well as my plans for future work.

Mezzo is a computer program designed that procedurally writes Romantic-Era style music in real-time to accompany computer games. Leitmotivs are associated with game characters and elements, and mapped into various musical forms.  These forms are distinguished by different amounts of harmonic tension and formal regularity, which lets them musically convey various states of markedness which correspond to states in the game story. Because the program is not currently attached to any game or game engine, “virtual” gameplays were been used to explore the capabilities of the program; that is, videos of various game traces were used as proxy examples.  For each game trace, Leitmotivs were input to be associated with characters and game elements, and a set of ‘cues’ was written, consisting of a set of time points at which a new set of game data would be passed to Mezzo to reflect the action of the game trace.  Examples of music composed for one such game trace, a scene from Red Dead Redemption , are given to illustrate the various ways the program maps Leitmotivs into different levels of musical markedness that correspond with the game state.

Creating a musical fitness function is largely subjective and can be critically affected by the designer's biases. Previous attempts to create such functions for use in genetic algorithms lack scope or are prejudiced to a certain genre of music. They also are limited to producing music strictly in the style determined by the programmer. We show in this paper that musical feature extractors, which avoid the challenges of qualitative judgment, enable creation of a multi-objective function for direct music production. The main result is that the multi-objective fitness function enables creation of music with varying identifiable styles. To demonstrate this, we use three different multi-objective fitness functions to create three distinct sets of musical melodies. We then evaluate the distinctness of these sets using three different approaches: a set of traditional computational clustering metrics; a survey of non-musicians; and analysis by three trained musicians.

In this position paper, the author proposes the use of social networks of characters as an AI narrative generation mechanism. The first part of the paper offers examples of recent research by literary critics on the relationship between character networks and narrative structure. The second part of the paper offers a simple example of story generation based on a structural balance network model.

Around the same time, a system called Player-Specific From Shakespeare's "Romeo and Juliet" to George Lucas' Stories via Automatically Generated Events (PaSSAGE) "Star Wars" to BioWare's "Jade Empire" to campfire stories (Thue et al. 2007) was proposed, which used AI techniques to baseball commentary, story-telling is a fundamental to model the player as he/she experiences a narrative-rich part of entertainment. A strong narrative resonates with our video game. Such a continuously updated player model was minds, hearts and souls and keeps us engaged. We remember used to dynamically adapt the story, tailoring it to the current the stories of our childhood and retell them to our own player. Unlike, ASD, PaSSAGE did not have any automation children. Story-telling has delighted and saddened the human at the design stage and relied on a human designer to race since the beginning of time and shows no signs of foresee all possible ways of a player breaking the story and slowing down. But can it be improved with technology?

Layered Statechart-based AI shows considerable promise by being a highly modular, reusable, and designer friendly approach to game AI. Here we demonstrate the viability of this approach by replicating the functionality of a full-featured and commercial-scale behaviour tree AI within a non-commercial game framework. As well as demonstrating that layered Statecharts are both usable and amply expressive, our experience highlights the value of several, previously unidentified design considerations, such as sensor patterns, the necessity of subsumption, and the utility of orthogonal regions. These observations point towards simplified, higher-level AI construction techniques that can reduce the complexity of AI design and further enhance reuse.

Adapting game content to a particular player's needs and expertise constitutes an important aspect in game design. Most research in this direction has focused on adapting game difficultyto keep the player engaged in the game. Dynamic difficulty adjustment, however, focuses on one aspect of the gameplay experience by adjusting the content to increase ordecrease perceived challenge. In this paper, we introduce a method for automatic level generation for the platform game Super Mario Bros using grammatical evolution. The grammatical evolution-based level generator is used to generate player-adapted content by employing an adaptation mechanism as a fitness function in grammatical evolution to optimizethe player experience of three emotional states: engagement, frustration and challenge. The fitness functions used are models of player experience constructed in our previous work from crowd-sourced gameplay data collected from over 1500 game sessions.

Player metrics are an invaluable resource for game designers and QA analysts who wish to understand players, monitor and improve game play, and test design hypotheses. Usually such metrics are collected in a straightforward manner by passively recording players; however, such an approach has several potential drawbacks. First, passive recording might fail to record metrics which correspond to an infrequent player behavior. Secondly, passive recording can be a costly, laborious, and memory intensive process, even with the aid of tools. In this paper, we explore the potential for an active approach to player metric collection which strives to collect data more efficiently, and thus with less cost. We use an online, iterative approach which models the relationship between player metrics and in-game situations probabilistically using a Markov Decision Process (MDP) and solves it for the best game configurations to run. To analyze the benefits and limitations of this approach, we implemented a system, called GAMELAB, for recording player metrics in Second Life.

We define metaphor computing as a way to transform difficult computational problems into easier human-solvable problems, and transform solutions back into computational solutions. This report explores initial ideas.