# Automated Graph Genetic Algorithm based Puzzle Validation for Faster Game Design

arXiv: https://arxiv.org/abs/2302.09040 · HTML: https://mlsanity.com/paper/2302.09040/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 25 references that are in the map.
- First posted on arXiv 17 Feb 2023.

## Builds on (most cited first, 5 of 5)

- [Mapping Hearthstone Deck Spaces through MAP-Elites with Sliding Boundaries](https://mlsanity.com/paper/1904.10656/) (2019)
- [Talakat: Bullet Hell Generation through Constrained Map-Elites](https://mlsanity.com/paper/1806.04718/) (2018)
- [A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles](https://mlsanity.com/paper/1711.06769/) (2017)
- [Rolling Horizon Evolutionary Algorithms for General Video Game Playing](https://mlsanity.com/paper/2003.12331/) (2020)
- [Dynamic Island Model based on Spectral Clustering in Genetic Algorithm](https://mlsanity.com/paper/1801.01620/) (2018)

## Abstract (arXiv)

Many games are reliant on creating new and engaging content constantly to maintain the interest of their player-base. One such example are puzzle games, in such it is common to have a recurrent need to create new puzzles. Creating new puzzles requires guaranteeing that they are solvable and interesting to players, both of which require significant time from the designers. Automatic validation of puzzles provides designers with a significant time saving and potential boost in quality. Automation allows puzzle designers to estimate different properties, increase the variety of constraints, and even personalize puzzles to specific players. Puzzles often have a large design space, which renders exhaustive search approaches infeasible, if they require significant time. Specifically, those puzzles can be formulated as quadratic combinatorial optimization problems. This paper presents an evolutionary algorithm, empowered by expert-knowledge informed heuristics, for solving logical puzzles in video games efficiently, leading to a more efficient design process. We discuss multiple variations of hybrid genetic approaches for constraint satisfaction problems that allow us to find a diverse set of near-optimal solutions for puzzles. We demonstrate our approach on a fantasy Party Building Puzzle game, and discuss how it can be applied more broadly to other puzzles to guide designers in their creative process.