拥有 10^28 种变化的黑白棋，被超算破解了！

luyuanhong

拥有 10^28 种变化的黑白棋，被超算破解了！

黑白棋又名奥赛罗棋，别名出处正是莎翁名剧《奥赛罗》——黑白两面象征着主角奥赛罗和他的妻子苔丝狄蒙娜；棋局间的博弈交锋象征着二人的你来我往。现在，科学家借助超算集群，穷尽棋局的所有变化，破解了黑白棋。这对恋人穿过四百多年的嫉妒与背叛、悔恨与泪水，最终以对等的姿态，紧紧相拥在一起。

撰文 | 嘉伟

A minute to learn, a lifetime to master（学会一分钟，精通一世功）。

——全球黑白棋爱好者都熟知的一句谚语

我相信，大多数 80、90 后第一次接触黑白棋，是在名为“文曲星”的电子词典上。同时，因为黑白棋的“社会地位”远远无法和文化传统厚重的围棋、自带精英气质的国际象棋相提并论，或许很多人会认为，黑白棋仅仅是一种简单易学的儿童棋类游戏。殊不知因为独特的规则，黑白棋与其他棋类不同。在局势变化有限的情况下，例如五子棋或象棋中的残局，棋手们常能轻易洞察局势。但黑白棋即便仅空下最后 6 格，计算起来也颇为不易。这种相对复杂性是由黑白棋的特性所决定的，它并不像其他棋类那样容易被“一目了然”地理解，因此很容易出现局势逆转，在游戏后期可能仅用几个回合就能让大量对方棋子倒戈，从而扭转局势。

所以，黑白棋不但拥有理论上惊人的 10^28 种变化组合数目，同时还需要极深的思维层次。顶级棋手甚至从前中期开始，就得思考最终决战时的棋法策略。

从下面这一点也可以看出黑白棋的复杂度之高：更有人气的五子棋（五连珠）早在 1993 年便已被计算机科学家 Victor Allis 破解（solved），并证明在无特殊开局规则的情况下，五子棋先行一方存在必胜的策略；但在过去的 30 年里，虽然人类所掌握的算力呈指数级增长，却一直无法穷尽黑白棋的所有变化——直到今年 10 月末，日本的计算机科学家滝沢拓己（Hiroki Takizawa）取得了里程碑式突破，宣布破解了黑白棋！

同时，针对黑白棋的研究，还和不久前在 AI 业界引发地震的 OpenAI 的管理层“政变”产生了奇妙的联系。

不过在进一步展开故事之前，为了方便那些不熟悉黑白棋的读者，先简要介绍一下这种棋的规则与历史。

什么是黑白棋

黑白棋中文也叫翻转棋，英文叫做 Reversi ，或者 Othello 。

黑白棋的原型最先在 19 世纪末由英国人发明，上个世纪 70 年代由日本人长谷川五郎将其发展和推广，借用莎士比亚名剧《奥赛罗》（Othello）为这个游戏重新命名（日语“オセロ”），才有了现在大家玩的黑白棋。为何借用莎士比亚名剧呢？是因为剧中男主角奥赛罗是一名黑人，他的妻子是白人。奥赛罗因受小人挑拨，怀疑妻子不忠，最终亲手杀死妻子。后来真相大白，他懊悔不已，自杀身亡。黑白棋就借用这个黑人白人斗争的故事而命名，故而棋子为正反黑白两面。


黑白棋的棋子与棋盘。图源：Reversi - Wikipedia

有些地方棋子为正反红、绿两色，此时也被称为“苹果棋”，因苹果有红苹果和青苹果之分。

基本规则：

● 最标准的开局，棋盘正中央的 4 格先置放黑白相隔的 4 枚棋子。通常黑子先行，双方轮流落子。


黑白棋开局。| 图源：日本最弱黑白棋 AI 对战平台最弱オセロ对局界面

● 只要落子和棋盘上任一枚己方的棋子在一条线上（横、直、斜线皆可）夹着对方棋子，就能将对方的这些棋子转变为己方棋子（翻面即可）。夹住的位置上必须全部是对手的棋子，不能有空格。并且，只有在可以翻转棋子的地方才可以下子。

● 一步棋可以在数个方向上翻棋，任何被夹住的棋子都必须被翻转过来，棋手无权选择不去翻某个棋子。必须是刚下的子夹住对方才能够给对方棋子翻面，因翻转对方棋子而夹住的棋子是不能被翻面的。

● 如果一方没有合法的棋步可下，就必须让对方继续下子，直到自己有合法的棋步为止。如果双方都没有合法的棋步可下，游戏就结束。

游戏结束时棋盘上棋子多的一方获胜。若棋数一样，则为和局。

策梅洛定理（Zermelo's theorem）与 Solved game

对任何一种棋类的研究，都脱不开德国数学家策梅洛在 1913 年发表的著名定理：

