Agency, being one's ability to perform an action and have some influence over the world, is fundamental to interactive entertainment. Although much of the games industry is concerned with providing more agency to its players, what seems to matter more is how much agency each player will actually perceive. In this paper, we present a computational model of this phenomena, based on the notion that the amount of agency that one perceives depends on how much they desire the outcomes that result from their decisions. Using a structure for high-agency stories that we designed specifically for this intent, we present the results of a 141-participant user study that tests our model's ability to select subsequent events in an original interactive story. Using a newly validated survey instrument for measuring both agency and fun, we found with a high degree of confidence that event sequences selected by our model result in players perceiving more agency than players who experience event sequences that our model does not recommend.

In recent years, real-time strategy (RTS) games have gained interest in the AI research community for their multitude of challenging subproblems — such as collaborative pathfinding, effective resource allocation and unit targeting, to name a few. In this paper we consider the build order problem in RTS games in which we need to find concurrent action sequences that, constrained by unit dependencies and resource availability, create a certain number of units and structures in the shortest possible time span. We present abstractions and heuristics that speed up the search for approximative solutions considerably in the game of StarCraft, and show the efficacy of our method by comparing its real-time performance with that of professional StarCraft players.

Path planning is a critical part of modern computer games; rare is the game where nothing moves and path planning is unneeded. A* is the workhorse for most path planning applications. Block A* is a state-of-the-art algorithm that is always faster than A* in experiments using game maps. Unlike other methods that improve upon A*'s performance, Block A* is never worse than A* nor require any knowledge of the map. In our experiments, Block A* is ideal for games with randomly generated maps, large maps, or games with a highly dynamic multi-agent environment. Furthermore, in the domain of grid-based any-angle path planning, we show that Block A* is an order of magnitude faster than the previous best any-angle path planning algorithm, Theta*. We empirically show our results using maps from Dragon Age: Origins and Starcraft. Finally, we introduce ``populated game maps'' as a new test bed that is a better approximation of real game conditions than the standard test beds of this field. The main contributions of this paper is a more rigorous set of experiments for Block A*, and introducing a new test bed (populated game maps) that is a more accurate representation of actual game conditions than the standard test beds.

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.

We pose the problem of constructing good search heuristics as an optimization problem: minimizing the loss between the true distances and the heuristic estimates subject to admissibility and consistency constraints. For a well-motivated choice of loss function, we show performing this optimization is tractable. In fact, it corresponds to a recently proposed method for dimensionality reduction. We prove this optimization is guaranteed to produce admissible and consistent heuristics, generalizes and gives insight into differential heuristics, and show experimentally that it produces strong heuristics on problems from three distinct search domains.

Much recent work in satisficing planning has aimed at striking a balance between coverage - solving as many problems as possible - and plan quality. Current planners achieve near perfect coverage on the latest IPC benchmarks. It is therefore natural to investigate their scaling behavior on more difficult instances. Among state of the art planners, LAMA (Richter, Helmert, and Westphal 2008) is able to generate high quality plans, but its coverage drops off rapidly with increasing prob- lem complexity. The Arvand planner (Nakhost and Müller 2009) scales to much harder instances but generates lower quality plans. This paper introduces a new algorithm, Monte Carlo Random Walk-based Local Tree Search (MRW-LTS), which uses random walks to selectively build local search trees. Experiments demonstrate that MRW-LTS combines a scaling behavior that is better than LAMA’s with a plan quality that is better than Arvand’s.

Korf, Reid, and Edelkamp launched a line of research aimed at predicting how many nodes IDA* will expand with a given depth bound. This paper advances this line of research in three ways. First, we identify a source of prediction error that has hitherto been overlooked. We call it the "discretization effect." Second, we disprove the intuitively appealing idea that a "more informed" prediction system cannot make worse predictions than a ``less informed'' one. More informed systems are more susceptible to the discretization effect, and in our experiments the more informed system makes poorer predictions. Our third contribution is a method, called "Epsilon-truncation," which makes a prediction system less informed, in a carefully chosen way, so as to improve its predictions by reducing the discretization effect. In our experiments Epsilon-truncation improved predictions substantially.

We focus on a class of models used for representing the dynamics between a discrete set of probabilistic events in a continuous-time setting. The proposed framework offers tractable learning and inference procedures and provides compact state representations for processes which exhibit variable delays between events. The approach is applied to a heart sound labeling task that exhibits long-range dependencies on previous events, and in which explicit modeling of the rhythm timings is justifiable by cardiological principles.

Real-time heuristic search algorithms that precompute search space-specific databases have demonstrated exceptional performance in video-game pathfinding. We discuss the first steps towards extending these algorithms to other search spaces that also benefit from the real-time property. We present our initial progress in characterizing the performance of current algorithms based on the features of a search space, and discuss future directions of this research.

In current search engines, ranking functions are learned from a large number of labeled <query, URL> pairs in which the labels are assigned by human judges, describing how well the URLs match the different queries. However in commercial search engines, collecting high quality labels is time-consuming and labor-intensive. To tackle this issue, this paper studies how to produce the true relevance labels for  <query, URL> pairs using clickthrough data. By analyzing the correlations between query frequency, true relevance labels and users’ behaviors, we demonstrate that the users who search the queries with similar frequency have similar search intents and behavioral characteristics. Based on such properties, we propose an efficient discriminative parameter estimation in a multiple instance learning algorithm (MIL) to automatically produce true relevance labels for  <query, URL> pairs. Furthermore, we test our approach using a set of real world data extracted from a Chinese commercial search engine. Experimental results not only validate the effectiveness of the proposed approach, but also indicate that our approach is more likely to agree with the aggregation of the multiple judgments when strong disagreements exist in the panel of judges. In the event that the panel of judges is consensus, our approach provides more accurate automatic label results. In contrast with other models, our approach effectively improves the correlation between automatic labels and manual labels.