分类目录归档:推箱子

量子计算机能快速求解推箱子关卡吗?

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3757 量子计算机常被大众媒体描述得十分神奇,甚至有科学家也添油加醋,如 David Deutsch 的 The Fabric of Reality 一书。用量子计算机能设计出快速求解推箱子关卡的算法吗?我在读了David Deutsch的书后,对此问题颇感兴趣。这个月,阅读了不少相关文献,找到了答案。答案是否定的。 首先,制造出通用的量子计算机仍然有极大的工程技术困难。 第二,再看看理论上,量子算法能干什么。最有名的量子算法就是Peter Shor的整数分解算法,这一算法使得基于大数分解比较困难的公钥加密算法岌岌可危。Shor的算法是1994年提出(Shor因此获得哥德尔奖Godel Prize),历史也没有太长。想要知道这一算法与传统计算机算法有何不同,可读Scott Aaronson的博文 《Shor, I’ll do it》。Scott Aaronson生于1981年,才36岁,是德州大学奥斯汀分校的教授,在理论计算机科学特别是计算复杂度理论方面有非常高的造诣。他博文中对Shor算法的核心解释得深入浅出。关键是整数分解还是有某种规律,量子算法恰恰能更好地利用这一规律,一定程度上避免了暴力穷举。 要注意的是,整数分解并非特别难的问题。在基于传统计算机(图灵机)的计算复杂度理论中,整数分解被认为不属于P,但也只是比P问题略难一些,介于P和NP-Complete之间,且更靠近P。因此,量子算法能快速分解大数也只是情理之中。 知道量子算法是怎么做的,能做什么,就更好地理解量子算法不能做什么。Scott Aaronson博客的站名banner位置有这么一段话,澄清大众对量子计算的误解: If you take just one piece of information from this blog: Quantum computers would … 继续阅读

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

庆祝推箱子比赛第一百期

  本文地址:http://sokoban.ws/blog/?p=3720 我们的推箱子比赛举办了第100期,可喜可贺。为此,anian特别邀请20603设计了主关,副关也是丹麦DrFogh为100期特别设计的。 除此之外,anian还另外特别设计了《百花齐放》关卡。关卡发到sokoban.org, 长期有效,欢迎大家提交答案。这个关卡代表了一种特殊的类型,就是用推箱子来模拟另外一个orimaze的游戏,且模拟得相当紧凑。 我又邀请了青年漫画家小矛为100期画了新的墙纸。小矛在2012年也为我们设计过一张墙纸。两张墙纸都可以在这里下载。

发表在 推箱子 | 留下评论

