# Level Assembly as a Markov Decision Process

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 27 Apr 2023.

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

- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [Robots that can adapt like animals](https://mlsanity.com/paper/1407.3501/) (2014)
- [Procedural Content Generation through Quality Diversity](https://mlsanity.com/paper/1907.04053/) (2019)
- [The VGLC: The Video Game Level Corpus](https://mlsanity.com/paper/1606.07487/) (2016)
- [Experience-Driven PCG via Reinforcement Learning: A Super Mario Bros Study](https://mlsanity.com/paper/2106.15877/) (2021)
- [Finding Game Levels with the Right Difficulty in a Few Trials through Intelligent Trial-and-Error](https://mlsanity.com/paper/2005.07677/) (2020)
- [Generating Levels That Teach Mechanics](https://mlsanity.com/paper/1807.06734/) (2018)
- [Addressing the Fundamental Tension of PCGML with Discriminative Learning](https://mlsanity.com/paper/1809.04432/) (2018)
- [Simple Strategies in Multi-Objective MDPs (Technical Report)](https://mlsanity.com/paper/1910.11024/) (2019)
- [On Linking Level Segments](https://mlsanity.com/paper/2203.05057/) (2022)

## Abstract (arXiv)

Many games feature a progression of levels that doesn't adapt to the player. This can be problematic because some players may get stuck if the progression is too difficult, while others may find it boring if the progression is too slow to get to more challenging levels. This can be addressed by building levels based on the player's performance and preferences. In this work, we formulate the problem of generating levels for a player as a Markov Decision Process (MDP) and use adaptive dynamic programming (ADP) to solve the MDP before assembling a level. We tested with two case studies and found that using an ADP outperforms two baselines. Furthermore, we experimented with player proxies and switched them in the middle of play, and we show that a simple modification prior to running ADP results in quick adaptation. By using ADP, which searches the entire MDP, we produce a dynamic progression of levels that adapts to the player.