このエントリーは #kosen10s Advent Calendar 2018 7日目のエントリーです。前日の担当はあらやくんで、kosen10s.NullPointerException at AdventCalendar.entry(2018-12-07)

今回はアドベンカレンダーに「オセロの話をします」で登録しましたが、オセロの話の中でもコンピューターによる完全解析の話です。果たしてオセロは完全解析できるのか、そしてそれらを支える技術はどのようなものか解説していきます。

完全解析とは

皆さんもご存知の通り、オセロというゲームは運の要素が介在しえないゲームです。つまりオセロというゲームが作られた時点で先手が必勝なのか、後手が必勝なのか、それとも引き分けなのというのが理論上決まっていることになります。それが実際のところどうなのかをコンピューターで調べるのが完全解析です。他の理論上は完全解析可能な例が、チェスや将棋、囲碁です。

衆知の通り、これらのゲームは完全解析されておりません。なぜなら、これらの問題のサイズが非常に大きく、現代のコンピューターで解くのは難しすぎるからです。この中でもっとも問題サイズが小さいのはオセロなので、それが解析されなければ他のものなど解けるわけがないということになります。

「解析なんてしてどうするの？」
「ロマンです」

いや、まあロマンではあるんですけど、この研究で新たな探索手法が生まれるとかゲームに例えることができる物事へのアプローチが創出されるなどの意味はあります。

※ 厳密には、将棋はルールの穴があり、勝敗引き分けを決められないケースがある。

完全読みと必勝読み

完全解析は、2つの種類に別れます。表題に挙げた「完全読み」と「必勝読み」です。

必勝読みはその名の通り、先後どちらが必勝なのかを解析することを指します。この解析によって得られるのは、先手必勝、後手必勝、引き分けのどれなのかということだけで、手順が一意に定まるわけではありません。必勝読みの結果だけでは、当てずっぽうに言っても正解する確率は三分の一ですから妥当性を検証するのは難しいでしょう。

そこでさらに制約を加え、互いのプレーヤーが完璧にプレイした場合に、どのような手順になるのかを解析するのが完全読みです。こちら結果は先ほどの三択とは違い具体的な手順ですから、追試もしやすくなります。 「完全解析」と言ったときには、一般的に完全読みの結果が求められるようです。

オセロと完全解析

オセロの完全解析について考えてみましょう。まずは、そもそも実時間で計算可能な問題なのかを検討する必要がありそうです。完全解析にかかる時間は、ゲーム終了時の局面がどれくらいのパターンあるのかということに依存しています。オセロの完全解析はいくつか先行研究がありますが、その一つによると最低でも10の22乗あると考えられています。

O(10^22) という計算量の問題は解くことができるのでしょうか？ ここでスーパーコンピューターに解いてもらうことを考えてみます。日本の京コンピューターは10PFLOPSという計算性能を持っています。仮に、1FLOPSで1つの盤面を評価できるとしましょう。すると、京コンピューターは１秒間に10ペタ盤面 = 10の16乗盤面を評価できます。つまり、京コンピューターで最終盤面全てを評価するには、最低でも 10^22 / 10^16 = 10^6 秒 = 277 時間かかることになります……

不可能ではなさそうだけれども、京コンピューターを10日間も占有しなければならないというのは無理そうですね。少なくとも、個人レベルでは解くことができなさそうです。

2018年12月現在において世界最速のスパコンの性能は、京コンピューターのおよそ10倍である140PFLOPSなので、そちらを使ったとしても丸１日かかることになります。ここからさらに10倍の性能を持ったスパコンが現れたとしたら、2時間半程度になるので、スパコンで解くにはそれを待つ必要がありそうです。

より小さな問題

オセロの盤面の大きさは8x8ですが、より小さな6x6や4x8といった盤面サイズはすでに完全解析されています。驚くべきことに、6x6の完全解析は1993年に後手必勝だと報告されています。当時は計算に2週間を要したそうですが、現代のコンピューターであれば、家庭用のものでも100時間程度で解くことができます。ここからは、その問題を解くためのテクニックを紹介します。

ビットボード