写在推箱子比赛第一百期之际

  本文地址:http://sokoban.ws/blog/?p=3627 作者:杨超 接触推箱子这个游戏已经近20年,发起在线推箱子比赛至今已8年有余。比赛每月一期,现在正进行第100期。由于这个比赛,使得我业余持续地关注推箱子游戏,并且推箱子游戏也持续地给我带来很大的乐趣。趁着第一百期之际,谈谈推箱子是什么,以及推箱子给我所带来的精神上的快乐。 一、推箱子是什么? 推箱子是一种成本极其低的智力消遣活动。早在推箱子出现之前,姜长英在1949年《论消遣》一文就分析过平民化的科学消遣的好处。最近看到《三联生活周刊》特约作者“土摩托”袁越在新浪微博问答中也表达了类似的观点:“……精神追求的成本越来越低了……我觉得这才是人类的未来,因为这是一种低成本满足所有人的唯一方式……”。 所以,以推箱子为爱好的朋友是非常幸福的,这玩意几乎不需要花钱。因为推箱子是一款纯软件产品。只要一个计算机系统足够开放和普遍,它上面一定会出现优秀且免费的推箱子软件,如Windows系统,如安卓系统。即便比较封闭的系统,如掌上游戏机、电子词典、电视机、机顶盒等等,都会出现推箱子。 我们举办网上的推箱子比赛的服务器成本也相当低。两个域名(sokoban.cn 和 sokoban.ws)加上租用服务器虚拟空间,平均每个月只要约28元,只相当吃一顿快餐。这么低的成本就可以把分散在全国乃至全世界各地的顶尖推箱子爱好者聚在一起,举办全世界水平最高的推箱子比赛,可算奇迹了。 这主要还是得益于电子计算机和互联网的快速发展。就最近来说,触屏式的智能手机只用了不到十年,就发展得非常成熟了,几乎取代了台式电脑,成为人们上网的主要设备。就我自己而言,微信等APP已经成为我获取信息的最重要渠道之一。很多跑步活动的信息我都是最先从微信获得,甚至就在微信中完成报名的。 因此,2014年7月,比赛网站也开通了微信订阅号,主要推送比赛开始等相关信息。继《推箱子加加》之后,愉翁又为安卓平台发布了《推箱快手》这款功能强大的APP。而苹果手机因系统较为封闭,虽是智能手机的引领者,却一直未见优秀的推箱子软件出现在该平台。 二、推箱子给我带来的快乐 下面罗列一些在推箱子中得到的快乐,其中很多事情做成了之后当时能高兴好几天。 为了测试各种平台下的推箱子,尝试了不同的操作系统。特别是编译运行了早期Linux平台下的XSokoban。为此至少连续使用了三年Linux的一个发行版Ubuntu作为平时工作生活的主要桌面系统。近三四年又以苹果的macOS X为主要的工作系统,因此对三大桌面系统Windows, macOS, Linux都算是比较熟悉了。甚至连PC-BSD, Solaris等非主流系统都安装试运行过几次。有了在不同的操作系统下的使用经验,对什么是操作系统的理解,比以前只会使用Windows时有了更深的认识。最近anian又告知有一款相当不错的Linux下KDE桌面的推箱子Sokoban SG,尚没有时间和精力测试。 学习并使用了多种编程语言。使用得比较多的语言是C、JavaScript、PHP。比较满意且花的功夫比较多的是用C编写的USokoban,用JavaScript编写的HTML5浏览器平台下的SokoPlayer HTML5,以及用服务器端编程语言PHP编写的比赛网站sokoban.cn以及关卡分享平台sokoban.org等。其它还尝试过写Firefox浏览器插件,用Python也写了一个简单的推箱子等等。后来因跑步和小孩出生,没有太多业余时间写程序了,但有些程序至今还时不时需要维护,如在第99期比赛时,还修正了比赛网站的一个bug:对副关的答案没有做“至少一推”的检验。 学习使用LAMP技术建设网站。LAMP是比较成熟的开源建站技术,租用服务器建站成本和技术难度都不算高。但是工信部对个人建立网站的管理时紧时松,为了比赛顺利进行,我还是在2011年初按工信部规定为比赛网站备了案。一开始只注册了sokoban.ws这个差强人意的域名,后来又注册到sokoban.cn和sokoban.org两个域名真是喜出望外。对整个互联网是如何运转的也有了些更深的认识。 琢磨了一些推箱子相关的算法。写USokoban时,实现了一个简单的解关器,掌握了解关器的一些基本算法。后来为了优化SokoPlayer HTML5推一个箱子的提示和寻径,想到了运用图论中找割点的算法,大大提高了计算的速度。 研究了推箱子及其变种的计算复杂度。计算了一系列具有指数长度答案的关卡所需要的精确步数。搞明白了推箱子问题的计算复杂度为什么是PSPACE完全的,还证明了推箱子的一个新变种也是PSPACE完全的,发表在学术期刊Theoretical Computer Science上面。 此外,关于推箱子的编关和解关,我几乎没有太多研究,还有许多宝藏有待今后挖掘。可见,推箱子是可以作为一生的爱好,不断地给人带来欢乐。  

发表在 推箱子, 数学, 算法, 编程, 计算机 | 留下评论

智能电视上运行《SokoPlayer HTML5》

    本文地址:http://sokoban.ws/blog/?p=3690 昨天,在海信智能电视上安装了第三方APP,测试了安卓版《推箱子加加》。今天,2017年6月21日,进一步测试在安卓电视上安装网页浏览器。我国的有线电视生态比较特殊。之前虽然没有电视,也从新闻中隐约知道,广电总局多次打压网络机顶盒。如在2015年,广电总局发布《关于依法严厉打击非法电视网络接收设备违法犯罪活动的通知》,禁止网络机顶盒提供视频聚合类APP或硬件服务(必须有全国牌照才行,如华数、上海文广、CIBN等。我的海信电视也是通过华数提供的牌照,提供预安装的视频聚集点播服务)。于是我对智能电视系统的封闭程度如何,能否随意安装第三方APP等不是特别乐观。经过一番网络搜索调研,发现《电视家浏览器》看上去还不错。于是,便和昨天一样,通过u盘和ES文件管理器,成功安装《电视家浏览器》,访问了比赛网站 http://sokoban.cn ,并运行了《SokoPlayer HTML5》,通过遥控器上下左右控制光标,可以完美地进行游戏。下面是一些图片。 注:发现最近对比赛网站首页微调后,在 Windows 10的默认浏览器Microsoft Edge中,右侧微信和QQ二维码和中栏有覆盖重叠。没想到在这个安卓TV版《电视家浏览器》中有同样的问题。在Firefox中则显示正常。此问题有待修正。(补充:2017年7月8日,修正了这个bug,把第二栏和第三栏交换)

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

