Mechanizing Exploratory Game Design (Adam M. Smith)

In one sentence: The designer sketches a space of appropriate artifacts with a constraint program, and the machine samples an artifact from the space; upon examining the artifact, the designer refines the sketch.

Added in September 2024: Listen to the dissertation in the form of a machine-genereted 9-minute podcast episode that unforuntately contains many embarrasing misinterpretations (the sort of thing that high-assurance generation might avoid).

Abstract

Game design is an art form that deals with inherently interactive artifacts. Game designers craft games (assembled from rule systems and content), but they really seek to manipulate play: the interaction between games and players. When developing new games that are similar to past games, a designer may rely on previous experience with related designs and relatively easy access to players familiar with conventional design choices. When exploratorily venturing into uncharted territory, uncovering games that afford novel modes of play, there is a need for practical and technological interventions that improve a designer's access to feedback from the unfamiliar design scenario. In the interdisciplinary space between game design, design studies, computational creativity, and symbolic artificial intelligence (AI), my program of mechanizing exploratory game design aims to amplify human creativity in game design; enable new game designs through deep, play-time design automation; and demonstrate novel tools that respect the concerns of design problems.

This dissertation advances a practice of modeling design spaces as logic programs in the answer set programming (ASP) paradigm. Answer set programs can concisely encode the key conditions of artifact appropriateness, and, paired with state of the art algorithms for combinatorial search and optimization, they yield efficient and expressively sculptable artifact generators. I present three major applications of ASP-encoded design spaces to exploratory game design: a powerful machine playtesting tool for analyzing designer-specified games, a novel game prototype employing machine-generated rulesets bound by iteratively discovered constraints, and a suite of level design automation tools that offer unprecedented control over the aesthetic and pedagogical properties of puzzles for a widely deployed educational game. This practice is further developed in a series of introductory programming and advanced modeling tutorials. By formally modeling design spaces as concise and authorable logic programs (and without the need for original algorithm design and maintenance), designer-programmers are broadly empowered to quickly build and evolve the in-house automation required by their own exploratory game design projects. These claims are backed by a spreading adoption of this practice by others and deployed applications to at-scale game design projects.

Taken as a whole, this dissertation offers new insight into the nature of game design in relation to other design disciplines, a new design research practice for understanding how design thinking can and should be mechanized, a novel model of transformational creativity suitable for discussing both humans and machines, and a set of new applications for symbolic AI that simultaneously broaden the applicability and tax the limits of this automated reasoning infrastructure.

1 Introduction
  1.1 Goals
    1.1.1 Amplify creativity of human game designers
    1.1.2 Support deep, play-time design automation
    1.1.3 Demonstrate tools that respect design problems
  1.2 Research Context
    1.2.1 Game Design
    1.2.2 Design Studies
    1.2.3 Computational Creativity
    1.2.4 Symbolic AI
  1.3 Contributions
    1.3.1 Mechanizing Design Spaces
    1.3.2 Situating Mechanized Design
  1.4 Approach
    1.4.1 Design Spaces
    1.4.2 Computational Caricature
    1.4.3 Target Audience: Procedurally Literate Designer-Programmers
    1.4.4 Automating Logical Reasoning
    1.4.5 Artifacts as Communication
  1.5 Outline of Dissertation

2 Interdisciplinary Context & Motivations

3 Game Design
  3.1 Best Practices
    3.1.1 Prototyping
    3.1.2 Playtesting
    3.1.3 Balancing
  3.2 Folks Psychology in Game Design
  3.3 Call for Structure
  3.4 Procedural Content Generation
    3.4.1 PCG Meets Game Design
    3.4.2 Typical Architectures for Content Generators
  3.5 Attempts at Formalization and Automation
    3.5.1 MDA
    3.5.2 A Factoring of the Concerns in Game Design
    3.5.3 Ludi
    3.5.4 A Generic Framework
  3.6 Game Design as a Design Discipline

4 Design Studies
  4.1 The Relationship between Science and Design
  4.2 Methods of Design Studies
  4.3 Vocabulary of Design
    4.3.1 Glossary
  4.4 The Automated Architect

