Games, puzzles, and computation
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/37913 |
| _version_ | 1811068939035213824 |
|---|---|
| author | Hearn, Robert A. (Robert Aubrey), 1965- |
| author2 | Erik D. Demaine and Gerald J. Sussman. |
| author_facet | Erik D. Demaine and Gerald J. Sussman. Hearn, Robert A. (Robert Aubrey), 1965- |
| author_sort | Hearn, Robert A. (Robert Aubrey), 1965- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. |
| first_indexed | 2024-09-23T08:03:10Z |
| format | Thesis |
| id | mit-1721.1/37913 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:03:10Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/379132019-04-09T16:20:51Z Games, puzzles, and computation Hearn, Robert A. (Robert Aubrey), 1965- Erik D. Demaine and Gerald J. Sussman. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. Includes bibliographical references (p. 147-153). There is a fundamental connection between the notions of game and of computation. At its most basic level, this is implied by any game complexity result, but the connection is deeper than this. One example is the concept of alternating nondeterminism, which is intimately connected with two-player games. In the first half of this thesis, I develop the idea of game as computation to a greater degree than has been done previously. I present a general family of games, called Constraint Logic, which is both mathematically simple and ideally suited for reductions to many actual board games. A deterministic version of Constraint Logic corresponds to a novel kind of logic circuit which is monotone and reversible. At the other end of the spectrum, I show that a multiplayer version of Constraint Logic is undecidable. That there are undecidable games using finite physical resources is philosophically important, and raises issues related to the Church-Turing thesis. In the second half of this thesis, I apply the Constraint Logic formalism to many actual games and puzzles, providing new hardness proofs. These applications include sliding-block puzzles, sliding-coin puzzles, plank puzzles, hinged polygon dissections, Amazons, Kohane, Cross Purposes, Tip over, and others. (cont.) Some of these have been well-known open problems for some time. For other games, including Minesweeper, the Warehouseman's Problem, Sokoban, and Rush Hour, I either strengthen existing results, or provide new, simpler hardness proofs than the original proofs. by Robert Aubrey Hearn. Ph.D. 2007-07-18T13:09:32Z 2007-07-18T13:09:32Z 2006 2006 Thesis http://hdl.handle.net/1721.1/37913 133170195 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 153 leaves application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Hearn, Robert A. (Robert Aubrey), 1965- Games, puzzles, and computation |
| title | Games, puzzles, and computation |
| title_full | Games, puzzles, and computation |
| title_fullStr | Games, puzzles, and computation |
| title_full_unstemmed | Games, puzzles, and computation |
| title_short | Games, puzzles, and computation |
| title_sort | games puzzles and computation |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/37913 |
| work_keys_str_mv | AT hearnrobertarobertaubrey1965 gamespuzzlesandcomputation |