智能电视上的推箱子

  本文地址:http://sokoban.ws/blog/?p=3659 因长期住了10多年学生宿舍和近10年的单位周转房,我很少使用过电视。2011年前后,利用出差的机会在宾馆里拍摄过几种有线电视机顶盒上的推箱子。那时的机顶盒可能都是用Linux加上中间件开发的。从那以后,电视也经历了高清化和智能化的发展,变化不少。如今年我在珠海看到的广东广电网络的上一代的“U互动”机顶盒就是采取较老的“Linux+中间件”技术(操作系统叫Hisi),支持直播、7天回放、点播三大功能。 由于智能手机安卓系统的发展,现在的智能电视和智能机顶盒基本上都是基于安卓系统开发,于是可以安装第三方软件。今年自己买的房子终于装修好了,买了电视,有机会尝试一下了。电视机买的是海信的50寸。有了电视后,先是报装了珠江数码的“甜果电视”,还附带宽带服务。电视信号是通过同轴电缆入户,接入一个调解器,再从调节器网线接入机顶盒,最后才从机顶盒通过HDMI接入电视机。从这接线看,本质上是IPTV技术提供的有线电视服务。接着又报装了电信宽带,赠送广东IPTV。电信宽带是光纤入户,接入光猫。光猫引出一根网线接入电信IPTV机顶盒,再通过HDMI接入电视机。于是我有了两个独立的电视信号和两个独立宽带。珠江数码甜果电视的信号是1080i,电信的IPTV信号是720p。 刚买了电视不久,我就从海信电视内置的“聚好用”里安装了ES文件管理器和《雪人难堆》这个推箱子的变种游戏。2017年6月20日,我把《推箱子加加》和《推箱快手》的apk文件拷入u盘,插入电视机,然后通过ES文件管理器从u盘安装,两个都能安装。可能电视的安卓版本比较老,只有《推箱子加加》能够正常运行,我用遥控器过了一关。 电视能否成为适合玩推箱子的一个平台呢? 今后值得尝试的事情:在电视上安装一个互联网浏览器。有线电视和电信的机顶盒虽然功能不少,总感觉局限太大,能否像电视机那样安装第三方APP?还可以尝试下互联网公司的网络机顶盒。    

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

《堆雪人推箱子》是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(图灵机)等术语对我如同天书。 … 继续阅读

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

parse.com 云数据存储服务关闭

  本文地址:http://sokoban.ws/blog/?p=3344 我编写的《SokoPlayer HTML5》在线推箱子程序于2013年7月提供了云数据存储功能,可以方便地跨设备保持和读取关卡和答案等。这一功能是由第三方parse.com提供的免费服务,数据也是存储在parse.com的服务器上(而不是存储在sokoban.cn)。 可惜这一商业模式未能生存下来,parse.com于2017年1月30日起正式永久关闭了。所以《SokoPlayer HTML5》的云存储功能也失效了,其余功能正常。

发表在 其他, 推箱子 | 留下评论

Kindle Paperwhite 上运行 SokoPlayer HTML5

  本文地址:http://sokoban.ws/blog/?p=2946 亚马逊的电子阅读器Kindle Paperwhite的显示屏使用的是一种电子墨水技术,和液晶显示屏相比,有不少的优点,但也有一个缺点是刷新慢,不适合玩游戏。即便如此,Kindle Paperwhite (Kindle 系列第七代)的系统也配备了一个具有完整功能,甚至支持HTML5的浏览器。我编写的网页推箱子程序 SokoPlayer HTML5 亦可在上面运行。

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

推箱子解关器算法(一):PI密室的故事
[ Sokoban Solver Algorithm (1) - A Story of PI-Corral ]

  本文链接:http://sokoban.ws/blog/?p=2570   作者:杨超  (by Yang Chao) 我曾在开源软件USokoban上实现一个简单的推箱子解关器,对其算法有一定了解,但不是太深入。最近发生了一件关于推箱子解关算法的论文剽窃事件,所以我也借此机会写写推箱子解关器算法。 I have implemented a simple solver in my open-source project USokoban,  so I have some basic understanding of Sokoban solver algorithm, but I am no expert on this topic. Recently, an idea … 继续阅读

发表在 推箱子, 算法, 编程 | 留下评论

