Computational Complexity of Puzzles and Strategic Games

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2261 papers364 conceptsfrozen 2026-10-04

Why is it that a child can play Angry Birds, yet a supercomputer might struggle to find the optimal solution? This question lies at the heart of a research direction that seeks to map the computational landscape of games and puzzles. By treating game mechanics as logical components, researchers like Matthew Stephenson, Erik D. Demaine, and Krishnendu Chatterjee are uncovering why certain interactive systems are fundamentally "hard" to solve.

The Mechanics of Hardness

To understand why a game is difficult, researchers look for "gadgets"—specific configurations of game rules that mimic the behavior of logic gates (AND, OR, NOT). If you can build a working computer out of the pieces of a game, then solving that game is at least as hard as any problem that computer can solve.

In Trainyard is NP-Hard, Matteo Almanza and colleagues demonstrated this by constructing complex logical gadgets out of trains and color-mixers. Similarly, Matthew Ferland showed in NP-Hardness of a 2D, a 2.5D, and a 3D Puzzle Game that modern titles like Baba Is You are NP-hard because their rule-rewriting mechanics can be used to simulate the 3-SAT logic problem.

This "gadget-based" reduction provides the intuition for the field: Complexity isn't about the theme of the game, but about the expressive power of its rules.

The Hierarchy of Play

The research categorizes games into a hierarchy of complexity classes, each representing a different "flavor" of difficulty:

  • NP-Hard (The Puzzle Tier): These are games where a solution is hard to find but easy to verify. Luciano Gualà and Stefano Leucci 0001 proved in Bejeweled, Candy Crush and other match-three games are (NP-)hard that the simple act of matching tiles can scale into an intractable search problem.
  • PSPACE-Complete (The State Tier): These games often involve moving pieces around a board where the same configuration can be revisited, requiring an exponential amount of time to explore all possibilities within a limited space. Edouard Bonnet showed that even the card game Durak falls into this category, as does Minesweeper with Limited Moves when analyzed by Serge Gaspers.
  • EXPTIME-Hard (The Strategy Tier): Usually reserved for multi-player games like Chess or Go, this tier represents games that require looking ahead through an astronomical number of turns. A landmark finding in The Computational Complexity of Angry Birds by Matthew Stephenson and Jochen Renz revealed that physics-based puzzles can actually reach this level, making them theoretically harder than many classic board games.

Information and Uncertainty

The difficulty of a game often shifts dramatically when information is hidden. Junkang Li and Bruno Zanuttini explored this in Combinatorial Games with Incomplete Information, proving that even if all actions are public, having hidden initial knowledge makes a game as computationally difficult as general extensive-form games.

Conversely, some games are surprisingly easy. Erik D. Demaine found in The complexity of UNO that while a single-player version is NP-complete, playing optimally against an opponent in a simplified two-player version can be solved in polynomial time. This highlights a recurring theme: Adding players doesn't always increase complexity; sometimes, the constraints of competition actually narrow the search space.

Beyond Entertainment: Graph Games

This research direction extends into formal verification and system design through "games on graphs." In these models, a "controller" plays against an "environment." Krishnendu Chatterjee has been a central figure here, exploring Multi-Mean-Payoff and Multi-Energy Games. These games model reactive systems (like a power grid) that must balance multiple objectives simultaneously.

The complexity of these games—often sitting in the intersection of NP and co-NP—remains one of the most tantalizing open questions. As Georg Loho suggests in Abstract Tropical Linear Programming, finding a polynomial-time solution for these "mean payoff" games would not just solve a puzzle, but would provide a breakthrough in how we verify the safety of complex automated systems.

Why It Works

The intuition of this field is that games are a microcosm of computation. By proving a game is PSPACE-complete or NP-hard, researchers aren't just saying the game is "tough." They are identifying the fundamental mathematical structure of the game's rules. This allows us to understand the limits of AI solvers, the inherent difficulty of human decision-making, and the boundary between simple entertainment and universal computation.

Papers in this version

Showing 60 of 261 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 154 papers
  2. Version 1 · 2026-10-04 · 261 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_game_complexity_2e336217,
  title = {stochastic game complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-game-complexity/rdr_2e33621776f249fe9bf6febc8aa59a87},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_complexity_of_puzzles_and__2e336217_v1,
  title = {Computational Complexity of Puzzles and Strategic Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-puzzles-and-strategic-games/rdr_2e33621776f249fe9bf6febc8aa59a87/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}