任何玩过井字棋的人可能都明白，在双方都不出错的情况下，井字棋总是可以以平局告终。事实上，创建一个无论对手如何走棋都能保证获胜或平局的算法是很容易的。
这是“已攻克”的游戏的一个简单例子——即结果从一开始就已确定。还有许多其他游戏也已被攻克，但也有很多尚未被攻克。
对于博弈论家和计算机科学家来说，攻克一款游戏的难度通常取决于其可能位置的数量。例如，在 6x7 网格上的“四子棋”游戏有 4,531,985,219,092 种可能的局面。计算机科学家在 1988 年解决了这个问题，证明了先手玩家总能迫使获胜。
十亿乘以十亿
跳棋（或称西洋跳棋）的复杂度要高得多，有 500 亿亿种可能的棋盘位置。直到 2007 年，计算机科学家才解决了这个问题，证明了如果双方都完美地对弈，游戏总是以平局告终。
现在，日本一家名为 Preferred Networks 的计算公司的生物信息学家 Hiroki Takizawa 攻克了跳棋游戏（也称为 Reversi），该游戏有 10 的 28 次方种可能的位置。“攻克跳棋游戏，确定双方都没有失误下的对局结果，长期以来一直是计算机科学领域的重大挑战，”Takizawa 说，并宣布：“跳棋游戏现在已经被攻克了。”
跳棋是一款 2 人棋盘游戏，在 8x8 的网格上进行，于 1883 年在英国发明。这款游戏在 20 世纪 70 年代在日本、美国和其他国家开始流行，自 1977 年以来（除了 COVID-19 大流行期间）每年都举办世界锦标赛。
玩家轮流将棋子放在棋盘上，棋子有黑白两面。游戏的独特性在于，当棋子被对方颜色棋子夹住时，可以将黑棋翻成白棋（反之亦然）。这种翻棋机制使得人类玩家难以预判，从而增加了游戏的难度。
当然，计算机算法没有这种烦恼，自 20 世纪 90 年代以来，它们就已经能够击败人类玩家。现在，Takizawa 对其中一个算法——一个名为 Edax 的程序进行了修改，通过穷举法来攻克这款游戏。
这是两个因素促成的。Takizawa 修改了 Edax，使其更适合解决这类跳棋游戏问题，然后将任务分解成更易于管理的部分。他观察了棋盘上已经走了 14 步、还剩 50 个空位的情况，然后又观察了只剩 36 个空位的情况。
然后，他在 Preferred Networks 拥有的一个名为 MN-J 的超级计算集群上运行了他的程序。该集群包括 MN-3，就能源效率而言，它目前是世界上排名第 11 位（2020 年排名第一）的超级计算机。
穷举法
结果是穷举法证明，双方完美对弈会导致平局。
这为能够完美对弈的计算机程序奠定了基础。“跳棋游戏的结论是人类的一项里程碑式成就，”Takizawa 说，可能有些言过其实。
Takizawa 的证明存在潜在问题。数学家们长期以来一直担心计算机证明的可靠性，因为无法知道是否可能发生了计算机错误。
Takizawa 承认这一点。“自然，我们无法完全排除 CPU 或内存故障导致的计算错误，”他承认。“然而，由于绝大多数计算是在具有纠错内存的计算机集群上执行的，我们认为结果几乎无可辩驳。”
那么，对于热衷于攻克游戏游戏的计算机科学家来说，下一步是什么？Takizawa 推测，国际象棋可能是下一个要作为重大挑战来攻克的游戏。然而，这将需要更多的工作。国际象棋的游戏局面数量高达 10 的 43 次方。
Takizawa 认为，如此庞大的搜索空间意味着攻克国际象棋将需要理论上的突破以及计算上的穷举。
如果您有空闲时间，并且能够使用一台备用的超级计算机，不妨试试看！
参考：跳棋游戏被攻克：arxiv.org/abs/2310.19387
