分类目录归档:推箱子

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) … 继续阅读

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

推箱子是PSPACE完全问题

  本文地址:http://sokoban.ws/blog/?p=2254 作者:杨超 本文是两篇博文《 一系列具有递归关系和指数长度答案的推箱子关卡》 和《 判断推箱子关卡是否有解的多项式空间的算法》 的续篇。这三篇博文构成推箱子与PSPACE问题三部曲。 一、什么是PSPACE完全问题(PSPACE-complete problems) 前两篇文章已经提过,PSPACE问题指的是:相对于实例(instance)的大小,存在多项式空间算法的判断性问题(decision problem)。 而PSPACE完全问题是PSPACE问题中最困难的一类。即一个问题A能够被称为PSPACE完全问题,如果问题A满足:对任何其他的PSPACE问题B,都存在一个多项式时间的方法把B的实例转化成A的实例,使得这两个实例在这两个问题中有相同的答案(都是“是”或者都是“否”)。由此定义,只要能给出某个PSPACE完全问题的快速算法,那么这个算法就可以用来解决所有的PSPACE问题。 我们这里所说的推箱子问题(SOKOBAN),指的是给出一个推箱子关卡(即实例),如何判断这个关卡是否有解。 无论从实践到理论,都有证据表明推箱子是非常困难的。 实践中,我们举办了好几年的MF8推箱子网络比赛,尚未见到有人或者组织能够用计算机快速解出我们的比赛主关。 在计算复杂性理论中,推箱子问题也被证明是一个PSPACE完全问题。本文的目的就是简单介绍一下这些证明。要证明推箱子问题(或者其他问题)是PSPACE完全问题,要论证两个方面: 一是推箱子首先是PSPACE问题。因为存在很多问题,其难度甚至超出PSPACE的范围,我们需要说明推箱子没有超出这个范围。这一点的证明较为容易,已经在三部曲的第二篇文中说过了。 二是证明推箱子是PSPACE问题里面最难的。这又有两种常用的方法,第一种方法是按照定义,描述一种方案把任何一个PSPACE问题的实例转化为推箱子实例。第二种方法就是,描述一种方案,把某一个已经被证明的PSPACE完全问题的每个实例转化成推箱子的实例。 无论是用那种方法证明,其技术性都是比较高的,比较依赖于巧妙的构思。 二、PSPACE完全问题的例子 已经有许许多多的问题被证明是PSPACE完全问题。这些问题可以被用来证明其他问题也是PSPACE完全问题。这里介绍两个比较有代表性的。 第一个是TQBF问题(True Quantified Boolean Formula)。这个问题的一个实例就是一个每个变量都带有量词(存在、任意)的布尔逻辑公式。公式中的每个变量只能取值“真”或者“假”。 如:(任意x)(存在y)(存在z) ((x或者y)并且z) 我们需要判断这样的一个公式是否总是“真”的。 第二个是LBA问题,即线性空间自动机(Linear Bounded Automata)。这个问题的一个实例是:给出一个线性空间自动机和一个输入,该自动机是否接受该输入。 这个问题的PSPACE完全性证明非常简单。因此利用此问题证明推箱子问题是PSPACE完全问题,和直接用定义证明推箱子问题是PSPACE完全问题,几乎没有多大区别。 除此之外,推箱子和滑块类游戏也是PSPACE完全问题的有趣例子。 三、推箱子是PSPACE完全问题 Dorit Dor和Uri Zwick在1996年写文章[1]研究了推箱子问题的计算复杂度,但未能证明推箱子是PSPACE完全的。加拿大阿尔伯特大学的Joseph C. Culberson看到该文后,在1997年就证明了推箱子是PSPACE完全问题[2]。 … 继续阅读

发表在 推箱子, 数学 | 一条评论

