Abstract
Traditional metrics for puzzle difficulty, such as solution length or the number of possible solutions, often fail to capture the true cognitive load experienced by players. This paper introduces MUSE (Minimum Uniform Solution Entropy) and ReMUSE (Relative MUSE), two information-theoretic metrics that quantify difficulty by measuring the uncertainty a player must resolve at each step. By modeling puzzles as directed graphs and incorporating human-like inference rules, these metrics demonstrate a significantly higher correlation with human-perceived difficulty in games like The Witness compared to conventional benchmarks.
Introduction
In game design, establishing a coherent difficulty curve is vital for player engagement. However, manually ranking puzzles is subjective and labor-intensive. Automated metrics like solution length are often misleading—a long but straightforward path is easier than a short, highly ambiguous one. The authors propose that difficulty is fundamentally a measure of the "information" or "uncertainty" a player encounters. By treating puzzle-solving as a communication problem, they develop a generalizable framework for difficulty estimation.
Methodology: Quantifying Uncertainty
The core of the approach involves representing a puzzle as a directed graph where nodes are junctions and edges are possible moves. This structure allows the researchers to calculate the probability of various paths and the information gain at each decision point.
MUSE and ReMUSE
The authors propose two primary metrics:
- MUSE (Minimum Uniform Solution Entropy): This metric calculates the total entropy of the path with the lowest cumulative uncertainty. If a player faces $n$ equally plausible choices at a junction, the entropy is $\log_2(n)$. MUSE represents the minimum bits of information an "oracle" would need to provide to guide a player to the goal.
- ReMUSE (Relative MUSE): Building on MUSE, ReMUSE utilizes Kullback–Leibler (KL) Divergence to account for the "decoy" effect. It measures how much a "wrong" move penalizes the player. If one path is clearly better than others, the entropy is low; if multiple paths look equally promising but only one works, the entropy (and difficulty) is high.
Modeling Human Logic
To make these metrics realistic, the authors do not simply consider all legal moves. Instead, they incorporate "inference rules" that reflect human deduction (e.g., "lines must separate different colored blocks"). This reduces the "effective" entropy, modeling a player who understands the game's underlying logic rather than one who moves randomly.
Results and Validation
The metrics were tested against community-rated puzzles from The Windmill and the original curriculum of The Witness. ReMUSE achieved a 0.57 correlation with user ratings, significantly outperforming solution length (0.47) and the number of solutions (0.32). Notably, the metrics correctly identified that smaller puzzles with high ambiguity can be more difficult than larger, more constrained ones. Furthermore, ReMUSE successfully replicated the difficulty ordering designed by professional developers for the introductory sequence of The Witness.
Conclusion
Entropy-based metrics provide a robust, generalizable way to measure puzzle difficulty by focusing on decision-making uncertainty rather than path geometry. While current implementations require hand-coded inference rules, future work aims to automate rule discovery using inductive logic programming. This approach holds promise not only for game design but also for optimizing educational curricula and logic-based assessments.
Summary updated