オセロの盤面は8x8の64マスからなります。それぞれのマスは黒の石があるか、白の石があるか、それとも石が無いかという状態を持ちます。なんだか64bit整数で管理しやすそうですね。それぞれのビットを盤面に対応させ、石のある位置はビットを立てておくということができるでしょう。このような方式をビットボードと言います。

黒白それぞれの石の位置をがわかれば盤面を表現できるので、64bitの値を2つでオセロの盤面を表すことができます。ビットで盤を表現することは利点が多くあり、盤に対する操作をビット演算で高速に行うことができます。詳細な実装方法に興味のある方は、下記を参照してください。

探索

盤面をビットボードで効率的に表現できたので、次はどのような手が完璧な手なのか探索していく必要があります。 ここで使われる探索手法がミニマックス法とアルファ・ベータ法です。

ミニマックス法は、盤面を列挙してそれらの優劣を評価し、相手の形成が最も悪くなる手を選択するという探索手法です。オセロにおける評価値は最終盤面の石の数とし、最終局面の評価を元により前の盤面の評価が決まります。深さ優先探索かつ全探索をするアルゴリズムで、非常に単純でわかりやすいアルゴリズムです。

しかし、ミニマックス法だと全ての局面を評価しなければならないため、非常に時間がかかってしまいます。それを改良したのがアルファ・ベータ法です。アルファ・ベータ法は、ミニマックス法に加えて探索の枝刈りを行います。ある途中の盤面Aを評価する場合を考えてみます。この盤面に到達するまでの探索で、盤面Aと同じ手数で直近の一手が異なる盤面A’における評価値がいくつか算出されています。今、盤面Aから一手進んだ盤面Bを評価してみます。この時、盤面Bが盤面A’よりも不利だとします。自分は盤面Aを選択すると相手は少なくとも盤面B以上の手を選んでくるわけですから、より自分に有利な盤面A’が判明している以上、盤面Aをこれ以上探索することは無駄になります。そこで、盤面Aの探索を中断し、評価値には盤面Bの値を採用します。このように評価する対象を現状に合わせて間引くことで、探索を効率化することができます。

アルファ・ベータ法は、面白いことに評価値の範囲が狭いほどより多く枝刈りできるという性質を持っています。これは評価値が勝ち・負け・引き分けの3種に限定される必勝読みにおいて非常に有利な性質です。そのため、必勝読みは完全読みに比べて短い時間で解くことができます。

ムーブオーダリング

効率的に問題を解くには、枝刈りを多くする必要があります。候補手の中でより評価値の高いであろう手から探索を行うと枝刈りがされやすくなります。このように、枝刈りがされやすいように候補手の探索する順番を決めることをムーブオーダリングと言います。

例えば「角のマスは優先的に打つ」「角の隣は打たないほうがいい」といった単純な経験則を元に順序づけするだけでも探索範囲が狭まります。より高度な手法としては、それぞれの候補手の盤面を探索しない何らかの方法で推測し、順序を決めるといったことが考えられます。

実装例

実はここまでの知識は、私がオセロの完全解析をしてみようと試みたことで得たものです。私が実際に取り組み、作成した必勝読みのプログラムが以下になります。

ysakasin/othello - GitHub

言語はC++で、コードの規模はおよそ500行、探索にはメガマックス法を少し発展させたネガマックス法を用いています。手持ちのサーバーで実行したところ、完了までに6日間かかりました。およそ140時間となりましたが、貧弱なオンボードAtomマシンで動かしたことを加味しても、完全読みが100時間程度という指標を大幅に超過しているように思えます。

まとめ

オセロの完全解析が実はできるのではないかという想像から、色々と調べたわけですが、検討してみると無茶な妄想だったことがわかりました。個人レベルでは無理ですが、将来さらにスパコン技術が発展したり、Googleが潤沢なコンピューティングリソースを使ってくれれば解けるかもしれません。

また、縮小版オセロの完全解析について簡単に解説をしました。そして、実際に6x6オセロの必勝読みプログラムを作成してみました。6x6はこのような比較的単純な方法で、手元の環境でも解くことができます。しかし、8x8になると、現在のコンピューターで解くことができなくなります。8x8という盤面のサイズは、非常に絶妙なサイズだということが実感できました。

明日12/8の担当も私です。お楽しみに！

参考文献