AAAI Conferences


Postmortem: MKULTRA, An Experimental AI-Based Game

AAAI Conferences

Games are inherently situated within the cultures of their players. Players bring a wide range of knowledge and expectations to a game, and the more the game suggests connections to that culture, the stronger those expectations are and/or the more problematic they can be. MKULTRA is an experimental, AI-heavy game that ran afoul of those issues. It’s interesting to hear a talk about or to see demonstrated by the author, but frustrating for players who do not already understand its internals in some detail. In this paper, I will give a postmortem of the game, in the rough style of industry postmortems from venues such as Gamasutra or GDC. I will discuss the goals and design of the game, what went right, what went wrong, and what I should have done instead. In my discussions of the game’s problems, I’ll focus on the ways in which it frustrated the players’ cultural expectations, and what we can learn from them for the design of future games.


CatSAT: A Practical, Embedded, SAT Language for Runtime PCG

AAAI Conferences

Answer-set programming (ASP), a family of SAT-based logic programming systems, is attractive for procedural content generation. Unfortunately, current solvers present significant barriers to runtime use in games. In this paper, I discuss some of the issues involved, and present CatSAT, a solver designed to better fit the run-time resource constraints of modern games. Although intended only for small problems, it allows designers to compactly specify simple PCG problems such as NPC generation, solve them in a few tens of microseconds, and to adapt solutions dynamically based on the changing needs of gameplay. We hope that by making adoption as convenient as possible, we can increase the uptake of declarative techniques among developers.


Automated Game Design via Conceptual Expansion

AAAI Conferences

Automated game design has remained a key challenge within the field of Game AI. In this paper, we introduce a method for recombining existing games to create new games through a process called conceptual expansion.Prior automated game design approaches have relied on hand-authored or crowd-sourced knowledge, which limits the scope and applications of such systems. Our approach instead relies on machine learning to learn approximate representations of games. Our approach recombines knowledge from these learned representations to create new games via conceptual expansion.We evaluate this approach by demonstrating the ability for the system to recreate existing games. To the best of our knowledge, this represents the first machine learning-based automated game design system.


Keeping the Story Straight: A Comparison of Commitment Strategies for a Social Deduction Game

AAAI Conferences

Social deduction games present a unique challenge for AI agents, because communication plays a central role in most of them, and deception plays a key role in game play. To be successful in such games, players need to come up with convincing stories, but also discern the truth of statements of other players and adapt to the information learned from them. In this paper we present an approach for virtual agents that have to determine how long to stick to their story in the light of information obtained from other players. We apply this approach to a particular social deduction game, One Night Ultimate Werewolf, and demonstrate the effect of different levels of commitment to an agent's story.


Evolutionary MCTS with Flexible Search Horizon

AAAI Conferences

In turn-based multi-action adversarial games each player turn consists of several atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, which is currently best played by Evolutionary MCTS (EMCTS) -- searching a tree with nodes representing action sequences as genomes, and edges representing mutations of those genomes. However, regular EMCTS is unable to search beyond the current player's turn, leading to strategic short-sightedness. In this paper, we extend EMCTS to search to any given search depth beyond the current turn, using simple models of its own and the opponent's behavior. Experiments on the game Hero Academy show that this Flexible-Horizon EMCTS (FH-EMCTS) convincingly outperforms several baselines including regular EMCTS, Online Evolutionary Planning (OEP), and vanilla MCTS, at all tested numbers of atomic actions per turn. Additionally, the separate contributions of the behavior models and the flexible search horizon are analyzed.


POMCP with Human Preferences in Settlers of Catan

AAAI Conferences

We present a suite of techniques for extending the Partially Observable Monte Carlo Planning algorithm to handle complex multi-agent games. We design the planning algorithm to exploit the inherent structure of the game. When game rules naturally cluster the actions into sets called types, these can be leveraged to extract characteristics and high-level strategies from a sparse corpus of human play. Another key insight is to account for action legality both when extracting policies from game play and when these are used to inform the forward sampling method. We evaluate our algorithm against other baselines and versus ablated versions of itself in the well-known board game Settlers of Catan.


GIGL: A Domain Specific Language for Procedural Content Generation with Grammatical Representations

AAAI Conferences

We introduce a domain specific language for procedural content generation (PCG) called Grammatical Item Generation Language (GIGL). GIGL supports a compact representation of PCG with stochastic grammars where generated objects maintain grammatical structures. Advanced features in GIGL allow flexible customizations of the stochastic generation process. GIGL is designed and implemented to have direct interface with C++, in order to be capable of integration into production games. We showcase the expressiveness and flexibility of GIGL on several representative problem domains in grammatical PCG, and show that the GIGL-based implementations run as fast as comparable C++ implementation and with less code.


Propositional Belief Merging with OWA Operators

AAAI Conferences

An Ordered Weighted Averaging (OWA) operator provides a parameterized family of aggregation operators which include many of the well-known operators such as the maximum, the minimum and the mean. We introduce OWA operators as propositional belief merging operators and investigate their logical properties, as well as their relation with IC and pre-IC merging operators.


Metric Temporal Extensions of DL-Lite and Interval-Rigid Names

AAAI Conferences

The DL-Lite description logics allow for modeling domain knowledge on top of databases and for efficient reasoning. We focus on metric temporal extensions of DL-Lite_bool and its fragments, and study the complexity of satisfiability. In particular, we investigate the influence of rigid and interval-rigid symbols, which allow for modeling knowledge that remains valid over (some) time. We show that especially the latter add considerable expressive power in many logics, but they do not always increase complexity.


Probabilistic Coalition Structure Generation

AAAI Conferences

We introduce a model for probabilistic coalition structure generation (PCSG). This model generalizes the standard CSG model to the case when some of the agents considered at start may be finally defective but a new coalition structure based on the remaining agents cannot be formed. In a PCSG, one seeks to maximize the expected utility of a coalition structure. Two policies making precise how the value of a coalition structure evolves when some agents are missing are also introduced.