10²⁸通りのバリエーションを持つゲーム「オセロ」がスーパーコンピューターによって解読されました!

オセロは白黒チェスとしても知られており、そのニックネームはシェイクスピアの有名な劇「オセロ」に由来しています。黒と白の面は主人公のオセロと妻のデズデモーナを象徴しています。チェスのゲームは両者の相互作用を象徴しています。現在、科学者たちはスーパーコンピュータークラスターを使用してゲームのすべてのバリエーションを解析し、オセロを解読した。恋人たちは400年以上の嫉妬と裏切り、後悔と涙を乗り越え、ついには平等に強く抱き合った。

著者 |ジアウェイ

学ぶには1分、習得するには一生。

——世界中のオセロファンに知られていることわざ

1980年代から1990年代に生まれた人の多くは、「文曲星」という電子辞書を通じて初めてオセロに触れたのではないかと思います。同時に、オセロの「社会的地位」は、深い文化的伝統を持つ囲碁や、独自のエリート気質を持つチェスと比較できるほどのものではないため、おそらく多くの人は、オセロは単にシンプルで覚えやすい子供向けのチェスゲームだと思っているだろう。オセロは独特のルールを持つため、他のチェスゲームとは異なっていることをあまり知られていません。囲碁やチェスの終盤など、状況のダイナミクスが限られている状況では、プレイヤーは状況を簡単に把握できることがよくあります。しかし、白黒チェスの最後の 6 つのマス目だけが空のままであっても、計算するのは依然として非常に困難です。この相対的な複雑さは、オセロの特性によって決まります。他のチェスゲームのように「一目で」理解できるものではないので、形勢が逆転してしまいやすいです。ゲーム後半では、数ラウンドで多数の相手の駒をあなたに不利に転じさせ、状況を逆転させることもできます。

したがって、オセロは理論的に驚異的な 10^28 通りの組み合わせを持つだけでなく、非常に深いレベルの思考も必要とします。トップクラスのチェスプレイヤーは、序盤から中盤の段階から最終決戦に向けたチェス戦略を考えなければなりません。

オセロの複雑さは、次の点からもわかります。より人気の高い五目並べは、1993 年にコンピューター科学者のビクター・アリスによって解読され、特別な開始ルールがない場合でも、五目並べでは先手が勝つ戦略があることが証明されました。しかし、過去 30 年間で、人間が習得した計算能力は飛躍的に向上したにもかかわらず、オセロのすべてのバリエーションを解明することは不可能でした。今年 10 月末、日本のコンピューター科学者である滝沢弘樹氏が画期的な進歩を遂げ、オセロを解読したと発表しました。

同時に、オセロの研究は、少し前にAI業界に激震をもたらしたOpenAIの経営における「クーデター」とも奇妙なつながりがある。

しかし、先に進む前に、オセロに馴染みのない読者のために、まずこのゲームのルールと歴史を簡単に紹介したいと思います。

リバーシとは

オセロは中国語ではリバーシまたはオセロ、英語ではReversiまたはOthelloとも呼ばれます。

オセロの原型は19世紀後半にイギリス人によって初めて発明されました。 1970年代に日本人の長谷川五郎氏によって開発され、普及されました。彼はシェークスピアの有名な戯曲「オセロ」（日本語では「オセロ」）にちなんでこのゲームの名前を変更し、今日誰もがプレイするオセロが誕生しました。なぜシェイクスピアの有名な戯曲から借用するのでしょうか?これは主人公のオセロが黒人で、その妻が白人だからです。オセロは悪党に唆されて妻の不貞を疑い、最終的に自らの手で妻を殺害した。その後、真実が明らかになると、彼は後悔の念に駆られ自殺した。オセロというゲームは黒人と白人の闘争の物語にちなんで名付けられたため、チェスの駒には黒と白の 2 つの面があります。

オセロのチェスの駒とボード。画像出典：リバーシ - Wikipedia

場所によっては、チェスの駒の表と裏が赤と緑になっています。この時、リンゴを赤リンゴと青リンゴに分けることから「アップルチェス」とも呼ばれています。

基本ルール:

• 最も標準的な開始方法は、ボードの中央にある 4 つのマス目に白と黒のチェスの駒を 4 つ置くことです。通常、黒の駒が最初に動き、両側が交互に動きます。

オセロのオープニング。 |画像出典：日本最弱のオセロAIバトルプラットフォーム、最弱のオセロゲームインターフェース

