看似简单的俄罗斯方块，可能是数学上最复杂的游戏
看似简单的俄罗斯方块游戏竟蕴含着让超级计算机都束手无策的数学难题。
作为90年代的孩子，我无法避开这款后来成为畅销游戏的俄罗斯方块。1984年由俄罗斯程序员Alexey Pajitnov推出后，俄罗斯方块迅速成为现象级游戏，多年来拥有数亿玩家。我自己也曾在Game Boy上花费数小时，试图让下落的方块尽可能完整地填满游戏区域。游戏过程中，这些方块下落得越来越快，我的拇指几乎跟不上操作节奏。
从原理上讲，所有游戏都可以从数学角度进行分析，无论是糖果传奇、万智牌还是Wordle这样迥异的游戏。但俄罗斯方块与数学有着特殊的联系。比如，游戏目标与几何学中的拼接问题非常相似，即判断是否能用无限大的瓷砖集合无缝覆盖某个区域。
对数学家而言，俄罗斯方块在复杂性方面尤其引人入胜。更具体地说，研究人员想知道在某些条件下真正"解决"俄罗斯方块需要多少计算能力，比如方块数量有限且能预知各种形状的出现顺序。结果表明，这种特定框架下的俄罗斯方块属于数学上最复杂的游戏之列。
在复杂性理论领域，数学家和计算机科学家致力于描述解决问题的难度特征。他们定义了多个复杂性类别，包括P类和NP类问题。简单来说，P类问题对传统计算机而言容易解决，而NP类问题更困难，但如果你有可能的解答，验证起来却很容易。NP问题就像数独游戏：填写可能需要数小时，但检验答案是否正确只需几分钟。
要确定任务的复杂性，必须将不同问题进行比较。例如，如果解决任务A的每个算法都能解决任务B，那么A比B更复杂。用数学家的话说：B可以"归约"到A。这意味着通过将俄罗斯方块与已知的P类或NP类问题比较，就能确定其复杂性。
那么如何选择合适的比较点呢？计算机科学家可以借助所谓的NP完全问题，所有其他NP问题都可以归约到这类问题。其中之一就是三分割问题。
三分割问题涉及这样一个问题：给定一组整数，比如{1, 2, 5, 6, 7, 9}，能否将其分成若干个三元素子集，使得每个子集中数字的和都相等。对于{1, 2, 5, 6, 7, 9}，一种分法是{1, 5, 9}和{2, 6, 7}，每个子集的和都是15。并非每个给定集合都能找到这样的分法。判断是否存在这种分法极其困难：三分割问题是NP完全问题。
2003年，麻省理工学院的计算机科学家证明，判断俄罗斯方块游戏板在给定情况下能否被清空的问题，本身就可以映射到三分割问题。研究人员将俄罗斯方块游戏中的空隙等同于问题中的子集，将下落的方块等同于需要分割的数字。
通过这种方式，科学家们证明了如果数字集合可以分成和相等的三元素子集，那么俄罗斯方块游戏区域也可以完全清空。他们证实了"集合能否三分割"和"俄罗斯方块游戏板能否清空"这两个问题在数学上是等价的。
这一洞察意味着判断给定方块能否适当排列的难题属于NP完全问题，使俄罗斯方块成为高度复杂的游戏。游戏包含的方块序列越长，计算机确定其可解性就越耗时。实际上，传统计算机很快就会不堪重负：没有算法能高效解决这个问题。
荷兰莱顿大学的计算机科学家Hendrik Jan Hoogeboom和Walter Kosters在2004年的论文中表明，俄罗斯方块还有更复杂的性质。他们研究了一个略有不同的问题。假设你观察一场只有细长I型方块的俄罗斯方块游戏。如果我给你预设的若干种方式，比如40个I型方块落到空游戏板上的8种方式，你能判断其中是否有一种能让游戏板最终清空吗？
Hoogeboom和Kosters证明，即便拥有无限的计算能力，这个问题实际上也是不可判定的。因为上述问题可以映射到与Kurt Gödel著名的不完备性定理相关的问题上。这些定理表明，数学中总会存在既无法证明也无法证伪的陈述。
当然，这些问题可能对你在俄罗斯方块中的成功毫无影响。在方块快速下落的情况下，几乎没有时间思考数学问题。
尽管如此，值得注意的是，40多年后，尽管游戏本质上保持不变，人们对俄罗斯方块的欣赏仍在不断增长和演变。例如，一种叫做"滚动"的游戏技巧使得玩家能够进行超快速输入，从而比以往任何时候都走得更远。过去，第29关被视为不可逾越的极限。但在2023年，一名当时13岁的少年通过滚动技巧突破了所有先前记录，达到第157关，导致游戏崩溃。我们只能等待看看俄罗斯方块未来还会带来什么惊喜。
