【簡単】誰でも分かる「オセロの解決」（解決してみる編） | cloud.config Tech Blog

前回は〇×ゲームを使って二人零和有限確定完全情報ゲームの性質に触れていきました。今回は〇×ゲームを実際に解決していこうと思います。

解決するために必要なこと

ゲームが「先手勝ち」と結論づけるには、後手がどうやっても負けてしまうことを証明する必要があるので、後手が選ぶことが出来る選択肢を全てしらみつぶしに確認する必要があります。またこの時、先手は絶対に勝てる選択肢が一つ分かれば良いので全通りを確認する必要はありません。

反対に、「後手勝ち」と結論づけるには先手が選ぶことが出来る選択肢を全て確認します。

最後に、「引き分け」と結論づけるには上の二つの両方を行い、双方に負けない選択肢があることを確認する必要があります。

実際にやってみましょう。

まず先手は最初に真ん中を埋めます。

次に後手の選択肢をしらみつぶしに確認するので空いている残りの8通りを調べる必要がありますが、この形は左右にも上下にも対称なので実質的には十字方向と斜め方向の2通りしか選択肢がありません。先に十字方向を調べてみましょう。

十字方向を代表して真ん中の上を埋めました。次に先手は真ん中の左を埋めます。

次の後手の選択肢には6通りありますが、先手にはリーチがかかっています。これを防がないと先手の勝ち、つまり負けないことが確定するので深く調べるのは真ん中の右を埋めたときだけで大丈夫です。

次に先手は左上を埋めてみましょう。

ダブルリーチなりました。残り4つの選択肢のどれを埋めても先手の勝ちです。

それでは少し巻き戻して斜め方向を埋めた場合を調べてみましょう。左上に代表してもらいます。

次に先手は真ん中の左を埋めます。

次に先手は真ん中の上を埋めます。

またリーチがかかりました。同じようにリーチを防ぐ選択肢だけ深く調べれば大丈夫です。真ん中の下を埋めます。

この時点で空いているのは3箇所で後手が埋めることが出来るのは残り1箇所です。後手にはリーチがかかっていないので、1箇所しか埋めずに勝つことは明らかに不可能です。

以上から、先手には絶対に負けない方法があることが証明出来ました。

〇×ゲームは先手の方が先にリーチをかけられるので自由度が高く、調べる必要がある選択肢がかなり多くなります。全部丁寧に調べていくと必要な局面図の数が恐ろしいことになってしまうので、次の3つの条件に従って進行の様子をまとめていきます。

それではいきましょう。まず最初の選択肢は9通りありますが、対称を省略すると「真ん中」「十字方向」「斜め方向」の3通りです。

「真ん中」を選んだ場合、後手が負けない進行は次のようになります。

局面が多すぎて頭がごちゃごちゃになってしまいそうですが、ゆっくり確認してみてください。最初の分岐の一番上の局面以外では、後手が負けない選択肢を見つけることが出来ました。

続いて、一番上の分岐からの進行は次のようになります。

おや？最初の分岐の左2つが途中で終わってますね。この次の選択肢はそれぞれ3通りあるはずです。

すみません。出来るだけ見やすい図にしようとするとどうしても描くスペースがありませんでした。この先を口頭で補足します。

途中で終わっている二つの図は、6箇所が埋まっていて残り3箇所です。このとき、後手はあと1箇所埋めることが出来ます。また、これらの局面で先手が揃えることが出来る可能性が残っているのはそれぞれ1列しかありません。つまり、後手はその列を潰すように埋めれば負けることはありません。

この状態の進行を省略することを4つめの条件に追加します。

以上から、先手が最初に真ん中を埋めたときに後手が負けないことを証明することが出来ました。

次に、「十字方向」を選んだ場合、後手が負けない進行は次のようになります。

最初の分岐で全て後手がリーチをかけることが出来て、次に条件4の状態にすることが出来ます。これで先手が最初に十字方向を埋めたときに後手が負けないことを証明することが出来ました。

最後に、「斜め方向」を選んだ場合、後手が負けない進行は次のようになります。

十字方向の進行とほとんど同じです。最初の分岐で後手がリーチをかけて、次に条件4の状態にすることが出来ます。これで先手が最初に斜め方向を埋めたときに後手が負けないことを証明することが出来ました。

以上から、後手には絶対負けない方法があることを証明出来ました。

長くなりましたが、これで〇×ゲームは「引き分け」で解決することが出来ました。オセロに比べて遥かに単純な〇×ゲームでもこれだけの数を調べる必要があります。オセロだと一体どれくらい膨大な数を調べることになってしまうのでしょうか。

今回は〇×ゲームを使って実際にゲームを解決してみました。これであなたもこのゲームは完全に理解したと言っても過言です。

...はい、過言なんです。次の局面を見てください。

この後お互いが最善を選んだ場合の結末が分かりますか？今回のブログでは一度もこの局面が出てきていませんでした。

どうして！解決したはずなのに！！

次回はそんな話を深掘っていきます。