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.
A reader should be able to learn the purpose of the article and the reason for its importance from the abstract. Introduction A brief introduction should portray the broad significance of the article. The whole text should be intelligible to readers in various disciplines. Technical terms should be defined the first time they are used. Headings Use headings to separate major sections of your article.
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.
Players of digital games face numerous choices as to what kind of games to play and what kind of game content or in-game activities to opt for. Among these, game content plays an important role in keeping players engaged so as to increase revenues for the gaming industry. However, while nowadays a lot of game content is generated using procedural content generation, automatically determining the kind of content that suits players' skills still poses challenges to game developers. Addressing this challenge, we present matrix- and tensor factorization based game content recommender systems for recommending quests in a single player role-playing game. We discuss the theory behind latent factor models for recommender systems and derive an algorithm for tensor factorizations to decompose collections of bipartite matrices. Extensive online bucket type tests reveal that our novel recommender system retained more players and recommended more engaging quests than handcrafted content-based and previous collaborative filtering approaches.
The ability of digital storytelling agents to evaluate their output is important for ensuring high-quality human-agent interactions. However, evaluating stories remains an open problem. Past evaluative techniques are either model-specific--- which measure features of the model but do not evaluate the generated stories ---or require direct human feedback, which is resource-intensive. We introduce a number of story features that correlate with human judgments of stories and present algorithms that can measure these features. We find this approach results in a proxy for human-subject studies for researchers evaluating story generation systems.
Partlan, Nathan (Northeastern University) | Carstensdottir, Elin (Northeastern University) | Snodgrass, Sam (Northeastern University) | Kleinman, Erica (Northeastern University) | Smith, Gillian (Worcester Polytechnic Institute) | Harteveld, Casper (Northeastern University) | El-Nasr, Magy Seif (Northeastern University)
Analysis of interactive narrative is a complex undertaking, requiring understanding of the narrative's design, its affordances, and its impact on players. Analysis is often performed by an expert, but this is expensive and difficult for complex interactive narratives. Automated analysis of structure, the organization of interaction elements, could help augment an expert's analysis. For this purpose we developed a model consisting of a set of metrics to analyze interactive narrative structure, enabled by a novel multi-graph representation. We implemented this model for an interactive scenario authoring tool called StudyCrafter and analyzed 20 student-designed scenarios. We show that the model illuminates the structures and groupings of the scenarios. This work provides insight for manual analysis of attributes of interactive narratives and a starting point for automated design assistance.
Oliveira, Victor M. (Universidade Federal de Goias) | Nascimento, Hugo A. D. do (Universidade Federal de Goias) | Soares, Fabrizzio A. A. M. N. (Universidade Federal de Goias) | Rocha, Cleomar S. (Universidade Federal de Goias)
In the present paper we explore the idea of combining computation power and the availability of ordinary art spectators in order to produce new interactive art works. This is investigated for a particular application, which consists of producing new behaviors for a programmable art apparatus named C3 Cubes. Given the nature of the problem and some difficult challenges to be dealt with, an Interactive Evolutionary Computation (IEC) approach was devised. Furthermore, it was necessary to adopt a surrogate function method for approximating the user's preferences and to implement a Web-based virtual simulation environment for speeding up the generation and the evaluation of C3 Cubes projects. The integration of all these elements is crucial for producing new user-guided cube projects with interesting behaviors. The main approaches experimented in this research and the proposed design solutions are useful to solving similar problems in other domain areas, for example, in the context of game design.
Moraes, Rubens O. (Universidade Federal de Viçosa) | Mariño, Julian R. H. (Universidade de São Paulo) | Lelis, Levi H. S. (Universidade Federal de Viçosa) | Nascimento, Mario A. (University of Alberta)
Search algorithms based on combinatorial multi-armed bandits (CMABs) are promising for dealing with state-space sequential decision problems. However, current CMAB-based algorithms do not scale to problem domains with very large actions spaces, such as real-time strategy games played in large maps. In this paper we introduce CMAB-based search algorithms that use action abstraction schemes to reduce the action space considered during search. One of the approaches we introduce use regular action abstractions (A1N), while the other two use asymmetric action abstractions (A2N and A3N). Empirical results on MicroRTS show that A1N, A2N, and A3N are able to outperform an existing CMAB-based algorithm in matches played in large maps, and A3N is able to outperform all state-of-the-art search algorithms tested.
The ability to extract the sequence of game events for a given player's play-through has traditionally required access to the game's engine or source code. This serves as a barrier to researchers, developers, and hobbyists who might otherwise benefit from these game logs. In this paper we present two approaches to derive game logs from game video via convolutional neural networks and transfer learning. We evaluate the approaches in a Super Mario Bros. clone, Mega Man and Skyrim. Our results demonstrate our approach outperforms random forest and other transfer baselines.
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.