仓库番在日本的发展史

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=2009 我曾在《推箱子软件简史》一文中总结过,推箱子在日本被发明出来并传遍世界后,推箱子在其发明国日本的发展则显得几乎停滞。最近(2015年9月25日)官方仓库番又出品新作Windows版《仓库番完美篇加A面》,在日本 vector.co.jp 网站提供网络下载并销售。据日本媒体报道,此款游戏有200关,其中153元来自经典的《仓库番完美篇》,另外47关是此前没有公布的关卡。 我第一时间购买测试后,发现从程序功能到关卡,的确都毫无新意。不过借此机会,对官方仓库番的发展做一个简单总结,作为《推箱子软件简史》的一个补充。 时期一:1982年-2000年 1982年《仓库番》诞生时,是个人计算机和家用游戏机产业刚开始发展的时候。而到了2000年,个人计算机已经被微软垄断,家用游戏机也渐渐稳定,性能也有了巨大的进步,互联网也开始普及了。 官方出品的《仓库番》有10个标准关,《仓库番2》有50关。 官方作品的顶峰是1989年的《仓库番完美篇》(Perfect)和1991年《仓库番复仇篇》(Revenge)。各有306关。 以上提到的4款游戏是Thinking Rabbit出品。1986年田中润司还出版了一本名为《The 仓库番》的书。 除此之外,就是守着那一点点知识产权和一成不变的老关卡,授权给其他软件公司移植到各个不同的电脑或者游戏机平台。今林宏行在sokoban.jp的致词中也是说二、三十年来授权移植出版的仓库番游戏很多(その後30年以上にも渡り、ライセンス契約も含め多くのハードウエアで「倉庫番」を移植することができました)。 如:Gameboy上的《Boxxle》和《Boxxle 2》。 超任上的《超级仓库番》(Super Sokoban)。 世嘉的MD上的《史上最大の倉庫番》。 索尼PS上的《倉庫番BASIC》、《倉庫番BASIC 2》、《究極の倉庫番》和《倉庫番 難問指南》。 一位资深日本仓库番玩家在其个人主页上也是如此评价《完美篇》:各機種に移植された総集編的なバージョン;和《复仇篇》:各機種に移植された総集編的なバージョンその2。即此两篇为关卡总集版本,各游戏主机和电脑移植版的关卡均出于此。由于此日本资深玩家接触和玩过大量版本(从他个人主页可以看出),所以他的话应该是可靠的。 时期二:2004-2007年 之后仓库番的商标权就归 Falcon 公司持有了。 据Falcon公司主页介绍,sokoban.jp 域名网站于2002年1月11日上线。(2002.01.11 倉庫番を独自ドメインに移しました。)今林宏行的《ごあいさつ》(致推箱子爱好者)也是于2003年出现在官网 sokoban.jp 这一时期为功能手机时期。Falcon大概和日本各大电信运营商(i-mode等)合作,出版了大量的手机版仓库番。具体商业模式如何不太清楚。 从游戏名大多带着パーフェクト(Perfect)和リベンジ(Revenge)可以断言,无非还是把那些老关卡拿出来炒冷饭。 2007年后手机从功能手机慢慢过度到智能手机,估计这个和电信运营商合作的模式也玩不下去了。 时期三:2015年-? 2015年,官网sokoban.jp上今林宏行的《致推箱子爱好者》一文做了微小改动。 并且开了官方推特(Twitter)账号,其中一条说:倉庫番の公式な製品は、2007年の携帯電話版を最後としてしばらく間隔があいてしまいましたが、現在ダウンロード専用のWindows(XP以降が対象)版を準備中です。 発売時期等は公式サイトでお知らせするほか、こちらでもツイートします。 即2007年以来已经很久没有发行过官方的《仓库番》了。 … 继续阅读

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

sokoban.cn 网站的访问者统计数据

  本文地址:http://sokoban.ws/blog/?p=1758 网站访问计数器对小网站来说是一个有趣的部件。在发现ClustrMaps提供免费的访问统计,并按访问者所在国家显示在世界地图中,便也在MF8推箱子比赛的网站sokoban.ws(后来增加了sokoban.cn域名)上添加了一个。 今年(2015年)3月底,ClustrMaps的4号服务器发生故障,丢失了少量数据。并且所有用户必须重新注册账号,计数和统计都从零开始。 虽然是采取免费的服务模式,他们还是定期备份数据,并且在故障发生后的一个月内整理出备份数据供用户存档。 下面便是从2012年9月6日至2015年3月16日这两年半的访问者数据。新计数器从2015年4月1日开始。 记录到113个国家或地区的访问数。

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

