分类目录归档:游戏

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 还是在学术出版过程中创造了不少价值。

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

跑步总结:第十个半年

  本文地址:http://sokoban.ws/blog/?p=4180   从2018年5月起,基本没有怎么跑步,体重一路增长到66公斤。一直在忙各种学术活动,以及送孩子上幼儿园。每月跑量如下: 2018年5月:0公里 2018年6月:0公里 2018年7月:4公里(西大球场1k+3k) 2018年8月:3公里(西大球场1k+2k) 2018年9月:0公里 2018年10月:4公里(西大球场1k+3k) 半年合计:11公里。    

发表在 游戏 | 留下评论

《花之谜题2》

  本文地址:http://sokoban.ws/blog/?p=3784 除了推箱子,能令人饶有趣味地玩的益智类游戏不多。六年前玩过的《花之谜题》便是其中之一(2011年就开始玩了,博文写于2012年)。 今年(2017年)8月,惊喜地发现,时隔六年,《花之谜题2》出来了,有35个新关卡。于是从itch.io网站下载了2代,并支付作者2美元,以感谢作者设计出如此有趣的游戏。顺带用下paypal支付。如今网上的海外支付都越来越多支持微信和支付宝,用到paypal的机会不多了。    

发表在 游戏 | 留下评论

《堆雪人推箱子》是PSPACE完全的

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3444 去年2月份,我写了一篇博文介绍了推箱子游戏(Sokoban)的计算复杂度是PSPACE完全的。同年4月份,我又写了一篇博文介绍了一个推箱子变种游戏《堆雪人推箱子(A good snowman is hard to build)》。 写了这两篇博文后,我产生了一个想法,证明堆雪人推箱子(简称Snowman)的计算复杂度也是PSPACE完全的。经过一番努力,我把这个想法写成了一篇论文,投到由荷兰的学术出版集团Elsevier发行的期刊《Theoretical Computer Science》。该论文有三名共同作者,我是通讯作者(corresponding author)。今年(2017年)3月,被正式接收了,并于3月18日在网上发表了。 该论文永久有效的DOI地址:http://dx.doi.org/10.1016/j.tcs.2017.03.011 根据和出版社之间的通常的版权协议,我有权在个人博客分享被接收的手稿(accepted manuscript),但经过重新排版的正式发表的期刊论文(published journal article)的版权归Elsevier出版集团。本篇博文的目的就是提供该论文手稿的下载。 手稿下载:snowman_is_pspace_complete.pdf 就在论文被接受前后,我在位于上海复旦大学校内的上海数学中心举办的一次小型的图论青年学者研讨会(Graph Young Theorists Workshop)上,对这个问题作了一个20分钟报告。My presentation slides for this workshop can be also downloaded from here. 文章被接收的时间恰逢MF8推箱子比赛马上第八周年了,而且只差几期就是第100期的比赛了。又关注推箱子已近二十年了,能发表一篇与推箱子相关的学术论文,我十分高兴。 我早在1999年上大学时通过互联网搜索,看到加拿大阿尔伯特大学的Joseph C. Culberson证明推箱子是PSPACE完全问题的文章。但是那时文章中出现的PSPACE和Turing Machine(图灵机)等术语对我如同天书。 … 继续阅读

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

