皆様、こんにちは。エンジニアの Hodoshima です。 今回はご存知の方も多いであろうオセロについて、とある研究結果が話題になっていたので、それについて紹介します。

導入

10 月 30 日、査読前の論文を見ることができる arXiv というサーバーに Preferred Networks 社の滝沢拓己博士による "Othello is Solved" というタイトルの論文が投稿されました。

この論文は皆さんがオセロと聞いて思い浮かべる縦横8マスずつ合計 64 マスで行うオセロについて「弱解決」をしたという旨の記載になっています。

強解決と弱解決の違い

"Othello is Solved" では「弱」解決をしたという旨の論文ですが、弱があるということは強もあります。 このオセロの問題における弱解決と強解決の間には以下の相違点があります。

• 弱解決: 初期状態 (4 枚のコマが置かれているゲーム開始時点での配置) から 2 人が勝つために最適な手を選択し続けた場合に最終的な局面がどのようになるかを解明すること。
• 強解決: どのような場面からでも 2 人が勝つために最適な手を選択し続けた場合に最終的な局面がどのようになるかを解明すること。

つまり、弱解決では最終局面を解明するための元の局面がゲームスタート時でなければならないのに対して、強解決においてはスタート時とは限らない全ての局面を元にして最終局面を解明する必要があります。このことから、今回の弱解決は強解決に「ゲーム開始時点から」という条件を付け加えた問題だということがわかります。

オセロの解析の歴史

ちなみに、通常の 8 x 8 よりも小さい 4 x 4 や 6 x 6 でのオセロについては既に研究がされています。結果の一部をここでは紹介します。

• 4 x 4: 黒 3 vs 11 白 (空き 2) で、白が勝つ。
• 6 x 6: 黒 16 vs 20 白で、白が勝つ。 (1993 Joel Feinstein)

なお、 8 x 8 のオセロはこの論文が出る前から、両者が再現を尽くせば引き分けになるであろうと予測されていたそうです。

探索アルゴリズム

この論文では、α-β (読み: アルファベータ) 法という 2 人で行う (実際には適用するための条件がまだある) ゲームに対して、どのような手が最も良いのかを決定するアルゴリズムを元に、さまざまな工夫を行って引き分けであることを求めたと書かれています。

実際、多くの工夫が施されていることが論文には書かれています。ここではその一部を紹介します。

• ゲーム開始時から空きマスが 50 個までの間はゲーム展開の数が (途中に比べて) 比較的少ないので、最初の 10 手くらいならば読み間違えないという 経験則 を利用している (なお、論文中では 「もし推測を用いた探索が誤っていたら、厳密な結果を使って再度推測、探索を行う」という旨の記述がある。)
• 空きマスが 30 個くらいになると完全に展開を読むことができる (らしい) 。 このことを参考にして、空きマスが 36 個の場面で評価値が厳密にわかっているならば、その評価値を返し、わかっていないのであるならば、別の方法で求めたり、暫定的な値を返すことを繰り返すことによって尤もらしい評価値に近づけていく。
• 残りの空きマスが 50 個から 36 個の間については空きマスが 36 個の状態の評価値を参考にして、盤面の評価値の推定や厳密な評価値が存在する範囲を狭めていく作業を繰り返す。
• 計算には Preferred Networks 社が所有するスーパーコンピュータMN-J の CPU を使用している。

そして、この論文では　α-β 法を用いて探索を行ったとありますが、α - β法は「基本的には全探索であるが、見なくても結果が変わらない部分については探索を省略することによって高速化を狙う」アルゴリズムです。ですので、全部見るという非常に計算量のかかる処理を泥臭く、そして経験に基づいて計算量を削除するということに重きが置かれています。

また、何か天才的な特別なアルゴリズムを用いているわけではなく、最終的にはスーパーコンピュータによって計算時間を削減しているのもポイントです。

最後に

今回紹介した論文で使用されたコードが GitHub 上で公開されているので、ここに掲載しておきます。 (GitHub reversi-scripts)

また、この論文には両者が最善手を打ち続けた場合の最終局面の一例が掲載されていたり、このブログでは紹介されていない工夫が書かれているので、興味がある方は是非論文を見ていただけると幸いです。

なお、論文での手法は経験則を用いていたり、プログラムを実行しているため、理論の誤りやバグを含んでいる可能性があり、まだ査読 (チェック) を受けていない論文です。しかし、これからの動向が非常に楽しみです。

ちなみに

この論文を執筆した滝沢氏が所属している Preferred Networks 社では業務時間のうち、 20 % は研究に使ってよい 「20%ルール」 というものがあり、この論文もそのルールを利用して書かれたらしいです。