bluuebunny/crossref_metadata_2025 huggingface dataset:
The Trial The Trail, Act 3 A Virtual Reality Drama Using Intelligent Agents
Authors: Shapiro Stuart , Anstey Josephine , Pape David , Nayak Trupti , Kandefer Michael , Telhan Orkan
Published: October 2022

The Trail is an interactive drama running on an immersive VR system. Imagine Tarkovsky's Stalker, crossed with Alice Through the Looking Glass, crossed with Monty Python and the Holy Grail. Now imagine embarking on a guided journey through this warped yet familiar landscape. Your guides are two intelligent agents, Patofil and Filopat. We consider a virtual reality drama to be a scripted play in which the computational agents are actors who have copies of the script, and one human audience member has been drafted to be a participant, but doesn't have a copy of the script. The computational actors must improvise reactions to the human participant's actions, but keep the play moving along in as close agreement to the script as possible. The goal is to provide the human participant with a specific emotional experience.
Goal-Directed Hierarchical Dynamic Scripting for RTS Games
Authors: Dahlbom Anders , Niklasson Lars
Published: October 2022

Learning how to defeat human players is a challenging task in today's commercial computer games. This paper suggests a goal-directed hierarchical dynamic scripting approach for incorporating learning into real-time strategy games. Two alternatives for shortening the re-adaptation time when using dynamic scripting are also presented. Finally, this paper presents an effective way of throttling the performance of the adaptive artificial intelligence system. Put together, the approach entails the possibility of an artificial intelligence opponent to be challenging for a human player, but not too challenging.
An Abstraction Framework for Cooperation Among Agents and People in a Virtual World
Authors: McDonald David , Leung Alice , Ferguson William , Hussain Talib
Published: October 2022

With increasing sophistication in modeling interpersonal interactions, including cultural and social factors, it is now possible and desirable to bring together state-of-the-art human behavior models (HBMs) developed through different approaches in a framework that facilitates interoperability, composability, and comparison. Such a framework is needed in order for game or simulation environments to allow heterogeneous agents (synthetic characters driven by HBMs) to interact with each other and to interact with human players, even though their information needs and operating premises may differ. An important part of such an interoperability framework is an agent message system supporting multiple levels of abstraction. To demonstrate the viability of such a framework, we created an environment that supported synthetic characters interacting with each other and a human player in a common scenario. The agents were provided by different researchers built upon different technical approaches, yet were able to communicate through messages featuring multiple levels of abstraction to describe actions and events. In this paper, we describe our choices of message abstraction levels, what we developed, and the architecture of the framework that we used to mediate the interaction among all the participants, synthetic and human.
Modelling Goal-Directed Players in Digital Games
Authors: Thue David , Bulitko Vadim
Published: October 2022

The pursuit of a viable model of player behaviour has gained momentum in research in recent years, and it is beginning to attract the attention of the designers of next-generation digital games. In this paper, we present a novel enhancement to player modelling that is well-suited to the digital role-playing and puzzle game industries, titled Goal-Directed- Player Modelling, in which state abstraction based on a player's goals is used to improve the performance of a classifier for predicting player actions. We survey a set of related research, formally introduce a method for Goal-Directed-Player Modelling, and present empirical results which clearly show the ability of Goal-Directed-Player Modelling to greatly improve the accuracy of a simple, online, low cost incremental classi ier to a level near those of more advanced and complex of line methods.
Procedural Level Design for Platform Games
Authors: Compton Kate , Mateas Michael
Published: October 2022

Although other genres have used procedural level generation to extend gameplay and replayability, platformer games have not yet seen successful level generation. This paper proposes a new four-layer hierarchy to represent platform game levels, with a focus on representing repetition, rhythm, and connectivity. It also proposes a way to use this model to procedurally generate new levels.
Normative Echoes: Use and Manipulation of Player Generated Content by Communities of NPCs
Authors: Baumer Eric , Tomlinson Bill , Yau Man , Alspaugh Thomas
Published: October 2022

Normative Echoes is an interactive installation that explores ways to combine player-created content with procedural content. Animated autonomous agents inhabit virtual islands on stationary computers; a tablet PC is used as a virtual raft to transfer agents between the islands. The agents on each island communicate with one another and form scenario-based computational representations of their social interactions. These scenarios represent emergent social patterns and norms within the society. Humans can communicate with the animated autonomous agents through the use of a microphone. Utterances spoken by participants are parsed, repeated, and learned by agents, then used by the agents in communications with their social partners. When transferred between islands, agents bring with themselves the utterances and norms they have learned, thus spreading those norms throughout the various communities in the installation. In this way, agents can meaningfully perform procedural operations on player-created content, allowing for a dynamic and engaging experience.
A Demonstration of ScriptEase Ambient and PC-Interactive Behavior Generation for Computer Role-Playing Games
Authors: Cutumisu Maria , Szafron Duane , Schaeffer Jonathan , Waugh Kevin , Onuczko Curtis , Siegel Jeff , Schumacher Allan
Published: October 2022

