Hanabiis a cooperative game that brings the problem of modeling other players to the forefront. In this game, coordinated groups of players can leverage preestablished conventions to great effect. In this article, we focus onad hocsettings with no previous coordination between partners. We introduce a “Bayesian Meta-Agent” that maintains a belief distribution over hypotheses of partner policies. The policies that serve as initial hypotheses are generated using MAP-Elites, to ensure behavioral diversity. We evaluate an “Adaptive” version of the agent, which selects a response policy based on the updated belief distribution and a “Generalist” version, which selects a response based on the uniform prior. In short episodes of ten games with a consistent partner, the “Adaptive” version outperforms the “Generalist” when the training and evaluation populations are the same. This presents a first step toward an agent that can model its partner and adapt within a time frame that is compatible with human interaction.

Game designers take into account the wide range of play-styles and skill levels of players to create enjoyable experiences. One important step in the game design process involves playtests with professional testers; this process is time-consuming and expensive. Hence, there exist several methods to create synthetic testers to test a game automatically. However, one shortcoming is the lack of realistic-playing with different play-styles and skill levels. In this paper, we propose a game level authoring tool that incorporates synthetic testers, which enable the control of play-styles and skill levels. Furthermore, we utilize visualization techniques to help assess the difficulty level of each part of the stage. Our user studies confirmed that our tool was effective for designing game stages appropriate for a particular type of player.

In complex scenarios where a model of other actors is necessary to predict and interpret their actions, it is often desirable that the model works well with a wide variety of previously unknown actors. Hanabi is a card game that brings the problem of modeling other players to the forefront, but there is no agreement on how to best generate a pool of agents to use as partners in ad-hoc cooperation evaluation. This paper proposes Quality Diversity algorithms as a promising class of algorithms to generate populations for this purpose and shows an initial implementation of an agent generator based on this idea. We also discuss what metrics can be used to compare such generators, and how the proposed generator could be leveraged to help build adaptive agents for the game.

Recommender Systems are widely and successfully applied in e-commerce. Could they be used for designƒ In this paper, we introduce Pitako1, a tool that applies the Recommender System concept to assist humans in creative tasks. More specifically, Pitako provides suggestions by taking games designed by humans as inputs, and recommends mechanics and dynamics as outputs. Pitako is implemented as a new system within the mixed-initiative AI-based Game Design Assistant, Cicero. This paper discusses the motivation behind the implementation of Pitako as well as its technical details and presents usage examples. We believe that Pitako can influence the use of recommender systems to help humans in their daily tasks.

From the beginning of the history of AI, there has been interest in games as a platform of research. As the field developed, human-level competence in complex games became a target researchers worked to reach. Only relatively recently has this target been finally met for traditional tabletop games such as Backgammon, Chess and Go. This prompted a shift in research focus towards electronic games, which provide unique new challenges. As is often the case with AI research, these results are liable to be exaggerated or mis-represented by either authors or third parties. The extent to which these game benchmarks constitute "fair" competition between human and AI is also a matter of debate. In this paper, we review statements made by reseachers and third parties in the general media and academic publications about these game benchmark results. We analyze what a fair competition would look like and suggest a taxonomy of dimensions to frame the debate of fairness in game contests between humans and machines. Eventually, we argue that there is no completely fair way to compare human and AI performance on a game.

We present Cicero, a mixed-initiative application for prototyping two-dimensional sprite-based games across different genres such as shooters, puzzles, and action games. Cicero provides a host of features which can offer assistance in different stages of the game development process. Noteworthy features include AI agents for gameplay simulation, a game mechanics recommender system, a playtrace aggregator, heatmap-based game analysis, a sequential replay mechanism, and a query system that allows searching for particular interaction patterns. In order to evaluate the efficacy and usefulness of the different features of Cicero, we conducted a user study in which we compared how users perform in game debugging tasks with different kinds of assistance.

This paper introduces a fully automatic method for generating video game tutorials. The AtDELFI system (Automatically DEsigning Legible, Full Instructions for games) was created to investigate procedural generation of instructions that teach players how to play video games. We present a representation of game rules and mechanics using a graph system as well as a tutorial generation method that uses said graph representation. We demonstrate the concept by testing it on games within the General Video Game Artificial Intelligence (GVG-AI) framework; the paper discusses tutorials generated for eight different games. Our findings suggest that a graph representation scheme works well for simple arcade style games such as Space Invaders and Pacman, but it appears that tutorials for more complex games might require higher-level understanding of the game than just single mechanics.