读书笔记(十五)《科学消遣》、《科学思维锻炼与消遣》

  本文地址:http://sokoban.ws/blog/?p=3364 一、从华容道玩具的历史说起 以华容道为代表的滑块类游戏,可视为推箱子的前身。 2007年下半年,我曾查阅许多资料,考究了一下华容道的历史,写了一篇小文《华容道玩具不是中国人发明的》。我把该文发给以学术打假称著的方舟子,发表在网络期刊《新语丝》2007年12期,但插图被略去了。我也把此文发布到其他多个网站,因此在网络上认识了世界魔方协会(WCA)的中国区第一个代表陈丹阳,他也对各种智力谜题有非常浓厚的兴趣。 写该文时,我所查到最早的关于华容道的中文记载是姜长英先生在1949年出版的《科学消遣》一书。此书修改后1997年以《科学思维锻炼与消遣》为名重版。可惜这两本书我当时都未能从图书馆或其他途径找的,只是从其他文献对这两本书的引用间接得知。 2015年7月,陈丹阳告诉我他搜到1948年第201期《中学生》杂志对华容道的介绍。于是这取代《科学消遣》一书,成为目前找到对华容道最早的中文记载。 2016年8月,又收到陈丹阳转发的关于华容道的新资料。是另一世界魔方协会代表常方圆在日本参加世界谜题大会(IPP)时,某喜欢益智游戏的日本退休教授的讲座投影。讲座给出了两种早期在日本流传的华容道的证据。一个据称1936年签订“日德反共协定”时的华容道实物,曹操的角色由共产国际扮演。另一个是侵华战争时期,日本士兵玩的一种以撵走常凯申为主题的华容道。 2016年12月,常方圆提交申请,成功修改了百度百科的魔方词条,删掉了“魔方与中国人发明的华容道,法国人发明的独立钻石一起被称为世界三大智力运动”这句话。接着陈丹阳也写了一篇关于华容道的微博头条文章《该说说华容道的事了》,非常生动精彩,值得一读。 2017年春节期间,我又从淘宝上买来了《科学消遣》和《科学思维锻炼与消遣》两本书。终于看到这两本一直想要查看的文献。49年出版的《科学消遣》单纯介绍了华容道的玩法,只有一小节两页纸。97年重版的《科学思维锻炼与消遣》则用三节来介绍华容道,其中单独一节讲述华容道的历史。其中核心的内容我已经通过其他书的引用看到过了。 二、华容道玩具形成的时间范围 我2007年写的小文主要是为了论证华容道不是中国人发明的。这个论断应该是比较可靠的。一眨眼快10年过去了,如上所述,我又看了一些新的资料,在此想把华容道这一特定形式的滑块游戏的形成时间粗略划定一下。 首先,我在2007年中的文章中就已经查到,1932年,英国有专利申请设计了一套10个滑块的大小方向(即1个2×2,4个1×2,1个2×1和4个1×1)和华容道一模一样的设计。只是2×1的摆放位置和两个小兵对调了一下。 中文文献最早的就是上面提到的1948年的《中学生》杂志和1949年的《科学消遣》。姜长英先生自己是最早1943年第一次见过华容道。他听西北工业大学的林德宽教授说1938年抗日战争后,躲避到陕西汉中城固县乡下见小孩子玩。 另外,就是前文提到的从常方圆处了解到的日本的资料。大概1936年日本就已经出现。 结合西方、日本和中国的零星资料,基本可以判断:华容道这一特定形态大概在1932年至1936年间形成。滑块游戏花样这么多,为什么唯独华容道流传和影响最大呢? 三、论消遣 这次颇费功夫查阅了《科学消遣》和《科学思维锻炼与消遣》两本书,并没有得到关于华容道历史的新的资料。不过1949年版《科学消遣》一书,姜长英先生在第一节有一篇《论消遣》一文则是写得比较精彩。可惜1997年以《科学思维锻炼与消遣》为名重版时,此文居然删改得索然无味了。 下面把《论消遣》这一节全文引用如下。1949年写的文章今天一点也不过时。文中提出的好的消遣方式的三大标准:趣味化、教育化、平民化,推箱子都完全符合,虽然推箱子游戏在该文出版30多年后才出现。另外,作者提出如果消遣的脑力游戏太难想不出答案时,应该持什么样一种态度,也同样适用于玩推箱子。文中还写道:“如有三五同好,就可比赛成绩,更能增加兴趣”,这不正是我们举办推箱子在线比赛的宗旨吗? 论消遣 作者:姜长英 我们做了一天或一星期工作,觉得神劳体倦,生趣索然的时候,自然需要调剂调剂,换换空气,作点消遣。将脑筋里的国家大计,人事纠纷,柴米油盐,……等等,暂且丢开,去想些或做些轻便省力,富有趣味,无关得失的事。使精神与肉体,因改变运用方式,而得到松弛或休息。现在的人,能在工作中求快乐的,实在是太少了。在他工作的余暇,找点消遣,寻些快乐,岂不是应该的?否则,除了吃饭睡觉,就是工作,这样的人生也太苦了吗? 说到消遣是应该的,于是就有人寻花问柳,呼卢喝雉,吐雾吞云,歌舞酒肉,……的迷恋起来。对人解释,对己宽慰,说是“逢场作戏,消遣消遣,偶一为之,无伤大雅”。其实这是堕落,绝不是消遣的正轨。社会上就有少数人,吃穿无忧,闲暇太多。他们以堕落为消遣,天天消遣,简直要拿消遣当作职业了。这是缺乏正当消遣所引起的社会病态。然而,怎样才是应该有的消遣呢? 凡是正当的消遣,最少须是无害的,再积极一点,好消遣必须有益的。一种消遣是否合于我们的需要,可以用三个尺度或条件去衡量它。这三个是: 一、趣味化 二、教育化 三、平民化 第一,既然是消遣,必须使人发生兴趣,引人入胜。第二,消遣宜能养神益智,有益身心。最低限度,也要对人对己,全无遗害。第三,好的消遣须要轻而易举,不必劳师动众,更不可劳民伤财。趣味化了,才能使人乐于参加,不致厌弃。教育化了,才能有利无弊,收安定社会之功。平民化了,才能持久,才能普遍,使人人有消遣的享受。 我们不愿意拿枯燥无味的事来作消遣。我们不应该拿堕落的事来作消遣。我们也没有力量拿高贵的娱乐来作消遣。(例如打高尔夫球应该是很好的消遣,但它需要一套球具,一片大草原。有几个人够这种资格呢?)有了理想的消遣,人们疲惫的精神可藉以寄托,空暇的时间可藉以消磨。好消遣代替了恶劣的消遣,挽救了人们的堕落,减少了社会的罪恶。所以理想的消遣,是我们所需要的,也是值得提倡的。 合于上述条件的消遣很多,如:琴,棋,书,画,骑马,射猎,游公园,荡马路,用牙牌打一回五开,随胡琴唱几句京戏,或伴三二知友品茗清淡,或手持一卷静读心爱的文字,……以上种种,只要能配合你的个性,只要时地的环境相宜,都是很正当的消遣。可惜,也许是因为世风不古,也许是人性近恶吧,社会中实行消遣的人虽多,但爱好正当消遣的,却实在有限。这确是一件遗憾的事。 本书以后各节,介绍一些消遣的新方法,也可以说是新游戏。它能增益智慧,消磨时间,使急躁的人心平气和,使粗糙的人心思细密。一个人不必找对手,可以随时随地独自消遣。如有三五同好,就可比赛成绩,更能增加兴趣。所以这是非常理想的合于科学的消遣。有人嫌这科学消遣太“伤脑筋”了,他被这句流行的俗语所误了,同时他也误解了消遣的真义。“伤”字的意思是“损害”。但“伤脑筋”并非是损害脑筋,而是“费事”,“烦恼”的代名辞。譬如处理政治上与家庭里的纠纷,通货膨胀时代设法保存币值,买户口米或其他配给物品,等等;都是很“伤脑筋”的。这些事毫无趣味而又要不得应付,所以“伤脑筋”的人是很痛苦的。 “用脑筋”或”费脑筋”与“伤脑筋”不同。在学校里学习国,算,英文,声,光,化,电,那一样不用脑筋?用了脑筋,学业才会进步。世界上的事,除了睡觉,那一样不用脑筋?不用脑筋,就容易受伤害受损失。只要用脑筋而不感到疲劳,那是有益的。还有一件事,太简单太容易了,那就太平庸了不能吸引人了。如说把一个鸡蛋放在桌子上,或是将8二等分了就得4,这谁不会?还有甚么意思?假如说把一个鸡蛋直立在桌子上,或是将8二等分了可以得3也可以得0,这就有点意思了。所以消遣的事情不能太容易太简单,当然必须要费点脑筋,假如你消遣了相当时间,用了不少脑筋,居然参透了一个曲折有趣的问题,或是达成了某一种不容易得到的游戏目标,这时你一定会快乐,满足,像大考得到一百分或赛跑得到第一名一样。假如消遣的题目稍难,或是时间不充分,或是脑筋想错了路线,一时得不到结果,这也是于你无损,毫无关系,不必懊丧。古人有两句名言:“胜固欣然,败亦可喜”。这正是消遣者应有的态度。假如你玩了一会之后,觉得它太容易或是太难,觉得自己兴致减退或精神疲倦了,那么,你可以随时放手丢开,或是另换一种消遣再玩,没有任何拘束。总之,消遣是兴趣的,自由的,主动的,无关得失的,调剂脑筋,而决不不损害脑筋的。消遣与那些使人烦恼而又难于摆脱的“伤脑筋”的事相比,正好像天堂比地狱一样呢。 下文介绍一些科学消遣,希望能增强理想消遣的阵营,扩大爱好消遣的选择范围。倘若科学消遣能够削弱了恶劣消遣的恶势力,因而减少了社会里的罪恶,这不是很好的事吗? 参考文献 1. “华容道”玩具不是中国人发明的. http://weibo.com/p/1001603864949104458788 (2007,2015) 2. 陈丹阳,该说说华容道的事了. … 继续阅读