• 配置するチェスの駒がボード上の自分のチェスの駒と同じ線（水平、垂直、または斜め）上にあり、相手のチェスの駒を挟んでいる限り、相手のチェスの駒を自分の駒に変えることができます（裏返すだけです）。囲まれた位置はすべて相手の駒で占められなければならず、空きスペースがあってはなりません。さらに、ピースは反転できる場所にのみ配置できます。

• 1 回の移動で駒を複数の方向にひっくり返すことができます。また、捕らえられた駒は必ず裏返さなければならず、プレイヤーには駒を裏返さないという選択肢はありません。相手の駒を裏返す前に、相手の駒を先ほど置いた駒で挟んでおく必要があります。相手の駒をひっくり返すことで挟まれた駒はひっくり返すことができません。

• 一方のプレイヤーが合法的な動きを持っていない場合、そのプレイヤーは合法的な動きができるまでもう一方のプレイヤーの動きを続けさせなければなりません。どちらのプレイヤーも合法的な動きをすることができない場合は、ゲームは終了します。

ゲーム終了時に盤上に最も多くの駒を持っている側が勝ちます。駒の数が同じ場合は引き分けとなります。

ツェルメロの定理と解かれたゲーム

チェスゲームの研究は、ドイツの数学者ツェルメロが 1913 年に発表した有名な定理と切り離すことはできません。

2 人の間で行われる有限のゲームにおいて、両方のプレイヤーが完全な情報を持ち、ゲームに運が関与していない場合、最初のプレイヤーまたは 2 番目のプレイヤーのいずれかが勝利/無敵の戦略を持っている必要があります。

多くの人がこの定理を正しく理解しておらず、明らかにナンセンスだと考えていることに注意してください。この定理の重要性を説明するために、まず「じゃんけん」のゲームについて考えてみましょう。

不正行為がなければ、「じゃんけん」は運のゲームであり、勝つための戦略はありません。では、運が絡まないゲームでは、一方が必ず勝つ/避けられない戦略を持っているとなぜ信じることができるのでしょうか?確かに、運が絡むゲームと絡まないゲームの間には根本的な違いがありますが、これは決して明白なことではなく、数学的な証明が必要です。

以下に、理解しやすい一般的な証明を示します。両方のプレイヤーが無限の知恵を持つ神であると仮定します。あるプレイヤーが特定の動き（チェスでチェックメイトされるなど）で負けた場合、そのプレイヤーは動きを撤回した後でも負けになります。そうでない場合は、私たちの「無限の知恵」に矛盾することになります（前の動きで間違った動きをしたため）。同様に、ゲームの結果は最初に決まる、つまり 1 人のプレイヤーが勝利戦略を持っていることがわかります。

実際、ツェルメロの定理は完全情報ゲーム理論の基礎となっています。このことから、有限の回数で終了できる従来のボードゲームでは、必ず勝つか、少なくとも負けないことが確実な側が 1 つあることがわかります。次の質問は、無敵の戦略を持つ側を見つけることです。

ゲームの最初のプレイヤーまたは 2 番目のプレイヤーが勝つ/負けない戦略を持っていることが確認された場合、そのゲームは解決されたゲームであると言います。現在、「解決されたゲーム」には統一された標準的な翻訳はありませんが、自然に「解決された」または「クラックされたゲーム」と直接翻訳できます。

クラックされたゲームには、3 つの強度レベルがあります。

超弱い解決法: どちらか一方がゲームに勝つことが保証されているか、ゲームが必ず引き分けに終わることが理論的に証明されていますが、勝つ方法や引き分けになる方法を具体的に示す必要はありません。このソリューションでは、すべての可能性を列挙することなく、数学的なツールのみを使用してゲームの抽象的な特性を分析する必要があります。

弱い解決策: ゲームの初期状態から開始し、1 人のプレイヤーがゲームに勝つか、どのプレイヤーもゲームに負けないことを保証できるアルゴリズムを提供します。このソリューションでは通常、ゲームツリーのすべてのブランチを徹底的に列挙するか、事前に生成されたデータベースを使用する必要があります。

強力な解決策: ゲームのどの状態からでも開始して、前の動きが完璧であったかどうかに関係なく、最善の動きを与えることができるアルゴリズムを提供します。このソリューションでは、ゲームツリーのすべてのノードを列挙するか、事前に生成されたデータベースを使用する必要があります。