围棋、推箱子和计算复杂度

  本文地址:http://sokoban.ws/blog/?p=2330 作者:杨超 这个月,2016年3月,Google 的 DeepMind 团队开发的围棋程序 AlphaGo 在韩国首都以 4:1 战胜世界冠军围棋九段李世石。早在近20年前,IBM 的国际象棋程序“深蓝”就已经战胜人类冠军。而围棋棋盘比较大,人们普遍认为人类对计算机程序的优势在围棋项目还可以保持比较长的时间。而这次 Google 团队的胜利,证明了其实开发一个战胜人类的下围棋程序并没有那么难,而是开发这样的程序没有太大的直接收益,哪怕是国际象棋和围棋这样就有悠久历史传统和广泛的群众基础和关注度的棋类。 围棋究竟有多难?我们拿它和推箱子来比较一下。恰好我刚刚完成了用三篇博文来介绍推箱子问题的计算复杂度:推箱子是PSPACE完全问题。 为了从计算复杂度方面和推箱子问题比较,我们需要准确地定义一下什么叫围棋问题。 虽然人们常说围棋的变化很多,但是无论变化有多少,终究是一个有限的数。所有有限步内能分出胜负的、没有隐藏信息、也没有运气成分的二人棋类游戏,一定有一方有必胜策略(或者必和策略)。打个比分说,19路围棋按照中国的贴目规则也许是先手有必胜策略。那么我们所说的围棋问题,就是对于任意的n x n棋盘上下的围棋,如何设计一个算法来确定究竟是先手必胜还是后手必胜?或者等价地说,先手究竟有没有必胜策略?(即这是一个回答“是”或者“否”的问题)通常的19路棋盘围棋是围棋问题的一个实例。要回答这个问题,除了穷举所有的对弈变化之外,人们暂时还没能找到其它规律来判断谁有必胜策略。对围棋而言,穷举所需要的时间随着棋盘 n 的增大,是成指数增长的。事实上,已经有文献证明,按日本规则,围棋问题是EXPTIME完全问题(见[1,2],该文章作者猜测,若按中国规则,围棋问题可能更难,成为指数空间完全问题)。也就是说,在指数时间可解的问题里面,围棋问题是最困难的其中一个。除了围棋,其它一些棋类问题如国际象棋、西洋跳棋(checkers)都被证明是EXPTIME完全问题。其中8×8棋盘的西洋跳棋在使用计算机花了近20年的穷举计算后,在2007年被证明双方都采取完美策略一定是和棋。 所以,从计算复杂度来看,包括围棋在内的许多棋类游戏比推箱子要难一个层次。计算复杂度的几个概念(EXPTIME、PSPACE、NP、P)的关系可用下图表示。虽然还没有从理论上严格证明,但是一般认为,从内到外,这四类问题的计算复杂度是严格地越来越难。 更有甚者,围棋问题的一些子问题,如征子能否成功问题在文献中被证明是PSPACE完全问题[3]。而围棋残局收官问题,则是PSPACE难的[4]。也就是说围棋问题的某些子问题就已经和推箱子问题一样难了。 那么,为什么比推箱子更难的围棋都已经开发出能战胜人类的程序,但是比围棋还容易一些的推箱子,我们却没有看到优秀的推箱子求解程序能够解出较大的、箱子数目较多的关卡呢?我想主要有以下这么一些因素。 首先,开发推箱子求解程序比开发下围棋程序更加无利可图。目前看到的一些求解程序基本都是个人单打独斗编写的,运行在个人电脑上,而且都是作为业余兴趣进行的。尚未看到有软件类企业或者研究团队投入较大资源来开发。作为对比,Google的AlphaGo程序投入了至少20人的开发团队,和李世石对战时动用了上千个CPU和GPU同时计算。 其次,AlphaGo虽然战胜了人类,但是并没有回答我们前面所定义的围棋问题,也就是说并不知道是否先手必胜。战胜人类并不需要穷遍所有变化,比判断19路围棋谁有必胜策略稍微容易一些。而一个推箱子关卡求解程序从某种意义上必须回答出推箱子问题,一般来说,必须穷遍所有路经才能判断一个关卡无解。而找到一个答案,除了穷举剪枝之外也还没有见到有人提出新的算法思路。 比较令人好奇的是,如果投入更多的人力和计算机运算资源,计算机求解推箱子能达到一个什么样的水平呢?能解出多大的关卡?解大关卡能比人解得更快吗? 第83期推箱子比赛,我们也借着这个机会,由麦英兄设计了一关AlphaGo关卡。这一关计算机能解出来吗? [参考文献] 1.  J. M. Robson, The complexity of Go, Proc. IFIP (1983) … 继续阅读

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