论文标题
Tumbleweed的游戏是Pspace-Complete
The Game of Tumbleweed is PSPACE-complete
论文作者
论文摘要
Tumbleweed是在著名的Mind Sport Olympiad上玩的新领土游戏的流行两者完美信息。我们定义了游戏的广义版本，其中板尺寸是任意的，可能的中性石头数量也是如此。 我们的结果：确定给定配置的复杂性哪种玩家具有成功的策略是Pspace complete。证明是通过T.J.的布尔公式游戏缩小日志空间的。 Schaefer，已知是PSPACE完整的。 我们在没有适当的“桥梁”的情况下将非平面schaefer游戏嵌入了平面风滚草板中，这是由于董事会的拓扑而不可能的。取而代之的是，我们的新技术使用了一场单行紧的比赛，该比赛仅根据玩嵌入式4-CNF游戏的协议而迫使玩家移动。
Tumbleweed is a popular two-player perfect-information new territorial game played at the prestigious Mind Sport Olympiad. We define a generalized version of the game, where the board size is arbitrary and so is the possible number of neutral stones. Our result: the complexity of deciding for a given configuration which of the players has a winning strategy is PSPACE-complete. The proof is by a log-space reduction from a Boolean formula game of T.J. Schaefer, known to be PSPACE-complete. We embed the non-planar Schaefer game within the planar Tumbleweed board without using proper "bridges", that are impossible due to the board's topology. Instead, our new technique uses a one-move tight race that forces the players to move only according to the protocol of playing the embedded 4-CNF game.
