推箱子解关器算法(一):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 in reducing the search space for Sokoban solver, which was first developed by Matthias Meger, the author of JSoko, and Brian Damgaard, the author of YASC, was stolen by an academic research paper. I would like to tell the story, and to talk about the idea that has been stolen, PI-corral, in this blog article.

一、解关器的基本算法

我曾向YASC的作者Brian请教过,他告诉我解关器算法的两大基本要素。有了这两大要素,就有了解关器算法的大框架。当然要提高算法效率,仍然需要结合许许多多的其他算法思想。

第一大要素,A*搜索算法,选取一个合适的启发函数(heuristic function)。Brian告诉我,对一个简单的解关器,启发函数可以如下计算:先计算初始状态下,每个格子在其他箱子都没有的情况下,如果这个格子上有一个箱子,那么这个箱子被推到目标点(只要推到目标点就行,不考虑目标点匹配问题)所需要的最少推动数目。

这个数目可以预先计算一遍,并保存。即每个格子有一个最小推动数。

任何一个中间状态S,其启发函数f(S)等于两部分数值相加,f(S)=g(S)+h(S)。g(S)是走到当前状态S已经用的推动数;h(S)是当前状态S的全部箱子所在格子的最小推动数之和。

在搜索过程中,总是优先考虑启发函数最小的新状态。按这个启发函数搜索,得到的答案一定是推动步数最少的。

第二大要素,Zobrist 散列函数(Zobrist hashing function)。

因为推箱子状态数目呈指数增长,所以如何快速判断一个状态是否已访问过是一个重要问题。散列函数是解决这类问题常用方法。而Zobrist散列函数是针对棋类游戏棋盘状态提出的一种方案,这种方法也适用于推箱子。

这两大要素都是算法实践中经典及具有普遍性的方法。

在此基础上,改进的手段很多,如:双向A*算法,利用死锁剪枝,等等。

二、PI密室

“PI密室”是Matthias Meger首先提出的一种算法思想,并于2005年通过电子邮件和Brian Damgaard交流,Brian也对此算法做了一些延伸,使之可以在更多的关卡构型可以应用。这个算法思想在YASS和JSoko都实现了。

几年后,Brian才在推箱子维基中详细描述了这个算法(见[1])。算法涉及关卡中某种特殊关卡构型,Brian在这篇网文中,首次给这类构型起了个正式的名字,称之为PI-corral,我这里意译为“PI密室”。

后来,捷克的Pavel Klavik  [2 ] 和芬兰Timo Virkkala [3] 都引述过Matthias和Brian的算法。

以下密室、I密室、PI密室的概念均来自于Brian的 [1] 文。

一个密室(Corral)指的是在如果不推动箱子,人无法到达的区域,包含区域边界的箱子。如下图:

一个I密室(I-Corral)指的是一个密室,并且人如果要进入密室,第一步只能把边界的箱子向密室里面推。如:

上图同时也叫PI密室(PI-Corral),即在I密室的基础上,还满足边界箱子的推动没有被密室以外的其他箱子挡住,可以直接推动。一个是I密室但是不是PI密室的例子如下:

在解关器的搜索过程中,如果某个中间关卡状态的局部存在PI密室,且由于密室边界箱子还不在目标位置等原因,可以判断密室边界的箱子必须要推动,才能过关。这个时候,搜索程序可以优先考虑先搜索密室边界的箱子推动步骤,避免以后每个状态依然保留这个选择。简而言之,就是把必推的箱子先推了,能大幅度减少搜索树的分叉数目。

2015年,四个巴西人在一篇关于推箱子的解关器的会议论文中,也引述了PI密室算法思想。他们四人在论文中一方面介绍了Matthias和Brian的PI密室的工作,介绍了I密室和PI密室等概念;另一方面却没有搞明白I密室和PI密室的含义,甚至认为Brian把PI密室的概念搞错了,声称他们才是PI密室思想的真正发现者。

对于这种学术不端行为,Brian当然十分不满。他写信向四个巴西人所在的大学申诉,并且把邮件转发到Yahoo推箱子群 [5]。这一申诉有何结果,我们还要拭目以待。

Brian指出,作为一篇学术论文,四位巴西人的文章 [4] 只在参考文献中列出YASC和JSoko两个开源项目在sourceforge上的地址,却没有列出Brian对这一算法的详细阐述,Sokoban Wiki(推箱子维基)上的 [1] 文。YASC和JSoko虽然都实现了这一算法,但是因为时间上在[1]文之前,项目中包括程序的注释都没有对算法的完整论述,更没有出现过“PI密室”一词。四个巴西人的论文使用了“PI密室” (PI-corral) 一词,可见他们是从项目主页以外的其他地方看到过Brian等对PI-corral的阐述。但是四人在论文中却有意隐瞒,试图把PI-corral的发现占为己有,这种学术欺骗的行为十分恶劣。

我对学术界随处可见的制造低水平的垃圾文章的现象也不陌生。推箱子求解算法领域也出现比较严重的论文剽窃作假情况,值得写一篇博客文章记录一下。

[参考文献]

1. Brian Damgaard, Sokoban solver “scribbles” by Brian Damgaard about the YASS solver

2. Pavel Klavik, Sokoban Solver—a short documentation

3. Timo Virkkala, Solving Sokoban. Master Thesis. 2011.

4. Renato R. Leme, Andre G. Pereira, Marcus Ritt, Luciana S. Buriol, Solving Sokoban Optimally with Domain-Dependent Move Pruning. 2015 Brazilian Conference on Intelligent Systems

5. Brian Damgaard, Solving Sokoban Optimally with Domain-Dependent Move Pruning – Stolen Ideas, Lies, and Incompetence. Yahoo Sokoban Group. 2016.

此条目发表在 推箱子, 算法, 编程 分类目录。将固定链接加入收藏夹。