admin 百科大全 2023-02-25 12:27:00

《算术与几何的妙趣》由计算机程序引导的最新惊人结果

一开始，没有人尝试对这个复杂游戏进行编程——游戏具有形变的拓扑性质，萌芽很难按照计算机程序要求的那样适用于符号表示。如何表示游戏状态，是个极具挑战性的难题。经过了 24 年的等待，美国匹兹堡卡内基梅隆大学的大卫·阿伯盖特、盖伊·雅各布森和丹尼尔·斯利特于 1991 年提出了一种改进的标记系统。这种标记方法借助字符编码，可以用统一的形式表示众多不同的游戏状态，但从游戏角度看，这些状态其实是等价的。这种有效的表示方法限制了组合的激增，同时，他们采用特殊的编程技术对最优策略进行树状搜索，最终能一直处理到 n=11 的情况。在 n=7 和 8 的情况下，都是第二位玩家取胜。在 n=9、10 和 11 的情况下，先开始的玩家取胜。研究人员在仔细观察这些结果后得出了一个简单的猜想。

萌芽游戏猜想：在初始有 n 个点的萌芽游戏中，若 n 除以 6 的余数是 0、1、2，第二为玩家获胜；若余数是 3、4、5，则第一位玩家获胜。换一个说法，如果依次列举 n=1, 2, 3, 4…的情况，获胜的玩家分别是 2、2、1、1、1、2、2、2、1、1、1、2、2、2、1、1、1……

在 2001 年，威尼斯大学的里卡尔多·佛卡迪和的利雅斯特大学的弗拉米尼亚·路奇奥通过研究游戏的数学性质（“游戏的有关信息”介绍了一些）人工解答了（不借助于计算机）曾被康威认为是不可能的 n=7 情况。用人工方法完成进一步研究似乎是不可想象的，但是，我们将看到人们如何通过一种间接方法实现目标。

最新的进展来自两位法国人，日本北陆先端科学技术大学院大学的助教西蒙·维耶诺和法国康塔尔省在职数学教师朱利安·勒莫瓦纳。他们细致而卓越的工作成果打破了包括人工研究在内的所有纪录。

二人首先对游戏状态的标记系统予以完善，仔细地编程检索“输”状态（即面对完美对手时必输的状态）并存储至计算机系统。存储“赢”状态（即确保每次都能获胜的状态）会占用过多的空间。赢状态比输状态多，是由于其各自定义中已经存在了不对称性：

(a) 根据游戏规则，无法再增加任何新弧线的状态是输状态；

4. 小甘蓝游戏

小甘蓝游戏的规则和萌芽游戏相同，除了在起始时，用可以连接4条弧线的十字代替了点，且在每条新添加的弧线上画一条短线（而不是点），因此，每一步增加了两个弧线端点，扩大了自由度。

这个游戏看起来同萌芽游戏类似，也许更难一点，不过也是一个数学趣味游戏。从 n 个十字开始，游戏一定持续 5n-2 步。若 n 为奇数，先开始的玩家取胜，哪怕每一步都随便乱画。若 n 为偶数，第二位玩家不用动脑子也可以取胜（参见下面一局如何开展）。

下面是证明游戏持续 5n-2 步的推理。

（1）一开始有 4n 个自由度且每一步消耗两个并新增两个，因此，自由度的数目一直都是 4n。

除了最多有 n-1 步例外，每一步都会在图中生成一个新的区域（开始时只有一个区域）。m 步之后，且不产生新区域的 n-1 种可能性被用尽时，恰好有 m-n+2 个区域。

（2）无论怎样做，每一个区域至少包含一个自由度。只要一个区域内有两个或两个以上的自由度，就可以在该区域继续游戏。当只有一个自由度的时候，无法在该区域继续，这便白白消耗了一个自由度。

（3）m 步之后，且不产生新区域的 n-1 种可能性被用尽时，区域的数目就恰好是 m-n+2。自由度数目一直是 4n。

