Entropy as a Measure of Puzzle Difficulty

Eugene You Chen Chen, Adam White, Nathan R. Sturtevant

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.

A puzzle represented as a grid of junctions with coordinate positions, forming the basis for the state-space graph.

MUSE and ReMUSE

The authors propose two primary metrics:

  1. 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.
  2. 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.

A 3x2 puzzle from The Witness showing how different solution paths interact with color-coded constraints, illustrating the role of inference rules in reducing effective entropy.

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

Abstract

Evaluating and ranking the difficulty and enjoyment of puzzles is important in game design. Typically, such rankings are constructed manually for each specific game, which can be time consuming, subject to designer bias, and requires extensive play testing. An approach to ranking that generalizes across multiple puzzle games is even more challenging because of their variation in factors like rules and goals. This paper introduces two general approaches to compute puzzle entropy, and uses them to evaluate puzzles that players enjoy. The resulting uncertainty score is equivalent to the number of bits of data necessary to communicate the solution of a puzzle to a player of a given skill level. We apply our new approaches to puzzles from the 2016 game, The Witness. The computed entropy scores largely reproduce the order of a set of puzzles that introduce a new mechanic in the game. The scores are also positively correlated with the user ratings of user-created Witness puzzles, providing evidence that our approach captures notions of puzzle difficulty and enjoyment. Our approach is designed to exploit game-specific knowledge in a general way and thus can extended to provide automatic rankings or curricula in a variety of applications.
BibTeX
@inproceedings{chen2023entropy,
  author = {Eugene You Chen Chen and Adam White and Nathan R. Sturtevant},
  title = {{Entropy as a Measure of Puzzle Difficulty}},
  booktitle = {AIIDE},
  year = {2023},
  doi = {10.1609/aiide.v19i1.27499},
}
Figure