ScriptEase is a visual tool that enables game designers to create complex interactive stories for computer role-playing games, without programming. In particular, ScriptEase automatically generates the scripting code for ambient and PC-interactive non-player character (NPC) behaviors from a set of behavior patterns. Without ScriptEase, a game designer would have to write scripting code manually to specify NPC behaviors. This demonstration describes the steps of generating complex and non-repetitive ambient and PC-interactive behavior scripts using generative behavior patterns with ScriptEase. We show how ambient behavior patterns are used to re-generate and improve the behaviors of all ambient NPCs in the Prelude module of the BioWare Corporation's Neverwinter Nights official campaign. We also demonstrate PC-interactive behaviors for a guard NPC in a custom Neverwinter Nights game module. With ScriptEase behavior patterns, game designers can easily and quickly populate a story with an engaging group of NPCs.
A Believable Agent for First-Person Shooter Games
Authors: Choi Dongkyu , Konik Tolga , Nejati Negin , Park Chunki , Langley Pat
Published: October 2022

In this paper, we present a principled approach to constructing believable game players that relies on a cognitive architecture. The resulting agent is capable of playing the game \uc/ in a plausible manner when faced with similar situations as its human counterparts. We discuss how architectural features like goal-directed but reactive execution and incremental learning can produce more believable synthetic characters.
Episodic Memory: A Final Frontier (Abbreviated Version)
Authors: Forbus Kenneth , Kuehne Sven
Published: October 2022

A major limitation of today's computer games is the shallowness of interactions with non-player characters. To build up relationships with players, NPCs should be able to remember shared experiences, including conversations, and shape their responses accordingly. We believe that progress in AI has already reached the point where research on using NLP and large KBs in games could lead to important new capabilities. We describe our Listener Architecture for conversational games, which has been implemented in a toolkit used to make short experimental games. Episodic memory plays a central role, using analogical reasoning over a library of previous conversations with the player. Examples and scale-up issues are discussed.
HPA* Enhancements
Authors: Jansen M. , Buro Michael
Published: October 2022

In video games, pathfinding must be done quickly and accurately. Not much computational time is allowed for pathfinding, but realistic looking paths are required. One approach to pathfinding which attempts to satisfy both of these constraints is to perform pathfinding on abstractions of the map. Botea et al.'s Hierarchical Pathfinding A* (HPA*) does this by dividing the map into square sectors and defining entrances between them. Although HPA* performs quick pathfinding which produces near-optimal paths, some improvements can be introduced. Here we discuss a faster path smoothing method, an alternative way to compute the weights of abstract edges, and lazy edge weight computations.
From Synthetic Characters to Virtual Actors
Authors: Louchart Sandy , Aylett Ruth
Published: October 2022

We discuss the extension of an emotionally-driven agent architecture already applied to the creation of emergent narratives. Synthetic characters are enhanced to perform as actors by carrying out a second cognitive appraisal, based on the OCC model, of the emotional impact of their projected actions before execution.
Navigation Challenges in Massively Destructible Worlds
Authors: Kruszewski Paul
Published: October 2022

The creation of lifelike believable characters is emerging as the central focus of next-generation game development and is viewed as critical to obtaining true mass-market appeal. Visually-realistic movement in complex physics driven worlds is an increasingly critical component in creating believable characters. The demo is based on our extension to the Unreal 3 engine (UE3) and runs on advanced PCs, the Xbox 360 and PlayStation 3 (PS3) and shows advance navigation behaviors such as dynamic obstacle avoidance, local dynamic path finding and advanced obstacle traversal such as vaulting. A typical first-person shooter (FPS) game level (an underground subway system) is constructed out of physics-simulated objects; the benches and garbage cans can be displaced by gun fire and the pillars and railings can be destroyed by grenades. This allows the player to quickly and significantly disrupt the world making it extremely difficult for the non-player characters (NPCs) to navigate towards the player. NPCs can be given specific movement abilities so that some NPCs can avoid obstacles by circumventing them while more advanced NPCs can vault over them. Upon discovery of blocked passageways such as staircases, NPCs can take alternative routes.
A Cover-Based Approach to Multi-Agent Moving Target Pursuit
Authors: Alejandro Isaza Alejandro Isaza , Lu Jieshan , Bulitko Vadim , Greiner Russell
Published: October 2022

