In computational game design, there is a persistent paradox: a puzzle that takes an AI milliseconds to solve can leave a human frustrated for hours, while a "massive" game with trillions of states might be strategically shallow and easy to master. Traditional computer science metrics—such as state-space size, branching factors, or the length of an optimal solution—often fail to predict how difficult a challenge actually feels to a person.
Researchers are now developing new frameworks to bridge this gap, moving away from raw computational power toward metrics that capture cognitive load, strategic depth, and the "aha!" moments of human discovery.
The Failure of Structural Metrics
For decades, the standard way to measure game difficulty was to look at its mathematical properties. If a game had more possible moves or a larger search tree, it was considered more "complex." However, as Martin Zinkevich et al. argue in A New Algorithm for Generating Equilibria in Massive Zero-Sum Games, these measures fail to capture the actual strategic depth perceived by players. A game can have a massive state space but very few "layers" of strategy, making it computationally heavy but mentally light.
This discrepancy is particularly visible in platformers and puzzles. In an empirical study of Super Mario Bros. levels, Julian R. H. Mariño et al. found that simple counts of hazards and power-ups show only a weak correlation with human-perceived difficulty in An Empirical Evaluation of Evaluation Metrics of Procedurally Generated Mario Levels. A level might be packed with enemies, but if a human can easily bypass them using a single intuitive movement, the "calculated" difficulty is meaningless.
Similarly, Nathan R. Sturtevant et al. demonstrate in The Unexpected Consequence of Incremental Design Changes that solution length is a poor proxy for challenge. In the game Snakebird, a puzzle requiring only a few steps can be significantly harder than one requiring fifty, provided those few steps involve non-intuitive mechanics that defy a player's initial expectations.
Deduction versus Execution
The core of the problem lies in how humans and machines solve problems differently. An AI typically uses search—exploring a tree of possibilities to find a path to a goal. A human, particularly in logic puzzles, uses deduction.
In Generalized Entropy and Solution Information for Measuring Puzzle Difficulty, J.L. Shen and Junwen Shen argue that difficulty stems from the cognitive effort required for logical inference rather than the physical steps taken. They suggest that if a player model includes highly efficient mathematical shortcuts, it will consistently underestimate how hard a puzzle feels to a human who does not naturally see those shortcuts.
This distinction between finding a solution and verifying one is also explored by Henry Förster et al. in GraphTrials: Visual Proofs of Graph Properties. They highlight that while a problem might be computationally NP-complete to solve, a "visual certificate" can leverage human perception to make the solution instantly verifiable, effectively decoupling computational complexity from perceptual effort.
Toward Human-Centered Metrics
To address these misalignments, researchers have proposed several "human-centered" metrics:
- Range of Skill (ROS): Proposed by Martin Zinkevich et al., this measure focuses on the strategic layers of a game rather than its state space, aligning more closely with how players learn and improve.
- Playing-level Complexity (PLC): In Depth, balancing, and limits of the Elo model, Marie-Liesse Cauwet et al. define difficulty through the lens of Elo ratings. PLC measures the gap between the strongest and weakest players, capturing how much room there is for a human to actually express skill.
- Information-Theoretic Entropy: Adam White 0001 et al. introduced MUSE and ReMUSE in Entropy as a Measure of Puzzle Difficulty. These metrics quantify the "uncertainty" a player feels. A puzzle is difficult not because it is long, but because the player is faced with high-information decisions where the correct path is not immediately obvious.
Applications in Automated Design
Understanding this divergence is not just theoretical; it is essential for Procedural Content Generation (PCG). If an algorithm generates levels based on search depth, it may produce content that is "hard" for an AI but trivial or boring for a human.
For instance, André Grahl Pereira et al. developed a system for Sokoban that generates levels harder for AI solvers than those made by experts, yet they note in Procedural Generation of Initial States of Sokoban that these levels may not translate to a better human experience. Similarly, the authors of Talakat: Bullet Hell Generation through Constrained Map-Elites, Ahmed Khalifa 0001 et al., emphasize that high projectile density does not equal high difficulty if "safe zones" exist that a human can easily spot.
By shifting the focus from what is hard for a computer to calculate to what is hard for a human to perceive, researchers are creating AI that can better predict, challenge, and engage the human mind.
Key Foundational Work
Generating and Solving Logic Puzzles through Constraint Satisfaction (2007) — contributed 1 concept elements to this direction.
A New Algorithm for Generating Equilibria in Massive Zero-Sum Games (2007) — contributed 1 concept elements to this direction.
Playable Experiences at AIIDE 2014 (2014) — contributed 1 concept elements to this direction.