先日、「Othello Is Solved」（オセロは解決された）という論文が発表されました。その論文では、オセロは両者が最善を尽くした場合引き分けになると述べられています。何だか面白そうですが難しい話ですね。

今回はこの内容が分かった気になれるように、一緒に１から勉強していきたいと思います。まず第一弾は、オセロのようなゲームにおける「解決」とは何かというところから理解していきましょう。

ゲームの性質

オセロは二人零和有限確定完全情報ゲームに分類されます。漢字が多すぎてちんぷんかんぷんですね。簡単に言うと運要素が無い１対１のボードゲームです。

このゲームには全知全能の神同士の対戦結果(お互いが最善を選び続けた結果)が理論上必ず存在するという性質があります。この性質を持つゲームの中で比較的単純な〇×ゲームを例にしてイメージを掴んでみましょう。

〇×ゲームの局面

このゲームは常に「先手勝ち」「後手勝ち」「引き分け」の3つの状態に分類することが出来ます。具体例を挙げてみましょう。

〇が先手のとき、次に左下を埋めれば勝ちですね。このとき後手がそれを防ぐ術はありません。つまりこの局面は「先手勝ち」に分類されます。

ところが次に先手がミスをしたらどうでしょう。

間違って真ん中の下を埋めてしまいました。次に後手が右上を埋めれば勝ちですね。つまりこの局面は「後手勝ち」に分類されます。

また別のミスをした場合を考えてみましょう。

間違って右上を埋めてしまいました。後手はここから勝つことは出来ませんが、次に左下を埋めることで引き分けに持ち込むことが出来ます。つまりこの局面は「引き分け」に分類されます。

これらから〇×ゲームは最善を尽くした場合の結果は常に決まっていて、そこからミスすることでその状態が移り変わっていくという性質があることが分かります。オセロも同様の性質を持っています。

それでは1枚目の状態から1手戻ってみましょう。

先手にダブルリーチがありますね。これでは後手はどうしようもありません。これも「先手勝ち」に分類されます。

さらに1手戻って...を繰り返してゲーム開始まで戻ってみましょう。

これは「先手勝ち」「後手勝ち」「引き分け」のどの局面に分類されるでしょうか。何回か遊んだことがある人なら「引き分け」ではないかという感覚があるかもしれません。正解です。厳密な調べ方は続編で紹介したいと思います。

このように、初期状態の局面の分類が分かれば、このゲームが解決したと言えるわけです。（実は解決にも種類があるのでその話もまた続編に）

まとめ

今回はゲームの解決について少しだけイメージを掴んでみました。冒頭で紹介した論文は、一言でまとめるとオセロの初期状態は「引き分け」だと分かったという内容です。言い換えると、オセロで負けた時は確実に何かしらミスをしているということですね。

第二弾では〇×ゲームを最初からサクッと解決してみたいと思います。