Games, Puzzles, and Computation
The authors show that there are underlying mathematical reasons for why games and puzzles are challenging (and perhaps why they are so much fun). They also show that games and puzzles can serve as powerful models of computation—quite different from the usual models of automata and circuits—offering a new way of thinking about computation. The appendices provide a substantial survey of all known results in the field of game complexity, serving as a reference guide for readers interested in the computational complexity of particular games, or interested in open problems about such complexities.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
activated Amazons Basis vertices Black blue edge Boolean circuit bounded games Bounded NCL combinatorial game theory complexity class configuration constraint graph constraint-logic game construction corresponding crate crossover gadget defined Deterministic Constraint Logic EXPSPACE EXPTIME EXPTIME-complete FANOUT following game forced win formula game games and puzzles given goal graph G hinged horizontally input 1 input Instance Konane latch lock nondeterminism nondeterministic algorithm Nondeterministic Constraint Logic NP-complete NP-hard one-player game output edge Peg Solitaire planar graphs plank puzzle play polynomial position problem Proof PSPACE PSPACE-complete PSPACE-hard Quantified Boolean Formulas quantifier gadget red edges red-blue vertices reduction reversible computer Rush Hour satisfied out satisfied Section shown in Figure signal sliding-block puzzles Sokoban space squares stone subgraph switch target edge team games Theorem TipOver tipper token TPCL Turing machine two-player games unbounded undecidable unpainted variable assignment vertex gadgets vertex types White wire zero-player games