超级马里奥比你想的更具数学性

# 超级马里奥比你想象的更数学化 来源：https://www.technologyreview.com/2026/06/23/1138262/super-mario-is-mathier-than-you-think 有一个你很可能在学校没解过的问题：你是一个来自布鲁克林、志向远大的年轻水管工，身处一个被名为"板栗仔"的暴力人形蘑菇统治的世界。你的挚爱被绑架了，于是你踏上了拯救她的征程，穿越充满管道和怪物的险恶地形，而你唯一的防护手段就是跳跃和踩踏。 这段旅程如此艰险，以至于没有任何计算机（无论是真实的还是假想的）强大到足以判断你是否能抵达她身边。根据MIT Hardness Group发表的研究，判断你的征程是否可能实现，至少和解码金融交易背后的加密一样复杂。但如果这个问题能说话，它第一句话就会是："你好，是我，马里奥！" ### 为了对游戏的爱 尽管拥有一个YouTube频道，但MIT Hardness Group并非一个正式的研究小组。相反，它是理论计算机科学项目的一个占位名称——包括几个与超级马里奥相关的项目——这些项目来自Erik Demaine的课程《算法下界：难度证明的乐趣》。 Demaine是计算机科学教授，曾因其在蛋白质折叠和折纸的计算几何学方面的工作获得麦克阿瑟奖学金（也称"天才"奖）。但他同时也研究复杂性理论，该理论专注于根据计算机解决问题所需的时间和内存空间来对问题进行归类。 他碰巧也是一位狂热的超级马里奥粉丝。"我是玩NES（任天堂娱乐系统）游戏长大的，"Demaine说。"小时候我花了很多时间玩，所以多年后回到这个游戏并将其与我的研究联系起来，很有意思。" *Erik Demaine研究复杂性理论，该理论考察计算机解决问题所需的时间和内存。他也是一位狂热的超级马里奥粉丝。* 图片来源：DONNA COVENEY/MIT 超级马里奥发生在一个水平滚动的平台、管道和其他障碍物的世界中。游戏的目标是营救蘑菇王国的君主桃花公主，玩家需要穿越这片地形，同时躲避或对战板栗仔和名为"刺球"的致命豪猪等怪物。游戏分为多个关卡；在原始版本中，每个关卡都以一根旗杆结束，旗杆会将马里奥送往任务的下一部分。 在过去14年里，Demaine和他的合作者证明了许多关于超级马里奥的事情，例如它比臭名昭著的旅行商问题（寻找多个地点之间最有效路线的问题）或大数分解问题更难。但最让Demaine惊讶的结果来自他的四位学生：Hayashi Ani '21, MEng '23; Holden Hall '26; Ricardo Ruiz '24, MEng '25; 以及Naveen Venkat '23, MEng '24。在2023年那门课的期末项目中，团队结合了粉丝制作的超级马里奥关卡编辑器和名为Super Mario Maker的平台，创造出了难度极高以至于不可判定的关卡。换句话说，不可能编写出一个计算机程序，能始终正确预测在这些关卡中马里奥能否到达城堡。 此前，Demaine曾认为超级马里奥属于PSPACE复杂度类，该类包含可解的问题，但随着问题规模增大，其解决方案会变得不切实际地复杂。当时，他甚至说过PSPACE是马里奥的"永久居所"。但新的发现将超级马里奥推入了RE-Complete，即不可判定问题的类别。"这是我们可以为这类游戏想象的最难的复杂度类，"Demaine说。 ### 计算机无法解决的问题 1936年，现代计算机科学之父艾伦·图灵创建了一个现在被称为"停机问题"的谜题，以证明不可能构建一台能*解决一切*的计算机。 停机问题的核心在于一个悖论，其内容如下：假设你有一台名为"预言机"的精密计算机，它能查看任何程序并正确判断执行该程序的计算机是否会停机。例如，如果看到程序"取1加3"，预言机会说该程序停机；但如果程序说"取1，不断加1直到变成0"，预言机会说它永远运行。 现在假设你有另一台计算机，名为"逆反机"，你把预言机放在里面。当你给逆反机一个程序时，它会将程序传递给预言机，然后做出与预言机所说的程序行为相反的操作。因此，如果预言机评估逆反机的程序并认为它会停机，逆反机就会永远运行。如果预言机认为程序会永远运行，逆反机就会停机。无论哪种情况，预言机的判断都是错误的，因此该分类问题是不可判定的。 超级马里奥不可判定的证明依赖于这个思想的更复杂版本。该团队的论证使用一种称为"归约"的技巧来拆解视频游戏，数学家将待解决的问题转化为一个他们已经有所了解的问题。"我记得数学课上有一个经典例子：如何煮一锅开水？"Demaine回忆道。"嗯，我从水龙头接满一锅水，放到炉子上，然后它最终煮沸。好了，现在我给你一锅已经装满水的水。你如何煮一锅开水？嗯，我先倒空水锅，然后归约到之前的问题。" 在他们那个充满平台和豪猪的特定世界里，团队将超级马里奥关卡分解为马里奥路径的局部部分，称为"小工具"，他们可以利用这些小工具来证明该关卡是不可判定的。 "在我们看来，小工具是你环境中任何决定你是否能通过（关卡内）某个模式的东西，"Jayson Lynch '12, MEng '15, PhD '20解释道，他是CSAIL研究科学家兼MIT FutureTech算法主管。例如，在一个小工具中，马里奥可能需要跳上一个平台以躲避怪物，同时穿过屏幕。作为Demaine指导的博士生，Lynch率先推动了小工具理论的形式化，并参与了早期一些超级马里奥论文的工作，但没有研究该游戏的不可判定性。 Lynch最喜欢的超级马里奥小工具之一是门小工具，它的作用类似于一扇门，马里奥可以打开、穿过并关闭。这扇门总是要么打开（当刺球在右侧时），要么关闭（当刺球在左侧时）。因此，如果一只刺球在门的左侧来回踱步，马里奥需要从移动的刺球下方穿过，并在刺球到达砖块时跳起撞击砖块。这会将刺球弹到右侧，从而打开门，让马里奥穿过横穿路径到达可以关门的位置。到达那里后，他必须再次在往复的刺球下方找准时机跳跃，将其送回小工具的左侧，从而在身后关上门。 *马里奥通过将刺球从左侧撞到右侧来打开门。* *刺球移开后，马里奥可以穿过打开的门，沿着横穿路径到达另一边。到达后，他再将刺球撞回左侧并关上门。* 由于一扇门总是开或关，其状态可以用来模拟真或假语句，开表示真，关表示假。早期的超级马里奥论文曾将多个门小工具串联起来，模拟一个复杂度研究人员已知的困难的真假问题。但为了展示不可判定性，团队使用超级马里奥关卡编辑器组合了另一种设备，称为计数器小工具，用于统计游戏中的怪物和障碍物。 Demaine说，如果你能用哪怕几个这样的计数器构建一台机器，你就可以模拟任意计算机——一台在给定足够时间和内存的情况下基本上能做任何非量子计算机能做的事情的计算机。而且，由于怪物数量没有限制，这样一台机器可以拥有无限扩展的内存，即使关卡大小保持不变，他认为这"相当疯狂"。换句话说，任何理论计算机都可以在超级马里奥关卡中构建。"你可以用它来解决任何能用计算机解决的问题，"Demaine说。"你可以让它帮你报税、编译代码、运行LLM，或者优化你的课程表。"你甚至可以构建擅长数独、构建最优国际象棋策略或证明任何可证明数学定理的超级马里奥关卡。 MIT数学家Marvin Minsky在1961年发明了计数器机，以弄清一台计算机可以多么简单却仍然"通用"（在给定足够时间的情况下与任何其他计算机一样强大）。这些理论计算机每台存储两个数字，并且可以通过加1、减1或者在数字达到设定值时执行特殊操作来改变它们。 在学生们为超级马里奥设计的计数器小工具中，数字反映了关卡中包含的板栗仔数量。当管道吐出一个板栗仔时数字增加，当马里奥踩扁一个板栗仔时数字减少。如果马里奥在没有踩扁的情况下撞到板栗仔就会死亡，因此只有当计数器为0时，他才能继续沿路径前进。 *MIT Hardness Group在Super Mario Maker 1中设计了此计数器小工具以证明不可判定性。* Minsky已经证明计数器机是不可判定的，因为它们可以运行不可判定的问题。由于研究人员证明了计数器小工具可以模拟计数器机，那么任何包含计数器小工具的超级马里奥关卡也将是不可解的。"将来，如果有人想证明一个游戏是不可判定的，"参与该项目的学生之一Holden Hall解释说，"他们只需要制作一个这样的小工具。" 像停机问题这样的不可判定问题的存在意味着可以构建一个不可判定的超级马里奥关卡。正如停机问题中那个独特的不可判定程序意味着不可能判断一个计算机程序是否会永远运行一样，该团队的不可判定关卡意味着无法判断任意一个马里奥关卡是否可以被通关。 ### 给超级马里奥加上"超级" 在Demaine关于难度证明的课程结束两年多后，他的一些学生仍每周聚会讨论他们的超级马里奥研究。 "从复杂性理论的角度来看，研究视频游戏的趣味主要在于教学原因，"瑞士南方应用科技大学的研究教授Fabrizio Grandoni在2016年告诉MIT News。"这是一种简单自然的方式，可以吸引学生研究这个特定话题。" Hall在上Demaine的课之前几乎没接触过复杂性理论的思想，他就是一个例子，他说："我选这门课是因为我认识的很多人都选了。但自从上了这门课，我非常喜欢它，所以我在这个领域又上了很多课。" MIT Hardness Group的工作应用远不止踩蘑菇和收集金币。例如，德克萨斯大学里奥格兰德河谷分校的研究人员（包括Timothy Gomez，现为MIT博士生）已经使用为分析超级马里奥等游戏而开发的小工具理论来研究与机器人运动规划和化学反应网络建模相关问题的复杂度。 "（小工具理论）可以用在消极的方面，比如说'哦，好吧，我们应该停止寻找算法，因为我们知道这个问题太难了'——或者可以用在积极的方面，因为通常为了证明某事很难，你是在展示你可以构建某种特定类型的计算机，"Demaine说。 虽然无法知道超级马里奥将在数学和计算机科学的未来留下怎样的印记，但有一件事是肯定的：无论他拯救了多少公主，这位小水管工的遗产注定将远远超越视频屏幕。