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.
Rational agents are becoming prevalent in many domains, from data analysis to entertainment and games. The increased prevalence of agents has evolved new tools and techniques to work with and design new agents. One such technique is system simulation. Systems simulation is a technique an author can use to imitate tasks, processes, or systems, and in particular, agents. Systems simulation has a variety of uses, ranging from simulating ecological systems to entertainment, such as interactive narratives and digital games. However, many system simulators use specialized programming languages and require prior programming experience. This causes a disconnect between individuals with limited programming experience who wish to use the simulation tools, and the software itself. New users may find the specialized languages daunting, and the initial learning process too intense for the anticipated reward. This research strives to bridge the gap between system simulation tools and users with little to no programming experience. Future work includes a corpus of narrative and autonomous agent creation tools designed for users with little to no programming experience.
An immersive, interactive environment and the non-player characters populating it often play a key role in interactive narrative experiences. We posit that if a procedurally generated narrative is better able to reflect real-world attributes of the player's surroundings, then the experience would be more transportive for the player. With this comes the problem of generating believable narratives and characters for an open, complex, real world. Simulating such a society within the constraints of the real environment, and allowing for virtual characters to more accurately mimic human behavior could increase the believability of the agents. The interactions amongst these agents sharing their cultural views, biases, and histories based on their real-world geolocation could inform the study of audience modeling and machine enculturation, allowing computers to learn or reason about social norms in regions. Finally, we posit this research would afford better applications in the field of entertainment or computational social science.
Many modern creative industrial processes rely on the collaboration between multiple humans, assisted by one or more computational systems, in a complex environment. However, most traditional systems lack the adaptability required to contribute in a flexible, co-creative manner, instead executing a fixed set of tasks in a preset time schedule. We believe games, especially cooperative games offer an ideal platform to conduct research in co-creativity. We present our motivation, preliminary work and future goals to study, build and measure game-inspired co-creative AI systems.
Samuel, Ben (University of New Orleans) | Reed, Aaron (Spirit AI) | Short, Emily (Spirit AI) | Heck, Samantha (University of Idaho) | Robison, Barrie (University of Idaho) | Wright, Landon (University of Idaho) | Soule, Terence (University of Idaho) | Treanor, Mike (American University) | McCoy, Joshua (University of California, Davis) | Sullivan, Anne (Georgia Institute of Technology) | Shirvani, Alireza (University of New Orleans) | Garcia, Edward (University of New Orleans) | Farrell, Rachelyn (University of New Orleans) | Ware, Stephen (University of New Orleans) | Compton, Katherine (University of California, Santa Cruz)
We describe a tool based on the Wave Function Collapse algorithm that performs example-based path generation on fixed maps. Our design aims at a practical system usable by non-programmers, and includes both easy input control and multiple post-processing steps. The design is implemented in Unity and enables users to easily visualize the results of experimenting with different path descriptions and game levels.
This report presents a tool developed for the analysis and visualisation of Rolling Horizon Evolutionary Algorithms, featuring a GUI which allows integration within the General Video Game AI Framework. Users are able to easily customize the parameters of the agent between runs and observe an in-depth analysis of its performance through various visual information extracted from gameplay data, live while playing the game. This visualisation aims to inform a deeper analysis into algorithm behaviour, in an attempt to justify why they make the decisions they do and improve their performance based on this knowledge.