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

 

作者:杨超

本文地址: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 not solve hard search problems instantaneously by simply trying all the possible solutions at once.

这句话翻译过来就是:如果你想从我的博客中只学一样东西,那就是量子计算机无法通过同时尝试所有可能来求解困难的搜索问题。

这句话简直是针对本文开头的问题的完美回答。就算大规模的量子计算机制造出来了,NP完全问题也不可能有快速算法,更不用说比NP完全问题更难的推箱子(PSPACE完全问题)了。

第三,有和没有快速算法(efficient algorithm)的分界线在哪里呢?Scott Aaronson在NP-complete Problems and Physical Reality一文(发表在2005年ACM SIGACT News)中也有深刻独特的见解。除了量子计算,他还逐一考察了蛋白质计算等若干未来可能有物理实现的计算机模型。文章最后,他给出了如下的一条分界线:

基于图灵机提出的P问题类也许未能很好的刻画有快速算法问题全体。具有快速算法的问题应该更广泛些,包含整数分解和图同构等。这也许是一条深刻的物理规律。

 

 

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

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

 

本文地址: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) 413-417.

2. J. M. Robson, Combinatorial games with exponential space complete decision problems, Proc. Mathematical Foundations of Computer Science, Springer-Verlag, LNCS 176, 1984, pp. 498-506

3. M. Crasmaru and J. Tromp, Ladders are PSPACE-complete, Proc. 2nd Int. Conf. Computers and Games, Springer-Verlag, LNCS 2063, 2000, pp. 241-249

4. D. Wolfe, Go Endgames Are PSPACE-Hard, More Games of No Chances, MSRI Publications, Volume 42, 2002, pp. 125-136

 

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

推箱子是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]。

Culberson的证明方法是把LBA问题的实例转化为推箱子问题的实例。为此,他利用推箱子的规则设计了一些巧妙的局部关卡模块。这些模块限定了推箱子中的人为了过关,只能按照规定的路线走。把这些不同功能的模块拼接起来,通过人的行走路径,可以模拟图灵机(即自动机)的运行。这样任何一个LBA问题的实例就能转换为一个推箱子关卡。LBA问题的实例有肯定的回答当且仅当相应的推箱子关卡有解。

后来,在2005年前后,麻省理工大学的博士生Robert A. Hearn又给出了推箱子是PSPACE完全问题的另一种的证明方法[3,4]。Hearn先定义了一种抽象游戏NCL(Nondeterministic Constraint Logic,Hearn称之为一种计算模型)。通过把TQBF的每个实例转化为NCL的实例,Hearn证明了NCL问题也是PSPACE完全问题。Hearn定义的这个新问题NCL问题有一个好处就是,通过它来证明包括推箱子、滑块类在内的一些益智游戏是PSPACE完全问题,相对来说显得比较简单和清晰。

然后,Hearn把NCL的每个实例转化为推箱子的实例。在这个过程中,Hearn也是设计了一些具有不同功能的推箱子局部关卡模块。和Culberson的证明不同的是,Hearn的模块中,主要利用推箱子规则,使得一些箱子只能要么处于目标点,要么只能偏离目标点一格,这样完美地模拟了NCL游戏中的核心要素:0和1两种状态。并且,这种转化同样保证了NCL的实例有解当且仅当相应的推箱子实例(关卡)有解。

下图示意两种证明的总体思路的区别。

从实例的转化设计的细节上,Culberson主要利用人的行走路线模拟图灵机的运行。Hearn主要利用箱子的状态来模拟0、1两种状态,转化得到的关卡对人来说是“开放”的,可以随时访问任何一个箱子,不存在行走路径的限制。两者都用到了推箱子的某些特殊局部构造。

[参考文献]

1. Dorit Dor, Uri Zwick. SOKOBAN and other motion planning problems. Computational Geometry 13 (1999) 215-228 (submitted in 1996)

2. Joseph C. Culberson. Sokoban is PSPACE-complete. Technical Report TR 97-02 of Dept. of Computing Science, The University of Alberta. April 1997.

3. Robert A. Hearn, Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science 343 (2005) 72-96.

4. Robert A. Hearn, Games, Puzzles, and Computation. PhD Thesis of MIT. June 2006.

[修改说明]