中国魔方俱乐部(MF8)十周年

  本文地址:http://sokoban.ws/blog/?p=1442 10月1日晚,参加了中国魔方俱乐部(MF8论坛)成立十周年的聚会,吃到了十周年蛋糕。 最早是2007年知道MF8论坛的。后来借MF8论坛这个平台,举办了MF8推箱子比赛。最近一年更是忙于跑步,渐渐地对魔方的关注也少了。这些年来,各种量产的非常规魔方越来越多,魔方竞速运动的开展也越来越广泛(2014年粗饼网上线),中国魔方俱乐部是这些发展的最早和最重要的一支力量。 这次聚会,非常有幸提前得到MF8的最新异形魔方产品--转棱魔方一个。还有香港SMAZ大师产的切半花瓣直升机魔方一个。 另,两年前2011年底,作为庆祝MF8成立八周年活动之一,荆先生还为第30期MF8推箱子比赛还专门设计了比赛关卡。  

发表在 推箱子, 魔方 | 留下评论

推箱子五年工作总结

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=1188 自从2009年4月魔方吧论坛开设推箱子版以来,我的业余生活有很大一部分被推箱子所占据,至今已经五年了。可以说推箱子成了我的一项业余“工作”。在2011年7月本站开设博客时,我在关于页面把推箱子工作归纳为三大部分: (1)举办大约每月一期的在线推箱子比赛; (2)提供本站开发的或获得授权的推箱子软件的下载或在线使用; (3)为推箱子爱好者提供一个交流的平台。 其中第一项工作在前一篇博文《魔方吧推箱子比赛五周年》已经专门总结过了。本文主要谈谈一下其他两项工作。很多朋友都为推广推箱子作了大量有益的工作,如stopheart写了不少优秀的推箱子教程。我这里主要是总结我或多或少参与到其中的部分工作。 一、推箱子软件 (1)和anian一起大力推广《歪推箱子》软件,制作了官方汉化和中文安装包,并编写中文使用说明。 (2)为安卓(Android)推箱子软件《推箱子加加》提供了官方中文翻译,并提供镜像下载。 (3)为风过了无痕的软件《睿斗推箱子》提供镜像下载。感谢风过了无痕编写了一个优秀的国产推箱子软件。 (4)编写了在线的推箱子程序《SokoPlayer HTML5》。 (5)和anian合作编写了一个推箱子关卡搜索工具《SokoFind》。 (6)写了一个开源的Linux推箱子软件《USokoban》和一个功能简单的python版推箱子sokoban.py,偶尔能为网站带来几个访问者。 二、推箱子交流平台 (1)改造魔方吧论坛的Discuz!程序,使得可以方便地在论坛中发关卡图片和Java Applet推箱子小程序。这主要是由anian的提议,并由站长cube_master实现的。其中Java Applet推箱子小程序是由我编写。 (2)建了推箱子QQ群,这主要是群主stopheart的功劳。 (3)占领了百度贴吧的推箱子吧,这主要是一品牛粪的功劳。 (4)购买了sokoban.org域名,并建立新网站,是一个分享关卡和提交答案的平台。 三、其他 (1)考究了推箱子的某些历史,写了博文。如XSokoban,大宇推箱子等。 (2)研究了推箱子程序中的一些算法问题,写了博文。如路径搜索中如何利用割点。    

发表在 推箱子 | 留下评论

