In this paper we propose a new algorithm for solving general two-player turn-taking games that performs symbolic search utilizing binary decision diagrams (BDDs). It consists of two stages: First, it determines all breadth-first search (BFS) layers using forward search and omitting duplicate detection, next, the solving process operates in backward direction only within these BFS layers thereby partitioning all BDDs according to the layers the states reside in. We provide experimental results for selected games and compare to a previous approach. This comparison shows that in most cases the new algorithm outperforms the existing one in terms of runtime and used memory so that it can solve games that could not be solved before with a general approach.
AI Magazine is an official publication of the Association for the Advancement of Artificial Intelligence (AAAI). It is published four times each year in fall, winter, spring, and summer issues, and is sent to all members of the Association and subscribed to by most research libraries. Back issues are available on-line (issues less than 18 months old are only available to AAAI members). The purpose of AI Magazine is to disseminate timely and informative expository articles that represent the current state of the art in AI and to keep its readers posted on AAAI-related matters. The articles are selected for appeal to readers engaged in research and applications across the broad spectrum of AI.
Answer-set programming (ASP), a family of SAT-based logic programming systems, is attractive for procedural content generation. Unfortunately, current solvers present significant barriers to runtime use in games. In this paper, I discuss some of the issues involved, and present CatSAT, a solver designed to better fit the run-time resource constraints of modern games. Although intended only for small problems, it allows designers to compactly specify simple PCG problems such as NPC generation, solve them in a few tens of microseconds, and to adapt solutions dynamically based on the changing needs of gameplay. We hope that by making adoption as convenient as possible, we can increase the uptake of declarative techniques among developers.
Games are inherently situated within the cultures of their players. Players bring a wide range of knowledge and expectations to a game, and the more the game suggests connections to that culture, the stronger those expectations are and/or the more problematic they can be. MKULTRA is an experimental, AI-heavy game that ran afoul of those issues. It’s interesting to hear a talk about or to see demonstrated by the author, but frustrating for players who do not already understand its internals in some detail. In this paper, I will give a postmortem of the game, in the rough style of industry postmortems from venues such as Gamasutra or GDC. I will discuss the goals and design of the game, what went right, what went wrong, and what I should have done instead. In my discussions of the game’s problems, I’ll focus on the ways in which it frustrated the players’ cultural expectations, and what we can learn from them for the design of future games.
Automatic game design is an increasingly popular area of research that consists of devising systems that create content or complete games autonomously. The interest in such systems is two-fold: games can be highly stochastic environments that allow presenting this task as a complex optimization problem and automatic play-testing, becoming benchmarks to advance the state of the art on AI methods. In this paper, we propose a general approach that employs the N-Tuple Bandit Evolutionary Algorithm (NTBEA) to tune parameters of three different games of the General Video Game AI (GVGAI) framework. The objective is to adjust the game experience of the players so the distribution of score events through the game approximates certain pre-defined target curves. We report satisfactory results for different target score trends and games, paving the path for future research in the area of automatically tuning player experience.
We present a suite of techniques for extending the Partially Observable Monte Carlo Planning algorithm to handle complex multi-agent games. We design the planning algorithm to exploit the inherent structure of the game. When game rules naturally cluster the actions into sets called types, these can be leveraged to extract characteristics and high-level strategies from a sparse corpus of human play. Another key insight is to account for action legality both when extracting policies from game play and when these are used to inform the forward sampling method. We evaluate our algorithm against other baselines and versus ablated versions of itself in the well-known board game Settlers of Catan.
Authoring in the context of Interactive Storytelling (IS) is inherently difficult, and there is a need for authoring tools that both enable and assist authors in the creation of new content. In this paper, we discuss our approach for creating an AI-assisted authoring tool via the concept of mixed-initiative systems. We introduce our tool, Mimisbrunnur, which uses this concept to assist authors in the creation of story content. We explain how the tool functions and introduce its fundamental components, including Natural Language Processing, a Suggestion Generator, and three authoring modules.
Wiggins, Joseph B. (University of Florida) | Kulkarni, Mayank (University of Florida) | Min, Wookhee (North Carolina State University) | Mott, Bradford (North Carolina State University) | Boyer, Kristy Elizabeth (University of Florida) | Wiebe, Eric (North Carolina State University) | Lester, James (North Carolina State University)
Player affect is a central consideration in the design of game-based learning environments. Affective indicators such as facial expressions exhibited during gameplay may support building more robust player models and adaptation modules. In game-based learning, predicting player mental demand and engagement from player affect is a particularly promising approach to helping create more effective gameplay. This paper reports on a predictive player-modeling approach that observes player affect during early interactions with a game-based learning environment and predicts selfreports of mental demand and engagement at the conclusion of gameplay sessions. The findings show that automatically detected facial expressions such as those associated with joy, disgust, sadness, and surprise are significant predictors of players' self-reported engagement and mental demand at the end of gameplay interactions. The results suggest that it is possible to create affect-based predictive player models that can enable proactively tailored gameplay by anticipating player mental demand and engagement.