第十一届全国数学文化论坛报告｜杨超：推箱子游戏与数学文化

luyuanhong

第十一届全国数学文化论坛报告｜杨超：推箱子游戏与数学文化

编者按

广东外语外贸大学的杨超副教授，对推箱子游戏情有独钟，不仅能够玩出花样来，更可贵的是，他还能看到数学玩具和游戏在数学普及和数学文化的传播中所起到的一定作用。2009 年 4 月他曾发起在线推箱子比赛，每月一期，至今已经连续举办了十三年共 165 期。杨超副教授更于 2022 年 7 月在河南开封举办的中国数学会第十一届全国数学文化论坛上作过一场题目为《推箱子游戏与数学文化》的 30 分钟报告，我们数学经纬网的成员因为报名参会并作报告，也亲自在现场聆听了杨老师的报告，印象非常深刻。为方便读者学习和交流，我们获得授权转载本报告。

摘要>>

数学玩具和游戏对数学的普及与数学文化的传播起到一定的作用。推箱子是一个电脑小游戏，通过控制一个仓库管理员在一个2维地图中把多个箱子推到指定的放置点而过关，可视为一个路径规划问题。本报告讨论推箱子游戏与数学文化的关系，主要包括以下几部分内容：

01  推箱子游戏的历史与渊源；

02 菲尔兹奖得主Wendelin Werner 喜欢玩推箱子的故事；

03 推箱子与计算复杂度的关系，高复杂度导致了推箱子关卡的多样性；

04  推箱子与人工智能，深度神经网络能否求解推箱子关卡；

05  介绍我们举办在线推箱子比赛十多年的经验，探讨利用推箱子作为数学普及与传播的方法。



这个报告主要受到两位专家的启发。一是汤涛院士在中国数学会数学教育分会上介绍数学体验馆的建设与实践。二是厦门大学林亚南教授在第十届全国数学文化论坛上展示的“智力玩具与数学”博物馆。

推箱子游戏可以作为一种数学体验的形式，同时也是一种电子形式的数学与智力玩具。

一、推箱子的游戏规则与历史

首先介绍一下推箱子的游戏规则。规则简单地说，只有两条：一是只能推，不能拉；二是只能推动一个箱子。

如下图是一个关卡的例子。关卡中有两个箱子，其中一个已经在目标点上了（颜色较浅的箱子表示已经位于目标点），只需要再把另一个箱子推到目标点即可。

若直接把未归位的箱子向左推一格，马上形成死锁。无法绕到箱子后面再把该箱子推到目标点。

正确的方法应该把已归位的箱子向上推一格，为第二个箱子腾出位置。从这个简单的例子我们可以看出，推箱子需要逻辑思考和分析，可以培养数学思维。



推箱子游戏是电脑时代的发明，是日本人今林宏行于 1981 年编程实现，并于 1982 年开始商业发行。



推箱子从某种意义上说，它继承了滑块类玩具的某些特点。但是规则从某种意义上讲则大大简化了，都是 1×1 大小的箱子。而滑块类游戏为了达到一定难度，必须有不同形状的滑块。从规则上的这一简化，可以说推箱子游戏是青出于蓝而胜于蓝。



在中国，大概上世纪 90 年代推箱子游戏就已经十分流行了。



如前所述，推箱子以其更简单的规则和更复杂的变化，拥有许多的爱好者，可能是电子形式的纯粹的益智游戏中最受欢迎的。



二、菲尔兹奖得主与推箱子

2006 年的菲尔兹奖得主 Wendelin Werner 也喜欢推箱子。他曾在某次数学报告中建议听众下载一个推箱子游戏玩一下。



三、举办在线推箱子比赛

我们的推箱子比赛于 2009 年开始，至今已经连续举办 13 年，共 165 期。比赛由 Anian Wu 和王毅琨两位总主编负责安排比赛关卡。这一个过程和数学学术期刊的文章发表有某些类似之处。推箱子爱好者把自己设计的关卡投稿给主编，主编解关后给出一些意见，看设计者设计的路线有没有漏洞。投稿者再根据主编的意见修改。这一过程有时可能会重复数十次，所以每一个比赛关卡都是反复打磨之作。



比赛是完全开放式，世界各地的任何人都可以参赛。



下面我们以一些关卡为例，展示推箱子如何可以在这么简单的规则下，有如此丰富多彩的变化。例子主要来自我们的比赛关卡和一些相关关卡。

首先，推箱子关卡的设计是开展造型艺术的一个理想的方式。laizhufu 最擅长于设计具有特别图案的关卡。



2021 年的建党 100 年关卡更是精妙。初始时，箱子排列成 1921 ，过关时排列成 2021 ，表明了党带领我们实现百年目标，一路克服了各种困难。而且过关后箱子整体向上移动一行，又表明了我们的道路是向上的、进步的，中华民族的伟大复兴是一定能够实现的。



