糖果粉碎' s令人困惑的数学

经过 托比·沃尔什(Toby Walsh)

这个简单的游戏背后隐藏着看似困难的计算问题,这也许就是为什么它如此让人上瘾的原因。

数学 统计数据

当前的问题

这篇文章从发行

2014年11月至12月

第102卷第6号
第430章

DOI: 10.1511 / 2014.111.430

有人说,在城市里,您离老鼠的距离不会超过几英尺。但是如今,您似乎很可能与玩Candy Crush Saga的人相距不超过几英尺。它是目前在Facebook上最受欢迎的游戏。

图片由Global King提供。

广告权利

它已被下载并安装在手机,平板电脑和计算机上超过五十亿次。很大程度上基于此成功,其开发商Global King最近在纽约证券交易所上市,首次公开募股使该公司的估值达到数十亿美元。对于简单的将糖果交换成三个或更多相同部分的链的简单游戏来说,这还不错。

《 Candy Crush》对玩家的吸引力很大一部分在于,看似简单的谜题具有复杂的基础。令人惊讶的是,该游戏也引起了研究人员的极大兴趣:它提供了对数学中最重要的开放性问题之一以及计算机系统安全性的洞察力。

在最近的证明中,我证明了《 Candy Crush》是一个数学上难以解决的难题(该论文可从以下网址获得: http://arxiv.org/abs/1403.1911)。为了证明这一点,我需要引用整个计算机科学中最重要和最美丽的概念之一,即“ 问题减少。 这个想法将一个问题映射到另一个问题,或者就像计算机科学家喜欢说的那样,它将一个问题简化为另一个问题。从本质上讲,出现此概念的原因是计算机代码具有多种用途:即使变量不同,也可以使用同一类型的代码来解决多个问题。如果开始时遇到的问题很困难,那么映射到的问题就必须至少同样困难。第二个问题再简单不过了,因为您必须能够使用能够解决第二个问题的计算机程序来解决第一个问题。而且,如果您能证明相反的话,第二个问题也可以简化为第一个问题,那么从某种意义上讲,这两个问题彼此一样难,并且需要花费相似的时间来解决。

确定问题的难度是数学的基本原则。但这不是语义要点。如果您可以根据问题的难易程度对问题进行分类,那么您就知道可以运用哪种计算能力,即使完全值得尝试解决。在某些方面,至少对于数学家来说,将Candy Crush视为数学问题可能像玩它一样上瘾。

硬解决方案,轻松检查

在对Candy Crush的分析中,我和我的合作伙伴从最著名的一类计算难题开始,称为NP(“不确定性多项式时间”),该术语的“时间”部分表示解决这些问题可能需要花费多长时间。 NP包含所有问题,如果您给我提供解决方案,那么我可以快速检查它是否是正确的答案,而这仅仅是问题大小的多项式函数。但是,首先找到解决方案似乎在计算上具有挑战性。许多此类众所周知的数学问题都属于此类计算难题,例如确定是否可以满足复杂的逻辑公式,或者是否可以对图形进行着色以使相邻节点具有不同的颜色。

在NP类下面,就复杂性而言,我们具有计算上的“简单”问题的P类。在这种情况下,P仅代表多项式。 P包含诸如对列表进行排序或在数据库中查找记录之类的问题。即使在最坏的情况下,高效的计算机程序解决此类问题所花费的时间也很短。从数学上讲,P中问题的运行时间是一个按问题大小缩放的多项式。例如,一种著名的排序算法BubbleSort像土豆比赛中的竞争对手一样,反复“冒泡”将第二个最大的项目排到列表的顶部。该过程花费的时间随着要排序的列表大小的平方而增长。即使我们将列表的大小加倍,在最坏的情况下,该算法也将花费四倍的时间。最糟糕的情况是列表的顺序相反,并且每个项目都必须冒泡通过每个较小的项目。如果列表不是相反的顺序,则算法将停止得更快。

在NP复杂度之上,我们遇到的问题在计算上非常困难。甚至在NP之上甚至存在我们的标准计算模型(我们所有计算机都实现的模型)不足的问题。对于此类问题,没有保证可以停止并返回答案的计算机程序。这些例子属于所谓的不确定的问题类别。此类课程包括诸如决定计算机程序是否会停止而不是在某个循环中永远运行等问题,计算机科学家称这为“ 停止问题。 计算之父之一艾伦·图灵(Alan Turing)证明了暂停问题尚不确定。没有计算机程序可以决定另一个计算机程序是否停止并且本身可以保证停止,因此使它成为一个非常非常困难的计算问题。

NP正好位于容易与困难之间。在NP内部,我们遇到许多具有挑战性的问题,例如如何安排卡车运送包裹,医院的花名册工作人员或学校的课程安排。事实证明,赢得《 Candy Crush》也属于此类。这些问题中的任何一个都可以减少到其他任何一个。从这个意义上讲,他们都是一样的努力。

不幸的是,随着NP问题的增加,我们拥有的最好的计算机程序的运行时间会急剧增加。在我的台式计算机上,我有一个程序,该程序需要几个小时才能找到10辆卡车的最佳路线,并证明该解决方案是最好的。但是对于100辆卡车,相同的程序将花费比整个宇宙更长的时间。从数学上讲,我程序的运行时间是问题大小的指数。

指数很快就变得非常大,如经典寓言中所举例说明的,一个维齐尔人赢得了他想要从苏丹得到的任何奖金,并在棋盘的第一个正方形上要求一粒小麦,然后在随后的每个正方形中将其翻倍。因此,第一个方块上有一个小麦粒,第二个方块上有两个,第三个方块上有四个,依此类推。在董事会的第64个也是最后一个方块上,您将需要18,446,744,073,709,551,615或超过18亿五千万个小麦粒。这大约是数百年来全球小麦产量的总和。指数很快就潜入您。

图片由CBS提供。

尽管计算机科学家广泛同意我的说法,即NP问题在  容易又困难,对于任何特定问题,都无法确定它位于哪一边。我们目前拥有最好的计算机程序,需要花费大量时间来解决NP中的问题。但是我们不知道是否有一些奇异的算法等待发现,它将在多项式时间内有效解决NP问题。 (数学家将此问题缩写为“ P = NP吗?”。)实际上,这是当今数学中最重要,最著名的开放问题之一。克莱数学研究所甚至为解决这个问题提供了100万美元的奖金。自2000年首次颁发以来,该奖项一直无人认领。

在有关P = NP是否正确的最新民意调查中,有83%的计算机科学家认为P不等于NP。也就是说,他们认为没有有效的算法可以解决NP中的问题,而且永远不会有。另一个计算机科学家民意测验被用来决定如何解决像NP中一样难以解决的问题,无论它们是否属于此类。选择的最终名称是比较平淡的NP-hard。但是民意测验确实显示出一种令人耳目一新的幽默感:一些替代性的写法是NP不切实际,NP棘手和NP硬屁股。

问题减少的思想对于P = NP问题至关重要。如果我们确实找到了一种可以有效解决NP中任何一个问题的算法,那么我们也可以有效解决NP中的所有问题。如果这一结果发生,世界将是一个截然不同的地方。从好的方面来说,我们将能够通过更好的时间管理,优化卡车路线,安排时间表的航班以及安排人员来省钱(并经常在Candy Crush中获胜)来度过我们的生活。但是,我们依赖于其他任务(例如破解代码)在计算上具有挑战性,因此我们的密码和银行帐户仍然安全。计算复杂性既可以是福也是祸。我们希望证明黑客很难计算如何解密消息。同样,我们需要能够轻松加密这些消息。

此示例可能使您想起NP的定义:容易检查答案却很难找到答案的问题。密码学就​​是要把计算障碍放在坏人的路上。如果这些障碍消失,我们的现代世界将陷入大麻烦。

游戏背后

为了说明Candy Crush在数学上是一个难题,我们可以将其从NP中的任何问题简化为难题。为了简化生活,我和我的同事从NP中所有问题的祖父那里开始,找到了解决逻辑公式的方法。这称为 可满足性问题。 如果您解决了逻辑难题,那么您将已经解决了此类问题。您必须决定哪些命题是正确的,哪些命题是错误的,以满足一组逻辑公式:英国人住在红房子里。西班牙人拥有这只狗。挪威人住在蓝房子旁边。西班牙人拥有斑马线的主张是对还是错?

为了减少对“ Candy Crush”问题的逻辑困惑,我们利用逻辑电路与电路之间的紧密联系。任何逻辑公式都可以用电路简单表示。毕竟,计算机只是大量逻辑门(AND,OR和NOT)的集合,它们之间通过电线将它们连接在一起。因此,我们需要做的就是证明您可以在Candy Crush游戏中构建电路。

芭芭拉·奥利奇诺的插图。

首先,我们需要一块电路板。该板必须是糖果的中性图案,其中糖果类型相对于其他糖果的顺序永远不会改变(见上图。)糖果拼凑而成,类似于交通信号灯:在偶数列中,我们交替使用红色软心豆粒糖和黄色柠檬滴,而在奇数列中,我们交替使用橙色的锭剂和绿色的口香糖片。在这样的背景下,即使我们上下移动列,也永远不会创建三个相同糖果的链。

在此框架中,我们插入了由紫色簇状糖果制成的电气组件。这些簇将其他糖果推开,而不是覆盖它们。连接这些集群可创建导线,以在电路周围传送信号,还可以将多条导线链接起来,以根据需要进行更复杂的配置(看图)。如果在左侧导线的输入上放置一个紫色簇,则将创建一个由三个紫色簇组成的链。该链被删除,这是游戏基本前提的一部分,该链向下移动受影响列中的糖果,并沿导线传播信号。最终,紫色的簇将出现在右侧的输出中。因此,信号在整个板上传输。

我们还需要用户可以设置的开关,以决定哪些电线处于活动状态。这些开关表示是否将布尔公式中的命题设置为true或false的选择。用户可以上下移动中间的紫色簇。此动作将在左侧或右侧引发一个信号。

最后,我们可以使用这些基本组件在其他紫色群集中构建AND,OR和NOT之类的逻辑门。然后,我们只需要用足够长的导线将开关连接到这些逻辑门,我们就有一个模拟逻辑公式的电路。电路有一个输出位,代表逻辑公式的真相。

观看此过程:

拼图映射

用这些电气逻辑电路来表达,玩《 Candy Crush》的难题在于确定要设置的开关,以便逻辑门正确触发,并且输出位设置为true。这样,我们减少了满足逻辑公式来解决Candy Crush问题的问题。由于满足逻辑公式是一个难题,因此必须解决Candy Crush板。

您也可以显示相反的内容。也就是说,您可以将Candy Crush问题简化为满足逻辑公式。我们只需要写下一系列代表Candy Crush棋盘游戏的公式即可。本质上,您会在播放它的任何程序中找到有关Candy Crush的逻辑描述。因此,《 Candy Crush》比NP中的任何问题都难,并且游戏与解决NP中的所有其他问题一样困难。如果我们有一种有效的方式来玩《 Candy Crush》,我们将有一种行之有效的方式来安排卡车,花名册上的人员或安排课程。另外,如果我们有一种有效的方法来安排卡车,花名册上的工作人员或安排课程,那么我们将有一种有效的方法来玩Candy Crush。这就是减少问题的力量。

计算复杂性既可以是福也是祸。

下次在给定数量的动作中未能解决Candy Crush棋盘时,您可以知道这是一个数学上很难解决的问题,您可以进行自我安慰。确实,这种特征可能是使游戏如此上瘾的部分原因。例如,如果它像井字游戏一样容易解决,那就不会那么吸引人了。

所有这些的核心是问题减少的基本而优美的想法,它使计算机科学家可以将不同计算问题的迷宫简化为较小的基本类别,例如P和NP,计算机科学家称之为复杂性动物园。目前,动物园中大约有500个问题类别,其中包括诸如Δ之类的外来名称2P,LogFew,NEEE和P关闭。 (如果您尚未解决,计算机科学家会喜欢首字母缩写词。)

如果极少数情况表明P等于NP,则复杂度动物园中不同类别的数量将急剧下降。实际上,许多被认为是不同的类会相互映射。另一方面,如果P不等于NP(如大多数计算机科学家所相信的那样),则该动物园正确地包含许多不同的问题类别。实际上,动物园的规模在不断扩大。复杂性动物学家最近引入了新的类来描述用量子计算机解决的问题的复杂性。

减少问题的想法为Candy Crush上瘾者提供了一种有趣的可能性。也许我们可以从人类花费数百万小时解决Candy Crush问题中获利?通过利用问题减少的思想,我们可以在这些难题中隐藏一些实际的计算问题。此类交互也会使其他计算问题受益:每次您通过解决CAPTCHA(您必须键入的单词或数字的无处不在的失真图像之一)来向网站证明您是人而不是机器人时,答案都是正确的帮助Google将旧书和报纸数字化。也许我们应该将Candy Crush拼图用于类似的良好用途。

我们对《 Candy Crush》的研究使我们对这种看似无害的消遣方式深表敬意。它实际上提供了对当今数学中最重要的开放性问题之一的了解,并且该问题的含义扩展到许多实际应用中,例如用于保护银行帐户安全的加密算法。您可能想在下一次被发现要向老板解释这幅大图时 再多一层.

美国科学家评论政策

保持话题。尊重。我们保留删除评论的权利。

请阅读我们的 评论政策 before commenting.