The automatic generation of game tutorials is a challenging AI problem. While it is possible to generate annotations and instructions that explain to the player how the game is played, this paper focuses on generating a gameplay experience that introduces the player to a game mechanic. It evolves small levels for the Mario AI Framework that can only be beaten by an agent that knows how to perform specific actions in the game. It uses variations of a perfect A* agent that are limited in various ways, such as not being able to jump high or see enemies, to test how failing to do certain actions can stop the player from beating the level.

We present a search-based approach to generating boards and decks of cards for the game Ticket to Ride. Our evolutionary algorithm searches for boards that allow for a well-shaped game arc, and for decks that promote an equal distribution of desirability for cities. We show examples of two boards generated by our algorithm and compare our results to those of the actual components of the game. Our approach creates game content that is specifically designed towards metrics that can affect gameplay in an impactful way.

We introduce several deck of cards and dice models that can be used to represent stochastic outcomes in tabletop games. We analyze these using a toy game introduced as a Micro Combat game. By simulating the outcome of the game with these different models we can analyze them in terms of their salience, disparity, fairness and obfuscation. We expect this analysis to help designers choose the method that best suits their intended experience.

In this paper, we explore the possibility of search-based agents in games with resource-intensive forward models. We implemented a player agent in the Pommerman framework and put it against the baseline agent to measure its performance. We implemented a heuristic agent and improved it by enabling depth-limited tree search in specific gameplay moments. We also compared different node selection methods during depth-limited tree search. Our result shows that depth-limited tree search is still viable when presented with inefficient forward models and exploitation-driven selection method is the most efficient in this specific domain.

We describe a search-based approach to generating new levels for bullet hell games, which are action games characterized by and requiring avoidance of a very large amount of projectiles. Levels are represented using a domain-specific description language, and search in the space defined by this language is performed by a novel variant of the Map-Elites algorithm which incorporates a feasible-infeasible approach to constraint satisfaction. Simulation-based evaluation is used to gauge the fitness of levels, using an agent based on best-first search. The performance of the agent can be tuned according to the two dimensions of strategy and dexterity, making it possible to search for level configurations that require a specific combination of both. As far as we know, this paper describes the first generator for this game genre, and includes several algorithmic innovations.

Beginner heuristics for a game are simple rules that allow for effective playing. A chain of beginner heuristics of length N is the list of N rules that play the game best. Finding beginner heuristics is useful both for teaching a novice to play the game well and for understanding the dynamics of the game. We present and compare methods for finding beginner heuristics in a simple version of Poker: Pre-Flop Heads-Up Limit Texas Hold'em. We find that genetic programming outperforms greedy-exhaustive search and axis-aligned search in terms of finding well-playing heuristic chains of given length. We also find that there is a limited amount of non-transitivity when playing beginner heuristics of different lengths against each other, suggesting that while simpler heuristics are somewhat general, the more complex seem to overfit their training set.

Game designers can use computer-aided game design methods to model how players may experience the perceived difficulty of a game. We present methods to generate and analyze the difficulty of a wide variety of minimal action game variants throughout game space, where each point in this abstract design space represents a unique game variant. Focusing on a parameterized version of Flappy Bird, we predict hazard rates and difficulty curves using automatic playtesting, Monte Carlo simulation, a player model based on human motor skills (precision and actions per second), and survival analysis of score histograms. We demonstrate our techniques using simulated game play and actual game data from over 106 million play sessions of a popular online Flappy Bird variant, showing quantitative reasons why balancing a game for a wide range of player skill can be difficult. Some applications of our techniques include searching for a specific difficulty, game space visualization, computational creativity to find unique variants, and tuning game balance to adjust the difficulty curve even when game parameters are time varying, score dependent, or changing based on game progress.

This survey explores procedural content generation via machine learning (PCGML), defined as the generation of game content using machine learning models trained on existing content. As the importance of PCG for game development increases, researchers explore new avenues for generating high-quality content with or without human involvement; this paper addresses the relatively new paradigm of using machine learning (in contrast with search-based, solver-based, and constructive methods). We focus on what is most often considered functional game content, such as platformer levels, game maps, interactive fiction stories, and cards in collectible card games, as opposed to cosmetic content, such as sprites and sound effects. In addition to using PCG for autonomous generation, cocreativity, mixed-initiative design, and compression, PCGML is suited for repair, critique, and content analysis because of its focus on modeling existing content. We discuss various data sources and representations that affect the generated content. Multiple PCGML methods are covered, including neural networks: long short-term memory networks, autoencoders, and deep convolutional networks; Markov models: $n$-grams and multi-dimensional Markov chains; clustering; and matrix factorization. Finally, we discuss open problems in PCGML, including learning from small data sets, lack of training data, multilayered learning, style-transfer, parameter tuning, and PCG as a game mechanic.

