When designing procedural content generation systems for games, we imagine that there is a space of potential designs, and each of those designs affords a space of potential play.However, in most generative systems, there is a complex relationship between input parameters and the design or play properties of system outputs.As generators grow in complexity, it becomes harder to predict what experiences players will have in the generated design.In both constructive and solver-based approaches, this leads to uncertainty about how changes to the generator itself will affect the distribution of outputs.In this paper, we contribute a new method for constructing generators by manipulating closed-form expressions for spaces of designs and their associated play properties.The resulting generators have highly predictable running times, precisely controllable output distributions, and allow enforcing arbitrary constraints about their outputs.We offer a sequence of increasingly complex examples showing how to compute design-interaction expressions and use them for generation.Finally, we document scaling strategies for handling design-interaction spaces where millions of gameplay states are reachable in each of trillions of designs.

We introduce a new approach to deploying constraint-based content generators that better supports online generation. Constraint-based generators ensure that certain properties hold in each design they output. However, when deployed a general-purpose solver is often required, thus guarantees come with unpredictable search times and little control over sequentially-generated outputs. In this paper, we outline how we can encode design constraints into a compact circuit representation that affords generation without search. These generators yield samples that are distributed uniformly over the space of valid designs. We illustrate our approach with binary decision diagrams (BDDs) in comparison to the traditional approach with answer-set programming (ASP) in two scenarios: a grid-based tile placement scenario inspired by WaveFunctionCollapse, and a playable platformer level design scenario. These compiled design-space models make constraint-based methods easier to deploy by improving on both the running time and diversity of previous constraint-based methods.

In large game worlds, players can get lost and feel overwhelmed as they try to figure out which immediate choices will make progress towards their own long-range goals in the game. This is a planning problem, but these games often have large state spaces. In this paper, we show that Binary Decision Diagrams (BDDs) can directly manipulate very large game state spaces, and this power can be leveraged to construct instantly responsive player assistance systems. We use BDDs to build a compressed representation of a game’s state-transition function, and use it to derive an action policy that makes shortest-path recommendations for any feasible state towards any achievable goal in milliseconds. We introduce the intuition behind planning with BDDs using a tiny grid world, and eventually scale to an integrated system for start-to-finish gameplay assistance in Super Metroid.

Machine playtesting systems often aim to demonstrate how to reach certain moments of play. To provide design feedback in a timely manner, they often internally rely on heuristic-guided search. However, there are many types of videogames for which sufficiently accurate heuristics are not available. We use an imperfect abstraction of an underlying game to define progress scores, and show that combining these scores yields a highly effective cell selection heuristic for use in the Go-Explore algorithm. We demonstrate the impact of this approach in automated gameplay for Super Metroid (involving mandatory item collection, destructible blocks, and backtracking) using a tile-based abstraction of the game that only models a small subset of the game’s mechanics. Surprisingly, our abstraction guidance mechanism is able to explore this complex game several orders of magnitude more efficiently than past work with similar exploration methods in Montezuma’s Revenge.

To understand genome evolution in a group of microbes, we need to know the timing of events such as duplications, deletions and horizontal transfers. A common approach is to perform a gene-tree / species-tree reconciliation. While a number of software packages perform this type of analysis, none are geared toward a complete reconstruction for all families in an entire clade. Here we describe an update to the xenoGI software package which allows users to perform such an analysis using the newly developed DTLOR (duplication-transfer-loss-origin-rearrangement) reconciliation model starting from genome sequences as input.

Academic Procedural Content Generation research has until recently overlooked a significant real-world application of generative methods to existing games: game randomizers. These programs remix existing games by changing things like item locations, enemy stats, or even room connections to create a fresh experience based on a beloved game, and are especially popular among speedrunning and streaming communities. They generate where high-production-quality full-scale games, explicitly geared towards replay value. Randomizers fulfill many of the stated motivations of the academic PCG research community, and important new research directions can be developed by investigating this space.

We introduce a hybrid neural + symbolic approach to map generation that combines neural discrete representation learning with symbolic constraint solving methods. In application to WarCraft II and Super Metroid map designs, we show how a vocabulary of directly manipulable latent tiles can be inferred from the raw pixels of design training data. Despite working with a very small tile vocabulary, our method is able to express a very large effective set of unique tiles at the level of pixel appearances. This work shows new ways of combining generative methods, resulting in directly controllable generators for domains that are primarily specified only by visual design examples.

Videogame level designs can contain errors called softlocks where a player traversing the level in an unintended manner can become permanently stuck. In this paper, we explore the automated detection of softlocks in the game Super Metroid using Computation Tree Logic (CTL). Super Metroid distinguishes itself as an example domain because of its velocity-based movement and rich item upgrade hierarchy. These factors can cause softlocks in Super Metroid to be challenging to detect visually. We contribute a tile-based gameplay abstraction for Super Metroid, and demonstrate verification of CTL properties for scenarios based on a segment of the original game’s level design. CTL can be used to define and test many other gameplay properties (e.g. which bosses can be skipped or which order items may be collected) and is immediately applicable to other game designs for which a compact abstraction of their state space can be enumerated. By making plausible design changes to a Super Metroid level fragment, we show how highly nonobvious softlocks can be detected and how the counterexamples resulting from verification failure can be turned into visualizations that explain the problem.

