「双方にミスがなければオセロは“引き分け”になる」を証明した方法 オセロAI世界1位が解説：Innovative Tech

[山下裕毅，ITmedia]

Innovative Tech：

このコーナーでは、2014年から先端テクノロジーの研究を論文単位で記事にしているWebメディア「Seamless」（シームレス）を主宰する山下裕毅氏が執筆。新規性の高い科学論文を山下氏がピックアップし、解説する。

Twitter: ＠shiropen2

　オセロで初期局面から双方のプレイヤーがミスをせずに打ち続ければ結果は引き分けになることを証明したと主張する論文「Othello is Solved」が、2024年1月にプレプリントとして発表された。

　この論文の日本語解説記事が、情報処理学会が会員向けに月刊で発行する学会誌「情報処理」の2024年2月発行分（65巻3号）において『「オセロが解けた」を白黒ハッキリさせようじゃないか』と題して掲載。この解説記事を書いたのは、CodinGameにおける「Othello」という常設のプログラミングコンテストで世界1位を経験した山名琢翔氏（現在、筑波大学を休学中）である。ここでは、その内容を簡潔に紹介したい。

学会誌「情報処理」（63巻3号）の『「オセロが解けた」を白黒ハッキリさせようじゃないか』ページの一部切り抜き

　ゲーム情報学の分野では、ゲームを解くことに「強解決」「弱解決」「超弱解決」という3種類が存在し、該当の論文では「弱解決」を適用している。弱解決とは、ゲームの初期局面から勝敗が明らかであり、その勝敗を導くために必要な各局面での最善手が特定されている状態を指す。この定義に基づき、オセロにおいては双方が最初から最後まで最善手を打ち続けると、結果として引き分けになることを明らかにした。

　論文では、オセロを弱解決するために1.5×10^18個の局面を分析したことを報告。これは通常のコンピュータでは時間的に計算しきれない膨大な数であるため、効率化のための工夫を施した。

序盤の局面選定

　オセロは初手から終局まで最大60手存在するが、全ての手順を直接探索することは困難である。そのため、最初の10手に焦点を当て、その中で弱解決のために勝敗の証明が必要と思われる局面を選び出した。

　この序盤10手に関しては、既存のオセロAIでは正確な勝敗予測が難しいが、評価値を基に勝敗に影響を及ぼす局面を予測できた。この予測を基に、近似的に正確な評価値を用い、残りの50手読みを探索する対象として2587個の局面を選定した。

局面の細分化

　選出された2587個の局面は、50手読みからさらに14手読みと36手読みに分けて探索する。

勝敗予測とその検証

　序盤10手の局面選定後、その後の50手読みにわたる厳密な探索を行い、序盤10手の勝敗予測の正確性を検証する。50手読みでは、14手読みで勝敗の予測を行い、その予測に基づいて残りの36手読みを既存のオセロAIを使って厳密に探索し、予測の正確性を検証する。

終盤の厳密な探索

　中盤の14手読みでは、オセロAIによる正確な勝敗予測が難しいため、取りあえず不正確な予測を基にして進める。しかし、終盤の36手読みについては、既存のオセロAIを用いた厳密な探索が可能であり、この段階での探索を繰り返すことで、中盤の14手読みの予測の正確性を徐々に高める。最終的に全ての予測が正しいと確認できれば、探索を終了する。

証明すべき局面の例

14手読みと36手読みの局面に分ける工夫をした

　このように局面を細分化することで、計算コストを大幅に削減しながら弱解決に至った。このような予測とその検証とを用いる探索手法は「APHID」（Asynchronous Parallel Hierarchical Iterative Deepening）アルゴリズムとして以前から知られている。

　APHIDは、大きな問題を独立した複数の小問題に分割し、それらを並列に解くことで、効率的に問題を解決する手法である。オセロの弱解決でも、弱解決という大きな問題を小問題に分割することで、並列探索を実現した。

　noteの記事はこちら。

Source and Image Credits: 山名 琢翔. 「オセロが解けた」を白黒ハッキリさせようじゃないか. 情報処理学会 情報処理, 65巻3号 134 - 136ページ 2024-02-15