擁有 10²?種變化的黑白棋，被超算破解了

本文來自微信公眾號：返樸 （ID：fanpu2019），作者：嘉偉

撰文 | 嘉偉

A minute to learn, a lifetime to master（學會一分鐘，精通一世功）.

—— 全球黑白棋愛好者都熟知的一句諺語

我相信，大多數(shù) 80、90 后第一次接觸黑白棋，是在名為“文曲星”的電子詞典上。同時，因為黑白棋的“社會地位”遠遠無法和文化傳統(tǒng)厚重的圍棋、自帶精英氣質(zhì)的國際象棋相提并論，或許很多人會認為，黑白棋僅僅是一種簡單易學的兒童棋類游戲。殊不知因為獨特的規(guī)則，黑白棋與其他棋類不同。在局勢變化有限的情況下，例如五子棋或象棋中的殘局，棋手們常能輕易洞察局勢。但黑白棋即便僅空下最后 6 格，計算起來也頗為不易。這種相對復(fù)雜性是由黑白棋的特性所決定的，它并不像其他棋類那樣容易被“一目了然”地理解，因此很容易出現(xiàn)局勢逆轉(zhuǎn)，在游戲后期可能僅用幾個回合就能讓大量對方棋子倒戈，從而扭轉(zhuǎn)局勢。

所以，黑白棋不但擁有理論上驚人的 10²⁸ 種變化組合數(shù)目，同時還需要極深的思維層次。頂級棋手甚至從前中期開始，就得思考最終決戰(zhàn)時的棋法策略。

從下面這一點也可以看出黑白棋的復(fù)雜度之高：更有人氣的五子棋（五連珠）早在 1993 年便已被計算機科學家 Victor Allis 破解（solved），并證明在無特殊開局規(guī)則的情況下，五子棋先行一方存在必勝的策略；但在過去的 30 年里，雖然人類所掌握的算力呈指數(shù)級增長，卻一直無法窮盡黑白棋的所有變化 —— 直到今年 10 月末，日本的計算機科學家滝沢拓己（Hiroki Takizawa）取得了里程碑式突破，宣布破解了黑白棋！

同時，針對黑白棋的研究，還和不久前在 AI 業(yè)界引發(fā)地震的 OpenAI 的管理層“政變”產(chǎn)生了奇妙的聯(lián)系。

不過在進一步展開故事之前，為了方便那些不熟悉黑白棋的讀者，先簡要介紹一下這種棋的規(guī)則與歷史。

什么是黑白棋

黑白棋中文也叫翻轉(zhuǎn)棋，英文叫做 Reversi，或者 Othello。

黑白棋的原型最先在 19 世紀末由英國人發(fā)明，上個世紀 70 年代由日本人長谷川五郎將其發(fā)展和推廣，借用莎士比亞名劇《奧賽羅》（Othello）為這個游戲重新命名（日語“オセロ”），才有了現(xiàn)在大家玩的黑白棋。為何借用莎士比亞名劇呢？是因為劇中男主角奧賽羅是一名黑人，他的妻子是白人。奧賽羅因受小人挑撥，懷疑妻子不忠，最終親手殺死妻子。后來真相大白，他懊悔不已，自殺身亡。黑白棋就借用這個黑人白人斗爭的故事而命名，故而棋子為正反黑白兩面。

有些地方棋子為正反紅、綠兩色，此時也被稱為“蘋果棋”，因蘋果有紅蘋果和青蘋果之分。

基本規(guī)則：

?最標準的開局，棋盤正中央的 4 格先置放黑白相隔的 4 枚棋子。通常黑子先行，雙方輪流落子。

?只要落子和棋盤上任一枚己方的棋子在一條線上（橫、直、斜線皆可）夾著對方棋子，就能將對方的這些棋子轉(zhuǎn)變?yōu)榧悍狡遄樱ǚ婕纯桑?。夾住的位置上必須全部是對手的棋子，不能有空格。并且，只有在可以翻轉(zhuǎn)棋子的地方才可以下子。