5 Computational Creativity
  5.1 Vocabulary of Creativity
    5.1.1 "Creativity"
    5.1.2 Novelty, Value, and Surprise
    5.1.3 Process vs. Product vs. Producer
    5.1.4 Combinatorial, Exploratatory, and Transformational Creativity
    5.1.5 Closed Loops
  5.2 Computational Creativity Meets Game Design
  5.3 Mechanization and Computational Creativity

6 Symbolic AI
  6.1 Logic Programming
    6.1.1 Deductive Logic Programming 
    6.1.2 Inductive Logic Programming 
    6.1.3 Abductive Logic Programming 
    6.1.4 Prolog
    6.1.5 Constraint Logic Programming
    6.1.6 Answer Set Programming
  6.2 Standard Solutions
  6.3 Standard Problems
    6.3.1 Backtracking and Completeness
    6.3.2 Heuristics
    6.3.3 Consistency and Propagation
    6.3.4 Constraint Learning
    6.3.5 Randomness and Restarts
  6.4 General Game Playing
    6.4.1 History
    6.4.2 Rule Representations
    6.4.3 General Game Playing vs. Action Planning
  6.5 Super-symbolic AI: The Knowledge Level

7 Synthesis of Goals

8 Mechanizing Appositional Reasoning
  8.1 Introduction
  8.2 Appositional and Abductive Reasoning
  8.3 Design Spaces
  8.4 Requirements for Knowledge Representations
    8.4.1 Constructivity
    8.4.2 Constraint
    8.4.3 Evolution
    8.4.4 Analysis
  8.5 Means of Mechanization
    8.5.1 SAT Solvers
    8.5.2 Abductive Logic Programming
    8.5.3 Answer Set Programming
    8.5.4 Future Demands
  8.6 Conclusion

9 Computational Caricature
  9.1 Introduction
  9.2 Computational Caricature
    9.2.1 Visual Caricature
    9.2.2 Procedural Portraits and Computational Caricature
  9.3 Computational Caricature of the Game Design Process
  9.4 Exemplars
    9.4.1 A Designer in a Box
    9.4.2 Cooperating with the Machine
    9.4.3 Imagining Gameplay
    9.4.4 Summary
  9.5 Conclusion

10 ASP for Design Automation
  10.1 ASP in Context
    10.1.1 AnsProlog as a Little Language
    10.1.2 Perspective
  10.2 Design Spaces in ASP
    10.2.1 Representing Artifacts
    10.2.2 Representing Spaces
    10.2.3 Modeled and Unmodeled Properties
    10.2.4 Modeling, Solving, Interpretation, and Refinement
  10.3 Programming Tutorials
    10.3.1 Hello Soggy World
    10.3.2 Graph Coloring, Complexity, and Visualization
    10.3.3 Golomb Rulers, Optimization, and Numerical Constraints
  10.4 Existing Design Automation Examples
    10.4.1 Diorama
    10.4.2 Anton
    10.4.3 Toast
  10.5 Modeling Tutorials
    10.5.1 Chess Mazes
    10.5.2 Strategy Game Maps
    10.5.3 Platformer Levels with Support for Mixed-Initiative Interaction

11 Applied Systems Overview

12 Ludocore
  12.1 Overview
  12.2 Building Games on the Event Calculus
  12.3 The Logical Game Engine
    12.3.1 State, Events, and Consequences
    12.3.2 Player Model Interface
    12.3.3 Relation to the General Event Calculus
    12.3.4 Using Player and Nature Models
  12.4 Ludocore in Action
    12.4.1 Gameplay Trace Inference
    12.4.2 Modifying Rules and Configuration
    12.4.3 Using Player and Nature Models
  12.5 Applications Enabled
    12.5.1 Game Design
    12.5.2 Crafting Game Playing Agents
  12.6 Conclusion

13 Biped
  13.1 Overview
  13.2 Playtesting Background
    13.2.1 Playtesting with Humans
    13.2.2 Playtesting with Machines
  13.3 System Overview
  13.4 Example Prototype
    13.4.1 Game Mechanics
    13.4.2 UI Bindings
    13.4.3 Human Playtesting
    13.4.4 Machine Playtesting
  13.5 Conclusions and Future Work

