Games, Puzzles, and Computation

Last updated
Games, Puzzles, and Computation
Games, Puzzles, and Computation.jpg
Book cover, first edition
Author Robert A. Hearn, Erik D. Demaine
LanguageEnglish
Publisher A K Peters
Publication date
1 July 2009
ISBN 978-1568813226

Games, Puzzles, and Computation is a book on game complexity, written by Robert Hearn and Erik Demaine, and published in 2009 by A K Peters. It is revised from Hearn's doctoral dissertation, which was supervised by Demaine. [1] [2] The Basic Library List Committee of the Mathematical Association of America has recommended it for inclusion in undergraduate mathematics libraries. [3]

Contents

Topics

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]

Audience and reception

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]

Related Research Articles

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

<span class="mw-page-title-main">Search algorithm</span> Any algorithm which solves the search problem

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values.

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

In computer science and artificial intelligence, combinatorial search studies search algorithms for solving instances of problems that are believed to be hard in general, by efficiently exploring the usually large solution space of these instances. Combinatorial search algorithms achieve this efficiency by reducing the effective size of the search space or employing heuristics. Some algorithms are guaranteed to find the optimal solution, while others may only return the best solution found in the part of the state space that was explored.

<span class="mw-page-title-main">Combinatorial game theory</span> Branch of game theory about two-player sequential games with perfect information

Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

<span class="mw-page-title-main">Generalized game</span> Game generalized so that it can be played on a board or grid of any size

In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an grid.

<span class="mw-page-title-main">Kakuro</span> Type of logic puzzle

Kakuro or Kakkuro or Kakoro is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword. Kakuro puzzles are regular features in many math-and-logic puzzle publications across the world. In 1966, Canadian Jacob E. Funk, an employee of Dell Magazines, came up with the original English name Cross Sums and other names such as Cross Addition have also been used, but the Japanese name Kakuro, abbreviation of Japanese kasan kurosu, seems to have gained general acceptance and the puzzles appear to be titled this way now in most publications. The popularity of Kakuro in Japan is immense, second only to Sudoku among Nikoli's famed logic-puzzle offerings.

<span class="mw-page-title-main">Sudoku</span> Logic-based number-placement puzzle

Sudoku is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 subgrids that compose the grid contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

<span class="mw-page-title-main">Mathematics of Sudoku</span> Mathematical investigation of Sudoku

Mathematics can be used to study Sudoku puzzles to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.

In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters. For example, the input to the bin packing problem is a list of objects of specific sizes and a size for the bins that must contain the objects—these object sizes and bin size are numerical parameters.

In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to the way its combinatorics depends on input, constraints and bounds. Combinatorial explosion is sometimes used to justify the intractability of certain problems. Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function.

<span class="mw-page-title-main">Go and mathematics</span> Calculations of the game complexity of go

The game of Go is one of the most popular games in the world. As a result of its elegant and simple rules, the game has long been an inspiration for mathematical research. Shen Kuo, an 11th century Chinese scholar, estimated in his Dream Pool Essays that the number of possible board positions is around 10172. In more recent years, research of the game by John H. Conway led to the development of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go).

A K Peters, Ltd. was a publisher of scientific and technical books, specializing in mathematics and in computer graphics, robotics, and other fields of computer science. They published the journals Experimental Mathematics and the Journal of Graphics Tools, as well as mathematics books geared to children.

<span class="mw-page-title-main">Edge-matching puzzle</span> Tiling puzzle

An edge-matching puzzle is a type of tiling puzzle involving tiling an area with polygons whose edges are distinguished with colours or patterns, in such a way that the edges of adjacent tiles match.

In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. This is a form of reversible logic in that each sequence of edge orientation changes can be undone.

In computational complexity theory and game complexity, a parsimonious reduction is a transformation from one problem to another that preserves the number of solutions. Informally, it is a bijection between the respective sets of solutions of two problems. A general reduction from problem to problem is a transformation that guarantees that whenever has a solution also has at least one solution and vice versa. A parsimonious reduction guarantees that for every solution of , there exists a unique solution of and vice versa.

In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.

Robert Aubrey Hearn is an American ultramarathon runner, computer scientist, and recreational mathematician.

References

  1. 1 2 3 4 5 6 O'Rourke, Joseph (December 2010), "Review of Games, Puzzles, and Computation", SIAM Review , 52 (4): 782–785, JSTOR   41062032
  2. 1 2 3 Aichholzer, O. (December 2012), "Review of Games, Puzzles, and Computation" (PDF), Internationale Mathematische Nachrichten (in German), 66 (221): 58
  3. 1 2 3 4 5 6 7 8 9 Harkleroad, Leon (December 2009), "Review of Games, Puzzles, and Computation", MAA Reviews, Mathematical Association of America
  4. 1 2 3 4 Babinkostova, Liljana (December 2009), "Review of Games, Puzzles, and Computation", zbMATH , Zbl   1175.91035