在二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中，那先行或后行者当中必有一方有必胜/必不败的策略。

注意，很多人不能正确地理解该定理，甚至认为它不过是一句显而易见的废话。为了彰显定理的意义，请大家先思考一下“石头剪刀布”的游戏。

在无作弊的情况下，“石头剪刀布”是一种运气游戏，它也不存在任何必胜策略。那么我们凭什么可以认为，一个非运气游戏就一定有一方存在必胜/必不败策略呢？掺杂了运气成分的游戏和不掺杂运气成分的游戏诚然有本质上的不同，但这绝非显然，而是需要数学证明的。

这里提供一个便于理解的通俗化证明思路：我们假设对弈双方都是智慧无限的神仙。如果一方在某一步败了（比如象棋中被将死），那么他在悔一步棋之后仍然是必败，否则与我们的“无限智慧”矛盾（因为他上一步就走错了），依次类推，我们知道游戏的胜负在开局就已经决定了——也就是有一方有必胜策略。

实际上，策梅洛定理就是完全信息博弈论的基石。由此我们知道，每一种可在有限步数内结束的常规棋类游戏，都有一方是必胜或至少是必不败的。后续的问题就是：找出存在必不败策略的那一方。

当我们确认了某游戏里先手或后手一方存在必胜/必不败策略的时候，就说该游戏是 solved game 。目前 solved game 还没有统一的标准译名，但可以很自然地直接翻译成已解决或已破解游戏。

对于已破解游戏，还分出三种强度。

超弱解（ultra-weak solution）：理论证明一方可以保证赢得游戏，或者游戏必然平局，但不需要给出具体的赢法或平局法。这种解法只需要借助数学工具分析游戏的抽象属性，而不需要穷举所有的可能性。

弱解（weak solution）：给出一个算法，可以从游戏的初始状态开始，保证某个玩家赢得游戏，或者任何玩家都不会输掉游戏。这种解法通常需要穷举游戏树的所有分支，或者利用预先生成的数据库。

强解（strong solution）：给出一个算法，可以从游戏的任何状态开始，给出最优的走法，无论之前的走法是否完美。这种解法需要穷举游戏树的所有节点，或者利用预先生成的数据库。

在 1993 年，五子棋得以破解。今年 10 月，黑白棋也获得了弱解。我们现在知道，如果两个拥有无限计算能力的神仙来下黑白棋，则他们必然是永远平局。换句话说，黑白棋是非常公平的棋类游戏。先手或后手一方，并未因此获得微弱的优势。这和高水准的黑白棋棋手的感觉一致。

同时，因为是弱解，来自日本初创AI研发企业 Preferred Networks 的生物信息学家和计算机科学家滝沢拓己还穷举了对弈双方的从开局开始的最佳策略。

（需要说明的是，人类并未破解围棋和国际象棋。虽然现在的下棋 AI 远比人类强大，但它们并没有找到最正确的走法。它们仅仅是找到了比我们人类更正确的走法。）

技术与意义

在计算机科学的襁褓时期，完全破解象棋等纯策略游戏就一直被认为是人类智慧的非凡成就。自那时以来，这也是人工智能（AI）领域的重大课题。早期的研究者包括查尔斯·巴贝奇（Charles Babbage）和克劳德·香农（Claude Elwood Shannon）。随着机器学习技术和计算能力的提升，人类制造出了拥有超高棋力的 AI（如里程碑式的 AlphaGo），但这些超强 AI 并不能完美地破解这些游戏。不久之前，人们还普遍认为黑白棋也太过复杂，无法被破解。所以它一直是人工智能领域里的一项宏伟挑战。

为了破解黑白棋，滝沢拓己用现代技术强化了上世纪 90 年代就已非常强大的下棋程序 Edax ，然后将任务分解成更易于管理的部分。他先分析了棋盘上剩下 50 个空位的情况，随后又考察了有 36 个空位时所有有意义的局势。他惊喜地发现，似乎现有算力足以支持弱解黑白棋。


粗体标注的路径为一条最佳分支。完美的玩家应按对应位置的粗体对策树行棋。| 图源：OTHELLO IS SOLVED

他在 Preferred Networks 拥有的名为 MN-J 的超级计算集群上运行了他的程序。该集群包括超算 MN-3 ，是目前在能效方面排名世界第 11 位（2020 年排名第 1 位）的超算。

最终滝沢在论文“Othello is Solved”中宣布，他破解了黑白棋。这是人类的一项重大成就，展示了计算机科学和人工智能技术的长足进步。

另一个值得注意的地方在于，破解黑白棋实际需要探索的位置数量远远少于先前研究中的评估量。滝沢认为这是由于他的团队拥有更精密的搜索算法配置。之前恰恰是因为评估出的计算量非常之大，导致许多人望而却步。或许这个故事的教益就在于：纸上分析终觉浅，绝知此事要躬行。

