Games, Puzzles, and Computation

Games, Puzzles, and Computation concerns the computational complexity theory of solving logic puzzles and making optimal decisions in two-player and multi-player combinatorial games. Its focus is on games and puzzles that have seen real-world play, rather than ones that have been invented for a purely mathematical purpose.^[2] In this area it is common for puzzles and games such as sudoku, Rush Hour, reversi, and chess (in generalized forms with arbitrarily large boards) to be computationally difficult: sudoku is NP-complete, Rush Hour and reversi are PSPACE-complete, and chess is EXPTIME-complete. Beyond proving new results along these lines, the book aims to provide a unifying framework for proving such results, through the use of nondeterministic constraint logic, an abstract combinatorial problem that more closely resembles game play than the more classical problems previously used for completeness proofs.^[1][3]

It is divided into three parts. The first part concerns constraint logic,^[3][4] which involving assigning orientations to the edges of an undirected graph so that each vertex has incoming edges with large-enough total weight.^[1][3] The second part of this book applies constraint logic in new proofs of hardness of various real-world games and puzzles,^[3][4] by showing that, in each case, the vertices and edges of a constraint logic instance can be encoded by the moves and pieces of the game. Some of these hardness proofs simplify previously-known proofs; some ten of them are new, including the discovery that optimal play in certain multiplayer games can be an undecidable problem.^[1] A third part of the book provides a compendium of known hardness results in game complexity,^[3][4] updating a much shorter list of complete problems in game complexity from the 1979 book Computers and Intractability. An appendix provides a review of the methods from computational complexity theory needed in this study, for readers unfamiliar with this area.^[3]

Although primarily a research monograph and reference work for researchers in this area, reviewer Oswin Aichholzer recommends the book more generally to anyone interested in the mathematics of games and their complexity.^[2] Liljana Babinkostova writes that Games, Puzzles, and Computation is enjoyable reading, successful in its "purpose of building a bridge between games and the theory of computation".^[4]

Leon Harkleroad is somewhat more critical, writing that the book feels padded in places,^[3] and Joseph O'Rourke complains that its organization, with many pages of abstract mathematics before reaching the real-world games, does not lend itself to cover-to-cover reading.^[1] However, both Harkleroad and O'Rourke agree that the book is well produced and thought-provoking.^[1][3]