Quantifying the difficulty of logic puzzles is a complex task because difficulty is inherently subjective. While execution-based games might use metrics like reaction time, logic puzzles challenge a player's deductive reasoning. This paper, presented at AIIDE 2024, proposes a mathematical framework to measure this "feeling" of difficulty by treating puzzle-solving as a communication problem between an all-knowing oracle and a player.
The Communication Framework
The authors model the puzzle-solving process as a search through a state space. If a player’s current strategy (or "policy") is unlikely to find the goal, an oracle must provide information to guide them. Difficulty is then defined as the amount of "help" or information required to reach a solution.
In this model, difficulty is proportional to the "surprise" of finding the solution. If a player's heuristics (inference rules) make a solution highly probable, the information content (and thus the difficulty) is low. Conversely, if the solution is counter-intuitive or hidden behind many distractors, the information required is high.
Puzzle Domain: The Witness
The researchers validated their metrics using puzzles from The Witness, a game where players draw paths on a grid while satisfying various local constraints. These constraints range from simple path requirements to complex regional rules.
Key Metrics: MSI and TSI
The paper introduces two primary information-theoretic metrics:
- Minimum Solution Information (MSI): Measures the information needed to find the single most likely solution based on the player's current knowledge.
- Total Solution Information (TSI): A more flexible metric measuring the information needed to find any valid solution. It is calculated as the negative log of the sum of probabilities of reaching all possible goal states.
These metrics generalize previous work like MUSE (Minimum Uniform Entropy) by allowing for non-uniform player policies. Instead of assuming a player moves randomly, MSI and TSI can incorporate "inference rules"—logical shortcuts that human players use to prune the search space.
Inference Rules and Player Modeling
To bridge the gap between theory and human behavior, the authors encoded specific logical deductions for The Witness. For example, the Along-the-path Rule (APR) evaluates if region constraints are violated incrementally as a path is drawn. They found that adding these rules significantly improved the correlation between their metrics and real-world player ratings from The Windmill community site.
Interestingly, the study found a "sweet spot" for modeling. Adding every possible mathematical shortcut actually decreased the correlation with human ratings, suggesting that humans do not always use perfect logic. Over-modeling player intelligence leads to an underestimation of perceived difficulty.
Results and Practical Applications
The TSI metric showed a strong Pearson correlation (0.563) with user upvotes, matching state-of-the-art performance while remaining mathematically simpler. Furthermore, a policy trained via machine learning achieved an even higher correlation (0.751) on specific puzzle sets, indicating that neural networks can effectively capture the nuances of human puzzle-solving.
Beyond theoretical measurement, these metrics have practical utility. The authors integrated TSI into a puzzle editor, enabling Exhaustive Procedural Content Generation (EPCG). This allows designers to automatically generate thousands of puzzles and sort them by difficulty, facilitating the creation of balanced level progressions.
Conclusion
By framing difficulty as the information required to correct a player's policy, this research provides a robust, generalizable way to quantify the challenge of logic puzzles. While difficulty and enjoyment are not always perfectly aligned, these metrics offer a powerful tool for game designers to understand and craft the player experience.
Summary updated