2016年4月16日,增加对Hearn方法转换得到的关卡的特点描述。

 

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

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个国家或地区的访问数。

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

魔方吧推箱子比赛五周年

 

作者:杨超

本文地址: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论坛的一位版主“七夜”要的,七夜没好意思直接拒绝,便赞助了两期铭浩之魔方。后来鬼手魔方也有意赞助我们的比赛,从第三期起到第五十五期,期间除了第三十期庆祝魔方吧论坛开坛八周年由大烟头赞助了宝石魔方,鬼手连续赞助了四年多。

从第三十四期到第四十八期,荆先生非常慷慨地赞助了幸运话费奖一年半。

比较遗憾的是目前比赛暂时没有了赞助,若有企业有兴趣赞助,我们非常欢迎。

发表在 推箱子 | 留下评论

用深度优先搜索(DFS)确定图的割点

本文地址:http://sokoban.ws/blog/?p=1000

之前的博文《推箱子游戏的一个箱子推动路径搜索算法 (二)》介绍了图论中寻找割点的算法在推箱子路径搜索中的应用。但是对用DFS寻找割点的原理说得不够清楚明白,本文的目的是试图进一步阐明这个算法,并把示意图画的更漂亮一些。

用DFS遍历一个图的所有顶点时,按访问顺序依次标号为1到n,称之为DFS数。顶点v的DFS数记作D(v)。并得到一棵DFS树(黑色边),称DFS树的边为树边(tree edge),其余的边(红色边)称为回头边(back edge)。如下图,图的边都按搜索过程中向外的方向定向,得到一个有向图。树边都是从DFS数小的顶点指向大的,回头边都是从DFS数大的顶点指向小的。

 

根据上面由深度优先搜索得到的有向图中,可定义每个顶点的低位数(lowpoint):从该顶点出发,只用最多一条回头边,沿有向边能走到的顶点中DFS数最小值。顶点v的低位数记为L(v)。

低位数取值有两种情况:一是没用上回头边,则能走到的DFS数最小的的顶点就是该点自身,对应的路是一个顶点构成的平凡的路。此时L(v)=D(v)。二是用了回头边,则一定是最后一条边是回头边,走到一个DFS数更小的顶点。此时L(v)<=D(v)。

所以,一般地,总有L(v)<=D(v)。

有了这两个参数,就可以确定割点了:对根节点,即DFS数为1的顶点,其为割点当且仅当在DFS树中有两个或以上子节点;其余所有非根节点v是割点的充分必要条件是:v存在一个子节点u(在DFS树中的子节点)满足u的低位数大于等于v的DFS数,即L(u)>=D(v)。

下图标出的顶点的低位数(圈外数字,没标圈外数字的顶点低位数和DFS数相等),绿色顶点为割点。

注:若用 DFS的深度(depth)来替代上面算法中的DFS数,并用深度来计算低位数,则算法一样能有效地找出割点。

[参考文献]
1. Shimon Even, Graph Algorithms (2nd Edition). Cambridge University Press. 2012. p52-54

