黑白棋又名奧賽羅棋，別名出處正是莎翁名劇《奧賽羅》——黑白兩面象徵着主角奧賽羅和他的妻子苔絲狄蒙娜；棋局間的博弈交鋒象徵着二人的你來我往。現在，科學家藉助超算集群，窮盡棋局的所有變化，破解了黑白棋。這對戀人穿過四百多年的嫉妒與背叛、悔恨與淚水，最終以對等的姿態，緊緊相擁在一起。

撰文 | 嘉偉

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

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

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

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

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

同時，針對黑白棋的研究，還和不久前在AI業界引發地震的OpenAI的管理層「政變」產生了奇妙的聯系。

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

什麼是黑白棋

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

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

黑白棋的棋子與棋盤。圖源：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

轉載內容僅代表作者觀點

不代表中科院物理所立場

如需轉載請聯系原公眾號

來源：返樸

編輯：ArtistET

近期熱門文章Top10

↓ 點擊標題即可查看 ↓

1.最近支原體感染大爆發？也許只是假象

2.頭發到底多久洗一次好？早上洗好，還是晚上洗好？答案…..

3.概率論不存在了？拋了35萬次硬幣後，他們發現兩面的結果不是1:1

4.兩個接觸面一個粗糙，一個絕對光滑，到底會不會產生摩擦力？| No.382

5.德國野豬泛濫沒人敢吃，因為它們體內核輻射超標11倍，來源竟是核爆？

6.機票300元，燃油費110元！我坐的飛機加的是什麼油？

7.100多年前被發現的布拉格峰，真的能幫助人類徹底攻克癌症嗎？

8.如何不使用任何能量冷卻物體？

9.為什麼指尖抽血時要用一根兩端通的透明細長管呢？| No.383

10.宇宙真的建立在數學之上嗎？

點此查看以往全部熱門文章