?一步棋可以在數(shù)個方向上翻棋，任何被夾住的棋子都必須被翻轉(zhuǎn)過來，棋手無權(quán)選擇不去翻某個棋子。必須是剛下的子夾住對方才能夠給對方棋子翻面，因翻轉(zhuǎn)對方棋子而夾住的棋子是不能被翻面的。

?如果一方?jīng)]有合法的棋步可下，就必須讓對方繼續(xù)下子，直到自己有合法的棋步為止。如果雙方都沒有合法的棋步可下，游戲就結(jié)束。

游戲結(jié)束時棋盤上棋子多的一方獲勝。若棋數(shù)一樣，則為和局。

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

對任何一種棋類的研究，都脫不開德國數(shù)學家策梅洛在 1913 年發(fā)表的著名定理：

在二人的有限游戲中，如果雙方皆擁有完全的資訊，并且運氣因素并不牽涉在游戲中，那先行或后行者當中必有一方有必勝 / 必不敗的策略。

注意，很多人不能正確地理解該定理，甚至認為它不過是一句顯而易見的廢話。為了彰顯定理的意義，請大家先思考一下“石頭剪刀布”的游戲。

在無作弊的情況下，“石頭剪刀布”是一種運氣游戲，它也不存在任何必勝策略。那么我們憑什么可以認為，一個非運氣游戲就一定有一方存在必勝 / 必不敗策略呢？摻雜了運氣成分的游戲和不摻雜運氣成分的游戲誠然有本質(zhì)上的不同，但這絕非顯然，而是需要數(shù)學證明的。

這里提供一個便于理解的通俗化證明思路：我們假設(shè)對弈雙方都是智慧無限的神仙。如果一方在某一步敗了（比如象棋中被將死），那么他在悔一步棋之后仍然是必敗，否則與我們的“無限智慧”矛盾（因為他上一步就走錯了），依次類推，我們知道游戲的勝負在開局就已經(jīng)決定了 —— 也就是有一方有必勝策略。

實際上，策梅洛定理就是完全信息博弈論的基石。由此我們知道，每一種可在有限步數(shù)內(nèi)結(jié)束的常規(guī)棋類游戲，都有一方是必勝或至少是必不敗的。后續(xù)的問題就是：找出存在必不敗策略的那一方。

當我們確認了某游戲里先手或后手一方存在必勝 / 必不敗策略的時候，就說該游戲是 solved game。目前 solved game 還沒有統(tǒng)一的標準譯名，但可以很自然地直接翻譯成已解決或已破解游戲。

對于已破解游戲，還分出三種強度。

超弱解（ultra-weak solution）：理論證明一方可以保證贏得游戲，或者游戲必然平局，但不需要給出具體的贏法或平局法。這種解法只需要借助數(shù)學工具分析游戲的抽象屬性，而不需要窮舉所有的可能性。

弱解（weak solution）：給出一個算法，可以從游戲的初始狀態(tài)開始，保證某個玩家贏得游戲，或者任何玩家都不會輸?shù)粲螒?。這種解法通常需要窮舉游戲樹的所有分支，或者利用預(yù)先生成的數(shù)據(jù)庫。

強解（strong solution）：給出一個算法，可以從游戲的任何狀態(tài)開始，給出最優(yōu)的走法，無論之前的走法是否完美。這種解法需要窮舉游戲樹的所有節(jié)點，或者利用預(yù)先生成的數(shù)據(jù)庫。

在 1993 年，五子棋得以破解。今年 10 月，黑白棋也獲得了弱解。我們現(xiàn)在知道，如果兩個擁有無限計算能力的神仙來下黑白棋，則他們必然是永遠平局。換句話說，黑白棋是非常公平的棋類游戲。先手或后手一方，并未因此獲得微弱的優(yōu)勢。這和高水準的黑白棋棋手的感覺一致。