This paper describes the design of SeekWhence, a retrospective analysis tool for gameplay session. SeekWhence is a new addition to the Cicero AI-assisted game design tool, which is built on top of the Video Game Description Language (VGDL) and the General Video Game Framework (GVG-AI). With SeekWhence, designers can prototype their games and record gameplay sessions simulated by agents or human players. They can go back and forth on every frame of the recorded session, analyzing it step by step and import it into their current project to edit it. This paper explains the technical details of SeekWhence and gives examples of its usage.

Ticket to Ride is a popular contemporary board game for two to four players, featuring a number of expansions with additional maps and tweaks to the core game mechanics. In this paper, four different game-playing agents that embody different playing styles are defined and used to analyze Ticket to Ride. Different playing styles are shown to be effective depending on the map and rule variation, and also depending on how many players play the game. The performance profiles of the different agents can be used to characterize maps and identify the most similar maps in the space of playstyles. Further analysis of the automatically played games reveal which cities on the map are most desirable, and that the relative attractiveness of cities is remarkably consistent across numbers of players. Finally, the automated analysis also reveals two classes of failures states, where the agents find states which are not covered by the game rules; this is akin to finding bugs in the rules. We see the analysis performed here as a possible template for AI-based playtesting of contemporary board games.

We introduce AniMesh, a system that supports interleaved modeling and animation creation and editing. AniMesh is suitable for rapid prototyping and easily accessible to non-experts. Source animations can be obtained from commodity motion capture devices or by adapting canned motion sequences. We propose skeleton abstraction and motion retargeting algorithms for finding correspondences and transferring motion between skeletons, or portions of skeletons, with varied topology. Motion can be copied-and-pasted between kinematic chains with different skeletal topologies, and entire model parts can be cut and reattached, while always retaining plausible, composite animations.

The creation of a 3D model is only the first stage of the 3D character animation pipeline. Once a model has been created, and before it can be animated, it must be rigged . Manual rigging is laborious, and automatic rigging approaches are far from real-time and do not allow for incremental updates. This is a hindrance in the real world, where the shape of a model is often revised after rigging has been performed. In this paper, we introduce algorithms and a user-interface for sketch-based 3D modeling that unify the modeling and rigging stages of the 3D character animation pipeline. Our algorithms create a rig for each sketched part in real-time, and update the rig as parts are merged or cut. As a result, users can freely pose and animate their shapes and characters while rapidly iterating on the base shape. The rigs are compatible with the state-of-the-art character animation pipeline; they consist of a low-dimensional skeleton along with skin weights identifying the surface with bones of the skeleton.

In this paper, we describe a design methodology that we have termed Minimalist Game Design. Minimalist games have small rulesets, narrow decision spaces, and abstract audiovisual representations, yet they do not compromise on depth of play or possibility space. We begin with a motivation for and definition of minimalist games, including terms such as "rules," "mechanics," "control," and "interface," and illustrate the importance of artificial design constraints. Using a number of examples, we show the strengths of minimalist game elements in systems, controls, visuals, and audio. Adhering to these constraints, these games feature a small set of mechanics and one core mechanic, while still being sufficiently deep and allowing for player exploration and performance. This depth comes from procedural methods, combinatorial complexity, probability, obfuscation, challenge, or any combination thereof. Our methodology embraces principles of holistic design, where there is no "filler," and where every element of the game contributes to the play experience in some meaningful, deliberate way.

The question of what are good views of a 3D object has been addressed by numerous researchers in perception, computer vision, and computer graphics. This has led to a large variety of measures for the goodness of views as well as some special-case viewpoint selection algorithms. In this article, we leverage the results of a large user study to optimize the parameters of a general model for viewpoint goodness, such that the fitted model can predict people's preferred views for a broad range of objects. Our model is represented as a combination of attributes known to be important for view selection, such as projected model area and silhouette length. Moreover, this framework can easily incorporate new attributes in the future, based on the data from our existing study. We demonstrate our combined goodness measure in a number of applications, such as automatically selecting a good set of representative views, optimizing camera orbits to pass through good views and avoid bad views, and trackball controls that gently guide the viewer towards better views.

The modeling of volumetric objects is still a difficult problem. Solid texture synthesis methods enable the design of volumes with homogeneous textures, but global features such as smoothly varying colors seen in vegetables and fruits are difficult to model. In this paper, we propose a representation called diffusion surfaces (DSs) to enable modeling such objects. DSs consist of 3D surfaces with colors defined on both sides, such that the interior colors in the volume are obtained by diffusing colors from nearby surfaces. A straightforward way to compute color diffusion is to solve a volumetric Poisson equation with the colors of the DSs as boundary conditions, but it requires expensive volumetric meshing which is not appropriate for interactive modeling. We therefore propose to interpolate colors only locally at user-defined cross-sections using a modified version of the positive mean value coordinates algorithm to avoid volumetric meshing. DSs are generally applicable to model many different kinds of objects with internal structures. As a case study, we present a simple sketch-based interface for modeling objects with rotational symmetries that can also generate random variations of models. We demonstrate the effectiveness of our approach through various DSs models with simple non-photorealistic rendering techniques enabled by DSs.

