Introduction
Generating a puzzle is a relatively straightforward task, but generating a good puzzle—one that is challenging, engaging, and satisfying to solve—presents a significant computational hurdle. Researchers at Gettysburg College have addressed this challenge in the context of "Birds of a Feather," a perfect-information solitaire game played on a 4x4 grid. In this game, players move cards onto adjacent cards of the same suit or rank, with the goal of reducing the entire grid to a single stack.
While randomly generated deals are common, they often result in puzzles that are either trivially easy or mathematically impossible. The authors sought to automate the creation of "tense" puzzles by identifying the objective features that correlate with subjective human enjoyment.
Methodology: Human-in-the-Loop Optimization
To bridge the gap between mathematical properties and human fun, the researchers employed an iterative, human-in-the-loop optimization process. This process relied on three core components:
- Stochastic Local Search (SLS): The team used a "Hill-Descent with Random Uphill Steps" algorithm to navigate the astronomical space of possible card distributions. The algorithm mutates a puzzle by swapping cards and evaluates the result against an "energy function"—a mathematical measure of puzzle "badness."
- Iterative Refinement: The study progressed through four iterations. In each phase, a batch of puzzles was generated by minimizing the current energy function. These puzzles were then manually solved and rated by humans on a scale of 0 to 10.
- Linear Regression: The researchers performed linear regression on these ratings, using objective features (such as suit diversity, rank clusters, and solvability ratios) as predictors. This allowed them to update the energy function based on which features actually drove higher quality ratings.
Initially, the energy function was a simple binary check for solvability. However, as the iterations progressed, it evolved into a sophisticated formula incorporating solvability ratios at various depths of the game's state space.
Key Insights: The Hourglass of Tension
The most significant discovery of the research was the identification of the "Halfway Solvability Ratio" as the primary driver of puzzle quality. This ratio measures the proportion of reachable states that remain solvable at the game's midpoint ($d = n/2$).
The authors found that high-quality puzzles often exhibit an "hourglass" state-space structure. These puzzles begin with a variety of possible moves but quickly narrow down to a highly constrained "bottleneck" in the mid-game. In this bottleneck, only a few specific sequences of moves lead to a solution. If a player makes a "wrong" move here, they enter an unsolvable branch of the state space. This creates a palpable sense of tension, as the player must navigate a narrow path to reach the endgame, where the puzzle opens up again for a simple conclusion.
Key Results and Feature Importance
In the final iteration of the study, the Halfway Solvability Ratio emerged with a massive negative regression coefficient (-40.7). This confirms that as the ratio of solvable mid-game states decreases (without reaching zero), the subjective quality and tension of the puzzle increase significantly.
Interestingly, the researchers found that some objective metrics were misleading. For instance, while high suit diversity might seem like a good feature, it often led to trivial solutions where a player could simply "sweep" same-suit cards into a stack without much thought. By focusing on the state-space structure rather than just card distribution, the algorithm successfully moved from generating trivial 4-card puzzles to sophisticated 16-card puzzles that feel intentionally designed.
Limitations and Future Work
While the current generator produces high-quality puzzles, it is computationally expensive. Calculating the exact halfway solvability ratio requires a full state-space search, which is feasible for small grids but slow for a full 16-card game.
Future work will focus on approximation methods to speed up the generation process. Techniques such as Beam Search or Midgame Sampling could allow the energy function to be estimated more quickly, potentially enabling real-time puzzle generation for consumer applications. Additionally, the authors suggest that their framework for modeling "tension" could be applied to other perfect-information solitaire games to automate the design of engaging content.
Summary updated