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.
Kantharaju, Pavan (Drexel University) | Alderfer, Katelyn (Drexel University) | Zhu, Jichen (Drexel University) | Char, Bruce (Drexel University) | Smith, Brian (Drexel University) | Ontanon, Santiago (Drexel University)
This paper focuses on tracing player knowledge in educational games. Specifically, given a set of concepts or skills required to master a game, the goal is to estimate the likelihood with which the current player has mastery of each of those concepts or skills. The main contribution of the paper is an approach that integrates machine learning and domain knowledge rules to find when the player applied a certain skill and either succeeded or failed. This is then given as input to a standard knowledge tracing module (such as those from Intelligent Tutoring Systems) to perform knowledge tracing. We evaluate our approach in the context of an educational game called Parallel to teach parallel and concurrent programming with data collected from real users, showing our approach can predict students skills with a low mean-squared error.
A significant amount of work has advocated that Learning from Demonstration (LfD) is a promising approach to allow end-users to create behaviors for in-game characters without requiring programming. However, one major problem with this approach is that many LfD algorithms require large amounts of training data, and thus are not practical for learning from human demonstrators. In this paper, we focus on LfD with limited training data, and specifically on the problem of active LfD where the demonstrators are human. We present the results of a user study in comparing SALT, a new active LfD approach, versus a previous state-of-the-art Active LfD algorithm, showing that SALT significantly outperforms it when learning from a limited amount of data in the context of learning to play a puzzle video game.
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.
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.
Modelling a player's understanding of NPC movements can be useful for adapting gameplay to different play styles. For stealth games, what a player knows or suspects of enemy movements is important to how they will navigate towards a solution. In this work, we build a uniform abstraction of potential player path knowledge based on their partial observations. We use this representation to compute different path estimates according to different player expectations. We augment our work with a user study that validates what kinds of NPC behaviour a player may expect, and develop a tool that can build and explore appropriate (expected) paths. We find that players prefer short simple paths over long or complex paths with looping or backtracking behaviour.
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.
Intelligent autonomous agents that are acting in dynamic environmentsin real-time are often required to follow long-termstrategies while also remaining reactive and being able to actdeliberately. In order to create intelligent behaviors for videogame characters, there are two common approaches – plannersare used for long-term strategical planning, whereas BehaviorTrees allow for reactive acting. Although both methodologieshave their advantages, when used on their own, theyfail to fully achieve both requirements described above. Inthis work, we propose a hybrid approach combining a HierarchicalTask Network planner for high-level planning whiledelegating low-level decision making and acting to BehaviorTrees. Furthermore, we compare this approach with a pureplanner in a multi-agent environment.