Constraint Logic: A Uniform Framework for Modeling Computation as Games
Erik D. Demaine, Robert Aubrey Hearn · 2008
We introduce a simple game family, called constraint logic, where players reverse edges in a directed graph while satisfying vertex in-flow constraints. This game family can be interpreted in many different game-theoretic settings, ranging from zero-player automata to a more economic setting of team multiplayer games with hidden information. Each setting gives rise to a model of computation that we show corresponds to a classic complexity class. In this way we obtain a uniform framework for modeling various complexities of computation as games. Most surprising among our results is that a game with three players and a bounded amount of state can simulate any (infinite) Turing computation, making the game undecidable. Our framework also provides a more graphical, less formulaic viewpoint of computation. This graph model has been shown to be particularly appropriate for reducing to many existing combinatorial games and puzzles - such as Sokoban, rush hour, river crossing, tipover, the warehouseman's problem, pushing blocks, hinged-dissection reconfiguration, Amazons, and Konane (hawaiian checkers) - which have an intrinsically planar structure. Our framework makes it substantially easier to prove completeness of such games in their appropriate complexity classes.