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.
Theatrical improvisation (impro or improv) is a demanding form of live, collaborative performance. Improv is a humorous and playful artform built on an open-ended narrative structure which simultaneously celebrates effort and failure. It is thus an ideal test bed for the development and deployment of interactive artificial intelligence (AI)-based conversational agents, or artificial improvisors. This case study introduces an improv show experiment featuring human actors and artificial improvisors. We have previously developed a deep-learning-based artificial improvisor, trained on movie subtitles, that can generate plausible, context-based, lines of dialogue suitable for theatre. In this work, we have employed it to control what a subset of human actors say during an improv performance. We also give human-generated lines to a different subset of performers. All lines are provided to actors with headphones and all performers are wearing headphones. This paper describes a Turing test, or imitation game, taking place in a theatre, with both the audience members and the performers left to guess who is a human and who is a machine. In order to test scientific hypotheses about the perception of humans versus machines we collect anonymous feedback from volunteer performers and audience members. Our results suggest that rehearsal increases proficiency and possibility to control events in the performance. That said, consistency with real world experience is limited by the interface and the mechanisms used to perform the show. We also show that human-generated lines are shorter, more positive, and have less difficult words with more grammar and spelling mistakes than the artificial improvisor generated lines.
Churchill and Buro (2013) launched a line of research through Portfolio Greedy Search (PGS), an algorithm for adversarial real-time planning that uses scripts to simplify the problem's action space. In this paper we present a problem in PGS's search scheme that has hitherto been overlooked. Namely, even under the strong assumption that PGS is able to evaluate all actions available to the player, PGS might fail to return the best action. We then describe an idealized algorithm that is guaranteed to return the best action and present an approximation of such algorithm, which we call Nested-Greedy Search (NGS). Empirical results on MicroRTS show that NGS is able to outperform PGS as well as state-of-the-art methods in matches played in small to medium-sized maps.
Summerville, Adam (California State Polytechnic University, Pomona ) | Martens, Chris (North Carolina State University) | Samuel, Ben (University of New Orleans) | Osborn, Joseph (Pomona College) | Wardrip-Fruin, Noah (University of California, Santa Cruz) | Mateas, Michael (University of California, Santa Cruz)
Current approaches to game generation don't understand the games they generate. As a result, even the most sophisticated systems in this regard, e.g., Game-o-Matic, betray this problem — generating games with goals that are at odds with their mechanics. We describe Gemini, the first bidirectional game generation and analysis system. Gemini is able to take games as input, perform a proceduralist reading of them, and produce possible interpretations that the games might afford. By utilizing the declarative nature of Answer Set Programming (ASP), this analysis pathway opens up generation of games targeting specific interpretations and makes it possible to ensure the generated games are consistent with the desired reading. For Gemini, we developed a game specification language capable of expressing a larger domain of games than is possible with VGDL, the most widespread representation. We demonstrate the generality of our approach by generating games in a series of domains. These domains are based on prototypes hand-created by a team without knowledge of the constraints and capabilities of Gemini.
We present a new way to represent and understand experience managers - AI agents that tune the parameters of a running game to pursue a designer's goal. Existing representations of AI managers are diverse, which complicates the task of drawing useful comparisons between them. Contrary to previous representations, ours uses a point of unity as its basis: that every game/manager pair can be viewed as only a game with the manager embedded inside. From this basis, we show that several common, differently-represented concepts of experience management can be re-expressed in a unified way. We demonstrate our new representation concretely by comparing two different representations, Search-Based Drama Management and Generalized Experience Management, and we present the insights that we have gained from this effort.
Within the area of procedural content generation (PCG) there are a wide range of techniques that have been used to generate content. Many of these techniques use traditional artificial intelligence approaches, such as genetic algorithms, planning, and answer-set programming. One area that has not been widely explored is straightforward combinatorial search -- exhaustive enumeration of the entire design space or a significant subset thereof. This paper synthesizes literature from mathematics and other subfields of Artificial Intelligence to provide reference for the algorithms needed when approaching exhaustive procedural content generation. It builds on this with algorithms for exhaustive search and complete examples how they can be applied in practice.
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.