You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCG

• URL: http://arxiv.org/abs/2409.00837v1
• Date: Sun, 1 Sep 2024 20:43:55 GMT
• Title: You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCG
• Authors: Jediah Katz, Bahar Bateni, Adam M. Smith,
• Abstract summary: We introduce You-Only-Randomize-Once (YORO) pre-rolling, a method for crafting a decision variable ordering for a constraint solver. We show that this technique effectively controls the statistics of tile-grid outputs generated by several off-the-shelf SAT solvers.
• Score: 3.581471126368696
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In procedural content generation, modeling the generation task as a constraint satisfaction problem lets us define local and global constraints on the generated output. However, a generator's perceived quality often involves statistics rather than just hard constraints. For example, we may desire that generated outputs use design elements with a similar distribution to that of reference designs. However, such statistical properties cannot be expressed directly as a hard constraint on the generation of any one output. In contrast, methods which do not use a general-purpose constraint solver, such as Gumin's implementation of the WaveFunctionCollapse (WFC) algorithm, can control output statistics but have limited constraint propagation ability and cannot express non-local constraints. In this paper, we introduce You-Only-Randomize-Once (YORO) pre-rolling, a method for crafting a decision variable ordering for a constraint solver that encodes desired statistics in a constraint-based generator. Using a solver-based WFC as an example, we show that this technique effectively controls the statistics of tile-grid outputs generated by several off-the-shelf SAT solvers, while still enforcing global constraints on the outputs.1 Our approach is immediately applicable to WFC-like generation problems and it offers a conceptual starting point for controlling the design element statistics in other constraint-based generators.

Related papers

• Controllable Generation via Locally Constrained Resampling [77.48624621592523]
  We propose a tractable probabilistic approach that performs Bayesian conditioning to draw samples subject to a constraint. Our approach considers the entire sequence, leading to a more globally optimal constrained generation than current greedy methods. We show that our approach is able to steer the model's outputs away from toxic generations, outperforming similar approaches to detoxification.
  arXiv  Detail & Related papers  (2024-10-17T00:49:53Z)
• A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints [87.08677547257733]
  Neuro-symbolic AI bridges the gap between purely symbolic and neural approaches to learning. We show how to maximize the likelihood of a symbolic constraint w.r.t the neural network's output distribution. We also evaluate our approach on Sudoku and shortest-path prediction cast as autoregressive generation.
  arXiv  Detail & Related papers  (2023-12-06T20:58:07Z)
• Using Integer Constraint Solving in Reuse Based Requirements Engineering [0.0]
  Product Lines (PL) have proved an effective approach to reuse-based configurations. It is now widely acknowledged that a product can be considered as a constraint satisfaction problem. It is natural to consider constraint programming as a first choice candidate to specify constraints on PL. This paper proposes to further explore the use of integer constraint programming to specify PL constraints.
  arXiv  Detail & Related papers  (2023-09-28T09:20:07Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP), derives global solutions to CCSPs.
  arXiv  Detail & Related papers  (2023-09-02T15:20:36Z)
• A New Computationally Simple Approach for Implementing Neural Networks with Output Hard Constraints [5.482532589225552]
  A new method of imposing hard convex constraints on the neural network output values is proposed. The mapping is implemented by the additional neural network layer with constraints for output. The proposed method is simply extended to the case when constraints are imposed not only on the output vectors, but also on joint constraints depending on inputs.
  arXiv  Detail & Related papers  (2023-07-19T21:06:43Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics [69.8062252611486]
  Cold decoding is a flexible framework that can be applied directly to off-the-shelf left-to-right language models. Our experiments on constrained generation tasks point to the effectiveness of our approach, both in terms of automatic and human evaluation.
  arXiv  Detail & Related papers  (2022-02-23T18:59:27Z)
• Discrete fully probabilistic design: a tool to design control policies from examples [2.6749261270690425]
  We present a discretized design that expounds an algorithm recently introduced in Gagliardi and Russo (2021) to synthesize control policies. The constraints do not need to be fulfilled in the possibly noisy example data, which in turn might be collected from a system that is different from the one under control.
  arXiv  Detail & Related papers  (2021-12-21T13:44:48Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.