Games, puzzles and computation
Games, puzzles and computation
复制标题
游戏、谜题和计算
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
E. Demaine
中科院分区：
文献类型：
--
作者：
R. Hearn;E. Demaine
游戏和计算的概念之间存在基本联系。从最基本的角度来看，这是任何游戏复杂性结果所暗示的，但是连接比这更深。一个例子是交替的非确定主义的概念，该概念与两个玩家游戏密切相关。
在本文的上半年。我将游戏的想法作为计算的程度比以前更大。我介绍了一个普通的游戏家族，称为“约束逻辑”，这在数学上很简单，非常适合减少许多实际的棋盘游戏。约束逻辑的确定性版本对应于一种单调和可逆的新型逻辑电路。在频谱的另一端，我证明了约束逻辑的多人游戏版本是不可确定的。在哲学上，使用有限的物理资源有不确定的游戏在哲学上很重要，并提出了与教会论文有关的问题。
在本文的下半年，我将约束逻辑形式主义应用于许多实际的游戏和难题，提供了新的硬度证明。这些应用包括滑动块难题，滑动地板拼图，木板拼图，铰接的多边形解剖，亚马逊，konane，cross，交叉用途，提示等。其中一些是众所周知的开放问题。对于其他游戏，包括Minesweeper，Warehouseman的问题，索科班和高峰时间，我要么加强现有结果，要么提供比原始证明的新的，更简单的硬度证明。 （专门从麻省理工学院图书馆提供的副本，RM。14-0551，剑桥，马萨诸塞州02139-4307。Ph。617-253-5668;传真617-253-1690。）
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, Konane, Cross Purposes, TipOver, and others. 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. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)