神経衰弱(その3)
注:(2001.12.19):加筆修正
もうずいぶん前になってしまいますが、前回(神経衰弱(その2))で私はこんなことを書きました。
・・・3組6枚ならば先手が勝つ確率が7/15、後手が勝つ確率が8/15で、これもやっぱり後手の方が有利です。以下、カードが増えて行くと先手と後手の確率は近づいて行きます。(4組8枚とか偶数組になると、「引き分け」も考慮する必要が出てきます。)
自分で書いておいてなんですが、このコラムを書いている現在、この主張に自信を失っています。 実はつい最近とある方から、「4ペアの時の確率はどうなるんですか?」というご質問をいただきました。 「神経衰弱(その2)」を書いた当時は面倒なので放っておいたのですが、せっかくご質問を戴いたのでちょっと調べてみたところ、どうやら先手・後手の勝率はそんなに単純に50%に近づいていくわけではないらしいということがわかってきました。
まず、前提条件をもう一度整理しておきます。
- カードは同じ種類のものが2枚ずつN種類、全部でN組で2N枚。トランプなら26組52枚。 ただしトランプの場合は本当は13種類4枚ずつですが、今回は単純のためN種類2N枚とします。
- カードは全て伏せて区別がつかないようにします。
- 自分の手番のとき、任意の2枚を開きます。その2枚が同じ種類ならばその2枚が自分のものになり、 続けて2枚開けます。開いた2枚が異なる種類であったらその2枚を同じ場所に再び伏せて、自分の手番は終わりです。
- これをプレーヤーが順番に繰り返し、伏せたカードがなくなるまで続けます。
- 伏せたカードがなくなったとき、自分のカードが多い人が勝ちです。
とりあえず、ペア4組くらいになってくると素朴な場合分けによる確率計算はとても厄介です。 といって一般解はまだ私は求まっていません。 そこで、計算機のプログラムを組んで、機械的に全部の可能性を調べさせることを考えてみました。 考え方としてはカードを開いてゆく場所を1つずつ変えながら調べてゆく方法と、カードを開く場所(順番)は固定しておいて、カードの配列を変えてゆく方法があります。今回は後者の方法、つまりカードの配列のすべての順列パターンを生成し、その1つ1つに対して先手・後手のどちらが勝ったかを調べてゆくというやり方をとりました。
とりあえず今回の検証では、それぞれのプレーヤーは以下のような戦略に従ってカードを開くものとしました。
1. オープンされたカードの中にペアがあればそれを開いて取るここでは、戦略2-2. がポイントです。ここの戦略を変えると、確率が変わります。 その結果は以下のとおりです。
2. ペアがなければ新たに1枚開く
2-1. 開けたものが過去にオープンされたものと同じならばそれをとる
2-2. 開けたものが今まで知っているカードの中になければ、もう1枚新たにあける
図 1 このグラフの横軸の1から6は、実験を行ったカードのペアの数です。縦軸は先手・後手の勝率を表します。 前回書いたように、1ペアでは先手が100%勝ち、2ペアでは先手:後手の勝率は1:2で後手有利、3ペアでは7:8で後手有利でした。 この計算機シミュレーションでも、理論値と全く同じ結果が出ていますので、プログラムの出力は一応信頼できると判断しました。
さて4ペア(8枚)ですが、結果を見ると先手:後手:引き分けの比率は9:4:2で、先手がものすごく有利です。 4ペアになると新たに「引き分け」という状況が発生するのですが、引き分けをすべて後手の勝ち、というということにしたとしてもなお、先手の勝率は60%で極めて有利です。 これを定性的に説明すると、最初に先手が開けた2枚がペアでないとき、後手の1枚目が先手の2枚のどちらかのペアである確率は1/3です。そうでない場合、つまり後手の1枚目が先手の2枚のどちらとも一致しない場合、後手の2枚目が偶然後手の1枚目とペアになる確率は1/5です。従って、先手も後手も1回目はとれない確率が高いのです(6/7 × 2/3 × 4/5 = 16/35)。 この場合、次の手番である先手は、8枚中の4枚の情報を知っているため、大変有利なのです。
では引き分けの可能性のある偶数ペアの場合は先手有利かというと、どうも単純にそういうわけではないらしくて、例えば6ペアの場合は、逆に引き分けをすべて先手の勝ちということにしても、わずかですが後手が有利です。
さらに、引き分けのない奇数ペアの場合、たとえば3ペアと5ペアを比べてみると、グラフからはよくわからないかと思いますが、先手の勝率は3ペアの時は7/15≒0.467 だったのが、5ペアになると 143/315≒0.454 と、若干ですがむしろ有利不利の差が広がっています。
参考までに、引き分けの分を除いて100%になるようにしてたグラフを載せておきます。
図 2 このグラフを見る限りでは、少なくとも勝率は単純に徐々に50%に近づいて行くわけではないということがわかります。
○ さて、7ペア以上の場合はどうでしょうか? 実は、現在の単純なプログラムでは時間がかかりすぎて計算できないのです。カードの順列の数を書き並べてみると
ペア⇒ カードの枚数 順列の数 1ペア⇒ 2枚 2!= 2 2ペア⇒ 4枚 4!= 24 3ペア⇒ 6枚 6!= 720 4ペア⇒ 8枚 8!= 40,320 5ペア⇒ 10枚 10!= 3,628,800 6ペア⇒ 12枚 12!= 479,001,600 7ペア⇒ 14枚 14!= 87,178,291,200 というように、いわゆる「組み合わせの爆発」が起こって、ペアを1つ増やすたびに調べるべき場合の数が数百倍ずつ増えてゆきます。つまり、3ペアならば、コンピュータの中では720回の神経衰弱ゲームをやっているのですが、6ペアになると4億7千9百万回のゲームをプレイして勝敗の記録をつける、ということをやります。手元のパソコンで1時間くらいで作ったいいかげんなプログラムなので速度も遅いのですが、今現在で5ペアを調べるのに十数秒、6ペアを調べるのに30〜40分かかっています。ということは同じプログラムで7ペアを調べようとしたら、計算機を走らせっぱなしで4日くらいかかることになります。8ペアならば1年以上、9ペアならば200年以上です。(ちなみに使っているパソコンのCPUは Pentium III 600MHz です。)
無論これはアルゴリズムが悪いわけで、もっとちゃんと考えればいいんですけれども、今回は「コンピュータの単純作業が増えても自分が考える時間・プログラミングする時間を最小にしよう」という方針にしました。恥ずかしいですけれども今回の議論の元となるデータを生成したプログラムを置いておきます。(pairs.c(9kbyte))
○ 実は、このシミュレーションは、1枚目を開いたときにそれが知らないカードならば、かならずもう1枚新しく開いてしまうという条件で考えています。これは、相手に新しく情報を与えてしまうという点で、最適な戦略ではない可能性があります。それをきちんと考慮しないと正しい「勝率」にはならないようです。
通常のプレイでは、1枚目が新しいカードだったからといって、2枚目に、わざわざ違うと判っている既存のカードを開いたりしないですよね? しかしルール上はこれは許されているプレイなわけです。今回はその部分を考慮しないシミュレーションになっていました。ご指摘下さった方に感謝致します。