月归档:一月 2019

3D推箱子之《Zoko》

  本文地址:http://sokoban.ws/blog/?p=4269 我之前的博文中介绍过不少3D的推箱子推广,如Puzzle Moppet、微软的Tinker、Berusky II、Psychoban、DeadEnd 3D、Sokoban 3D等等。 《Zoko》这个游戏也是一款极有特色的3D推箱子,发现这个游戏至少有一两年了,已经记不清是什么时候第一次见到这个游戏的。最近偶尔又从浏览器书签了翻出了这个游戏。这个游戏是个开源的作品,可以浏览器在线玩:https://lulea.github.io/game-off-2012/,一共只有5关,算是个半成品吧。这也反映出3D推箱子的流行程度比经典推箱子可能要更低一个数量级。 3D推箱子要解决人怎么往上走的问题,很多游戏的解决方案都是电梯。本游戏的电梯的特点是有人或箱子压在上面则上升,离开则下降复原。而其他更多的游戏是人踏上电梯,电梯则上升(或下降,取决于电梯当前状态),人离开电梯不动,导致空载的电梯可以处于升起或降下两种状态之一,状态更加不确定一些。 《Zoko》的另外一个特点是人可以推动竖直叠在一起的两个(或多个?)箱子,但水平的两个箱子推不动。 我想,3D推箱子流行度还有待提高的其中一个原因是:规则变多了,但是游戏的难度(计算复杂度)并没有得到提升,还是PSPACE完全。 为什么说3D推箱子还是PSPACE完全的呢?一是包括《Zoko》在内,许多3D推箱子的推广限制在2D情况等同于经典推箱子,所以难度不低于PSPACE。二是《Zoko》游戏中,每个3D格子的可能状态只有有限的几种(如空闲、有人或有箱子),从而关卡总状态是关卡格子数目的指数函数,因而有多项式空间算法可解,即难度也不高于PSPACE。      

发表在 推箱子, 游戏, 计算机 | 留下评论

《花之谜题》的计算复杂度

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=4244 “P是否等于NP?”是Clay数学研究所(Clay Mathematics Institute,缩写CMI)2000年评出的七个奖金100万美元公开数学问题中的一个。Clay数学研究所的官网对每个问题都有正式的描述,其中对“P=NP?”问题的描述中,以扫雷游戏作为NP完全问题的代表,作了一些深入浅出的介绍,见下面官网截图。可见,一些益智小游戏和被数学家认为最重要的数学问题也有密切联系。 由于长期对推箱子游戏的喜爱,从而对推箱子类游戏的计算复杂度也很感兴趣。一般有点意思的推箱子类游戏对应的判定问题的计算复杂度,大多是NP完全或PSPACE完全的。对于具体一个推箱子类游戏,要完全确定其计算复杂度,有时也不见得容易。其中涉及的一个特别的因素是游戏的答案长度:是否总有多项式长度的答案?还是存在例子使得答案长度达到指数级别? 《花之谜题》(Hanano Puzzle)是一个令人爱不释手的游戏,我之前有两篇博文都分别介绍过。这个游戏特别之处在于一方面具有引力,另一方面可以通过开花抵抗引力向上推。 最近,我和合作者在 Elsevier 出版集团旗下的学术期刊 Information Processing Letters 上发表了一篇文章,研究了这个游戏的计算复杂度。有兴趣的朋友可以在此下载该文章的被接收的手稿: Hanano Puzzle is NP-hard 正式发表的版本可以在 Elsevier 官网下载: https://authors.elsevier.com/a/1YRTa4ZKAYBpN(此链接于2019年3月13日前都可以免费下载)正式版本的排版更为赏心悦目一些,学术出版集团 Elsevier 还是在学术出版过程中创造了不少价值。

发表在 数学, 游戏, 计算机 | 留下评论