We explore the task of designing an efficient multi-agent system that is capable of capturing a single moving target, assuming that every agent knows the location of all agents on a fixed known graph. Many existing approaches are suboptimal as they do not coordinate multiple pursuers and are slow as they re-plan each time the target moves, which makes them fare poorly in real-time pursuit scenarios such as video games. We address these shortcomings by developing the concept of cover set, which leads to a measure that takes advantage of information about the position and speed of each agent. We first define cover set and then present an algorithm that uses cover to coordinate multiple pursuers. We compare the effectiveness of this algorithm against several classic and state-of-the-art pursuit algorithms, along several performance measures. We also compute the optimal pursuit policy for several small grids, and use the associated optimal scores as yardsticks for our analysis.
Modeling the Dynamics of Non-Player Characters' Social Relations in Video Game
Authors: Ochs Magalie , Sabouret Nicolas , Corruble Vincent
Published: October 2022

Building credible Non-Player Characters (NPCs) in games requires not only to enhance the graphic animation but also the behavioral model. This paper tackles the problem of the dynamics of NPCs social relations depending on their emotional interactions. First, we discuss the need for a dynamic model of social relations. Then, we present our model of social relations for NPCs and we give a qualitative model of the influence of emotions on social relations. We describe the implementation of this model and we briefly illustrate its features on a simple scene.
Combining Model-Based Meta-Reasoning and Reinforcement Learning For Adapting Game-Playing Agents
Authors: Ulam Patrick , Jones Joshua , Goel A.
Published: October 2022

Human experience with interactive games will be enhanced if the software agents that play the game learn from their failures. Techniques such as reinforcement learning provide one way in which these agents may learn from their failures. Model-based meta-reasoning, a technique in which an agent uses a self-model for blame assignment, provides another. This paper evaluates a framework in which both these approaches are combined. We describe an experimental investigation of a specific task (defending a city) in a computer war strategy game called FreeCiv. Our results indicate that in the task examined, model-based meta-reasoning coupled with reinforcement learning enables the agent to learn the task with performance matching that of an expert designed agent and with speed exceeding that of a pure reinforcement learning agent.
Navigating Detailed Worlds with a Complex, Physically Driven Locomotion: NPC Skateboarder AI in EA’s Skate
Authors: Wesley Mark
Published: October 2022

This talk describes the motivation, design and implementation behind the AI for the NPC Skateboarders in skate. The complexity of the physically driven locomotion used in skate means that, at any given point, there is an extremely large number of degrees of freedom in potential motion. In addition to this, the rules governing whether it is possible to navigate from any given point A to a secondary point B are entirely dependent on the skateboarder's state at point A. The state required at point A involves a large number of variables, as well as a complex set of previously executed maneuvers to have reached it.
Adaptive Spatial Reasoning for Turn-Based Strategy Games
Authors: Maurice Bergsma Maurice Bergsma , Spronck Pieter
Published: October 2022

The quality of AI opponents often leaves a lot to be desired, which poses many attractive challenges for AI researchers. In this respect, Turn-based Strategy (TBS) games are of particular interest. These games are focussed on high-level decision making, rather than low-level behavioural actions. For efficiently designing a TBS AI, in this paper we propose a game AI architecture named ADAPTA (Allocation and Decomposition Architecture for Performing Tactical AI). It is based on task decomposition using asset allocation, and promotes the use of machine learning techniques. In our research we concentrated on one of the subtasks for the ADAPTA architecture, namely the Extermination module, which is responsible for combat behaviour. Our experiments show that ADAPTA can successfully learn to outperform static opponents. It is also capable of generating AIs which defeat a variety of static tactics simultaneously.
A Framework for the Semi-Automatic Testing of Video Games
Authors: Nantes Alfredo , Brown Ross , Maire Frederic
Published: October 2022

Game environments are complex interactive systems that require extensive analysis and testing to ensure that they are at a high enough quality to be released commercially. In particular, the last build of the product needs an additional and extensive beta test carried out by people that play the game in order to establish its robustness and playability. This entails additional costs from the viewpoint of a company as it requires the hiring of play testers. In the present work we propose a general software framework that integrates Artificial Intelligence (AI) Agents and Computer Vision (CV) technologies to support the test team and help to improve and accelerate the test process. We also present a prototype shadow alias detection algorithm that illustrates the effectiveness of the framework in developing automated visual debugging technology that will ease the heavy cost of beta testing games.
Monte-Carlo Tree Search: A New Framework for Game AI
Authors: Chaslot Guillaume , Bakkes Sander , Szita Istvan , Spronck Pieter
Published: October 2022

Classic approaches to game AI require either a high quality of domain knowledge, or a long time to generate effective AI behaviour. These two characteristics hamper the goal of establishing challenging game AI. In this paper, we put forward Monte-Carlo Tree Search as a novel, unified framework to game AI. In the framework, randomized explorations of the search space are used to predict the most promising game actions. We will demonstrate that Monte-Carlo Tree Search can be applied effectively to (1) classic board-games, (2) modern board-games, and (3) video games.
Integrating Drama Management into an Adventure Game
Authors: Sullivan Anne , Chen Sherol , Mateas Michael
Published: October 2022

