《俄罗斯方块》的复杂程度，甚至可以挑战超级计算机的极限

图片来源：unsplash

撰文 | Manon Bischoff

翻译 | 时小舟

编辑 | 冬鸢

出生在20世纪90年代的我无法抵挡《俄罗斯方块》（Tetris）这款畅销游戏的诱惑。1984年，俄罗斯程序员阿列克谢·帕吉特诺夫（Alexey Pajitnov）发布了它，瞬间引发了轰动，几十年来已经积累了数以亿计的玩家。我会花好几个小时在任天堂游戏机上，试图让掉落的方块尽可能填满游戏区域。游戏过程中，方块会掉落得越来越快，我的拇指几乎完全来不及操作。

理论上来讲，所有游戏——无论是《糖果传奇》、《万智牌》还是猜词游戏《Wordle》——都可以从数学的角度来解析。而《俄罗斯方块》与数学之间存在许多特殊的关联：比如，该游戏的目的十分类似几何学里的“铺砖问题”（parquet problems）——用无穷多的瓷砖不留缝隙地铺满平面区域。

但是《俄罗斯方块》的复杂性激发了数学家的极大兴趣。具体来说，研究人员非常好奇在假定条件（例如有限数量的方块、预先得知即将掉落的方块形状和顺序等）下，要想确定《俄罗斯方块》是否存在真正意义上的解法，需要多少计算能力。事实证明，这种对问题的特殊设定方式，使《俄罗斯方块》跻身于数学上最复杂的游戏之列。

任天堂游戏机与俄罗斯方块（图片来源：unsplash）

定义复杂性

在复杂性理论（complexity theory）领域，数学家与计算机科学家试图将解决问题的难度描绘出来。他们定义了多个复杂性类（complexity classes），包括P问题和NP问题。简单来说，P问题是很容易被传统计算机解决的；NP问题难度更高，解决起来需要大量时间，但一旦有了候选解，就很容易验证。（NP问题可以被想成是一道数独题：你也许需要几个小时去填满空格，但只需几分钟就能验证答案是否正确）

想要判定一项任务的复杂性，必须将不同问题相互比较。比如，如果每个能解决A任务的算法也能解决B任务，那A就比B更复杂。又或是像数学家描述的：B“可归约”（reducible）于A。也就是说，《俄罗斯方块》的复杂性可以通过与另一个已知的P或NP问题对比来判定。

那么我们应该如何选择合适的参照问题呢？计算机科学家可以转向所谓的NP完全问题（NP-complete problems）。NP完全问题是NP问题里难度最高的，所有其他NP问题都可归约到这类问题。其中一个典型代表是三划分问题（three-partition problem）。

三划分问题探讨的是：一组整数，比如{1,2,5,6,7,9}，是否可以被划分为各含三个元素的两个子集，使每个子集里数字的和相等。对于{1,2,5,6,7,9}，可以将其划分为{1,5,9}和{2,6,7}两组，每组数字加起来都等于15。然而不是每个集合都能做到这样的划分，最难的一点在于判断是否存在这样一个解。因此，三划分问题是一个NP完全问题。

图片来源：unsplash

2003年，美国麻省理工大学（Massachusetts Institute of Technology）的计算机科学家表示，在给定的游戏条件下，能否清空俄罗斯方块游戏区域里的方块，这个问题本身就可以被映射到三划分问题。为了做到这一点，研究人员将《俄罗斯方块》里的空隙视为三划分问题里的子集，将掉落的方块视为需要被划分的数字组。

科学家因此表示，如果这组数字可以被划分若干个和相等的三元素子集，那么俄罗斯方块的游戏区域也可以被清空。这样一来，他们证明了“一个集合能否三划分？”和“俄罗斯方块的游戏区域可以被清空吗？”从数学的角度来看是相同的。

这一发现代表着，能否让已知的方块以合理的方式掉落这个问题属于NP完全问题，说明《俄罗斯方块》是一个极为复杂的游戏。游戏中的方块序列越长，计算机判断可解性的速度就越慢。实际上，传统计算机很快就会招架不住，因为压根不存在能够高效解决此问题的算法。

可计算性的上限

根据荷兰莱顿大学（Leiden University in the Netherlands）的计算机科学家亨德里克·简·霍格布隆姆（Hendrik Jan Hoogeboom）和瓦尔特·科斯特斯（Walter Kosters）在2004年发表的一篇文章所述，。他们聚焦在一个不太一样的问题上。假设你看到一款《俄罗斯方块》游戏里只有长条的“I”形方块。如果我告诉你一定数量的方块掉落方式，比如让40个“I”形方块以8种预设的方式（即摆放位置）落入空的游戏区域，你是否能判断出其中是否存在一种方式能使游戏区域里的方块全部消除？

图片来源：pixabay

霍格布隆姆和科斯特斯证明了该问题实际上是不可判定的，即便有无限大的计算能力也无济于事。这是因为上述的问题可以映射到一个与库尔特·哥德尔（Kurt Gödel）提出的颠覆性的不完全性定理（incompleteness theorem）相关的问题。不完备定理指出，在数学里必定存在一些既不能被证实也不能被证伪的命题。

当然，以上这些问题对你能否通关《俄罗斯方块》应该没有什么影响。毕竟方块掉落的速度那么快，你根本没时间去思考这些数学问题。

仍令人惊叹的是，40多年过去，虽然游戏本身几乎没有什么变化，但人们对《俄罗斯方块》的理解和喜爱仍在持续深化和发展。例如，一种叫做“rolling”的技术使玩家能够突破以往不可企及的关卡。在过去，第29关曾被视为不可逾越的极限。但在2023年，一名年仅13岁的玩家利用该技术一路闯至第157关，最终导致游戏程序崩溃，刷新了所有历史纪录。我们唯有拭目以待，看《俄罗斯方块》在未来还会带来怎样的惊喜。