下面一关还是来自 laizhufu 。2021 年是牛年，同时华为在国际贸易中受到一些无理的打压。Laizhufu 巧妙地把牛的形象和“华为”二字融为一体，寓意华为一定能够克服困难，扭转乾坤。果不其然，这一关发布后的几个月，华为孟晚舟女士就顺利回国。

从这一关的演变过程，我们看到一个优秀的关卡是如何经过千锤百炼而成的。



邹永忠先生是国内推箱子关卡创作的开山鼻祖。我 90 年代末上网时，就是从邹永忠先生的推箱子网页了解到很多推箱子资讯。邹先生早期开展的推箱子擂台，可以说是我们推箱子比赛的一个雏形。

邹先生的优秀关卡很多，因为这是一个数学文化论坛，下面选取一个和数学关系最紧密的代表关卡。下图这个二维码关卡巧妙地利用了里德-所罗门（Reed-Solomon）纠错码的特点，改动了二维码的几个黑白元素，得到一个难度不小的关卡。再结合特别设计的皮肤，可以扫一扫打开比赛网站。



邹先生的关卡的另一个迷人之处是每一关卡都有一个故事。比赛十周年时，我们邀请邹先生特别设计了一个关卡。邹先生欣然接受，体现了他希望比赛能够培养出更多的推箱子高手的期待。



下面两位：陈锦超和刘泽鸿，是我们比赛中涌现出来的优秀青年人才的代表。他们的关卡都多次成为了比赛关卡。

陈锦超的《我的大学》系列，造型类似，但过关路线完全不同，具有极高的迷惑性，是优秀关卡设计中的一种方法。



刘泽鸿是最年轻的推箱子高手的代表。



要参加推箱子比赛，需要相对专业的软件。我们的比赛网站也提供了功能极其强大的安卓推箱子应用《推箱快手》。



推箱子的复杂与多变，还体现在 3 个箱子的关卡也可以极其困难，下图中 Zika 的关卡是一个代表。Anian Wu 为庆祝比赛 100 期设计的《百花齐放》关卡，其实是模拟了另外一种滑块游戏，背后还有故事，在此处就不再展开讲了。



下面几页从解关需要的最少步数的角度，来展示推箱子关卡的复杂度。

我们限制在 50×50 大小的关卡里面讨论。若只有一个箱子，解关需要步数最多的是邹先生的《一箭十万》。



若不限制箱子的数目，解关步数可以呈指数增长。下面是一个例子，这个例子的解关需要的步数的通项公式以 1.618 为底，恰好是黄金分割的倒数。上午袁亚湘院士（在第十一届全国数学文化论坛）给大家展示了黄金分割无处不在。这一系列推箱子关卡也证明了这一点，推箱子中也出现了黄金分割。



邹先生利用较小的空间设计出了以 4 为底增长的小单元。



结合了上面的两种指数增长的设计，邹先生和西北天狼设计的《穰步犹移》，是目前所知的 50×50 以内过关需要步数最多的关卡。



四、 计算复杂度与关卡多样化

推箱子的多样性可以用数学中的计算复杂理论帮助我们解释。



通过常见的一些数学玩具作对比，可见推箱子是复杂度最高的。



魔方看上去难，其实是比较容易举一反三的，这是因为从计算复杂度理论上，这是一个多项式时间可解的问题（P）。



推箱子是 PSPACE 完全的，文献中先后有两个不同的证明。其中第二个证明是麻省理工的 Erik Demaine 教授的团队给出。



除了推箱子，大众喜闻乐见的滑块类游戏也是 PSPACE 完全的。其中限制了方向的 1×1 Rush Hour 最近刚刚也被 Erik Demaine 团队证明是 PSPACE 完全的，前面提到的《百花齐放》关卡与 1×1 Rush Hour 有内在联系。



五、推箱子与人工智能

最近几年，由于深度神经网络的成功应用，人工智能又变得非常火。我们的比赛是完全开放式的，但我们的比赛关卡（除了少数容易关卡外），特别是每期的难、中等级的关卡，从来未见被人用计算机暴力求解攻破。



在 2016 年 AlphaGo 战胜围棋九段顶级高手时，我们也应景地发布了一关，可以说是我们向人工智能发出的公开挑战。



从计算复杂度上看，围棋也是 PSPACE 完全的，貌似和推箱子难度相等。但是围棋是二人博弈，推箱子是单人游戏。但是要战胜人类，电脑并不需要回答这个 PSPACE 完全问题。而推箱子不同，要过关必须回答出相应的 PSPACE 问题。推箱子是人工智能面临的下一个重大难题。