Often, video game designers must choose between creating a linear experience, and designing an open world with many different story lines that fail to form a tightly crafted narrative arc. A drama manager (DM) can provide a solution to this dilemma. ADM monitors an interactive experience, such as a computer game, and intervenes to shape the global experience so that it satisfies the author's expressive goals without decreasing a player's interactive agency. In this demo we present the first integration of declarative optimization-based drama management (DODM) into an adventure-style dungeon game called EMPath.
Prototyping Games with BIPED
Authors: Smith Adam , Nelson Mark , Mateas Michael
Published: October 2022

We demonstrate the use of BIPED, a system that explores a new approach to supporting the early stages of game design. Using BIPED, a game designer can leverage a single, concise game definition to get both a playable prototype and a formal rule system. In this way, BIPED's two legs give a designer access to insight: the first through feedback from human players (revealing player hesitation, engagement, or fun) and the second through automated analysis (revealing emergent properties, exploits, and puzzle solutions). Our system focuses on board-game-like prototypes. On screen, human players manipulate individual tokens that are arranged on board spaces linked by paths. Using the mouse, they can trigger game events that interact with the designer-specified game mechanics. On the design side, designers have access to timers, allowing them to create interesting, real-time dynamics. In addition to play testing with human subjects, we support a form of machine play testing. Using only the game definition, our analysis engine is capable of imagining complete play traces showing a log of game state and events over time. To drill down on interesting scenarios, the designer may specify additional constraints and ask the engine to show only (and possibly all) traces that fit these constraints. Examples include: defeat happens at time seven, no more than six monsters are slain, and the player character always picks up treasures.
A Method for Acquiring Body Movement Verbs for a Humanoid Robot through Physical Interaction with Humans
Authors: Hasegawa Dai , Rzepka Rafal , Araki Kenji
Published: October 2022

In this paper, we propose a language grounding method that relates verbs which imply body manipulation to motor angle patterns in a humanoid robot to make robots more entertaining. In established methods, verbs are represented by statistical models based on trajectories or motor patterns of a trajector. In our method we use a novel representation model that has six features including both trajector-reference point relationships and the trajector's trajectory. By using this model, some verbs which do not depend on a trajectory, e.g. "move the right hand close to the left hand." are represented more adequately. In our language grounding method a humanoid robot generates abstract verb meanings independent of context. As input it uses sets of a user input textual command and a motor pattern. The motor pattern is taught using direct physical feedback resembling playing with child. We implemented the algorithm in a humanoid robot and conducted a verb acquisition experiment. As a result, four problematic verbs, "place-on", "move-close-to", "move-away-from", and "touch-with" were acquired correctly.
Using Semantics to Improve the Design of Game Worlds
Authors: Tutenel Tim , Smelik Ruben , Bidarra Rafael , De Kraker Klaas Jan
Published: October 2022

Design of game worlds is becoming more and more labor-intensive because of the increasing demand and complexity of content. This is being partially addressed by developing semi-automated procedural techniques that help generate (parts of) game worlds (e.g terrains, cities and buildings). However, most level editors rather deficiently capture and deploy designer's intent. For example, common positional or functional relationships between objects are usually limited to pre-processing a number of anticipated cases. In this paper we propose a novel scheme for specifying high-level semantics of objects within a game virtual world, and in particular we illustrate its application to a variety of layout solving problems raised by procedural generation methods. Our approach combines the genericity of a semantic class library with the power of a layout solver, and it shows to be both very flexible and effective. Moreover, this scheme can be useful for improving both manual, automated and mixed modeling techniques, always leading to a more efficient layouting process for game worlds. We conclude that by allowing designers to capture more of their intent and real-life knowledge in the objects with which they populate a game world, the integration of semantics will strongly contribute to stimulate content reusability, enrich the game play, and eventually also significantly cut down design duration and cost.
Investigating the Interplay between Camera Viewpoints, Game Information, and Challenge
Authors: Jhala Arnav , Schwartz Martin , Perez Martinez Hector , Yannakakis Georgios
Published: October 2022

Players perceive information about game environments through a virtual camera. While a significant discussion in the industry and in academic research circles has centered around effective camera control, it is focused mainly on occlusion free placement and smooth movement. The relationship between information communicated by the camera about game state and the selection of camera parameters has not been investigated.In this paper, we present a systematic investigation of the effect of different camera profiles on player experience in a 3D prey/predator test-bed game. We describe a constraint-based dynamic camera system that maintains the position and orientation of the camera based on the constraints imposed by given camera profiles. The impact of different profiles on the amount of game information provided to the player and the player's game challenge preferences is investigated through a user experiment. An artificial neural network model of challenge constructed using artificial evolution reveals the non-linear mapping between challenge and information features.
BehaviorShop: An Intuitive Interface for Interactive Character Design
Authors: Heckel Frederick , Youngblood G. Michael , Hale D. Hunter
Published: October 2022

