数学から眺めた五目並べ 🌱
こんにちは。
ちゅんちゅんです 🐣
先日、五目並べをして遊びました。
五目並べは碁盤と碁石を使って2人で戦うゲームです。
黒と白の石を順番に置いていき、
先に石が5個並んだ方の勝ちというシンプルなルールです。
僕は弱くて、いっぱい負けました 😂
悔しくて、勝つためのコツが無いかと思って調べました。
すると、勝つためのコツとは全く関係ないのですが、
n 目並べに関する興味深い定理に出会いました 🌱
ここで、n 目並べとは、
五目並べのルールを「石を n 個並べた方の勝ち」としたゲームです。
定理 1.
n 目並べは、対局者が十分賢ければどんな n でも次のどちらかが成り立つ。
(1) 先手必勝である
(2) 勝負がつかない
この定理の面白いところは、
アルゴリズム的な証明はなく、いわゆる存在定理であるところです。
つまり、先手有利であることは証明されても、
実際に有利に振る舞うための戦略自体は謎に包まれたままなのです！
従って、遊びとしての n 目並べの面白さは
この定理によって全く損なわれません❗
◎ ◎ ◎ ◎ ◎
また、一般の対局ゲームに関する面白い定理も知りました。
ただし、対局ゲームとは、2人で交互に何か行動して戦うゲームです。
定理 2.
運要素のない対局ゲームでは、対局者が十分賢ければ次のどれかが必ず成り立つ。
(1) 先手必勝である
(2) 勝負がつかない
(3) 後手必勝である
つまり、十分に賢い人同士の対局なら、
どんな対局ゲームでも戦う前から勝敗の行方が分かるという定理です。
いくつかの対局ゲームでは (1)〜(3) のどれが成り立つかが知られていて、
具体的な必勝戦略(あるいは引き分けに持ち込む戦略)も解析されています。
例えば三目並べや21ゲームなどは戦略が具体的に解析されています。
21ゲームとは、自然数を小さい順に3つずつまで交互に言い合い、21を言った方の負けというゲームです。
将棋や囲碁なども、運要素のない対局ゲームです。
従って、(1)〜(3) のどれかをみたす戦略が存在していて、
戦う前から勝敗が決まっているということになります。
ところが実際には、将棋や囲碁の戦略の幅は非常に広く、
コンピュータを用いても戦略が解析され切っていません。
従って、将棋や囲碁はまだまだ人間にとって面白いゲームであるといえます🙆
◎ ◎ ◎ ◎ ◎
定理 1 も定理 2 も、証明のためにゲーム理論の知識は必要ありませんでした。
非自明な定理にも関わらず、高校数学までで習う簡単な論理計算だけで証明できて、面白かったです。
以下に、2つの定理の証明をザックリと書いておきます。
◎ ◎ ◎ ◎ ◎
定理 2 の証明.
運要素のない対局ゲーム G を任意にとる。
「G は先手必勝である」 という命題を P とする。
￢P は「G において後手が負けることはない」という意味である。
また、「G は後手必勝である」という命題を Q とする。
￢Q は「G において先手が負けることはない」という意味である。
そして、「G は勝負がつかないゲームである」という命題を R とする。
R は、「先手も後手も負けない」と言い換えられる。
つまり、次が成り立つ。
R ≡ (￢P)∧(￢Q)
このとき、次が成り立つ。
P∨Q∨R
≡ P∨Q∨((￢P)∧(￢Q))
≡ (P∨Q∨(￢P))∧(P∨Q∨(￢Q))
ここで、P∨(￢P) と Q∨(￢Q) は真なので、
(P∨Q∨(￢P))∧(P∨Q∨(￢Q)) も真である。
よって、P∨Q∨R も真である。 ■
◎ ◎ ◎ ◎ ◎
定理 1 の証明.
定理 2 より、次を示せばよい;
n 目並べでは後手必勝があり得ない。
これを背理法によって示す。
後手必勝の戦略 S が存在すると仮定する。
対局者を A さん、B さんと名付けておき、
A さんを先手、B さんを後手とする。
すると、A さんは以下の戦略によって勝つことができてしまう;
まず A さんは第 1 手をてきとーな位置 x に何も考えず打ち、
これを第 0 手だと思い込むことにする。
この思い込みによって、A さんを後手と見なせる。
A さんは、次の番から戦略 S に従って戦う。
ただし、戦略 S の第 k 手で位置 x に石を打つ必要があった時は、
第 k 手をてきとーな位置 y に何も考えず打ち、
第 0 手を位置 y に打ち第 k 手を位置 x に打ったと思い込むことにする。
以上が A さんの戦略である。
S は後手必勝の戦略であり、今 A さんは後手と見なされているので、A さんはこの方法で勝てる。
ところが、実際には後手は B さんなので、
A さんが勝つ結果は後手必勝の仮定に矛盾する。
よって仮定は誤りで、後手必勝の戦略は存在しない。 ■
では。
感想や質問など、なんでも気軽にコメントしてください 🌱
0コメント