（4）只要 4n 大于 m-n+2 就可以继续游戏，因为这时同一个区域内至少有两个自由度。相反，m-n+2 每步增加一，只要达到与 4n 相等，每个区域包含最少一个自由度且正好包含一个（由于仅有一个而无法被利用），则一局结束。一局游戏准确地持续到 m-n+2=4n 的时候结束，即准确地到 m=5n-2 时，并且再也不会有下一步。

(b) 若从某个状态开始，至少有一种走法能得出一个输状态，该状态就是赢状态；

从以 (a) 点判定为输的无解状态开始，回溯游戏的树状分支，便可以依据 (b) 和 (c) 两点逐步判定所有的状态是赢还是输。

勒莫瓦纳和维耶诺之所以能够成功，关键在于他们引入一种办法，将某些状态分解为若干简单独立的状态，从而逐个处理。他们希望采用新的标记方法以及分解法能够逐步确定越来越多的输状态，通过存储记录，进而超越阿伯盖特、雅各布森和斯利特在 1991 年提出程序所得的结果。实际上，他们通过这种方法已经成功处理了 n=12 和 13 的情况，结果与之前的猜想相符合。然而，他们的程序此后便陷入无用且笨拙的计算，n=13 仍然是个无法超越的极限。为了继续下去，他们借助了一个简单的想法：应该对程序进行指导。

为了确定某个游戏状态本质上到底是输还是赢，并不需要掌握从该状态得出的整个树状分支上的每一种状态。只需找到能得出一个输状态的一种走法，就能由此判定一个赢状态，这也就免除了对游戏其他可能性的判定。因此，掌握一小部分状态就足够了。于是，判定一个赢状态的困难在于哪一种走法能得出输状态。经验以及对游戏的领会能起到帮助作用。我们也注意到，这和西洋跳棋的情况相同。

于是，勒莫瓦纳和维耶诺便开发了一个计算机界面来精准、实时地跟踪程序所进行的试验，并对程序的抉择进行指导，例如让它放弃解答一种状态，而将计算能力专注在另一个被认为更加有意义的状态上。这一如同人机共生的结合奇迹般地解答了一直到 n=44 的所有情况，还有 n=46、47 和 53 这些离散情况。进展如此可观，完全出人意料，已经远远超越了加德纳和康威认为不可企及的 n=8 ！

勒莫瓦纳和维耶诺仍然希望他们的系统能够自己判断得出人类给予的指导建议。尽管经过多次尝试，程序还是无法自动选择应该放弃哪些分支或研究哪些分支。看起来，人类智慧在此处提供建议时，运用了多样而微妙的想法，这些想法来自以往经验和策略性思考，很难通过程序实现。这是一个人工智能问题，虽然目前还不可行，但并不能说明今后也无法实现这样的自动化方法。

两位法国人指出，引导程序来检索最优走法是一件十分有趣的事情，而且令人上瘾。这一程序如今可在网上随意获取。两位编程者提醒用户，使用其交互系统可能对社交生活构成影响，需要当心。

这些结果是对程序进行好几个小时的“引导”才获得的。现在，限制更进一步发展的瓶颈不是机器解决特殊问题所用的时间过长，而是人类用来引导程序从而实现更进一步的时间过长。

勒莫瓦纳和维耶诺小组的成功不止于此。即便受人类指导，计算机证明的结论仍存有疑问：其中不会有错误吧？如何最终验证所得结果？二位英雄用了许多种方法来回答这些问题。首先，他们开发了一个模块，对计算机在指导下的遍历过程中得出的所有输状态进行验证。在论证中寻找捷径，即寻找能够得出相同整体结果，但更小的输状态集合，是一种“后验”的结果验证方法，可以提高可靠性。这一优化方法不禁令人称叹，只需要知道 499 个输状态就可以证明 n=17 的输赢情况，而 1991 年匹兹堡小组的程序在判断 n=11 的情况时则需要 116 299 个状态。（让·保罗·德拉耶）

本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。