Artificial intelligence for interactive characters is held back by the difficulty of actually creating those characters. There is a need for intuitive tools which simplify the process of building complex AI characters. In this paper, we present BehaviorShop, a tool for building interactive characters, and the results of a study to test the effectiveness and ease of use of this tool. The majority (80%) of test subjects were able to successfully create a complex character using BehaviorShop. Our results show success with this interface, and the advantage of using the subsumption architecture as a paradigm for character creation.
A Surprise Triggered Adaptive and Reactive (STAR) Framework for Online Adaptation in Non-stationary Environments
Authors: Nguyen Truong-Huy , Leong Tze-Yun
Published: October 2022

We consider the task of developing an adaptive autonomous agent that can interact with non-stationary environments.  Traditional learning approaches such as Reinforcement Learning assume stationary characteristics over the course of the problem, and are therefore unable to learn the dynamically changing settings correctly.  We introduce a novel adaptive framework that can detect dynamic changes due to non-stationary elements. The Surprise Triggered Adaptive and Reactive (STAR) framework is inspired by human adaptability in dealing with daily life changes.  An agent adopting the STAR framework consists primarily of two components, Adapter and Reactor. The Reactor chooses suitable actions based on predictions made by a model of the environment. The Adapter observes the amount of “surprisingness” and triggers the generation of new models accordingly. Preliminary experimental results show that STAR agents are competitive in performance as compared with current approaches, while being much more cost-effective by avoiding the negative effects of historical data. Furthermore, since response and adaptability are decoupled in the framework, the adaptive component can benefit other autonomous agents in a variety of domains with non-stationary environments.
Learning Character Behaviors Using Agent Modeling in Games
Authors: Zhao Richard , Szafron Duane
Published: October 2022

Our goal is to provide learning mechanisms to game agents so they are capable of adapting to new behaviors based on the actions of other agents. We introduce a new on-line reinforcement learning (RL) algorithm, ALeRT-AM, that includes an agent-modeling mechanism. We implemented this algorithm in BioWare Corp.’s role-playing game, Neverwinter Nights to evaluate its effectiveness in a real game. Our experiments compare agents who use ALeRT-AM with agents that use the non-agent modeling ALeRT RL algorithm and two other non-RL algorithms. We show that an ALeRT-AM agent is able to rapidly learn a winning strategy against other agents in a combat scenario and to adapt to changes in the environment.
Invited Talks
Authors: Basu Sumit , Jurney Chris , Sottilare Bob , Young R.
Published: October 2022

Abstracts of the invited talks presented at the 2010 AAAI AIIDE Conference.
Designing a Massively Multiplayer Online Game / Research Testbed Featuring AI-Driven NPC Communities
Authors: Zyda Michael , Spraragen Marc , Ranganathan Balki , Arnason Bjarni , Landwehr Peter
Published: October 2022

Massively Multiplayer Online Games (MMOGs), in their aspect as online communities, represent an exciting opportunity for studying social and behavioral models.  For that purpose we have developed Cosmopolis, a free MMOG containing several key research-oriented features.  First, Cosmopolis consists of an outer game for larger-scale social modeling, as well as a set of subgames suitable for tightly-controlled sandbox-style experiments, all allowing a high level of data logging configuration and control by researchers.  Also, Cosmopolis’s world model incorporates configurable, AI-driven non-player character communities, as a means of researching interactions between individuals and societies
Breaking Path Symmetries on 4-Connected Grid Maps
Authors: Harabor Daniel , Botea Adi
Published: October 2022

Pathfinding systems that operate on regular grids are common in the AI literature and often used in real-time video games. Typical speed-up enhancements include reducing the size of the search space using abstraction, and building more informed heuristics. Though effective each of these strategies has shortcomings. For example, pathfinding with abstraction usually involves trading away optimality for speed. Meanwhile, improving on the accuracy of the well known Manhattan heuristic usually requires significant extra memorWe present a different kind of speedup technique based on the idea of identifying and eliminating symmetric path segments in 4-connected grid maps (which allow straight but not diagonal movement). Our method identifies rectangular rooms with no obstacles and prunes all interior nodes, leaving only a boundary perimeter. This process eliminates many symmetric path segments and results in grid maps which are often much smaller and consequently much faster to search than the original. We evaluate our technique on a range of different grid maps including a well known set from the popular video game Baldur's Gate II. On our test data, A* can run up to 3.5 times faster on average. We achieve this without using any significant extra memory or sacrificing solution optimality.
DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds
Authors: Kring Alexander , Champandard Alex , Samarin Nick
Published: October 2022