黑白棋与 AI

可能日本是黑白棋爱好者最多的国家。据 2005 年的统计数据，在日本，黑白棋爱好者约有 6000 万人（日本将棋爱好者约 1500 万人；围棋爱好者约 500 万人；国际象棋爱好者约 300 万人）。

因此，最终由日本的科学家破解黑白棋，可说是顺理成章。滝沢期待未来可以在国际象棋上有所突破。国际象棋的复杂度比黑白棋还要高出 15 个数量级，破解国际象棋甚至是计算机和 AI 技术发展的原动力之一。

不过除了超强 AI ，也有人打算反其道而行之。日本AI公司 AVILEN 有感于如今的弈棋 AI 过于强大，故而研发了一款名叫“奥赛罗”的黑白棋对弈 AI ，它的目标是尽可能地输给人类玩家，而不是像其他的 AI 那样追求胜利。

这个 AI 的原理是通过修改 AI 对黑白棋规则的理解，让 AI 每次都选择对自己最不利的落子，同时给人类玩家最大的优势。这样，人类玩家就很难输给 AI ，甚至需要用一些特殊的策略才能做到。奥赛罗在网上公开挑战人类玩家，截至 2019 年 7 月 29 日，它已经进行了 22 万场比赛，只赢了 1000 多场，胜率低于 0.5% 。它甚至引来了一些职业黑白棋手的挑战，想要看看能否输给它。

有研究者认为奥赛罗打破了人工智能领域里的常规思维，展示了 AI 的另一种可能性。它也引发了一些人们对于 AI 的思考，比如 AI 是否有自己的意志，AI 是否能够理解人类的情感……

一定程度上，关于黑白棋的 AI 实验，确实给上面的思考提供了线索。

11 月 17 日，因开发出 ChatGPT 和 GPT-4 而一跃成为 AI 领域领航者的 OpenAI 官方，毫无征兆地宣布，原首席执行官萨姆·奥特曼（Sam Altman）被董事会解除职务。这被视为是一场“政变”。后面的剧情更是跌宕起伏，很多细节至今尚未披露。

其中有一种说法是，OpenAI 在 AI 领域再次获得了重大突破，他们的首席科学家伊尔亚·苏茨克维（Ilya Sutskever）因为对最新技术怀有疑虑，所以不希望把它商业化，因此和萨姆·奥特曼出现了分歧。最终矛盾激化，引发了管理层的大清洗。当然，后来我们知道伊尔亚又后悔了，决定站到奥特曼一方反对董事会的决议。

那么 OpenAI 最有可能在哪个方向上获得了突破呢？其实不久前 Ilya 曾向媒体透露过，他认为：

“训练大型神经网络来准确预测各种文本中的下一个词时，实际上是在构建一个世界的模型。这些文本本质上是对现实世界的一种映射。神经网络正在不断深入学习世界的方方面面，涵盖了人类、人类环境、期望、梦想、动机等各个方面。AI 学习了对人类世界的压缩、抽象，以及可用的表征方式。”

上面的说法让人看得似懂非懂，但用联系本文主题的通俗类比，就是我们给 AI 看棋谱，但是不告诉它那是棋谱。最终 AI 学会了下棋，但是又不知道自己在下棋。

OpenAI 是否验证了这一概念——证明大语言模型（LLM）仅通过学习语言，最终用语言重新表征了世界——我们尚不得而知，但近期另一项黑白棋研究，却佐证了这一理论。


图源：https://openreview.net/forum?id=DeG07_TcZvT

研究人员利用从大量实际对局游戏中采样的 2000 万个序列样本，训练一个名为 OthelloGPT 的神经网络。OthelloGPT 并不了解游戏规则或输入序列所代表的游戏概念，它只接触到文本标记的序列字符串。类似于大型语言模型对自然语言的训练，OthelloGPT 的训练目标是预测序列中接下来可能出现的字符串。

在获取足够多的棋谱之后，OthelloGPT 能够准确预测未来的合法棋步，即使对于训练数据中从未见过的字符串（也就是棋谱里的序列）也是如此！

OthelloGPT 并不知晓自己在下黑白棋，但是通过阅读大量的棋谱（由字母和数字构成的字符串），它找到了其中的规律，在事实上学会了下棋。虽然对 OthelloGPT 来说，它仅仅是在预测字符串的生成模式。

最后，如果哪位朋友读罢本文竟对黑白棋产生了兴趣，这里推荐一本可在网上找到的入门读物《黑白棋指南》（Brian Rose 著）。

参考资料

[1] OTHELLO IS SOLVED，2310.19387.pdf (arxiv.org)

[2] Reversi - Wikipedia

[3] 日本最弱黑白棋 AI 对战平台：最弱オセロ | PROJECTS（プロジェクト） | 株式会社AVILEN

原创 嘉伟 返朴 2023-12-27 08:02 发表于北京