1993年、Gobangはクラックされました。今年10月にはオセロも弱い解を得た。無限の計算能力を持つ二人の神がオセロをプレイすると、必ず引き分けになるということが今ではわかっています。言い換えれば、リバーシは非常に公平なボードゲームです。その結果、先攻または後攻のどちらにもわずかな利点は生まれません。これは、上級オセロプレイヤーの感覚と一致します。

同時に、これは弱い解決策であるため、日本の新興AI研究開発企業であるPreferred Networksのバイオインフォマティクス専門家兼コンピューター科学者である滝沢巧氏は、ゲーム開始時から両プレイヤーにとって最善の戦略も列挙しました。

(人間は囲碁やチェスを解読していないことに注意する必要があります。今日のチェスをプレイする AI は人間よりもはるかに強力ですが、最も正しいプレイ方法を見つけたわけではありません。単に人間よりも正しいプレイ方法を見つけただけです。)

技術とその意義

コンピュータサイエンスの黎明期から、チェスなどの純粋な戦略ゲームを完全に解読することは、人類の知性の驚くべき成果であると考えられてきました。それ以来、人工知能（AI）の分野でも大きな話題となっています。初期の研究者にはチャールズ・バベッジやクロード・エルウッド・シャノンなどがいました。機械学習技術と計算能力の向上により、人間は超高度なチェススキルを持つ AI (画期的な AlphaGo など) を作成しましたが、これらのスーパー AI はこれらのゲームを完全に解読することはできません。つい最近まで、オセロは解読するには複雑すぎると広く信じられていました。したがって、人工知能の分野では常に大きな課題となってきました。

オセロを解くために、滝沢氏は最新の技術を使って、1990年代の強力なチェスプログラムであるEdaxを強化し、さらにその課題をより扱いやすい部分に分割した。彼はまず、チェス盤に 50 個の空きマスが残っている状況を分析し、次に 36 個の空きマスがある意味のある状況をすべて調べました。彼は、既存の計算能力がオセロの弱い解をサポートするのに十分であるように思われることに驚き、うれしく思いました。

太字でマークされたパスが最適な分岐です。完璧なプレーヤーは、対応するポジションの大胆な戦略ツリーに従ってプレイする必要があります。 |出典: オセロは解決した

彼は、Preferred Networks が所有する MN-J と呼ばれるスーパーコンピューティングクラスター上でプログラムを実行しました。このクラスターには、エネルギー効率の点で現在世界第11位（2020年は第1位）にランクされているMN-3スーパーコンピューターが含まれています。

結局、滝沢は論文「オセロを解いた」の中で、オセロを解いたと発表した。これは人類にとって大きな成果であり、コンピュータサイエンスと人工知能技術の大きな進歩を示しています。

もう一つ注目すべき点は、オセロを解読するために実際に探索する必要があるポジションの数は、以前の研究で推定された数よりもはるかに少ないということです。滝沢氏は、これは彼のチームのより洗練された検索アルゴリズムの構成によるものだと考えています。以前は、推定される計算量が非常に多かったため、多くの人がこれを実行することを躊躇していました。おそらくこの話の教訓は、紙の上での分析は表面的なものであり、本当に理解するには実践しなければならないということでしょう。

リバーシとAI

日本はオセロ愛好家が最も多い国かもしれません。 2005 年の統計によると、日本には約 6,000 万人のオセロ愛好家がいます (将棋愛好家約 1,500 万人、囲碁愛好家約 500 万人、チェス愛好家約 300 万人)。

したがって、日本の科学者がついにオセロを解読したのは当然のことでした。滝沢さんは将来、チェスで躍進を遂げることを期待している。チェスの複雑さはオセロの複雑さより 15 桁も高いです。チェスの攻略は、コンピューターや AI 技術の発展の原動力の一つでもあります。

しかし、スーパーAI以外にも、その逆のことを計画している人もいます。日本のAI企業AVILENは、現在のチェスAIが強力すぎると感じ、「オセロ」と呼ばれる白黒チェスAIを開発した。その目標は、他の AI のように勝利を追求するのではなく、人間のプレイヤーにできるだけ負けることです。

この AI の原理は、オセロのルールに対する理解を修正し、AI が毎回自分にとって最も不利な動きを選択しながら、人間のプレイヤーに最大の利点を与えるようにすることです。このように、人間のプレイヤーが AI に負けることは非常に難しく、負けるためには特別な戦略を使う必要があるかもしれません。オセロはオンラインで人間のプレイヤーに公開挑戦します。 2019年7月29日時点で22万回のゲームが行われ、勝ったのは1,000回以上で、勝率は0.5%未満です。プロのオセロプレイヤーたちも、このゲームに勝てるかどうか挑戦してきました。