In 2004, Botea et al. published the HPA* algorithm (Hierarchical Pathfinding A*), which is the first detailed study of hierarchical pathfinding in games. However, HPA* can be optimized. In this paper, we introduce the DHPA* and SHPA* hierarchical pathfinding algorithms, along with a metric for comparing the dynamic performance of pathfinding algorithms in games. We show that DHPA* searches up to an order of magnitude faster than HPA*, but consumes significantly more memory and produces slightly less optimal paths. The SHPA* algorithm searches up to five times faster than HPA* and consumes less memory, but it also produces slightly less optimal paths, and is only fit for static environments. When comparing the algorithms in dynamic environments, our results show that DHPA* often outperforms HPA*. Unlike many other hierarchical pathfinding algorithms, both solutions presented in this paper maintain a read-only terrain representation during search, which simplifies programming and debugging, and improves multithreaded performance.
A Semantic Scene Description Language for Procedural Layout Solving Problems
Authors: Tutenel Tim , Smelik Ruben , Bidarra Rafael , De Kraker Klaas Jan
Published: October 2022

Procedural content generation is becoming more and more relevant to solve the problem of content creation for the ever growing virtual worlds of games, simulations and other applications. However, these procedures are often unintuitive or use vague parameters, making it somewhat difficult for a designer to express his or her creative intent. Even worse, most of these techniques lack an accessible and easy to use interface.We have developed a generic layout solving approach to automatically create sensible content for virtual worlds. In that context, this paper proposes a high-level scene description language that allows designers to specify particular types of scenes. This description language allows designers to easily specify which objects need to be present in a scene, their attributes, and possible interrelationships. Application of the language, based on the rich vocabulary taken from a semantic library, is illustrated with several examples, showing its flexibility, intuitiveness and ease of use.
Realistic Fireteam Movement in Urban Environments
Authors: Darken Christian , McCue Daniel , Guerrero Michael
Published: October 2022

Realistic simulations of the movement of infantry in urban environments with 3D models and at interactive rates is of wide and enduring interest. Many video games have attempted it, and military simulations are increasingly doing the same. Previous attempts have fallen short in two areas: properly coordinating movement, and adequate modeling of the detection of hostile targets. Novel algorithms to simulate fireteam movement and visual scanning appropriate to urban environments are described. Measurements of the computational performance of the most expensive components of the approach are provided.
Terrain Analysis in Real-Time Strategy Games: An Integrated Approach to Choke Point Detection and Region Decomposition
Authors: Perkins Luke
Published: October 2022

Autonomous agents in real-time strategy (RTS) games lack an integrated framework for reasoning about choke points and regions of open space in their environment. This paper presents an algorithm which partitions the environment into a set of polygonal regions and computes optimal choke points between adjacent regions. This representation can be used as a component for AI agents to reason about terrain, plan multiple routes of attack, and make other tactical decisions. The algorithm is tested on a set of popular maps commonly used in international Starcraft competitions and evaluated against answers made by human participants. The algorithm identified 97% of the choke points that the participants found and also identified a number of bottlenecks that human participants did not recognize as choke points.
Player Modeling in Civilization IV
Authors: Spronck Pieter , Den Teuling Freek
Published: October 2022

This research aims at building a preference-based player model of Civilization IV players. Our model incorporates attributes which are defined for AI players. We use a sequential minimal optimization (SMO) classifier to build the player model based on a training set with observations of a large number of games between six AI players. The model was validated on a test set of games between the same six AI players. While it did not seem to generalize well to the preferences of different AI players, it did manage to accurately predict some of the preferences for a veteran human player. Further tests showed that AI players with the same play styles but different preference values were often confused by the model. We conclude that for a complex game such as Civilization IV a model that attempts to accurately predict specific preference values is hard to construct. A model that focusses on play styles might succeed better.
On the Complexity of Two-Player Attrition Games Played on Graphs
Authors: Furtak Timothy , Buro Michael
Published: October 2022

The attrition game considered in this study is a graph based strategic game which is a movement-prohibited analogue of small-scale combat situations that arise frequently in popular real-time strategy video games. We present proofs that the attrition game, under a variety of assumptions, is a computationally hard problem in general. We also analyze the 1 vs. n unit case, for which we derive optimal target-orderings that can be computed in polynomial time and used as a core for heuristics for the general case. Finally, we present small problem instances that require randomizing moves — a fact that at first glance seems counter-intuitive.
Multi-Agent Coordination Using Dynamic Behavior-Based Subsumption
Authors: Heckel Frederick , Youngblood G.
Published: October 2022

Team coordination of non-player characters can create a deeper sense of immersion in real-time games by allowing characters to work together to produce better tactics and strategy. Achieving multi-agent coordination can be a difficult problem, and can incur substantial computational costs. Our goal with this work is to produce a reactive method for coordinating game characters that will allow computationally inexpensive team coordination. Reactive teaming creates teams of agents through the use of simple constant-time agent interactions without increasing the difficulty of authoring game characters.
Novice-Friendly Authoring of Plan-Based Interactive Storyboards
Authors: Skorupski James , Mateas Michael
Published: October 2022