14 Variations Forever
  14.1 Overview
    14.1.1 Variations Forever as a Game Project
    14.1.2 Variations Forever as a Research Project
  14.2 Related Work
  14.3 Repersenting Game Rulesets in Logical Terms
  14.4 VF's Generative Space
  14.5 Zooming in on Games of Interest
  14.6 Generating Playable Mini-games
    14.6.1 Game Generator
    14.6.2 Game Engine
  14.7 Discussion
    14.6.1 Coupling between Generator and Engine
    14.6.2 Tradeoffs in Levels of Abstraction
    15.6.3 Evaluation
  14.8 Conclusion

15 Refraction Tools
  15.1 Introduction
  15.2 Related Work
  15.3 Answer Set Programming
    15.3.1 ASP for PCG
  15.4 Refraction Puzzle Design
  15.5 Problem Formulation
    15.5.1 Mission Generation
    15.5.2 Grid Embedding
    15.5.3 Puzzle Solving
  15.6 System Descriptions
    15.6.1 Feed-Forward Mission Generation
    15.6.2 Grid Embedding with DFS
    15.6.3 Puzzle Solving with DFS
    15.6.4 Grid Embedding with ASP
    15.6.5 Mission Generation with ASP
    15.6.6 Puzzle Solving with ASP
  15.7 Analysis
    15.7.1 Quantitative Comparisons
    15.7.2 Qualitative Comparisons
  15.8 Conclusion

16 Rational Curiosity
  16.1 Introduction
  16.2 Game Design Practices
  16.3 An Analogy with Science
    16.3.1 Scientific Practices
    16.3.2 Automated Discovery
  16.4 Newell's Knowledge Level
  16.5 Creativity as Rational Curiosity
    16.5.1 Transformational Creativity in Game Design
  16.6 Discussion
    16.6.1 Computational Creativity in Game Design
    16.6.2 New Perspective for Computational Creativity
  16.7 Conclusion

17 Evaluation
  17.1 ASP for PCG
  17.2 Applied Systems
    17.2.1 Ludocore
    17.2.2 Biped
    17.2.3 Variations Forever
    17.2.4 Refraction Tools
  17.3 Recap

18 Conclusion
  18.1 Goals
    18.1.1 Amplify creativity of human game designers
    18.1.2 Support deep, play-time design automation
    18.1.3 Demonstrate tools that respect design problems
  18.2 Research Context
    18.2.1 Game Design
    18.2.2 Design Studies
    18.2.3 Computational Creativity
    18.2.4 Symbolic AI
  18.3 Contributions
  18.4 Approaches
    18.4.1 Design Spaces
    18.4.2 Computational Caricature
    18.4.3 Target Audience: Procedurally Literate Designer Programmers
    18.4.4 Automating Logical Reasoning
    18.4.5 Artifacts as Communication
  18.5 Future Work
    18.5.1 Two-level Design Spaces
    18.5.2 Integration infrastructure
    18.5.3 Broader base of modeling examples
    18.5.4 Automating discovery of design knowledge
  18.6 Epilogue

Notable Updates

I've figured out how to model universally quantified constraints using disjunctive ASP. Using a small language extension I developed, it's now possible to directly express conditions of appropriateness in the form of constraints over the entire space of play for an interactive artifacts.
The Refraction tools sketched in this dissertation evolved into a mixed-initiative level progression design tool and a public version of the game employing a generated progression of generated game levels.
By cross-compiling the Potassco tools from C++ into JavaScript and ActionScript, I was able to directly embed ASP technology into web-based end-user interactive experiences.
I've started work on a probabilistic interpretation for ASP that both enables statements about probabilities in the definition of design spaces and sketches a path for using a corpus of example artifacts to refine a design space definition.
"Generative AI" exploded onto the scene ten years after this dissertation, involving ideas almost completely unconnected to those in it. Around the same time, I realized the BDDs (binary decision diagrams) could represent design spaces as composable, closed-form expressions for all valid designs. If we read ASP as doing lazy construction of designs from a formal design space specification, BDDs do eager summarization of the same space. In a fun twist, they are interpretable as a kind of large language model too (they are regular expressions over the language of bitvector representations of satisfying designs).

Mechanizing Exploratory Game Design

Abstract

Table of Contents

Notable Updates