2018年4月12日木曜日

マルバツゲームはベストを尽くせば引き分けになる

マルバツゲームは引き分けになる | 高校数学の美しい物語:

 今回は「高校数学の美しい物語」の中から、マルバツゲームは引き分けになるという話をご紹介したいと思います。マルバツゲームは、三目並べとか様々な呼び名がありますが、アメリカだとTic tac toe、イギリスだとNoughts and Crossesなど、世界的に遊ばれているゲームです。昔黒板に書いたコレ(↓)です。

 ルールは改めていうまでもないでしょう。9つのマスに2人が交互にマルとバツを描いていき、縦・横・斜めの一列に自分のマークが揃うと勝ちというオセロの簡易版のようなゲームです。このゲームは、実は「二人零和有限確定完全情報ゲーム」という種類のゲームで、お互いにベストを尽くせば先手必勝か後手必勝か引き分けのどれになるかが決まっています。そして、マルバツゲームの場合は互いにベストを尽くせば引き分けになることが分かっているのです。

 ただ、やってみると分かるのですが、このゲーム先手が圧倒的に有利に思えます。先手が真ん中にマルを打つと、もう後手は防戦一方です。つまり、このゲームの本質は、後手がベストを尽くして引き分けに持ち込むことができるかどうかにあるのです。そういう意味で、後手のつもりになってベストの手を考えてみましょう。

 まず常套手段で先手が真ん中にマルを打ってきた場合ですが、後手のベストの手は角にバツを打つことです。そうした時の先手のパターンは以下のように4通りありますが、基本的な戦略は相手のリーチを妨害することです。マルとバツが一つずつの時、次の先手はマルを揃えようとしてきます。したがって、下の最初の3つのケースはそれに当たりますが、相手のマルが揃わないようにバツを打ちます。実は最後のケースはコレに当たりませんが、その場合だけ特殊な戦略が必要です。この場合は、先手の戦略は次に右上か左下にマルを打ってダブルリーチに持ち込もうという戦略ですので、右上か左下にバツを打って相手の戦略を潰します。これであとはベストを尽くせば引き分けに持ち込めます。

 次は先手が角にマルを打ってきた場合です。この場合の後手は、遠慮せず真ん中にバツを打ってください。実は先手は、下のように対角線上にマルを打って、次に右上か左下でダブルリーチを狙う作戦ですが、後手が真ん中にバツを打っている時点で先手と後手の有利さが逆転しています。遠慮せず自分のバツを3つ揃えようと打てば(↓)、先手は守らざるを得なくなります。結果的には、このケースも引き分けになります。

 そして、最後は先手が辺にマルを打ってきた場合。このケースも、後手は遠慮せずに真ん中にバツを打ってください。以降の戦略は、先手が最初に角に打ってきたケースと同じです。

いかがでしたか。やっぱり圧倒的に先手有利、というより真ん中に打った方が圧倒的に有利にゲームを進めることができますが、真ん中を取れなくてもベストを尽くせば引き分けに持ち込めるのです。

理論上は完全な先読みが可能であり、双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か引き分けかが決まるという点である。実際には選択肢が多くなると完全な先読みを人間が行う事は困難であるため、ゲームとして成立する。

 「二人零和有限確定完全情報ゲーム」は、理論上は完全な先読みが可能で、互いがベストを尽くせば結果が決まっているのですが、選択肢が多くなると人間が完全な先読みを行なうのは困難になり、ゲームとして成立することになります。そういう意味では、今回のマルバツゲームは人間が完全な先読みできる点で、必ず引き分けに持ち込めますが、他の「二人零和有限確定完全情報ゲーム」である将棋やチェス・オセロ・囲碁などの場合は、選択肢が多すぎて人間には完全な先読みができません。

 つまりゲーム理論からすれば、いくら複雑であろうとも「二人零和有限確定完全情報ゲーム」である限りは、人工知能(AI)などコンピュータが人間を凌駕するのは明らかです。DeepMindのAlphaGoや山本一成氏のポナンザなど、人間のチャンピオンを凌駕するソフトウェアが次々と開発されていますが、理論的にはそれも当然の流れと言えるのかもしれません。

0 件のコメント:

コメントを投稿