Story Canvas is a visual authoring tool for the creation of interactive, generative stories. Aimed at authors without a technical background in computational storytelling, our system takes an existing author goal-based narrative planning architecture and adds a highly visual authoring and reading interface to the technology, using the language of storyboards and comics as a framework for both authoring and interacting with the resulting narratives. In this paper we describe Story Canvas and its evolution from our previous authoring work, including how our interface choices have been driven by our previous experiences with non-technical authors, and describe the details of translating the visual authoring constructs into story plans within the story generator.
Minstrel Remixed: Procedurally Generating Stories
Authors: Tearse Brandon , Wardrip-Fruin Noah , Mateas Michael
Published: October 2022

We are recreating, investigating, and defining new uses for one of the most influential artificial intelligence projects of the past 25 years: Scott Turner’s Minstrel, which is regarded as a landmark in both the story generation and computational creativity communities. We compare our new system, Minstrel Remixed, with the implementation of the original, and discuss the various additions made during our rational reconstruction which facilitate investigations into the inner workings of the system. In conclusion, we evaluate the performance of Minstrel Remixed and determine that its results are quite close to those of the original.
AIPaint: A Sketch-Based Behavior Tree Authoring Tool
Authors: Becroft David , Bassett Jesse , Mejia Adrian , Rich Charles , Sidner Candace
Published: October 2022

Current behavior authoring tools force game designers to split their attention between the game context and the tool context. We have addressed this problem by developing a behavior authoring tool that merges these two contexts. This paper outlines the design and implementation of a gameindependent behavior tree authoring tool, called AIPaint, that allows a designer to create and edit behavior trees via a natural sketching interface overlaid on the game world. We demonstrate the use of AIPaint to author computercontrolled characters in two simple games and report on an observational evaluation.
CAPIR: Collaborative Action Planning with Intention Recognition
Authors: Nguyen Truong-Huy , Hsu David , Lee Wee-Sun , Leong Tze-Yun , Kaelbling Leslie , Lozano-Perez Tomas , Grant Andrew
Published: October 2022

We apply decision theoretic techniques to construct non-player characters that are able to assist a human player in collaborative games. The method is based on solving Markov decision processes, which can be difficult when the game state is described by many variables. To scale to more complex games, the method allows decomposition of a game task into subtasks, each of which can be modelled by a Markov decision process. Intention recognition is used to infer the subtask that the human is currently performing, allowing the helper to assist the human in performing the correct task. Experiments show that the method can be effective, giving near-human level performance in helping a human in a collaborative game.
Learning Policies for First Person Shooter Games Using Inverse Reinforcement Learning
Authors: Tastan Bulent , Sukthankar Gita
Published: October 2022

The creation of effective autonomous agents (bots) for combat scenarios has long been a goal of the gaming industry. However, a secondary consideration is whether the autonomous bots behave like human players; this is especially important for simulation/training applications which aim to instruct participants in real-world tasks. Bots often compensate for a lack of combat acumen with advantages such as accurate targeting, predefined navigational networks, and perfect world knowledge, which makes them challenging but often predictable opponents. In this paper, we examine the problem of teaching a bot to play like a human in first-person shooter game combat scenarios. Our bot learns attack, exploration and targeting policies from data collected from expert human player demonstrations in Unreal Tournament. We hypothesize that one key difference between human players and autonomous bots lies in the relative valuation of game states. To capture the internal model used by expert human players to evaluate the benefits of different actions, we use inverse reinforcement learning to learn rewards for different game states. We report the results of a human subjects' study evaluating the performance of bot policies learned from human demonstration against a set of standard bot policies. Our study reveals that human players found our bots to be significantly more human-like than the standard bots during play. Our technique represents a promising stepping-stone toward addressing challenges such as the Bot Turing Test (the CIG Bot 2K Competition).
Toward a Rapid Prototyping Environment for Character Behavior
Authors: Horswill Ian
Published: October 2022

I describe work in progress on a system for interactiveprototyping of AI-based characters. A sort of "Sims construction set," the system combines a simple physics simulation with a set of domain-specific languages to allow programmers to quickly build and test character AI. It allows iterative, incremental development in which behaviors can be compactly authored, tested, monitored, and hot-swapped for new behaviors, using in-game editing and debugging facilities.
AI for Massive Multiplayer Online Strategy Games
Authors: Barata Alexandre , Santos Pedro , Prada Rui
Published: October 2022

