[老游杂谈] 《推箱子（仓库番）》

日本其实逻辑谜题一直比较流行，Sudoku，Nonogram之类的经典的谜题大都是在日本发展起来的，这要归功于谜题出版商Nikoli。
电脑解谜游戏方面，日本也比较领先，70年代末才出现了第一代个人电脑，而推箱子也是同一时代的作品。它是在在1981年由Hiroyuki Imabayashi（今林宏行）设计，英文名叫Sokoban（日文倉庫番），用BASIC语言编写，运行在PC-8801上，这是日本的第一代PC。
据传他当时并没有打算商业化，做出来只是给朋友玩。后来在一名软件发行公司的推销员建议下才开始商业化制作。他成立了Thinking Rabbit，自己担任社长，并发行了这个游戏。
最初版本只有20关，其中前10关是正常关卡，后面10关则是带有隐藏墙壁的变化关卡，因为后面不是纯逻辑谜题了，所以一般在讨论关卡数时认为初代只有10关。
两年后，也就是1984年，他们推出了2代，有50关，这也就是到现在为止很多作者模仿的经典版。
此后，Thinking Rabbit分别在1989年和1991年推出了Sokoban Perfect和Sokoban Revenge，各有306关，这些关卡合起来基本就是现在市面上各种推箱子游戏关卡的来源。
这四款游戏都是发布在日本NES产的个人电脑， Spectrum HoloByte在1988年才把这款游戏引入欧美，移植到了比较流行的IBM-PC，Apple II之类的平台上，是经典版的50关。

在1990年，台湾大宇公司推出了仓库世家，正式将推箱子引入了中囯，此游戏一共250关。1995年，大宇又先后引进了Sokoban Perfect和Sokoban Revenge，游戏名分别叫仓库番：史上完整版和仓库番：玩家复仇版。

Thinking Rabbit也是很长时间没有出什么新作，只是不断的推出沿用之前关卡的作品和授权移植，推箱子被移植到了十几个平台，包括GB，MD，PS等。但新关卡其实不多，大部分关卡也都是来自于Perfect和Revenge两作。
04年之后，推箱子归属Falcon公司，他们推出了各种手机平台的推箱子游戏，大多是运营商合作的，发行则大部分是SE发行，也有Konami发行的。 15年后他们重新推出Windows版，这次是Perfect Plus，First Step Plus和Revenge的再版，都是Windows平台。此后又推出了苹果和安卓版本，不过两大应用商店早就有各种推箱子仿制品，官方版本基本被淹没了，不过相比较而言官方版本的画面和关卡都是很不错的。

推箱子属于滑块谜题（Sliding Piece Puzzle）的一种，有一本同名的书专门介绍这类谜题，是1986年牛津大学出版的，其中介绍了各种滑块谜题。其中大部分都是实体谜题，比如15谜题，华容道之类的（顺便说一下，华容道虽然是三国背景，但直到20世纪才有记载，是晚于欧洲的同类谜题的）。
推箱子之所以能归入这一类是因为箱子和滑块没有本质区别，只不过只占一格，人可以看做唯一能自由移动的滑块。
在这本书里，推箱子的原版10关在上面都有列举，同时作者还对各种谜题进行了难度评分，这10关的难度基本是逐步上升的。
游戏的难度变化曲线，也就是游戏的节奏对于解谜游戏来说至关重要。人对于解谜游戏的要求实际上是比较苛刻的，解谜游戏既要难，但又不能太难。这里难指的是足够复杂，能够实现各种不同的解题方向，给玩家思考的空间；而简单则是指符合玩家的水平，不能超出太多，否则人们会乱试几下就失去兴趣，实际上游戏的节奏保持稍高与玩家的水平才更能吸引人们。
难度需要一个量化标准，有不少理论研究了这方面的内容，因为推箱子是有实际意义的，比如机器人的控制和物品摆放这些实际问题可以简化为推箱子，这也是游戏的初始背景，而研究人的解谜方式则对人的认知和思维过程的理解都有所帮助。不过，理论上来讲，推箱子对于人和计算机的难度都很高。
对计算机来说难度的判断依据是复杂度理论，这里简单介绍一下，计算机专业或对理论不感兴趣的话可以跳过。
复杂度理论主要用计算机的理论模型图灵机作为研究对象，主要研究的内容是时间和空间的复杂度。 图灵机是一个无限长纸带，划分成小格，每格有一个符号，这是内存的抽象。还有一个读写头，可以左右移动，读写纸带上的符号，这是对总线的抽象。还有一个起始状态，终止状态，一个状态转移表根据读入的符号转到下一状态，这是对CPU的抽象。非确定图灵机就是每次能转移到多个状态，最终只要其中一个是终止状态就可以。

