Move pruning is a low-overhead technique for reducing the size of a depth first search tree. The existing algorithm for automatically discovering move pruning information is restricted to games where all moves can be applied to every state. This paper demonstrates an algorithm which handles a general class of single player games. It gives experimental results for our technique, demonstrating both the applicability to a range of games, and the reduction in search tree size. We also provide some conditions under which move pruning is safe, and when it may interfere with other search reduction techniques.

Social networks play an increasingly important role in today's society. Special characteristics of these networks make them challenging domains for the search community. In particular, social networks of users can be viewed as search graphs of nodes, where the cost of obtaining information about a node can be very high. This paper addresses the search problem of identifying the degree of separation between two users. New search techniques are introduced to provide optimal or near-optimal solutions. The experiments are performed using Twitter, and they show an improvement of several orders of magnitude over greedy approaches. Our optimal algorithm finds an average degree of separation of 3.43 between two random Twitter users, requiring an average of only 67 requests for information over the Internet to Twitter. A near-optimal solution of length 3.88 can be found by making an average of 13.3 requests.

If given manually-crafted goal selection knowledge, goal reasoning agents can dynamically determine which goals they should achieve in complex environments. These agents should instead learn goal selection knowledge through expert interaction. We describe T-ARTUE, a goal reasoning agent that performs case-based active and interactive learning to discover goal selection knowledge. We also report tests of its performance in a complex environment. We found that, under some conditions, T-ARTUE can quickly learn goal selection knowledge.

Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all the alternatives. It has been suggested to let agents submit partial orders instead. Then, given a voting rule, a profile of partial orders, and an alternative (candidate) c, two important questions arise: first, is it still possible for c to win, and second, is c guaranteed to win? These are the possible winner and necessary winner problems, respectively. Each of these two problems is further divided into two sub-problems: determining whether c is a unique winner (that is, c is the only winner), or determining whether c is a co-winner (that is, c is in the set of winners). We consider the setting where the number of alternatives is unbounded and the votes are unweighted. We completely characterize the complexity of possible/necessary winner problems for the following common voting rules: a class of positional scoring rules (including Borda), Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.

The attrition game considered in this study is a graph based strategic game which is a movement-prohibited analogue of small-scale combat situations that arise frequently in popular real-time strategy video games. We present proofs that the attrition game, under a variety of assumptions, is a computationally hard problem in general. We also analyze the 1 vs. n unit case, for which we derive optimal target-orderings that can be computed in polynomial time and used as a core for heuristics for the general case. Finally, we present small problem instances that require randomizing moves — a fact that at first glance seems counter-intuitive.

As game designers shift focus from graphical realism to immersive stories, the number of game-object interactions grows exponentially. Games use manually written scripts to control interactions. ScriptEase provides game designers with generative patterns that generate scripting code to control common interactions. This paper describes a new kind of generative pattern, quest patterns, that generate scripting code to control story plot. We present our quest pattern architecture and study results that show quest patterns are easy-to-use and reduce plot scripting errors.

In the context of interactive, virtual experiences, the use of personality models to maintain consistent character behaviour is becoming more widespread in both industry and academia. Most current techniques, however, are limited in one of three ways: either they overly restrict user actions, have a high cost for creating varied content, or rely on a representation that prohibits conveying complex content to the user.  Toward addressing these issues, we introduce Socially Consistent Role Passing, a mechanism for ensuring consistent character behaviour that leverages the design of PaSSAGE, an existing system for generating adaptive, interactive stories.  While results from previous human user studies have shown that PaSSAGE improves the enjoyment of players with little gaming experience, we present results from a new study showing that PaSSAGE's adaptive stories, augmented with Socially Consistent Role Passing, improve the enjoyment of all players versus a set of fixed-structure alternatives.

This research aims at building a preference-based player model of Civilization IV players. Our model incorporates attributes which are defined for AI players. We use a sequential minimal optimization (SMO) classifier to build the player model based on a training set with observations of a large number of games between six AI players. The model was validated on a test set of games between the same six AI players. While it did not seem to generalize well to the preferences of different AI players, it did manage to accurately predict some of the preferences for a veteran human player. Further tests showed that AI players with the same play styles but different preference values were often confused by the model. We conclude that for a complex game such as Civilization IV a model that attempts to accurately predict specific preference values is hard to construct. A model that focusses on play styles might succeed better.

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.