Massive Multiplayer Online Strategy games present several unique challenges to players and designers. There is the need to constantly adapt to changes in the game itself and the need to achieve a certain level of simulation and realism, which typically implies battles involving combat with several distinct armies, combat phases and diferent terrains; resource management which involves buying and selling goods and combining lots of diferent kinds of resources to fund the player's nation and cutthroat diplomacy which dictates the pace of the game. However, these constant changes and simulation mechanisms make a game harder to play, increasing the amount of effort required to play it properly. As some of these games take months to be played, players who become inactive have a negative impact on the game. This work pretends to demonstrate how to create versatile agents for playing Massive Multiplayer Online Turn Based Strategy Games, while keeping close attention to their playing performance. In a test to measure this performance the results showed similar survival performance between humans and AIs.
Any-Angle Path Planning for Computer Games
Authors: Yap Peter , Burch Neil , Holte Robert , Schaeffer Jonathan
Published: October 2022

Path planning is a critical part of modern computer games; rare is the game where nothing moves and path planning is unneeded. A* is the workhorse for most path planning applications. Block A* is a state-of-the-art algorithm that is always faster than A* in experiments using game maps. Unlike other methods that improve upon A*'s performance, Block A* is never worse than A* nor require any knowledge of the map. In our experiments, Block A* is ideal for games with randomly generated maps, large maps, or games with a highly dynamic multi-agent environment. Furthermore, in the domain of grid-based any-angle path planning, we show that Block A* is an order of magnitude faster than the previous best any-angle path planning algorithm, Theta*. We empirically show our results using maps from Dragon Age: Origins and Starcraft. Finally, we introduce ``populated game maps'' as a new test bed that is a better approximation of real game conditions than the standard test beds of this field. The main contributions of this paper is a more rigorous set of experiments for Block A*, and introducing a new test bed (populated game maps) that is a more accurate representation of actual game conditions than the standard test beds.
Design and Evaluation of Afterthought, A System that Automatically Creates Highlight Cinematics for 3D Games
Authors: Dominguez Mike , Young R. Michael , Roller Stephen
Published: October 2022

Online multiplayer gaming has emerged as a popular form of entertainment. the course of a multiplayer game, playerinteractions may result in interesting emer- gent narratives that go unnoticed. Afterthought is a system that monitors player activity, recognizes instances of story elements in gameplay and renders cinematic highlights of the story-oriented game play, allowing players to view these emergent narratives after completing their gameplay session. This paper describes Afterthought’s implementation as well as an empirical human-subjects evaluation of the effectiveness of the cinematics that it creates.
Wasp-Like Scheduling for Unit Training in Real-Time Strategy Games
Authors: Santos Marco , Martinho Carlos
Published: October 2022

Gameplay in real-time strategy games seems somehow to be confined to a de facto standard where economical micro-management is equally important as combat strategy, if not more important. To enable stronger combat-oriented gameplay without sacrificing other key aspects of the genre, we propose an automated system for scheduling unit training, which we believe may allow the exploration of new paradigms of play. To be accepted by the player, such a system must, among other things, be efficient and reliable, which is a non-trivial task considering the highly dynamic nature of the environment in this genre of games. To overcome such a challenge, we propose a system inspired in the swarm intelligence demonstrated by social insects, namely wasps, and describe its limitations and benefits, based on the evaluation of an implementation of the approach as a modification of the game Warcraft III The Frozen Throne (Blizzard Entertainment, 2003).
Corpus Annotation in Service of Intelligent Narrative Technologies
Authors: Finlayson Mark
Published: October 2022

Annotated corpora have stimulated great advances in the language sciences. The time is ripe to bring that same stimulation, and consequent benefits, to computational approaches to narrative. I describe an effort to construct a corpus of semantically annotated stories. I outline the structure of the corpus, a structure which colloquially can be described as a "handful of handfuls." One handful of the corpus has already been constructed, viz., 18k words of Russian folktales. There are two handfuls under construction: legal cases focused on the area of probable cause, and stories from Islamist Extremist Jihadists. Four more handfuls are being planned: folktales from Chinese, English, and a West Asian culture, and stories of international conventional and cyber conflicts. There are numerous additional handfuls under discussion. The main focus of the corpus so far has been on textual materials that are annotated for their surface semantics using conventional annotation tools and techniques; nonetheless, there are numerous novel dimensions along which the corpus might grow and become useful for different communities. In particular I propose for discussion the outlines of a few novel sources, annotation schemes, and collection methodologies that could potentially make the corpus of great use to the interactive narrative or narrative generation communities.
Initial Results for Measuring Four Dimensions of Narrative Conflict
Authors: Ware Stephen , Harrison Brent , Young R. Michael , Roberts David
Published: October 2022

Conflict is an essential element of interesting stories. In previous work, we proposed a formal model of narrative conflict. We also described 7 dimensions which can be used to distinguish one conflict from another: participants, subject, duration, balance, directness, intensity, and resolution. This paper presents the results of an experiment designed to measure how well our metrics for balance, directness, intensity, and resolution predict the responses of human readers when asked to measure these same values in a set of four stories. We conclude that our metrics are able to rank stories similarly to human readers.