Bulitko, Vadim


Towards Positively Surprising Non-Player Characters in Video Games

AAAI Conferences

Video games often populate their in-game world with numerous ambient non-playable characters. Manually crafting interesting behaviors for such characters can be prohibitively expensive. As scripted AI gets re-used across multiple characters, they can appear overly similar, shallow and generally uninteresting for the player to interact with. In this paper we propose to evolve interesting behaviors in a simulated evolutionary environment. Since only some evolution runs may give rise to such behaviors, we propose to train deep neural networks to detect such behaviors. The paper presents work in progress in this direction.


Effects of Self-Knowledge: Once Bitten Twice Shy

AAAI Conferences

Procedurally generating rich, naturally behaving AI-controlled video game characters is an important open problem. In this paper we focus on a particular aspect of non-playable character (NPC) behavior, long favored by science-fiction writers. Specifically, we study the effects of self-knowledge on NPC behavior. To do so we adopt the well-known framework of agent-centered real-time heuristic search applied to the standard pathfinding task on video-game maps. Such search agents normally use a heuristic function to guide them around a map to the goal state. Heuristic functions are inaccurate underestimates of the remaining distance to goal. What if the agent somehow knew how long it (the agent) would actually take to reach the goal from each state? How would using such self-knowledge in place of a heuristic function affect the agent's behavior? We show that similarly to real life, knowing of one's irrational behavior in a situation can deter the agent from getting into that situation again even if it is, in fact, a part of an optimal solution. We demonstrate the "fear" with a simple example and empirically show that the issue is common in video-game pathfinding. We then analyze the issue theoretically and suggest that "fear" induced by self-knowledge is not a bug but a feature and may potentially be used to develop more naturally behaving NPCs.


Deep Learning for Speech Accent Detection in Videogames

AAAI Conferences

In video games, a wide range of characters make up the world players inhabit. These characters, NPCs, have traits, such as their appearance and speech accent, that determine certain things about them, including moral inclination, levels of trustworthiness, social class, levels of education, and ethnic background. But what does an accent say about a character in a video game? We use deep learning to train a neural network to detect speech accents and establish the degree to which machines can be used to recognize these accents. This research aims to help sociolinguists and discourse analysts establish critical study and content analytical findings for instance about stereotypical uses of speech accents, to better analyze who has what accent in video games, and what kind of language ideologies and social value judgments the use of accents in games construct and perpetuate. This paper presents the results of the first deep learning experiments, which were conducted on Standard North American, British Received Pronunciation, and Spanish English. We discuss our methodological considerations and some early deep learning results, which show relatively low levels of accuracy (61%). We discuss possibilities of improving our method, and of enriching our training datasets.


Deep Learning for Real-Time Heuristic Search Algorithm Selection

AAAI Conferences

Real-time heuristic search algorithms are used for creating agents that rely on local information and move in a bounded amount of time making them an excellent candidate for video games as planning time can be controlled. Path finding on video game maps has become the de facto standard for evaluating real-time heuristic search algorithms. Over the years researchers have worked to identify areas where these algorithms perform poorly in an attempt to mitigate their weaknesses. Recent work illustrates the benefits of tailoring algorithms for a given problem as performance is heavily dependent on the search space. In order to determine which algorithm to select for solving the search problems on a map the developer would have to run all the algorithms in consideration to obtain the correct choice. Our work extends the previous algorithm selection approach to use a deep learning classifier to select the algorithm to use on new maps without having to evaluate the algorithms on the map. To do so we select a portfolio of algorithms and train a classifier to predict which portfolio member to use on a unseen new map. Our empirical results show that selecting algorithms dynamically can outperform the single best algorithm from the portfolio on new maps, as well provide the lower bound for potential improvements to motivate further work on this approach.


Per-Map Algorithm Selection in Real-Time Heuristic Search

AAAI Conferences

Real-time heuristic search is suitable for time-sensitive pathfinding and planning tasks when an AI-controlled non-playable character must interleave its planning and plan execution. Since its inception in the early 90s, numerous real-time heuristic search algorithms have been proposed. Many of the algorithms also have control parameters leaving a practitioner with a bewildering array of choices. Recent work treated the task of algorithm and parameter selection as a search problem in itself. Such automatically found algorithms outperformed previously known manually designed algorithms on the standard video-game pathfinding benchmarks. In this paper we follow up by selecting an algorithm and parameters automatically per map. Our sampling-based approach is efficient on the standard video-game pathfinding benchmarks. We also apply the approach to per-problem algorithm selection and while it is effective there as well, it is not practical. We offer suggestions on making it so.


Flow for Meta Control

arXiv.org Artificial Intelligence

The psychological state of flow has been linked to optimizing human performance. A key condition of flow emergence is a match between the human abilities and complexity of the task. We propose a simple computational model of flow for Artificial Intelligence (AI) agents. The model factors the standard agent-environment state into a self-reflective set of the agent's abilities and a socially learned set of the environmental complexity. Maximizing the flow serves as a meta control for the agent. We show how to apply the meta-control policy to a broad class of AI control policies and illustrate our approach with a specific implementation. Results in a synthetic testbed are promising and open interesting directions for future work.


Interactive Narrative: An Intelligent Systems Approach

AI Magazine

Interactive narrative is a form of digital interactive experience in which users create or influence a dramatic storyline through their actions. The goal of an interactive narrative system is to immerse the user in a virtual world such that he or she believes that they are an integral part of an unfolding story and that their actions can significantly alter the direction and/or outcome of the story.In this article we review the ways in which artificial intelligence can be brought to bear on the creation of interactive narrative systems. We lay out the landscape of about 20 years of interactive narrative research and explore the successes as well as open research questions pertaining to the novel use of computational narrative intelligence in the pursuit of entertainment, education, and training.


Interactive Narrative: An Intelligent Systems Approach

AI Magazine

Interactive narrative is a form of digital interactive experience in which users create or influence a dramatic storyline through their actions. The goal of an interactive narrative system is to immerse the user in a virtual world such that he or she believes that they are an integral part of an unfolding story and that their actions can significantly alter the direction and/or outcome of the story.In this article we review the ways in which artificial intelligence can be brought to bear on the creation of interactive narrative systems. We lay out the landscape of about 20 years of interactive narrative research and explore the successes as well as open research questions pertaining to the novel use of computational narrative intelligence in the pursuit of entertainment, education, and training.


Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions

arXiv.org Artificial Intelligence

In this paper, we consider planning in stochastic shortest path (SSP) problems, a subclass of Markov Decision Problems (MDP). We focus on medium-size problems whose state space can be fully enumerated. This problem has numerous important applications, such as navigation and planning under uncertainty. We propose a new approach for constructing a multi-level hierarchy of progressively simpler abstractions of the original problem. Once computed, the hierarchy can be used to speed up planning by first finding a policy for the most abstract level and then recursively refining it into a solution to the original problem. This approach is fully automated and delivers a speed-up of two orders of magnitude over a state-of-the-art MDP solver on sample problems while returning near-optimal solutions. We also prove theoretical bounds on the loss of solution optimality resulting from the use of abstractions.


Recap of the Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE)

AI Magazine

The Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment was held from October 11–14, 2011, on the campus of Stanford University near Palo Alto, California. This report summarizes the conference and related activities.