[文中的图使用http://draw.io制作]

发表在 数学, 算法 | 留下评论

推箱子游戏的一个箱子推动路径搜索算法 (二)

作者:杨超

本文地址:http://sokoban.ws/blog/?p=843

在博文《推箱子游戏的一个箱子推动路径搜索算法》中,我介绍了推箱子游戏如何用鼠标双击或拖放来进行推箱子操作。我知道的大概有十多个甚至二十多个推箱子软件都实现了这一功能。最近,anian告诉我,他通过用20603兄的《一箭十万》关卡测试了多个推箱子软件,发现《YSokoban》的速度最快,点击箱子,瞬间程序就给出了所有能被推到的格子的提示。而我编写的《SokoPlayer HTML5》则需要约2秒。经过和anian兄的讨论,我们改进了算法,大幅度提高的效率,使得《SokoPlayer HTML5》也能瞬间给出提示(约3毫秒)。下面简单介绍一下我们如何作出改进的。

在一个箱子推动路径搜索过程中,要反复判断人是否能从箱子的一侧自由移动(即不推动箱子情况下)到箱子的另一侧。这个不难判断,用简单的广度和深度优先搜索都能在线性时间内得到答案。但是箱子推动过程中,箱子位置在变化,要在不同的位置都作出判断。假设涉及到的格子有n个,每判断一次要O(n)时间,但箱子最多也可能出现在n个不同的格子,要做n次这样的判断,所以总的时间复杂度是O(n^2)。当关卡比较大时,如《一箭十万》是50×50的关卡,不算墙体,格子也上千,导致计算时间比较长。

后来,我们发现判断各种位置下人能否从箱子一侧自由移动到另一侧,可以用一个线性时间算法完成。这可以用图论里的割点(Cut Vertex)和块(Block)的理论和算法来帮助我们。举一个具体的例子来说明什么是割点和块。割点把关卡区域分割成不连通的小区域,称为块。下图关卡中,黄色格子为割点,共有10个块,分别用数字1到10标记。

我们若能把推箱子地图所对应的图中的割点和块全部标记出来,那么回答人能否从一侧移动到另一侧就很简单了。可以用这两步来判断:(1)先看箱子是否在一个 割点上。若不是割点,则人一定能从箱子一侧移动到任意的另一侧。若是割点,则还要进行第2步判断。(2)看该箱子这两侧的格子是否属于同一个块。若是,则 能移动。否则不行。

如上图中,若箱子在割点G6位置,人能从箱子左侧(F6)移动到上侧(G5),因为属于同一个块3号。但不能从左侧(F6)移动到右侧(H6)。又若箱子在H4位置,由于H4不是割点,人可以从一侧移动到任意的另一侧。

标记图的所有割点和块,有一个线性时间算法。这是一个基于深度优先搜索(Depth First Search)的算法。在深度优先搜索过程中,对每个结点记录两个参数。一个是结点的深度depth,另一个是结点的低位数(low point)。一个结点v的低位数是这样计算的,取下面三者的最小值:(a)v自身的深度,(b)v的所有邻点(DFS树中的父结点除外)的深度,(c)DFS树中v的所有子结点的低位数。

在实现中,通常用递归函数来进行深度优先搜索,于是计算低位数可以这样处理。每发现一个新结点v时,把低位数初始为该结点的深度(即a)。对v的每个邻点,若是父结点,不管;若是父结点以外的已访问结点,且若该结点的深度较当前的低位数小,重新赋值v的低位数为该结点的深度(即b);若是未访问结点,那么找到了一个子结点,于是递归调用搜索函数进行下一层搜索,返回时,若该子结点的低位数较小,则用它的更新v的低位数(即c)。

下面两幅图给出了一个例子,给出其DFS树(红色边),每个结点的深度和低位数。括号内为低位数,黄色结点为割点。

有了深度和低位数,如何判断割点和块呢?

对于割点,判断条件很简单,若结点v有某一个子结点的低位数大于等于v的深度,则v是割点。

搜索的根结点比较特殊,它是割点的条件是在DFS树中有至少两个子结点。

对于块的标记可以按如下方法实现。首先注意到割点同时属于多个块,其他点则恰属于一个块。在深度搜索过程中,每从一个子结点返回,并且由子结点判断出其父结点v是割点时,就意味着找到一个新的块了。此时,把v及其所有子孙都标记为同一个块。标记之后,在DFS树中,把v的所有子孙删掉,但保留v。这样v的子孙就不会被重复标记。而v是割点,还可能属于另外一个块。

以上文的图为例。2(2)是个割点,从子结点3(2)返回是能判断出来,同时能发现一个块。而从子结点3(3)返回时也发现2(2)是割点,于是2(2)在另外一个块中也被标记了。

[后两个图用LibreOffice Draw制作]

2013年12月22日补充:关于寻找割点算法,可参看用深度优先搜索(DFS)确定图的割点

发表在 推箱子, 算法 | 一条评论

判断推箱子关卡是否有解的多项式空间的算法

作者:杨超

本文地址:http://sokoban.ws/blog/?p=630

之前写过一篇博文介绍了一系列具有递归关系和指数长度答案的推箱子关卡。本文给出判断推箱子关卡是否有解的多项式空间的算法。这两篇博文结合起来,可以对计算复杂性理论里面的PSPACE问题的概念有比较直观的理解。推箱子游戏是一个非常好的PSPACE问题的例子。

一、P, NP和PSPACE

先定义推箱子问题。本文中说的推箱子问题,是指如下的一个判断性的问题:给出一个推箱子关卡,这个关卡是否有解?注意这里只判断是否有解,也就是说只要回答“是“或“否“,如果回答“是“,也不需要给出一个具体可行的lurd答案。

判断一个推箱子关卡是否有解,是一个PSPACE完全(PSPACE-complete)问题。PSPACE-complete问题是计算复杂性理论里面的一个术语。PSPACE-complete 所讨论的是推箱子问题的空间复杂度。简单地说,空间就可以理解为计算机的内存。我们假设一个推箱子关卡宽度为w,高度为h,则我们称这个推箱子关卡的大小为n=w*h。显然,一个关卡越大,我们用程序去计算关卡是否可解时,需要的内存就越多。PSPACE-complete 有两层意思。第一层意思是推箱子问题存在多项式空间的算法,也就是说存在一个算法A,这个算法对大小为n的推箱子关卡,最多使用$ n^k $(k是某一个与关卡无关的常数)的大小的内存就能回答出这个关卡是否可解。当然,所用的时间没有限定。第二层意思是推箱子问题是所有多项式空间可解的问题里面最难的一类。PSPACE表示所有多项式空间可解问题的全体,PSPACE-complete是PSPACE 的一个子集,是里面最难的那些问题的全体。这里“最难“是有严格的数学定义的,在此我们直观地认为从空间复杂度考虑最难就可以了。

计算复杂性理论的完整的理论体系建立于20世纪的70年代(1970年代)。而推箱子最早被证明是PSPACE-complete问题是在上世纪90年代末。就像我们前面解释的那样,证明推箱子问题是PSPACE-complete问题有两个要点。一是要说明推箱子是多项式空间可解的。二就是说明推箱子问题是多项式可空间可解问题里面最难的。其中第一点比较容易,本文的目的是给出一个判断推箱子关卡是否有解的多项式空间的算法。注意,这个算法只是理论上有意义,不适宜用来实际求解。在实践中,大多推箱子求解程序使用大量的内存,往往是随推箱子关卡大小呈指数增长。

在具体讨论算法之前,先说些题外话。前些年,媒体曾热炒过“庞加莱猜想”,这是Clay数学研究所(Clay Mathematics Institute)于2000年悬赏100万美元的七个尚未解决的数学问题之一,每个100万美元。其中“庞加莱猜想”最近已经被解决了。2010年,这个百万大奖授予俄罗斯数学家佩雷尔曼(Grigoriy Perelman)。但佩雷尔曼拒绝接受这个奖项和奖金。 在其他六个尚未解决的价值百万美元的问题中,有一个是属于理论计算机科学里面的问题,更具体地说是关于计算复杂性理论的问题:即 P vs NP问题。

我们用P来表示所有能用多项式时间(注意是时间,不是空间,区别于PSPACE)算法解决的判断问题全体。用NP表示所有所有能用“非确定性(Non-deterministic)”多项式时间算法的判断问题全体。可以证明,任何一个P问题都一定是NP问题,也就是说P是NP的子集。但是现在尚未确定的是,究竟P是NP的真子集,还是P=NP?这就是所谓的P vs NP问题,七个百万问题之一。

P和 NP都是从时间复杂度上考虑的,而PSPACE是从空间复杂度上考虑的。大家很自然会问,有没有NPSPACE问题?也就是说是否有“非确定性“多项式空间算法问题的全体呢?有的。但是作为著名的Savitch定理的一个推论,可以证明PSPACE=NPSPACE。即两者实际上是同一个集合,因此一般只提PSPACE。

Savitch定理是由Walter Savitch 于1970年证明的。我搜索了一下他的主页,发现他主页(http://cseweb.ucsd.edu/users/savitch/) 上照片似乎是在中国照的,大家可以去看看。这里提到Savitch定理的一个重要原因是下面介绍的算法是基于Savitch定理(参看[1])的证明设计的。


(图片来自Walter Savitch的个人主页)

可以证明,凡NP问题都是PSPACE问题,NP是PSPACE的子集。那么究竟NP是PSPACE的真子集,还是NP=PSPACE?这也是一个悬而未决的问题。多数数学家和理论计算机学家都倾向于认为P,NP和PSPACE三者,前一个都是后一个的真子集,也就是可用下图示意:

二、判断推箱子关卡是否有解的多项式空间的算法

下面开始讨论算法。

我们知道一个大小为n的关卡,实际有效的格子实际上是小于n的,但我们不妨设就是n。每个格子要么是箱子,要么是人,要么什么也没有,所以所能形成的不同的局面不会超过$ 3^n $种(事实上$ 3^n $高估了所有可能的局面数,但从数量级上是基本一致的),其中有一个局面是初始局面,有一个是目标局面。所以,如果一个关卡是可解的,一定在$ 3^n $步内解出来,如果$ 3^n $步内不可解,这个关卡就是不可解了。并且我们也知道存在关卡,其解法的步数和关卡大小n是成指数函数关系,在博文《一系列具有递归关系和指数长度答案的推箱子关卡》中已经给出了例子。

一种直观的想法是用深度优先搜索(Depth-First Search)去穷尽所有$ 3^n $步以内的解法。但是这种算法需要用到一个后入先出的队列,这个队列的长度在极端情况下有可能是n的指数函数,这就超出了只用到关于n的多项式大小的空间的限制,就不是一个多项式空间算法了。

于是我们考虑一个基于二分法的递归算法去解决这个问题。

定义Savitch算法如下(姑且称之为Savitch算法吧,因为它是基于Savitch定理的证明,但文献中我没有看到有这样提法的)。

Savitch(c1,c2,t)
输入:初始局面c1,目标局面c2, 步数 t  (初始局面和目标局面均为大小为n的关卡)
输出:若能在t步内由局面c1变换到局面c2,返回“是“,否则返回“否“

1,若t==1,能直接判断,返回“是“或者“否“。
        1.1若c1==c2,返回“是“
        1.2若c1!=c2,但能一步从c1变到c2,返回“是“
        1.3其他情况,返回“否“
2,若t>1执行下面步骤。
3,对每个所有可能的中间局面cm
        3.1递归调用 Savitch(c1,cm, [t/2])
        3.2递归调用Savitch(cm,c2, [t/2]),(若t为奇数时,3.2调用Savitch(cm,c2,[t/2]+1) )
        3.3若3.1和3.2均返回“是“,则直接返回“是“
4,若遍历了所有中间局面cm,3.3都没有返回,则返回“否“

对于一个大小为n的推箱子关卡,我们这样调用算法Savitch(c1,c2, $  3^n $),则返回值就是我们想要的答案。下面说明一下算法只用了多项式空间。

每一层迭代,我们需要分配新的内存空间给c1,c2,t和cm,所以用的的空间不超过4n。那么最多迭代多少次呢?每迭代一次,步长除以2,所以最多经过 $ \log_2 3^n = (\log_2 3) n $次迭代,步长小于1,直接返回。所以,任一时刻,算法所用到的空间不会超过 $ (\log_2 3) n \cdot 4 n = (4\log_2 3) n^2$,这是关于n的一个2次多项式。所以这是一个多项式空间算法。

注:算法第3步遍历所有中间局面cm时,可按照局面的某种自然的字典排序去遍历,几乎不需要额外空间。

【参考文献】

[1] Sipser, Michael (1997), “Section 8.1: Savitch’s Theorem”, Introduction to the Theory of Computation, PWS Publishing, pp. 279–281

写于2011年1月,2012年8月26日修改

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

一系列具有递归关系和指数长度答案的推箱子关卡

作者:杨超

本文地址:http://sokoban.ws/blog/?p=430

推箱子的其中一个很重要的魅力来源于推箱子求解问题在计算复杂性理论里是一个 PSPACE 完全问题。在这里不对什么是 PSPACE 完全问题作出解释,但是推箱子的一部分美妙之处可以认为正是来源于它的计算复杂度达到了 PSPACE 完全问题的级别。具体表现就是可以设计出很多不同模式的关卡,而且我们目前所涉及到的模式只是一小部分,还有很广阔的空间等待我们去探索。另外一个表现就是存在一系列具有指数长度答案(相对与关卡的大小)的关卡,这一类关卡就是推箱子关卡众多模式里面非常有趣的一类,也是本文要讨论的对象。

2009年6月8日,我曾在魔方吧论坛发贴子介绍了一类指数长度答案的关卡。无独有偶,约一个月后的2009年7月5日,Matrix67的一片博客文章也介绍了这一关卡。我的贴子和 Matrix67 的博文介绍的关卡都是基于2000年国外的一个关于推箱子问题的解答

对这个关卡的具体分析这里就不再重复了,简单的说它就是由一个个的“房间”构成,上图是三个房间的情况。要过关,最左侧一个房间要进入2次,但要进入左一房间1次,就要进入左二房间2次,所以左二房间一共要进入4次。同理,左三房间就要进入8次。一般的,若有n个房间的话,第n个要进入2^n次,于是答案长度便成指数增长了。

这个关卡设计巧妙,让人感受到推箱子的美。下面我们要介绍一个更美的更简洁紧凑,但同样也是具有指数长度的答案的系列关卡。

这个更漂亮的系列关卡也是在推箱子玩家里面流传了很长时间了,有很多变化形式,其中最经典的可能是如下图所示。

这是 Aymeric du Peloux 2001年设计的 Picokosmos 第17关。David Holland 在2002年曾分析过这个关卡。Dries De Clercq 在这个基础上作了名为 Fibo 系列的变形关卡。上图所示的经典形式不只是一个关卡,而是一系列关卡,关卡可以纵向任意伸长(同时箱子也增加),只要保持箱子总数是偶数个就行了(奇数的时候关卡无解)。若用n表示箱子的数目,随着n增大,答案步数以n的指数函数增长。

没有玩过这一关的朋友可以点击此链接在线玩。先提前警告,虽然只有8个箱子,要解出来不太容易。

我是2009年在魔方吧发了前面提到的贴子之后,才注意到这个关卡,当时没有看到 David Holland 的分析文章,独立地研究了这一系列关卡的步数。下一节将简要的介绍一下我的计算方法。

上一节提到,这一系列关卡只对偶数个箱子有解。为了便于建立递推关系,我对箱子位置作了以下微妙调整,使得对奇数也有效。主要有两处改动:一是最下方一个箱子连同目标移动了一格;二是最上方一侧的箱子移下一格(哪一侧由奇偶性确定)。如下面所示,分别是4到8个箱子的情形(注意本节的图和上一节的图左右反了)。

本关在线游戏链接

本关在线游戏链接

设 n 个箱子的上述关卡的最佳答案需要用 M(n) 步移动,P(n)步推动过关。可以得到下面的递推关系:

M(n)= M(n-1)+M(n-2)+n +12,      n 是奇数
M(n)= M(n-1)+M(n-2)+n+10,       n 是偶数

P(n)= P(n-1)+P(n-2)+8 .

要得到上面的递推关系,需要观察出这系列关卡的过关规律,下面以n=7 为奇数的时候推导以上公式。

首先观察到这样一个现象:过关时,箱子把关卡分割成左右两侧不相通的区域。以最佳答案过关时,人是停留在右侧区域,如下图所示的位置。

要想人最后留着左侧区域也是可以做到的,但是就是要多用2步移动,推动步数不变,最后位置如下。我们这里述而不证的这一观察到的结束位置的规律是必须亲自解过这一系列关卡才能有体会。如果你还没来得及解关,下面的递推关系就会彻底地揭示了求解的秘密了。

下面开始推导递推关系了。根据实践规律,当 n=7 个箱子时,前6步必须是 ldDDRU (6步移动,4步推动)。这6步之后,关卡变成下图。

————(1)

此时,若忽略最上面两个箱子,关卡实际上就是 n=5 个箱子的情形。利用 n=5 的时候的解法,可以走到下图的状态。

————(2)

从状态(1)到状态(2),基本相当于解一个 n=5 个箱子的关卡,但由于人最后是停在左侧区域,根据前面提到的观察规律,中间需要移动 M(5) + 2 步和推动 P(5) 步。

接下来的步骤必须是 uuuuurrDDLU (移动11步,推动4步)。一般地,则是移动 n+4 步,推动还是4步。经过这11步,得到状态(3)。

————(3)

从状态(3)开始,直到最后过关,相当于解一个 n=6 个箱子的关卡,因为最上方的箱子保持不动。所以余下共移动 M(6) 步,推动 P(6) 步。

经过上面以 n=7 为例的分析,我们得到奇数时的递推关系:

M(n)=6+M(n-2)+2+n+4+M(n-1)=M(n-1)+M(n-2)+n+12
P(n)=4+P(n-2)+4+P(n-1)=P(n-1)+P(n-2)+8.

偶数的时候原理一样,具体的推导过程在此就省略了。

有了递推公式,和 n=4,5 时最佳步数,我们很容易就可以计算出下面的通项公式。

M(n)=(-1)^(n+1)  + (9+sqrt(5)) * a^n + (9-sqrt(5)) * b^n – n -14 ,
P(n)=( (10+4*sqrt(5))/5 ) * a^n +  ( (10-4*sqrt(5))/5 ) * b^n  – 8,
其中 a=(1+sqrt(5))/2 , b=(1-sqrt(5))/2.

下面用 MathJax 显示一下上述两个通项公式。

$ M(n)=(-1)^{n+1} + (9+\sqrt{5})\cdot\Big({\frac{1+\sqrt{5}}{2}}\Big)^n + (9-\sqrt{5})\cdot\Big({\frac{1-\sqrt{5}}{2}}\Big)^n-n-14 $ ,

$ P(n)={\frac {10+4\sqrt{5}}{5} } \cdot \Big({\frac{1+\sqrt{5}}{2}}\Big)^n + {\frac {10-4\sqrt{5}}{5} }\cdot\Big({\frac{1-\sqrt{5}}{2}}\Big)^n-8 $ .

从通项公式中,我们可以看出,无论是移动还是推动,答案都是具有指数长度的。

常系数线性递推关系的求解是比较经典的数学理论了,中学数学竞赛常常有这方面的题目,在高等数学里亦有不少应用。这一系列关卡结构紧凑浑然天成,却又蕴含如此典型的递推关系,实在是令人意想不到,堪称常系数线性递推关系的求解最有趣的应用之一。

第四节7个箱子关卡的最佳答案(306移动,102推动),答案格式说明请参看xsb和lurd格式简介:

ldDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUrdrddLLUlldR
drUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuuuurrDDLUrdDDL
UrdrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuul
lDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRd
rUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulD

GIF动画演示答案(GIF动画用YSokoban,irfanview和gifsicle制作,可参看制作推箱子GIF动画教程):

还是这一关,人最后停止在左侧区域的答案(308移动,102推动),移动多了2步,最后十来步稍微有区别:

ldDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUrdrddLLUlldR
drUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuuuurrDDLUrdDDL
UrdrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuul
lDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRd
rUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluR

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

推箱子游戏的一个箱子推动路径搜索算法

作者:杨超

地址:http://sokoban.ws/blog/?p=298

推箱子自1981年诞生至今,已经超过30年了。推箱子软件的功能也有了很大的改进。从刚开始的只能用键盘一步一步的移动,到上世纪90年代后期起,用电脑辅助搜索一个箱子的推动路径,从而实现用鼠标两次点击(或是拖放)就能实现一个箱子的任意推动。可以说,电脑辅助路径搜索,已经成为推箱子软件的一个标准功能,使得人们从繁琐的逐步操作中解放出来,在更大一些的关卡中探寻更多的挑战和乐趣。

一个箱子的推动路径搜索并不是一个很难的算法,用最基本的广度优先搜索算法(Breadth-first search),就可以很快地找到一个推动数最少(但此时移动步数不一定最少)的路径。我2002年春写《Final Sokoban》第一次实现了这个算法,2004年写《M2 Sokoban》又实现了一次。这两次都是用C++或C在Windows平台下写的。2010年后写Java Applet《SokoPlayer》,用C写Linux下的《USokoban》和用Javascript写《SokoPlayer HTML5》,都实现过这个算法。下面简单说一下这个算法的要点。

首先,必须明确搜索的一个结点是什么。我们是考虑选中一个箱子后,不推其他箱子的前提下,把选中的箱子推到一个目的地。于是,在推动这个箱子的过程中,其他箱子可以视为墙体。又我们以推动一步为基本的单位来搜索,不以移动一步来搜索。所以搜索的一个结点由两个要素确定:一是箱子的位置,二是人相对于箱子的方向。这是因为箱子可以把人隔在关卡中不同的区域。

以下面这个简单的关卡为例:

(图一)

可以点击下面链接玩这一关。

http://sokoban.ws/sokoplayer/?w=4&h=9&lvl=HHHH|H__H|H__H|H__H|H__H|HH$H|_HaH|_H.H|_HHH

这一关的按广度优先搜索得到的树如下:

在上述搜索树中我们看到,结点a 和结点 f 的箱子位置是一样的,但是由于人的位置不同,所以是两个不同的结点。一般地,当前要推动的箱子最多把关卡隔为四个不同区域(即上下左右,在程序中可以用0,1,2,3或其他常数表示)。所以若关卡大小不超过n*n,则搜索总的结点不超过 4n*n 个。

广度优先搜索通常要用到一个先入先出(First-in first-out)的队列(Queue)来保存搜索过程中的结点。根据前面的分析,每个结点只需保存箱子位置和人相对于箱子的位置。如,结点a可记为[(C, 6) 下],其中(C, 6)是图一中箱子标尺坐标,“下”表示人相对于箱子的位置。这样,一个结点在搜索队列中用2到3个字节便可以保存。

其次,搜索过程中,结点可能重复出现,我们必须记住哪些结点前面已经访问过了,只把新的结点添加到搜索队列中。比如上面例子中,结点 e 箱子有向上和向下推两种可能。向上推得到新结点g;向下推得到的本质上是结点c,这个在前面已经出现,所以忽略不要。

幸好,我们已经分析过了,总结点不超过4n*n个,我们可以用一个4n*n个单元的数组来记录结点是否已经访问过。初始时,数组全为0,每遇到一个新结点,它在数组上对应的位置改为1,表示访问过了。于是,搜索中,我们每推一步得到一个结点,只需查看该数组的相应位置是0还是1,快速判断这个结点是否新结点。

比如,结点c我们可以记为[(C,4)下]。我们确认它是一个新结点加入队尾时,把[(C,4)下]对应的位置标记为1。注意,同时我们把[(C,4)左]和[(C,4)上]也标记为1,因为这三者本质上是同一个结点。在具体的算法实现上,我们检查一下人能否从箱子下方在不推动任何箱子的前提下,自由地移动到箱子的其他方向。

有了以上的分析,我们可以把总的算法描述如下(假设关卡不超过80 x 80):

(1)初始化准备:建立搜索队列q,把初始结点入队。用数组t[80][80][4] 来记录结点是否访问过,初始化为全为o,然后把数组t中与初始结点对应的位置和与之等价的位置标记为1。

(2) 主循环:根据队列是否为空,分别执行操作(2.1)或(2.2)

(2.1) 若队列非空,让队头结点出队。从此结点出发,分别尝试向上下左右推动箱子一格。(如:看是否能向左推动,就是看人能否自由的移动到箱子右侧一格,且箱子左侧一格为空) 若能推动,检查得到的结点是否新结点。

若是,加入搜索队列q的队尾。并在t中把这一新结点标记为1,同时把与之本质上一样的结点也标记为1。若同时还是目标结点,跳出循环,执行第(3)步。

若不是新结点,什么都不用做。

上下左右都尝试过后,回到第(2)继续。

(2.2)若队列为空,全部可能结点搜索完毕。到目标结点的路径不存在,返回。

(3) 路径找到。从目标结点出发,回溯 lurd 路径。为了回溯路径,在前面的搜索过程中,实际上还需要保存额外信息,如每个新结点的前继结点是哪个一个等等。

上面是需要返回目标结点的路径的算法流程。若不需要回溯路径,如只搜索哪些格子是能够推到的,算法只需作相应调整:不保存前继结点的信息,且第(2.1)步不跳出循环,直到队列为空算法停止,等等。

通过以上的算法分析,我们看到,箱子的路径搜索算法同时还要用到人自由移动的路径搜索的算法作为帮助函数来实现。

实践表明,因为问题本身的计算复杂度不高,即便是算法的具体实现不是特别好(如具体实现中,本可避免的大数组的复制操作太多),程序的表现也非常不错。比如,我用浏览器解释执行的 Javascript 语言编写的《SokoPlayer HTML5》,执行效率应该说比C之类的编译型语言差很多,但是对于80 x 50的超大型关卡,路径搜索也就是几秒的时间,绝大多数情况下是瞬间完成搜索。

发表在 推箱子, 编程 | 一条评论