Using search algorithm statistics for assessing maze and puzzle difficulty

Abstract

A video game’s difficulty has a large impact on player engagement. For instance, it is crucial in some genres to give the players a challenge difficult enough without frustrating them. We propose a simple method for assessing game-level difficulty as a precursor to adapting it to a specific player. In particular, we propose using simple performance metrics of algorithms such as A* and Breadth-First Search (BFS) as a proxy for the difficulty of puzzles. We performed user studies using a 2D maze simulator and a Sokoban game implementation; both built into the Unity game engine. We show that, for 2D mazes generated by Binary Space Partitioning, the number of nodes expanded by BFS highly correlates with the number of steps a human player takes to reach the goal. For Sokoban puzzles, the closed list length of an A* search is highly correlated to perceived difficulty and the number of movements a human player takes to solve the puzzle. These results show that simple metrics are probably good enough to assess a given level’s difficulty, which is a first step towards being able to personalize the difficulty of a maze or a puzzle to a particular player

This research was partially funded by the National Agency for Research and Development (Agencia Nacional de Investigación y Desarrollo, ANID Chile), ANID-Subdirección del Capital Humano/Doctorado Nacional/2023-21230824 and FONDECYT Iniciación grant 11220438. This work was also partially funded by project PID2021-122136OB-C22 from Ministerio de Ciencia e Innovación, Spain. Open Access funding provided thanks to the CRUE-CSIC agreement with Elsevier