山名琢翔（筑波大学）

オセロが解かれた？！

　"Othello is Solved"というタイトルの論文がarXivに投稿されました^{☆1}．オセロでは，初期局面から双方のプレイヤがミスをせずに打ち続ければ，終局結果は引き分けになると証明できたというのです．

　オセロを「解く」とはどういうことなのか．どうやって解いたのか．また，解かれた後のオセロはどうなるのか．この記事ではオセロを解くということについて解説します．なお，このarXivに投稿された論文"Othello is Solved"は記事執筆時点で査読や追試を経たものではないことに注意すべきです．

オセロを「解く」とはどういうこと？

　ゲーム情報学の分野では，ゲームを「解く」という行為がいくつか存在して，それぞれに名前がついています．具体的には強解決，弱解決，超弱解決の3種類です．論文本体の話題に入る前に，まずはオセロを解くということについての基礎知識を簡単に紹介します．

　強解決とは，オセロの初期局面から合法手を打つことで生まれるすべての局面において，その局面から双方のプレイヤが最善手を打ち続けた場合の勝敗が分かっていて，プレイヤの最善手も分かっている状態を言います．弱解決とは，オセロの初期局面において勝敗が分かっていて，それを証明するために必要な各局面の最善手も分かっている状態です．超弱解決は，オセロの初期局面の勝敗は分かっているものの，最善手については分かっていない状態です^{☆2}．Othello is Solvedという論文では，オセロを弱解決したという内容を扱っています．

　実は弱解決では，強解決と比べて勝敗を証明しなくてはいけない局面の数が非常に少なく済みます．たとえばオセロが引き分けであると証明したい場合，一部の局面は引き分けまたは一方の勝ちを証明するだけでよかったり（図-1において☆をつけた局面），大多数の局面はそもそも何も証明しなくてよかったりします（図-1において★をつけた部分）．このため，強解決よりも弱解決は計算量が少なくなります．

　なお，オセロにおいては本来，勝敗だけでなく自分と相手の石数の差である石差を最大化することが求められるのですが，今回はオセロが引き分けになるという結論ですので，分かりやすく勝敗という言葉で解説します．

どうやってオセロを解いたのか？

　この論文では，オセロを弱解決するにあたって1.5×10^{18}個の局面の勝敗を調べたと報告されています．これは膨大な数で，普通のコンピュータでは現実的な時間で計算できません．ここでは，この大量の局面を処理するための工夫を簡単に解説します．

　オセロは初手から終局まで最大で60手かかります．しかし，60手を愚直に探索するのは非常に大変なので，この論文では初手から10手打つことをまず考え，その中で弱解決のために勝敗を証明すべきと思われる局面を厳選し， 50手読みの局面を2,587個選定しました．そして，これらの50手読みをさらに14手読みと36手読みに分けます．

　この論文では，勝敗の予測を使うことで，結果を証明すべき局面をあらかじめ絞り，後に厳密な探索を使ってその予測が正しかったことを確認するという手法をとっています．序盤10手打ったところで，結果を確認すべき局面を推測を使いながら絞り，残りの50手を厳密に探索して，10手打った局面での勝敗の予測が正しかったことを確認します．また，50手読みに関しても，14手進めたところで勝敗の予測を行って結果を確認すべき局面を列挙し，残りの36手を既存のオセロAIによって厳密に終局まで読み切るようになっています．

　この手数で分けることには，論文内で明記はされていないものの意味を推測することができます．まず，最終36手程度は既存のオセロAIで終局まで厳密に読み切ることができます（ただし，計算時間は多くかかります）．また，序盤の10手程度は，終局まで読み切ることこそできませんが，既存のオセロAIを使って近似的に非常に正確な評価値（その局面から双方が最善手を打ち続けた場合の終局結果）が分かります．この論文では，これらの経験的事実をうまく使ったようです．

　なお，中盤の14手読みに関しては，既存のオセロAIだと正確な勝敗を高速に予測することができなかったようで，多少不正確な予測であろうととりあえず正しいものとして扱っています．これを終盤36手の厳密な探索と合わせて繰り返し行い，探索結果をメモして適宜参照することで徐々に予測を正確なものにしていきます．最終的に予測がすべて正しくなれば，探索終了としています（図-2）．

　実は，このように予測とその検証とを用いる探索手法はAPHID（Asynchronous Parallel Hierarchical Iterative Deepening）という名前でずっと以前に考案されています．APHIDは元々並列探索のためのアルゴリズムでしたが，Othello is Solvedでも弱解決という1つの大きな問題を独立した複数の問題に分けることで，並列化を達成しているようです．

解かれた後のオセロとオセロAI

　実は，オセロプレイヤの間では，オセロが恐らく引き分けになるということはほぼ確実な予測として常識的に存在していました．今回のオセロの弱解決は，この常識を証明した形になります．また，そもそも人間の暗記量には限度があり，最善手をすべて覚えてしまうという行為も困難です．そのため，今回の成果はオセロプレイヤにとってオセロの打ち方に大きな変化を起こすものではないでしょう．

　人間のプレイヤの役に立つよう，オセロAIは今後，もしかしたら「人間のようなミスをするAI」や「良い手の意味を言語化するAI」という方向で発展していくかもしれません．今後の研究分野の発展が楽しみですし，私自身もそういった研究にかかわりたいと思います．

脚注
☆1　Takizawa, H. : Othello is Solved, https://arxiv.org/abs/2310.19387
☆2　田中哲朗：ゲームの解決，https://doi.org/10.11429/sugaku.0651093

（2023年11月30日受付）
（2023年12月15日note公開）