Platformer games let players solve real-time, physics-based puzzles by jumping and moving around to reach different goals. Designing levels for this context is a non-trivial task; the placement of well-timed jumps, moving platforms, in- teresting traps, etc., has a complex relationship to in-game challenge and the existence of possible solutions. In this work, we describe three different search algorithms (A⋆, MCTS and RRT) that could be used to simulate player be- haviour in the platformer domain. We evaluate and compare the three approaches applied to three non-trivial levels, show- ing a possible iterative workflow of use to designers, and re- search progress in designing search algorithms for platformer games.

This document contains a summary of research performed by the author on the topic of search algorithms for games. An outline of the problems being addressed is provided, along with the progress already made, and planned future work. The specific subjects studied are: parallelizing UCT search on GPUs, the development of a hierarchical search framework for Real-Time Strategy (RTS) games and the building placement problem in RTS games. We propose to take advantage of different parallel architectures to help solve these problems.

We investigate the problem of learning the control of small groups of units in combat situations in Real Time Strategy (RTS) games. AI systems may acquire such skills by observing and learning from expert players, or other AI systems performing those tasks. However, access to training data may be limited, and representations based on metric information -- position, velocity, orientation etc. -- may be brittle, difficult for learning mechanisms to work with, and generalise poorly to new situations. In this work we apply \textit{qualitative spatial relations} to compress such continuous, metric state-spaces into symbolic states, and show that this makes the learning problem easier, and allows for more general models of behaviour. Models learnt from this representation are used to control situated agents, and imitate the observed behaviour of both synthetic (pre-programmed) agents, as well as the behaviour of human-controlled agents on a number of canonical micro-management tasks. We show how a Monte-Carlo method can be used to decompress qualitative data back in to quantitative data for practical use in our control system. We present our work applied to the popular RTS game Starcraft.

State evaluation and opponent modelling are important areasto consider when designing game-playing Artificial Intelligence.This paper presents a model for predicting whichplayer will win in the real-time strategy game StarCraft.Model weights are learned from replays using logistic regression.We also present some metrics for estimating player skillwhich can be used a features in the predictive model, includingusing a battle simulation as a baseline to compare playerperformance against.

This paper presents a constraint optimization approach to walling in real-time strategy (RTS) games. Walling is a specific type of spatial reasoning, typically employed by human expert players and not currently fully exploited in RTS game AI, consisting on finding configurations of buildings to completely or partially block paths. Our approach is based on local search, and is specifically designed for the real-time nature of RTS games. We present experiments in the context of the RTS game StarCraft showing promising results.

Recent years have witnessed growing interest in data-driven approaches to interactive narrative planning and drama management. Reinforcement learning techniques show particular promise because they can automatically induce and refine models for tailoring game events by optimizing reward functions that explicitly encode interactive narrative experiences’ quality. Due to the inherently subjective nature of interactive narrative experience, designing effective reward functions is challenging. In this paper, we investigate the impacts of alternate formulations of reward in a reinforcement learning-based interactive narrative planner for the Crystal Island game environment. We formalize interactive narrative planning as a modular reinforcement-learning (MRL) problem. By decomposing interactive narrative planning into multiple independent sub-problems, MRL enables efficient induction of interactive narrative policies directly from a corpus of human players’ experience data. Empirical analyses suggest that interactive narrative policies induced with MRL are likely to yield better player outcomes than heuristic or baseline policies. Furthermore, we observe that MRL-based interactive narrative planners are robust to alternate reward discount parameterizations.

Glaive is a state-space planner based on Hoffmann and Nebel's Fast-Forward which solves the narrative planning problem defined by Riedl and Young — to construct a plan which achieves the author's goals out of steps which are clearly motivated and goal-oriented toward individual character goals. Glaive reasons about how characters cooperate and conflict based on causal structures and possible worlds. By leveraging the unique constraints of narrative planning, Glaive reduces its branching factor and calculates a more accurate heuristic. We evaluate it on 8 narrative planning problems and demonstrate that it can solve certain non-trivial problems in under 1 second.

Genomic is Python software that evolves sound treatments and produce novel sounds. It offers features that have the potential to serve sound designers and composers, aiding them in their search for new and interesting sounds. This paper lays out the rationale and some design decisions made for Genomic, and proposes several intuitive ways of both using the software and thinking about the techniques that it enables for the modification and design of sound.

In this paper we examine the build order problem in real-time strategy (RTS) games in which the objective is to optimize execution of a strategy by scheduling actions with respect to a set of subgoals. We model the build order problem as a multi-objective problem (MOP), and solutions are generated utilizing a multi-objective evolutionary algorithm (MOEA). A three dimensional solution space is presented providing a depiction of a Pareto front for the build order MOP. Results of the online strategic planning tool are provided which demonstrate that our planner out-performs an expert scripted player. This is demonstrated for an AI agent in the Spring Engine Balanced Annihilation RTS game.

In this paper we describe a hierarchical method for procedurallygenerating maps using Markov chains. Ourmethod takes as input a collection of human-authoredtwo-dimensional maps, and splits them into high-leveltiles which capture large structures. Markov chains arethen learned from those maps to capture the structure ofboth the high-level tiles, as well as the low-level tiles.Then, the learned Markov chains are used to generatenew maps by first generating the high-level structure ofthe map using high-level tiles, and then generating thelow-level layout of the map. We validate our approachusing the game Super Mario Bros., by evaluating thequality of maps produced using different configurationsfor training and generation.