魔方吧推箱子比赛五周年

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=1133 随着第57期MF8(魔方吧)推箱子比赛结束,我们这个在线的推箱子比赛足足举办了五周年。这是一件值得高兴的事情,借这个时机总结一下这五年中比赛的发展变化。比赛能够举办五年,主要原因我想是推箱子爱好者们在编关和解关中得到了乐趣。anian、stopheart、荆先生、20603、zhenying、西北天狼、laizhufu、zhouxh、风过了无痕、(捷克)Přemysl Zíka、shamying、tengxi、Many illusions等都为比赛贡献过关卡。参加比赛的朋友就更多无法一一列出了。每期一般少则十来人,多则近三十人提交答案。参赛者来自中国、德国、法国、西班牙、保加利亚、阿鲁巴、丹麦、巴西、比利时、美国、俄罗斯等十多个国家或地区。我对编关和解关参与得较少,主要负责比赛的后勤工作。关于编关解关中故事,有待其他朋友来讲述,在此我说说比赛是如何办起来的,以及这五年中比赛网站、形式和奖品等的变化。 一、比赛的由来 比赛是借助魔方吧论坛这个平台办起来的,所以叫MF8推箱子比赛。魔方这个上世纪80年代风靡一时的智力玩具在2006年后又开始变得越来越流行了。究其原因,很重要的一个是有个民间组织叫WCA(世界魔方协会World Cube Association)在全球各地举办了越来越多的魔方竞速比赛。在这股潮流下,我也弄到了以前比较少见的四阶五阶魔方,并且于2007年夏天在MF8论坛注册了账号,而我注册的账号是sokoban。到了2009年,也跟MF8论坛的站长cube_master混了个脸熟。 2009年4月初,可能是由于老封关掉了他的推箱子论坛,MF8站长cube_master在魔方吧论坛里开增设了一个推箱子版。我马上毛遂自荐担任了推箱子版版主。可能是看到魔方的各种竞速比赛举办得红红火火,我很自然地也想在新成立的推箱子版搞一个在线比赛。于是开版才几天,第一期的MF8推箱子比赛就仓促开始了。 最初提交答案的方式极为麻烦。参赛者把答案加密打包在论坛回复,并站内私信把密码发给我。我再人工验证答案。比赛以这种很原始的方式运行了一年多,才得到改进。 前几期的比赛关卡也是由我从现有关卡中选取或是由我随意编的,质量不高。幸运的是,anian很快就加入比赛关卡的编排组织工作中,之后stopheart、荆先生和更多的朋友都为比赛提供了精彩的关卡,保证了比赛关卡的质量。 二、比赛网站 比赛的第一年,提交答案的方式的确很繁琐,很不友好。到了2010年6月,我学习了一些简单的PHP网站编程后,便利用国外的免费虚拟主机 http://sokoutil.orgfree.com 建立一个简易的在线提交和验证答案系统,简化了答案提交的流程。 比赛网站建立不到半年,由于不可抗拒的原因,中国大陆无法直接访问。于是把比赛网站整体迁移到另一国外的免费虚拟主机 http://sokoban.zzl.org 。搬家才两个月,中国大陆又无法访问了。一气之下,我便从国内的互联网服务提供商租用了虚拟主机,把网站再次迁移,从国外搬到了国内的服务器。同时依照工信部的规定,于2011年初通过了备案,成为一个合法的网站。 为了使比赛网站看上去更像一个正式网站,2010年底,注册使用了域名 sokoban.ws。2012年5月后,中国互联网信息中心(CNNIC)重新开放个人注册.cn域名,同年11月,我们又成功注册了 sokoban.cn 域名。 下面贴几个不同时期的比赛网站截图: 2010年10月 2011年11月 2012年4月 2014年3月(手机版截图) 三、比赛形式 我们一直希望吸引到更多的朋友参加到比赛中来,为此比赛形式做过一些调整。 第三十一期设立的围观答案,参赛者可以提交n-1个箱子归位的答案。到了四十三期,取消了围观答案,取而代之的是每期设立一主一副两个关卡。副关较为容易,降低参赛的门槛。事实上我们的比赛一直是完全公开的,不设任何门槛,参赛者甚至不需要在比赛网站注册账号,就可以参赛。 四、比赛奖品 我们的比赛虽然开始得比较仓促,但从第一期起就提供了奖品。 头两期的奖品是我厚着脸皮向MF8论坛的一位版主“七夜”要的,七夜没好意思直接拒绝,便赞助了两期铭浩之魔方。后来鬼手魔方也有意赞助我们的比赛,从第三期起到第五十五期,期间除了第三十期庆祝魔方吧论坛开坛八周年由大烟头赞助了宝石魔方,鬼手连续赞助了四年多。 从第三十四期到第四十八期,荆先生非常慷慨地赞助了幸运话费奖一年半。 比较遗憾的是目前比赛暂时没有了赞助,若有企业有兴趣赞助,我们非常欢迎。

发表在 推箱子 | 留下评论