同時，因為是弱解，來自日本初創(chuàng) AI 研發(fā)企業(yè) Preferred Networks 的生物信息學家和計算機科學家滝沢拓己還窮舉了對弈雙方的從開局開始的最佳策略。

（需要說明的是，人類并未破解圍棋和國際象棋。雖然現(xiàn)在的下棋 AI 遠比人類強大，但它們并沒有找到最正確的走法。它們僅僅是找到了比我們?nèi)祟惛_的走法。）

技術(shù)與意義

在計算機科學的襁褓時期，完全破解象棋等純策略游戲就一直被認為是人類智慧的非凡成就。自那時以來，這也是人工智能（AI）領(lǐng)域的重大課題。早期的研究者包括查爾斯?巴貝奇（Charles Babbage）和克勞德?香農(nóng)（Claude Elwood Shannon）。隨著機器學習技術(shù)和計算能力的提升，人類制造出了擁有超高棋力的 AI（如里程碑式的 AlphaGo），但這些超強 AI 并不能完美地破解這些游戲。不久之前，人們還普遍認為黑白棋也太過復(fù)雜，無法被破解。所以它一直是人工智能領(lǐng)域里的一項宏偉挑戰(zhàn)。

為了破解黑白棋，滝沢拓己用現(xiàn)代技術(shù)強化了上世紀 90 年代就已非常強大的下棋程序 Edax，然后將任務(wù)分解成更易于管理的部分。他先分析了棋盤上剩下 50 個空位的情況，隨后又考察了有 36 個空位時所有有意義的局勢。他驚喜地發(fā)現(xiàn)，似乎現(xiàn)有算力足以支持弱解黑白棋。

他在 Preferred Networks 擁有的名為 MN-J 的超級計算集群上運行了他的程序。該集群包括超算 MN-3，是目前在能效方面排名世界第 11 位（2020 年排名第 1 位）的超算。

最終滝沢在論文“Othello is Solved”中宣布，他破解了黑白棋。這是人類的一項重大成就，展示了計算機科學和人工智能技術(shù)的長足進步。

另一個值得注意的地方在于，破解黑白棋實際需要探索的位置數(shù)量遠遠少于先前研究中的評估量。滝沢認為這是由于他的團隊擁有更精密的搜索算法配置。之前恰恰是因為評估出的計算量非常之大，導致許多人望而卻步。或許這個故事的教益就在于：紙上分析終覺淺，絕知此事要躬行。

黑白棋與 AI

可能日本是黑白棋愛好者最多的國家。據(jù) 2005 年的統(tǒng)計數(shù)據(jù)，在日本，黑白棋愛好者約有 6000 萬人（日本將棋愛好者約 1500 萬人；圍棋愛好者約 500 萬人；國際象棋愛好者約 300 萬人）。

因此，最終由日本的科學家破解黑白棋，可說是順理成章。滝沢期待未來可以在國際象棋上有所突破。國際象棋的復(fù)雜度比黑白棋還要高出 15 個數(shù)量級，破解國際象棋甚至是計算機和 AI 技術(shù)發(fā)展的原動力之一。

不過除了超強 AI，也有人打算反其道而行之。日本 AI 公司 AVILEN 有感于如今的弈棋 AI 過于強大，故而研發(fā)了一款名叫“奧賽羅”的黑白棋對弈 AI，它的目標是盡可能地輸給人類玩家，而不是像其他的 AI 那樣追求勝利。

這個 AI 的原理是通過修改 AI 對黑白棋規(guī)則的理解，讓 AI 每次都選擇對自己最不利的落子，同時給人類玩家最大的優(yōu)勢。這樣，人類玩家就很難輸給 AI，甚至需要用一些特殊的策略才能做到。奧賽羅在網(wǎng)上公開挑戰(zhàn)人類玩家，截至 2019 年 7 月 29 日，它已經(jīng)進行了 22 萬場比賽，只贏了 1000 多場，勝率低于 0.5%。它甚至引來了一些職業(yè)黑白棋手的挑戰(zhàn)，想要看看能否輸給它。