发表在 游戏, 读书 | 留下评论

《Push it. Sokoban edition.》

  本文地址:http://sokoban.ws/blog/?p=3326 两年半前写过博文介绍《Push The Box》/《Pushing Machine》这一有趣的推箱子变种。近日,发现此变种的一个新发展:《Push it. Sokoban edition.》。俄罗斯人开发的,有安卓和苹果版本。安卓版是2016年12月20日发布到Google Play上。开发者官网是:http://gruv-apps.com 相对于《Pushing Machine》,有两个变化:一是机械手臂可最多4个方向;二是箱子可区分颜色。游戏最大支持8×8大小关卡。

发表在 游戏 | 留下评论

烤香肠推箱子《Stephen’s Sausage Roll》

  本文地址:http://sokoban.ws/blog/?p=2429 很长时间没有写关于推箱子类游戏的博文,没想到这个月一写就写了四篇(含本篇)。发现“新”游戏的过程都是类似,就是睡前在手机上用“推箱子”等关键词在各种社交网络或软件商城上搜索、随意看看,居然每次都有些新发现。 这次发现的是Steam上的一个游戏《Stephen’s Sausage Roll》,新出才两三天。游戏的自我介绍很简单:a simple 3D puzzle game。我也有比较长一段时间没在Steam上买游戏了,Steam之前增加了支付宝作为支付手段,我还没有来得及尝试,这一方式就暂停了,还是只能用信用卡,但是能用人民币支付。而之前我在Steam上都是用美元信用卡支付的。购买后只玩了两关,还没有接触到3D的元素。 游戏主角只占据一个格子大小,但是前面拿着个叉子,于是占了两格,叉子可以转向。每根香肠都是1×2大小,沿着长的方向只能移动,而横向则只能翻动。关卡中有些特定位置是火炭,人不能踩上火炭,但是每条香肠正反两面四个单位都要恰好被火炭烤一次,才能过关。 这规则和网上常见的一类叫《翻木块》(又叫Bloxorz)的游戏有点相似。但是翻木块向任何方向都是翻动,没有平移滑动,感觉比较单调,变化不多。所以我从来也没有为翻木块游戏写一篇博文的打算。而烤香肠增加了一些变化后,规则还是非常单一,但是变化和趣味性都大大提高。 游戏用上下左右来控制人的移动和叉子的旋转。由于视角不能自主改变,所以上下左右的方向是固定的。 和上一篇博文介绍的堆雪人推箱子一样,这个烤香肠推箱子也是把每一关的小地图拼接成一个大地图世界。通过在大地图中的走动来选关,这也许能让游戏看上去没那么生硬,更像一个game,而不是一个puzzle。推箱子类益智游戏本来就是处于电子游戏(video game)和难题谜题(puzzle)之间。 最后,引用Steam上一位玩家deuteranopia的评论结束本文。他的评论有四大点,我觉得都比较中肯,只引用第一点如下: 1. This is a game for puzzle-game lovers. If you’re not into puzzle games, it isn’t going to thrill you. If you love puzzle … 继续阅读

