Video game worlds are getting increasingly large and complex. This poses challenges to the game AI for both pathfinding and strategic decisions, not least in real-time strategy games. One way to alleviate the problem is to manually pre-label the game maps with information about regions and critical choke points, which the game AI can then take advantage of. We present a method for automatically decomposing game maps into non-uniform sized regions. The method uses a flooding algorithm at its core and has the benefit, in addition to its effectiveness, to be relatively intuitive both conceptually and in implementing. Empirical evaluation on game maps shows that the automatic decomposition results in intuitive regions of a comparable standard to human-made labeling. Furthermore, we show that our automatic decomposition, when used by a pathfinding algorithm capable of taking advantage of pre-labeled regions, significantly improves search effectiveness.

This paper introduces a search-based generative process for first person shooter levels. Genetic algorithms evolve the level's architecture and the placement of powerups and player spawnpoints, generating levels with one floor or two floors. The evaluation of generated levels combines metrics collected from simulations of artificial agents competing in the level and theory-based heuristics targeting general level design patterns. Both simulation-based and theory-driven evaluations target player balance and exploration, while resulting levels emergently exhibit several popular design patters of shooter levels.

Mobile digital games are dominantly released under the freemium business model, but only a small fraction of the players makes any purchases. The ability to predict who will make a purchase enables optimization of marketing efforts, and tailoring customer relationship management to the specific user's profile. Here this challenge is addressed via two models for predicting purchasing players, using a 100,000 player dataset: 1) A classification model focused on predicting whether a purchase will occur or not. 2) a regression model focused on predicting the number of purchases a user will make. Both models are presented within a decision and regression tree framework for building rules that are actionable by companies. To the best of our knowledge, this is the first study investigating purchase decisions in freemium mobile products from a user behavior perspective and adopting behavior-driven learning approaches to this problem.

Artificial Intelligence (AI) techniques have been widely used in video games to control non-playable characters. More recently, AI has been applied to automated story generation with the objective of managing the player's experience in an interactive narrative. Such AI experience managers can generate and adapt narrative dynamically, often in response to the player's in-game actions. We implement and evaluate a recently proposed AI experience manager, PACE, which predicts the player's emotional response to a narrative event and uses such predictions to shape the narrative to keep the player on an author-supplied target emotional curve.

Horror games form a peculiar niche within game design paradigms, as they entertain by eliciting negative emotions such as fear and unease to their audience during play. This genre often follows a specific progression of tension culminating at a metaphorical peak, which is defined by the designer. A player's tension is elicited by several facets of the game, including its mechanics, its sounds, and the placement of enemies in its levels. This paper investigates how designers can control and guide the automated generation of levels and their soundscapes by authoring the intended tension of a player traversing them.

IW(1) is a simple search algorithm that assumes that states can be characterized in terms of a set of boolean features or atoms. IW(1) consists of a standard breadth-first search with one variation: a newly generated state is pruned if it does not make a new atom true. Thus, while a breadth-first search runs in time that is exponential in the number of atoms, IW(1) runs in linear time. Variations of the algorithm have been shown to yield state-of-the-art results in classical planning and more recently in the Atari video games. In this paper, we use the algorithm for selecting actions in the games of the general video-game AI competition (GVG-AI) which, unlike classical planning problems and the Atari games, are stochastic. We evaluate a variation of the algorithm over 30 games under different time windows using the number of wins as the performance measure. We find that IW(1) does better than the sample MCTS and OLMCTS controllers for all time windows with the performance gap growing with the window size. The exception are the puzzle-like games where all the algorithms do poorly. For such problems, we show that much better results can be obtained with the IW(2) algorithm, which is like IW(1), except that states are pruned in the breadth-first search when they fail to make true a new pair of atoms.

In many navigational domains the traversability of cells is conditioned on the path taken. This is often the case in videogames, in which a character may need to acquire a certain object (i.e., a key or a flying suit) to be able to traverse specific locations (e.g., doors or high walls). In order for non-player characters to handle such scenarios we present InvJPS, an “inventory-driven” pathfinding approach based on the highly successful grid-based Jump-Point-Search (JPS) algorithm. We show, formally and experimentally, that the InvJPS preserves JPS’s optimality guarantees and its symmetry breaking advantages in inventory-based variants of game maps.

Community Question Answering (CQA) websites are a popular tool for internet users to fulfill diverse information needs. Posted questions can be multiple sentences long and span diverse domains. They go beyond factoid questions and can be conversational, opinion-seeking and experiential questions, that might have multiple, potentially conflicting, useful answers from different users. In this paper, we describe a large-scale formative study to collect commonsense properties of questions and answers from 18 diverse communities from stackexchange.com. We collected 50,000 human judgments on 500 question-answer pairs. Commonsense properties are features that humans can extract and characterize reliably by using their commonsense knowledge and native language skills, and no special domain expertise is assumed. We report results and suggestions for designing human computation tasks for collecting commonsense semantic judgments.

This paper examines the importance of presenting simple, intuitive tasks when conducting microtasking on crowdsourcing platforms. Most crowdsourcing platforms allow the maker of a task to present any length of instructions to crowd workers who participate in their tasks. Our experiments show, however, most workers who participate in crowdsourcing microtasks do not read the instructions, even when they are very brief. To facilitate success in microtask design, we highlight the importance of making simple, easy to grasp tasks that do not rely on instructions for explanation.

This paper examines the effect of various modalities of expression on the reliability of crowdsourced sentiment polarity judgments. A novel corpus of YouTube video reviews was created, and sentiment judgments were obtained via Amazon Mechanical Turk. We created a system for isolating text, video, and audio modalities from YouTube videos to ensure that annotators could only see the particular modality or modalities being evaluated. Reliability of judgments was assessed using Fleiss Kappa inter-annotator agreement values. We found that the audio only modality produced the most reliable judgments for video fragments and that across modalities video fragments are less ambiguous than full videos.