In this paper we present an algorithm for watertight meshing of closed, sketched curves. The sketch is resampled as a piecewise linear (PWL) curve and placed onto a triangular grid. A small boundary (seed) that describes a closed path along grid points is placed inside the sketch and grown until it resembles the sketch. Vertices of the evolved grid boundary are projected onto the stroke to establish a bijective, ordered mapping. Finally, valences along the boundary are optimized while retaining the previously established mapping. The resulting mesh patch can be duplicated, stitched and inflated to generate a new shape, or used to fill a hole in an existing shape. We have implemented our algorithm in FiberMesh, an interactive sketch based interface for designing freeform surfaces, where it is used for the all mesh generation processes. The triangulation generated with our algorithm improves the quality of the model by reducing the number of irregular vertices, while running at real time rates.

This paper presents a system for designing freeform surfaces with a collection of 3D curves. The user first creates a rough 3D model by using a sketching interface. Unlike previous sketching systems, the user-drawn strokes stay on the model surface and serve as handles for controlling the geometry. The user can add, remove, and deform these control curves easily, as if working with a 2D line drawing. The curves can have arbitrary topology; they need not be connected to each other. For a given set of curves, the system automatically constructs a smooth surface embedding by applying functional optimization. Our system provides real-time algorithms for both control curve deformation and the subsequent surface optimization. We show that one can create sophisticated models using this system, which have not yet been seen in previous sketching or functional optimization systems.

Abstract Physically based deformable models have been widely embraced by the Computer Graphics community. Many problems outlined in a previous survey by Gibson and Mirtich have been addressed, thereby making these models interesting and useful for both offline and real‐time applications, such as motion pictures and video games. In this paper, we present the most significant contributions of the past decade, which produce such impressive and perceivably realistic animations and simulations: finite element/difference/volume methods, mass‐spring systems, mesh‐free methods, coupled particle systems and reduced deformable models‐based on modal analysis. For completeness, we also make a connection to the simulation of other continua, such as fluids, gases and melting objects. Since time integration is inherent to all simulated phenomena, the general notion of time discretization is treated separately, while specifics are left to the respective models. Finally, we discuss areas of application, such as elastoplastic deformation and fracture, cloth and hair animation, virtual surgery simulation, interactive entertainment and fluid/smoke animation, and also suggest areas for future research.

We present a sampling strategy and rendering framework for intersectable models, whose surface is implicitly defined by a black box intersection test that provides the location and normal of the closest intersection of a ray with the surface. To speed up image generation despite potentially slow intersection tests, our method exploits spatial coherence by adjusting the sampling resolution in image space to the surface variation in object space. The result is a set of small, view-dependent bilinear surface approximations, which are rendered as quads using conventional graphics hardware. The advantage of this temporary rendering representation is two-fold: First, rendering is performed on the GPU, leaving CPU time for ray intersection computation. As the number of primitives is typically small, complex per vertex or per fragment programs can be used to achieve a variety of rendering effects. Second, bilinear surface approximations are derived from the geometry and can be reused in other views. Here, graphics hardware is exploited to determine the subset of image space in need of re-sampling. We demonstrate our system by ray casting an implicit surface defined from point samples, for which current ray-surface intersection computations are usually too slow to generate images at interactive rates.

In this paper we present a method for the intuitive editing of surface meshes by means of view-dependent sketching. In most existing shape deformation work, editing is carried out by selecting and moving a handle , usually a set of vertices. Our system lets the user easily determine the handle, either by silhouette selection and cropping, or by sketching directly onto the surface. Subsequently, an edit is carried out by sketching a new, view-dependent handle position or by indirectly influencing differential properties along the sketch. Combined, these editing and handle metaphors greatly simplify otherwise complex shape modeling tasks.

Patch-based texture synthesis has proven to produce high quality textures faster than pixel-based approaches. Previous algorithms differ in how the regions of overlap between neighboring patches are treated. We present an approach that produces higher quality overlap regions than simple blending of patches or computing good boundaries, however, that is faster than resynthesizing invalid pixels using a classical per-pixel synthesis algorithm: we use a k-nearest neighbor (knn) data structure, obtained from the input texture in a precomputation step. Results from our implementation show that the algorithm produces high-quality textures, where the time complexity of the synthesis stage is linear in the number of resynthesized pixels and, therefore, scales well with the size of the input texture