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.
翻译:Tumbleweed 是著名的Mind Sport奥林匹克运动会上流行的双玩者完美信息新地域游戏。 我们定义了游戏的通用版本, 棋盘大小是任意的, 中性石的可能数量也是任意的。 我们的结果是: 决定一个特定配置的复杂性, 哪个球员拥有获胜策略是完成的 PSPACE 。 证据是来自T. J. Schaefer( 已知为PSPACE- 完成的) Boolean 公式游戏的日志空间缩小。 我们将非平板 Schaefer 游戏嵌入平板中, 但不使用适当的“ 桥 ” 。 而由于棋盘的地形学, 我们的新技术使用了一动紧的竞赛, 迫使球员只按照嵌入式 4CNF 游戏的游戏程序行动。