Level Assembly as a Markov Decision Process
This addresses the issue of player disengagement in games due to poorly paced difficulty, though it is incremental as it applies existing methods to a specific domain.
The paper tackled the problem of non-adaptive game level progression by formulating level generation as a Markov Decision Process and using adaptive dynamic programming to create dynamic levels that adapt to player performance. It found that this approach outperformed two baselines in case studies and allowed quick adaptation when player proxies were switched.
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.