有研究者認為奧賽羅打破了人工智能領(lǐng)域里的常規(guī)思維，展示了 AI 的另一種可能性。它也引發(fā)了一些人們對于 AI 的思考，比如 AI 是否有自己的意志，AI 是否能夠理解人類的情感……

一定程度上，關(guān)于黑白棋的 AI 實驗，確實給上面的思考提供了線索。

11 月 17 日，因開發(fā)出 ChatGPT 和 GPT-4 而一躍成為 AI 領(lǐng)域領(lǐng)航者的 OpenAI 官方，毫無征兆地宣布，原首席執(zhí)行官薩姆 ` 奧特曼（Sam Altman）被董事會解除職務(wù)。這被視為是一場“政變”。后面的劇情更是跌宕起伏，很多細節(jié)至今尚未披露。

其中有一種說法是，OpenAI 在 AI 領(lǐng)域再次獲得了重大突破，他們的首席科學家伊爾亞?蘇茨克維（Ilya Sutskever）因為對最新技術(shù)懷有疑慮，所以不希望把它商業(yè)化，因此和薩姆?奧特曼出現(xiàn)了分歧。最終矛盾激化，引發(fā)了管理層的大清洗。當然，后來我們知道伊爾亞又后悔了，決定站到奧特曼一方反對董事會的決議。

那么 OpenAI 最有可能在哪個方向上獲得了突破呢？其實不久前 Ilya 曾向媒體透露過，他認為：

“訓練大型神經(jīng)網(wǎng)絡(luò)來準確預(yù)測各種文本中的下一個詞時，實際上是在構(gòu)建一個世界的模型。這些文本本質(zhì)上是對現(xiàn)實世界的一種映射。神經(jīng)網(wǎng)絡(luò)正在不斷深入學習世界的方方面面，涵蓋了人類、人類環(huán)境、期望、夢想、動機等各個方面。AI 學習了對人類世界的壓縮、抽象，以及可用的表征方式?！?/p>

上面的說法讓人看得似懂非懂，但用聯(lián)系本文主題的通俗類比，就是我們給 AI 看棋譜，但是不告訴它那是棋譜。最終 AI 學會了下棋，但是又不知道自己在下棋。

OpenAI 是否驗證了這一概念 —— 證明大語言模型（LLM）僅通過學習語言，最終用語言重新表征了世界 —— 我們尚不得而知，但近期另一項黑白棋研究，卻佐證了這一理論。

研究人員利用從大量實際對局游戲中采樣的 2000 萬個序列樣本，訓練一個名為 OthelloGPT 的神經(jīng)網(wǎng)絡(luò)。OthelloGPT 并不了解游戲規(guī)則或輸入序列所代表的游戲概念，它只接觸到文本標記的序列字符串。類似于大型語言模型對自然語言的訓練，OthelloGPT 的訓練目標是預(yù)測序列中接下來可能出現(xiàn)的字符串。

在獲取足夠多的棋譜之后，OthelloGPT 能夠準確預(yù)測未來的合法棋步，即使對于訓練數(shù)據(jù)中從未見過的字符串（也就是棋譜里的序列）也是如此！

OthelloGPT 并不知曉自己在下黑白棋，但是通過閱讀大量的棋譜（由字母和數(shù)字構(gòu)成的字符串），它找到了其中的規(guī)律，在事實上學會了下棋。雖然對 OthelloGPT 來說，它僅僅是在預(yù)測字符串的生成模式。

最后，如果哪位朋友讀罷本文竟對黑白棋產(chǎn)生了興趣，這里推薦一本可在網(wǎng)上找到的入門讀物《黑白棋指南》（Brian Rose 著）。

參考資料

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

• [2] Reversi - Wikipedia

• [3] 日本最弱黑白棋 AI 對戰(zhàn)平臺：最弱オセロ | PROJECTS（プロジェクト） | 株式會社 AVILEN

廣告聲明：文內(nèi)含有的對外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。