发表在 游戏 | 留下评论

堆雪人推箱子《A good snowman is hard to build》

  本文地址:http://sokoban.ws/blog/?p=2405 这个堆雪人的游戏《A good snowman is hard to build》出来至少有一年的时间了,我最近才注意到。游戏在Steam在线游戏商城上有卖各种桌面操作系统版本,也有iOS和安卓上的手机版本。 堆雪人的游戏规则受到推箱子启发。这也证明了推箱子游戏的确受到许多人的喜爱,有些人还希望从中衍生出一些别具一格的游戏。推箱子持续地给游戏制作者提供创作素材,可见纯粹的2d推箱子游戏是经典中的经典。 回到堆雪人游戏的规则本身。游戏中推雪球堆雪人,大中小三个雪球可以堆成一个雪人。相对较小的球可以推到相对较大的上面。比较特别的是,两个雪球垒成一堆时,上面较小的雪球还可以被推到另一侧的空格。另外还有一个特别的地方是,空地分为雪地和非雪地,雪球通过雪地,大小会增加一个级别,即小球会变成中球,中球会变成大球,大球还是大球。推过一个雪球后,雪地就变成普通的空地了。因为有这两个规则,所以要安排好路径和腾挪,才能成功堆出雪人。一个关卡中可以有3n个雪球,堆出n个雪人为过关。 游戏规则可以设计出极难的关卡,但游戏开发者所设计的小关卡明显没有利用好规则的全部潜力。我看Steam上的评论大多认为关卡过于简单。对于常玩推箱子的朋友来说,通关可以说是易如反掌,基本没有难度。  

发表在 游戏 | 留下评论

三维空间的推箱子

  本文地址:http://sokoban.ws/blog/?p=2393 之前的博文中写过不少3d的推箱子游戏。这些游戏大多有两大特点:一是推箱子是游戏的其中一个元素,游戏中还有其它的元素;二是有重力,箱子在没有支撑的情况下会下落。 近日,我发现了一个与众不同的、比较纯粹的三维空间推箱子游戏叫《Sokoban 3d》,是巴西人制作的,同时有iOS和Android版本。但是Android版本和我手机设备不兼容,暂时安装不了。 说这个游戏纯粹,因为它的目标就是控制人(红色)把所有箱子(黄色)推到目标点(白色透明)。并且没有重力,如果玩家不控制移动人或者推动箱子,所有箱子和人都停在那里不动,就如悬浮在空中。 而且,这个游戏的操作性尚可,有的设计还挺不错。首先,可以随意切换视角,这对三维推箱子游戏来说必不可少。其次,用三种颜色来指示空间的三个方向。红箱子向三个方向射出这三种颜色的激光状细线,对应三组不同颜色虚拟键。这样,即便切换视角后,也不会迷失方向。  

发表在 游戏 | 留下评论