一部の研究者は、オセロが人工知能の分野における従来の考え方を打ち破り、AIの新たな可能性を示していると考えています。また、AIには意志があるのだろうか、AIは人間の感情を理解できるのだろうかなど、AIについて考えるきっかけにもなりました。

ある程度、オセロに関する AI 実験は上記の考え方の手がかりを提供します。

ChatGPTやGPT-4の開発でAI分野のリーダーとなったOpenAIは11月17日、前CEOのサム・アルトマン氏が取締役会によってその役職から解任されたことを予告なく発表した。これは「クーデター」とみなされた。その後のストーリーはさらに起伏があり、詳細はまだ明かされていない部分が多い。

一つの説は、OpenAIがAI分野で新たな大きな進歩を遂げたが、その主任科学者であるイリヤ・スツケヴァー氏が最新技術に疑問を抱いており、商業化を望んでいないため、サム・アルトマン氏と意見が合わないというものだ。最終的に紛争は激化し、経営陣の大規模な粛清が引き起こされた。もちろん、後にイリヤは再び自分の決断を後悔し、理事会の決定に反対してウルトラマンの側に立つことを決意したことがわかりました。

では、OpenAI がブレークスルーを達成する可能性が最も高いのはどの方向でしょうか?実際、イリヤはつい最近、メディアに対して次のように信じていると明かした。

「大規模なニューラルネットワークをトレーニングして、さまざまなテキストの次の単語を正確に予測するようにすると、実際には世界のモデルを構築していることになります。これらのテキストは、本質的には現実世界のマッピングです。ニューラルネットワークは、人間、人間の環境、期待、夢、動機など、世界のあらゆる側面について常に学習しています。AI は、人間の世界を圧縮、抽象化し、使いやすい方法で表現することを学習します。」

上記の記述は混乱を招くかもしれませんが、この記事のトピックに関連する一般的な例えを使用すると、AI にチェスの記録を示しますが、それがチェスの記録であることを AI に伝えません。結局、AI はチェスの遊び方を学習しましたが、チェスを遊んでいることを知りませんでした。

OpenAI がこの概念を検証したかどうか、つまり大規模言語モデル (LLM) が言語を学習するだけで世界を言語で再表現することを証明したかどうかはまだわかりませんが、最近の別の Othello 研究がこの理論を支持しています。

画像ソース: https://openreview.net/forum?id=DeG07_TcZvT

研究者たちは、多数の実際のゲーム試合からサンプリングされた 2,000 万のシーケンスサンプルを使用して、OthelloGPT と呼ばれるニューラルネットワークをトレーニングしました。 OthelloGPT は、ゲームのルールや入力シーケンスによって表されるゲームの概念を認識しておらず、テキストトークンの連続した文字列のみにさらされています。自然言語の大規模言語モデルのトレーニングと同様に、OthelloGPT のトレーニング目標は、シーケンス内の次の可能な文字列を予測することです。

十分な数のチェスの記録を取得すると、OthelloGPT は、トレーニングデータでこれまで見たことのない文字列 (つまり、チェスの記録内のシーケンス) であっても、将来の正当なチェスの動きを正確に予測できるようになります。

OthelloGPT はオセロをプレイしていることを知りませんでしたが、大量のチェスの記録 (文字と数字の文字列) を読み取ることでパターンを見つけ、実際にチェスのプレイ方法を学習しました。 OthelloGPT の場合、文字列の生成パターンを予測するだけです。

最後に、この記事を読んでオセロに興味を持った方がいたら、ネット上で入手できる入門書「オセロガイド」（ブライアン・ローズ著）をおすすめします。

参考文献

[1] オセロは解決した、2310.19387.pdf (arxiv.org)

[2] リバーシ - Wikipedia

[3] 日本最弱のオセロAI対戦プラットフォーム：The Weakest Osero |プロジェクト（プロジェクト） |株式会社アビレン

この記事は科学普及中国星空プロジェクトの支援を受けています

制作：中国科学技術協会科学普及部

制作：中国科学技術出版有限公司、北京中科星河文化メディア有限公司

特別なヒント

1. 「Fanpu」WeChatパブリックアカウントのメニューの下部にある「特集コラム」に移動して、さまざまなトピックに関する人気の科学記事シリーズを読んでください。