您是否曾花费数小时玩 Candy Crush Saga？您并不孤单。自 2012 年发布以来，它一直是 Facebook 和移动设备上最受欢迎的游戏之一。该应用程序在 2023 年上半年下载次数超过 1.06 亿次，成为该期间下载次数第二多的游戏应用（仅次于一款名为 Subway Surfers 的游戏）。
该游戏的原理很简单：在一个布满各种颜色糖果的网格上，您尝试通过相互交换相邻的糖果来形成至少三个相同糖果的水平或垂直链。一旦形成这样的链，其中的糖果就会消失，并且它们上方的其他糖果会向下移动。游戏的不同关卡有不同的目标。例如，一个目标是仅使用最多次数的交换来形成至少最少数量的链。部分由于其简单性，该游戏广受欢迎。也许它有点太受欢迎了。Candy Crush 因具有高度成瘾性而受到批评——而且可能不仅仅是对其玩家而言。
“在某些方面，至少对于数学家来说，将 Candy Crush 视为数学问题可能与玩它一样让人上瘾，”澳大利亚新南威尔士大学的计算机科学家 Toby Walsh 在为American Scientist撰写的一篇文章中写道。早在 2014 年，他就被 Candy Crush 的漏洞所困扰。但与大多数其他粉丝不同，他并没有尽力掌握这款游戏。相反，他想从数学的角度理解 Candy Crush 有多复杂。换句话说，如果给定机器最大交换糖果次数，计算机形成一定数量的三糖果链有多难？
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保未来能够继续讲述关于塑造我们当今世界的发现和想法的具有影响力的故事。
游戏能有多复杂？
为了将数学任务划分为不同的难度级别，理论计算机科学家引入了所谓的复杂度类别的概念。例如，存在一些计算问题，尚不清楚计算机是否会得出答案；它可以无限期地计算而不会得出答案。从某种意义上说，这些是所有任务中最困难的。事实证明，纸牌游戏Magic: The Gathering属于此类：可能会出现游戏情况，即使在最佳条件下，也无法确定哪个玩家会获胜。
要确定游戏的复杂度，您需要知道是否可以快速检查提出的解决方案。例如，如果您面前有一个已完成的数独谜题，您可以毫不费力地确认解决方案是否正确。如果计算机检查解决方案的计算时间仅随任务大小呈多项式增长，则该问题属于非确定性多项式时间 (NP) 类——该类别描述了某些数学问题的复杂性。Candy Crush 也是如此：通过追踪据称创建糖果链的各种交换步骤，您可以快速判断显示的結果（被消除的糖果链的数量）是否正确。
但问题在于 NP 类中并不能说明解决问题有多难或多容易。这是因为多项式时间 (P) 类别中的简单问题（另一个复杂度类别）也位于 NP 类中。对于 P 类问题，计算机解决问题的计算时间仅随问题大小呈多项式增长。乍一看，这听起来与 NP 的定义相似——本质区别在于，这里我们讨论的是解决任务的计算时间，而不是检查其解决方案的计算时间。因此，P 类问题可以有效地解决和检查。这些“简单”的问题包括对列表进行排序。在最坏的情况下，计算时间随列表大小的平方增长。因此，如果元素数量翻倍，您必须等待四倍的时间才能对列表进行排序。虽然这听起来很耗时，但从计算机科学家的角度来看，这并不是什么大问题。因此，位于 P 类中的任务被认为是简单的：通常可以毫不费力地解决它们。
相比之下，NP 类中存在难题。解决它们所需的计算时间随问题大小呈指数增长。“在我的台式电脑上，我有一个程序需要几个小时才能找到 10 辆卡车的最佳路线，并证明该解决方案是最佳的。但是对于 100 辆卡车，同样的程序将花费比宇宙寿命更长的时间，”沃尔什在他的文章中解释道。最佳路线是“NP-hard”问题的典型例子，NP-hard 问题是指至少与 NP 中最复杂的问题一样难以解决的任务。
鉴于这些定义，几乎总是必须查看关于游戏的概括才能评估其复杂性，这是有道理的。毕竟，像国际象棋、围棋甚至 Candy Crush 这样的游戏都有由可用游戏场地确定的大小。在这种情况下，理论计算机科学家经常研究游戏的虚构扩展，其中棋盘和棋子或棋子的数量（或糖果）可以任意大。
Candy Crush 与逻辑陈述有何关系？
沃尔什提出了 Candy Crush 属于哪个复杂度类的问题。计算机是否总是可以毫不费力地找到游戏的有效解决方案策略？如果是这样，Candy Crush 将属于 P 类。或者计算机是否也难以找到要交换的合适糖果？沃尔什使用一种称为“归约”的常见计算机科学技术来检验这个问题。为了证明一个问题是 NP-hard 问题，必须证明 NP 中的所有其他问题都可以归约到它。也就是说，如果问题 A 的解决方案算法也可以解决所有其他 NP 问题，则问题 A 是 NP-hard 问题。
沃尔什有一个解决此问题的计划。即，存在一整套已知问题，这些问题既属于 NP 类又是 NP-hard 问题。如果他能证明其中一个问题类似于 Candy Crush——它们可以相互映射——他将证明这款流行游戏从数学角度来看是复杂的。沃尔什选择将 NP-hard 的“3-SAT 问题”与 Candy Crush 进行比较。
3-SAT 是逻辑中的一项任务，其中需要判断逻辑表达式的链接序列或“连接”是否正确或导致矛盾。此类连接的一个示例是：x ∧ ¬x。乍一看，这看起来很复杂。但是，如果您知道“∧”代表“并且同时”，“¬”代表否定，则可以快速翻译该语句。因此，该语句可以翻译为：x 并且同时非 x。现在的任务是为变量x分配“真”或“假”值，以使整个语句为真（换句话说，使其不产生矛盾）。在本例中，这是不可能的，因为您要么得到真并且同时非真（对于 x = 真），要么得到假并且同时非假（对于 x = 假）。这两个语句都没有意义：某件事不可能同时为真和为假。因此，此表达式的连接无法满足。
3-SAT 问题涉及链式语句，每个语句都以 (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ ... ∧ (an ∨ bn ∨ cn) 的形式直接链接三个变量。这里符号“∨”表示“或”。计算机必须尝试为变量分配真值，以便使整个语句为真。事实证明，此任务是 NP-hard 问题。随着任务长度的增加，所需的计算时间呈指数增长。
沃尔什现在需要证明任何 3-SAT 问题都可以在 Candy Crush 中表示，并且解决 Candy Crush 问题会自动解决相关的 3-SAT 问题。为此，他将 Candy Crush 游戏中的糖果配置与 3-SAT 问题中的变量和逻辑连接相匹配，以便某种糖果模式代表一个变量。通过这种方式，他能够证明任何 3-SAT 形式的逻辑语句都可以通过 Candy Crush 中适当的糖果分布来表示。
以下是它的工作原理：当玩家进行特定交换时，沃尔什将其解释为为变量分配真值——例如，“变量 1 为假”。每次交换都会更改游戏场地。此外，它还可以创建一条立即消失的三糖果链，从而使其他糖果可以向下移动到棋盘上。如果他们进行的交换次数与相应的 3-SAT 问题拥有的变量数一样多，他们就可以从棋盘上剩余的糖果中判断相关的 3-SAT 语句是真还是假。例如，如果在所有交换之后，第三行第二列的方格包含黄色柠檬糖，则这对应于语句“真”。沃尔什预先在游戏场地上分配了糖果，以便只有在形成最少数量的三糖果链时，黄色柠檬糖才会落入该字段——因此 Candy Crush 任务已成功解决。
这就是沃尔什如何在2014 年 3 月证明 Candy Crush 是 NP-hard 问题，因此从数学角度来看是复杂的。如果您在另一个 Candy Crush 关卡中失败，这可能会让您感到欣慰。但这种复杂性也具有吸引力。正如沃尔什在American Scientist中写道，“这种特性可能是使游戏如此令人上瘾的部分原因；例如，如果它像井字棋一样容易解决，那么它就不会那么吸引人了。”
本文最初发表于Spektrum der Wissenschaft，并经许可转载。