Generalized Entropy and Solution Information for Measuring Puzzle Difficulty

Abstract

Metrics for problem difficulty are used by many puzzle generation algorithms, as well as by adaptive algorithms that are expected to provide players with the puzzles at the correct level of difficulty. A recently proposed general metric, puzzle entropy, combines an analysis of game mechanics with a model of player knowledge in the form of inference rules to predict problem difficulty. The entropy of a puzzle is the amount of information required, given a player’s knowledge about the puzzle, to describe a solution to a puzzle. This thesis generalizes the concepts of puzzle entropy and solution information, providing a better foundation for the previous work and creating new algorithms, Minimum Solution Information and Total Solution Information. While functionally similar to past work, the new algorithms allow knowledge about a puzzle to be represented as a policy. We then evaluate the impact of inference rules, policies, and player knowledge in the 2016 game The Witness.