SUMMARY: We describe eMPRess, a software program for phylogenetic tree reconciliation under the duplication-transfer-loss model that systematically addresses the problems of choosing event costs and selecting representative solutions, enabling users to make more robust inferences. AVAILABILITY AND IMPLEMENTATION: eMPRess is freely available at http://www.cs.hmc.edu/empress. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Analyses of microbial evolution often use reconciliation methods. However, the standard duplication-transfer-loss (DTL) model does not account for the fact that species trees are often not fully sampled and thus, from the perspective of reconciliation, a gene family may enter the species tree from the outside. Moreover, within the genome, genes are often rearranged, causing them to move to new syntenic regions. RESULTS: We extend the DTL model to account for two events that commonly arise in the evolution of microbes: origin of a gene from outside the sampled species tree and rearrangement of gene syntenic regions. We describe an efficient algorithm for maximum parsimony reconciliation in this new DTLOR model and then show how it can be extended to account for non-binary gene trees to handle uncertainty in gene tree topologies. Finally, we describe preliminary experimental results from the integration of our algorithm into the existing xenoGI tool for reconstructing the histories of genomic islands in closely related bacteria. CONCLUSIONS: Reconciliation in the DTLOR model can offer new insights into the evolution of microbes that is not currently possible under the DTL model.

Gene trees can differ from species trees due to a variety of biological phenomena, the most prevalent being gene duplication, horizontal gene transfer, gene loss, and coalescence. To explain topological incongruence between the two trees, researchers apply reconciliation methods, often relying on a maximum parsimony framework. However, while several studies have investigated the space of maximum parsimony reconciliations (MPRs) under the duplication-loss and duplication-transfer-loss models, the space of MPRs under the duplication-loss-coalescence (DLC) model remains poorly understood. To address this problem, we present new algorithms for computing the size of MPR space under the DLC model and sampling from this space uniformly at random. Our algorithms are efficient in practice, with runtime polynomial in the size of the species and gene tree when the number of genes that map to any given species is fixed, thus proving that the MPR problem is fixed-parameter tractable. We have applied our methods to a biological data set of 16 fungal species to provide the first key insights in the space of MPRs under the DLC model. Our results show that a plurality reconciliation, and underlying events, are likely to be representative of MPR space.

BACKGROUND: Maximum parsimony reconciliation in the duplication-transfer-loss model is a widely-used method for analyzing the evolutionary histories of pairs of entities such as hosts and parasites, symbiont species, and species and genes. While efficient algorithms are known for finding maximum parsimony reconciliations, the number of such reconciliations can be exponential in the size of the trees. Since these reconciliations can differ substantially from one another, making inferences from any one reconciliation may lead to conclusions that are not supported, or may even be contradicted, by other maximum parsimony reconciliations. Therefore, there is a need to find small sets of best representative reconciliations when the space of solutions is large and diverse. RESULTS: We provide a general framework for hierarchical clustering the space of maximum parsimony reconciliations. We demonstrate this framework for two specific linkage criteria, one that seeks to maximize the average support of the events found in the reconciliations in each cluster and the other that seeks to minimize the distance between reconciliations in each cluster. We analyze the asymptotic worst-case running times and provide experimental results that demonstrate the viability and utility of this approach. CONCLUSIONS: The hierarchical clustering algorithm method proposed here provides a new approach to find a set of representative reconciliations in the potentially vast and diverse space of maximum parsimony reconciliations.

BACKGROUND: Reconciliation methods are widely used to explain incongruence between a gene tree and species tree. However, the common approach of inferring maximum parsimony reconciliations (MPRs) relies on user-defined costs for each type of event, which can be difficult to estimate. Prior work has explored the relationship between event costs and maximum parsimony reconciliations in the duplication-loss and duplication-transfer-loss models, but no studies have addressed this relationship in the more complicated duplication-loss-coalescence model. RESULTS: We provide a fixed-parameter tractable algorithm for computing Pareto-optimal reconciliations and recording all events that arise in those reconciliations, along with their frequencies. We apply this method to a case study of 16 fungi to systematically characterize the complexity of MPR space across event costs and identify events supported across this space. CONCLUSION: This work provides a new framework for studying the relationship between event costs and reconciliations that incorporates both macro-evolutionary events and population effects and is thus broadly applicable across eukaryotic species.

BACKGROUND: Maximum parsimony reconciliation in the duplication-transfer-loss model is widely used in studying the evolutionary histories of genes and species and in studying coevolution of parasites and their hosts and pairs of symbionts. While efficient algorithms are known for finding maximum parsimony reconciliations, the number of reconciliations can grow exponentially in the size of the trees. An understanding of the space of maximum parsimony reconciliations is necessary to determine whether a single reconciliation can adequately represent the space or whether multiple representative reconciliations are needed. RESULTS: We show that for any instance of the reconciliation problem, the distribution of pairwise distances can be computed exactly by an efficient polynomial-time algorithm with respect to several different distance metrics. We describe the algorithm, analyze its asymptotic worst-case running time, and demonstrate its utility and viability on a large biological dataset. CONCLUSIONS: This result provides new insights into the structure of the space of maximum parsimony reconciliations. These insights are likely to be useful in the wide range of applications that employ reconciliation methods.

We present an approach for simultaneously separating and localizing multiple sound sources using recorded microphone data. Inspired by topic models, our approach is based on a probabilistic model of inter-microphone phase differences, and poses separation and localization as a Bayesian inference problem. We assume sound activity is locally smooth across time, frequency, and location, and use the known position of the microphones to obtain a consistent separation. We compare the performance of our method against existing algorithms on simulated anechoic voice data and find that it obtains high performance across a variety of input conditions.