复杂性理论依据问题对时间和空间的要求分成不同的复杂性类，P是指多项式时间内确定性图灵机能判定的问题，NP指多项式时间内非确定图灵机能判定的问题。PSPACE是指确定图灵机多项式空间能判定的问题。 多项式指的是所需的空间或时间能写成an^k+bn^(k-1)+…+cn+d这样的形式。n是问题的规模，在这里就是地图大小。 判定指的是答案为真或假的问题，对于推箱子来说就是判定一个地图是否有解。
下面说结论：已经有人证明了推箱子问题是PSPACE-COMPLETE的，也就是说它可以用多项式空间解决，同时所有用多项式空间能解决的问题都可以在多项式时间内规约成为推箱子问题。
证明的方法一般就是把一个已经证明为PSPACE-Complete的问题规约到推箱子问题。这里面包括的问题就很多了，其中一个是LBA（Linear Bounded Automata）问题，就是线性有界自动机能否接受一个输入，一般内存是有限的，LBA可以看成更接近于实际计算机的模型。
另一个问题就是判断一个句子是否符合上下文相关语法。还有就是TQBF（True Quantified Boolean Formula）问题，就是判断一个只能取真和假，所有变量有全称和存在量词限定的逻辑表达式是否为真的问题。
Robert A. Hearn和Erik D. Demaine合著了一本书叫《Games, Puzzles, and Computation》，这本书里就把0人游戏也就是自动机，1人游戏也就是解谜游戏，2人的博弈比如围棋等放到了一个约束逻辑框架中，证明了各种情况下的复杂性，然后又用这个框架证明各种实际游戏的复杂性。
对于解谜游戏就是采用将TQBF规约到约束逻辑的方法证明的。 实际上Robert Hearn是MIT的博士，Erik Demaine是他的导师，这本书原来是他的博士论文。而Erik Demaine更是研究了很多关于游戏方面的理论，包括折纸和谜题等，还开设了好几门课程，对理论研究有兴趣的话可以去他的主页看看。 http://erikdemaine.org/
复杂度理论还是比较有意思的，在这方面上可以说解谜游戏，逻辑，语言和计算都是等价的。
不过，对一般程序员来说，复杂性理论主要的作用是劝退，如果一个问题证明是NP-hard的话，除非想要把数学和计算机的奖得个大满贯，否则就不用费心找低复杂度的算法了。
所以计算机解决推箱子问题的方法还是只能穷举，搜索所有可能的步骤寻找解，因此只能处理很小的地图，因为所需时间是随地图大小指数增长的，几百格的地图所需要的计算时间就远远大于宇宙的年龄了，而且计算机的速度提升几倍也就能处理的地图大小也就比原来+1而已，这也是区分多项式复杂度和指数复杂度的意义。
但人类和计算机的解决方法并不相同，人类不依靠搜索来解题，而是靠直觉（也就是heuristics），之前就有使用启发式算法进行搜索优化的，比如Hill-Climb Heuristic，就是把所有箱子离目标的距离之和作为优化的目标。
但Petr Jarusek和Radek Pelanek认为这些方法并不能正确衡量谜题对人类的难度，他们建立了一个游戏网站记录每个人游戏时思考的时间，然后提出了一种人类模型，他们发现大多数人在初始位置附近花费的时间很多，但几乎不会在无效状态花费时间，一旦到达离最终点超过一半时就能很快完成谜题。
因此他们提出了一个将随机走和有序走结合的模型，走到死路的概率为0，可以到达目标的状态权重高于其他状态，然后通过计算机多次模拟这个模型得到的平均步数来判断谜题对人的难度。
他们认为人类适合抽象，问题分解和模式识别，因此还提出了另一个基于问题分解的方法，具体就是把箱子分成两组，每种分法计算在不同组之间交换最少的解法步数，最后得到所有分法的最小步数，第二种方法是每个箱子一组，计算不同箱子间交换最少的解法步数。 以上两关是对人类难但对计算机容易的关卡，人类平均解决实际都超过了40分钟。

其实人是喜欢挑战的，大多数游戏复杂度都很高，很少有NP-hard以下的，毕竟难才有研究的意义，如果有固定解法的话很快就会变得无聊。
有的游戏，比如Wayout和Zasa就都是P类问题，作为解谜游戏而言难度上限就差了一些，相比较而言也更容易无聊。
关于推箱子的研究还有几方面，其中有关卡求解器，我们已经知道不存在有效算法来求解，但是可以对特定情况优化，用一些启发式搜索算法，同时尽早排除无效的情况可以提高能解决问题的大小。
还有一方面的研究是随机关卡生成，纯随机生成的关卡大概率是无解的，而且不存在有效的判断方法，难度也很难界定。 随机关卡生成和求解方法其实差不多，先生成一块地图和目标点最为最终结果，然后从最终结果开始，依据不同的判断规则寻找离目标最远的情况。

顶科普好文

posted by wap, platform: Android
当时看到这个游戏，觉得设计者构思太巧妙。

posted by wap, platform: 小米5
gameboy上的两作当年在大学宿舍研究很深入

某人今生都几乎没碰过电子游戏，当年外地上学时电子词典《推箱子》可谓消磨时间神器