How computers generate puzzle levels, and why checking matters

In 2011 Julian Togelius, Georgios Yannakakis, Kenneth Stanley and Cameron Browne mapped a fast-growing field and gave it a name: search-based procedural content generation. Their survey sorts generators by what they make, how that content is represented inside the program, and, most importantly, how its quality is evaluated. The search-based approach treats level design as optimisation. Generate candidates, score each one with an evaluation function, keep the best and vary them, and repeat, often with evolutionary algorithms borrowed from biology.

The evaluation function is where design lives. It can measure a level directly (how many pieces, how much empty space), by simulation (let an artificial player try it and see what happens), or interactively (ask real players). Each has a cost. Direct measures are cheap but shallow. Simulation is more faithful but needs a program that can actually play the game. Asking people is the most faithful and by far the slowest.

For a sliding-block puzzle, it is easy to picture. A candidate is a grid with bricks placed on it. A variation moves, adds or removes a brick. A direct measure might count how crowded the board is; a simulation-based measure hands the board to a solver and records whether it can be cleared and how long the route it finds is. Keep the boards that score well, vary them again, and after thousands of rounds the generator has drifted towards whatever the evaluation function rewards. That is its power and its danger: it will find exactly what you asked for, including boards that satisfy the numbers and bore the player.

Sources1Source 1Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 172–186.

A different school starts from the other end. Instead of evolving boards and hoping good ones emerge, Adam Smith and Michael Mateas proposed describing the space of acceptable designs explicitly, as a set of logical constraints, and letting a general-purpose solver find boards that satisfy them. Using a technique called answer set programming, a designer can write rules such as “the exit must be reachable” or “this piece must move at least twice” and receive only boards that obey them.

The appeal for puzzle design is obvious. Many of the things that make a board interesting are constraints: this brick must be blocked by that one, this key must be needed. Writing them down forces a designer to say what they actually want, which is a discipline as useful to humans as to machines.

Sources2Source 2Smith, A. M., & Mateas, M. (2011). Answer set programming for procedural content generation: A design space approach. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 187–200.

Whatever the generator, a puzzle must first be solvable, and proving it is often the hardest step. Noor Shaker, Mohammad Shaker and Julian Togelius faced this with Cut the Rope, a physics puzzle with continuous time and space, where brute-force search is hopeless. Their answer was a reasoning agent that proposed only sensible moves at each state, which shrank the search enough that a straightforward depth-first search could find solutions and confirm that generated levels were playable.

Bilal Kartal, Nick Sohre and Stephen Guy took another route for Sokoban, the classic box-pushing puzzle. Their generator builds puzzles through simulated play using Monte Carlo tree search, so every puzzle it produces is solvable by construction. Sliding-block puzzles are a hard case too: the general problem is PSPACE-complete, as our history of sliding block puzzles explains, so there is no known shortcut that solves every board quickly.

Sources3Source 3Shaker, N., Shaker, M., & Togelius, J. (2013). Evolving playable content for Cut the Rope through a simulation-based approach. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 9(1), 72–78.4Source 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.

A board can be solvable and still be dull, or solvable only by a route no human would find. Kartal and colleagues tackled this head-on. They ran a user study to find board features that were cheap to compute and correlated with how difficult people found the puzzles, combined them into a scoring function, and then confirmed in a second study that higher-scoring puzzles were perceived as harder. Difficulty, in other words, had to be learned from people, not assumed.

Yannakakis and Togelius generalise the point in their framework for experience-driven procedural content generation: model the player’s experience, whether from behaviour, reports or physiology, and generate content to shape it. It is an ambitious goal, and the honest state of the art is that models of fun and frustration remain rough. For a puzzle, qualities like elegance, the satisfying “aha” and fairness are still easier to recognise than to compute. We look at what fairness means for players in what makes a puzzle feel fair.

Sources4Source 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.5Source 5Yannakakis, G. N., & Togelius, J. (2011). Experience-driven procedural content generation. IEEE Transactions on Affective Computing, 2(3), 147–161.

For players, a useful rule of thumb follows from all this. “Infinite levels” tells you a generator exists; it does not tell you how its levels are tested. Look for games that say how they check boards, and be wary when difficulty jumps around at random, which is often a sign that nothing is modelling it.

A few other signs of a well-made puzzle set, generated or not: new ideas are introduced one at a time, as research on puzzle pacing recommends; boards feel distinct rather than like near-copies with one piece moved; and when you are stuck, you believe a solution exists. That last one is the hardest to fake, and the one generators have worked longest to earn.

OutBrick’s 2,000 boards are a fixed, authored set rather than a stream generated on your device, and every one had its clearing route replayed against the game’s own rules before release. We describe that process, including why a solver running out of budget means “unknown” rather than “impossible”, in how we verified 2,000 sliding-block boards. A solver proves a route exists; it does not prove the board is fun, which is why pacing is judged separately. You can see the result for yourself on today’s daily board.