2012年05月28日

おじゃま掘りで発火されない確率計算 第1回 結論

相手フィールドが以下の状況で、こちらが(相手ツモを確認せずに)追い打ちを打った時に刺さる確率(相手がn手以内に発火できない確率)の計算です。


より詳しい問題設定は前々回の記事を参照して下さい。

何色でもいいので現在手からネクネクまでの3手に一番多く含まれているぷよがk個である確率は、前回の記事で求めたとおり、
P(k≧4) = 616/4096 = 15.0%
P(k=3) = 2040/4096 = 49.8%
P(k=2) = 1440/4096 = 35.2%
でした。

また、冒頭の問題の確率をp(x4*:n)と表すと、
p(x4*:n)=P(k=3)*p(a1*:n-3)+P(k=2)*p(a2*:n-3)
となります。
ただし、p(a1*:n)はn手で欲しい色が1個も来ない確率、p(a2*:n)はn手で欲しい色が2個以上来ない確率を表します。詳しくはこちらのページで。

これらより、相手が2手〜6手引ける場合の確率を計算すると、

p(x4*:2) = 98.4%
p(x4*:3) = 85.0%
p(x4*:4) = 61.0%
p(x4*:5) = 41.7%
p(x4*:6) = 27.6%

となりました。
少ない手数では高確率で刺さりますが、手数が多くなるほど急激に刺さりにくくなっています。
最初の状況では必要ぷよ数が多いものの、相手はネクネクまで見て一番多い色を選んでいるため、残り1個の状態までには簡単に持っていけることが理由だと考えられます。
こちらの追い打ちの長さは、2連鎖(できればおじゃま3段以上のマルチ)が限界といったところでしょうか。
もちろん、相手をあそこまで埋めた時点でぷよ数的にこちらがものすごく不利な場合は3連鎖でも打ったほうがいいかもしれませんが。
結論は以上です。

さて、次の問題ですが、今回は相手がハチイチで本線へのキーを置けていることが不運だったということで、やはりキーが無い場合を考えることになりそうです。(緑はあるけど青へのキーが足りない状況。)


まさに相手におじゃまを送った直後の状況ですね。
まだどういう風に計算するかも決めてないので、次の更新は少し間が開くかもしれません。
1つ面倒な要素は、一度単発でおじゃまを消して本線を発火するという手もあり得る点です。


それと、ちょっと悩んでいる点をメモしておきます。

・そもそも相手がネクネクまで見て手を決めることは可能なのか?現在手とネクストだけを見た場合の最善手にした方が良いか?(2ぷよなら瞬間的にネクネクが表示されるので可能かもしれないが、AC版だとネクネク表示が少し遅いのでAIでも不可能かもしれない?)

・やはりこちら側も(つぶしを打つ側)も相手の現在手・ネクスト・(可能ならネクネクも)把握しておいた上での確率にした方が良いか?(ただし、把握したところで相手が最善手を取った場合のフィールドを再現すれば良いだけなので、今までの問題と解答に変更が生じるわけではない。単に、ネクネクまで置いた状況が問題の状況、ということにすれば良い。)

それでは今回はこの辺で。
posted by むうむ at 21:20 | Comment(0) | ぷよぷよ | このブログの読者になる | 更新情報をチェックする

おじゃま掘りで発火されない確率計算 第1回 解答編

前回の記事で、相手がおじゃま掘りでいずれかの色4つが欲しい状況で、こちらの追い打ちが刺さるかどうかの問題で、以下の部分問題を解くことになりました。
「現在手からネクネクまでの3ツモ(6ぷよ)中に含まれる同色ぷよをの数を4色それぞれについて数え、その最大値をk(2≦k≦6)とします。k≧4、k=3、k=2となる確率をそれぞれ求めなさい。」
詳しくは、前回の記事を参照して下さい。
http://puyopuyonote.seesaa.net/article/271980812.html

この問題を高校数学の問題集で出てもおかしくない文にすると、以下のようになります。
「赤・緑・青・黄の4色の球を6つランダムに選んで並べます。その順列に含まれる赤・緑・青・黄の球の個数をそれぞれ数え、その最大値をk(2≦k≦6)とします。k≧4、k=3、k=2となる確率をそれぞれ求めなさい。」


これは重複順列タイプの確率の問題です。
基本は、(条件を満たす順列の数)/(全ての順列の数)で計算します。
全ての順列の数は、順列の6箇所がそれぞれ4色どれでもいいので(重複順列なので)、4^6=4096通りです。
実は、この4096通りの順列を生成してそれぞれkがいくつか調べるプログラムを書けばコンピュータが勝手に答えを出してくれるのですが、せっかく手計算で解ける問題なので、答えを書いておきます。
なお手計算の結果については、その4096通りの順列を生成するプログラムで答え合わせしているので正しいかと思います。

以下、簡単のため赤=R、緑=G、青=B、黄=Yと表記します。
また、C(n,m)は二項係数nCmを表します。


(1)k=6となる順列
RRRRRR、GGGGGG、BBBBBB、YYYYYYの4通り。


(2)k=5となる順列
RRRRRGの組み合わせを選んだ場合、順列の数はGの場所を考えて、C(6,1)=6通り。
具体的にはRRRRRG、RRRRGR、RRRGRR、RRGRRR、RGRRRR、GRRRRRの6通りです。
今回は5つある色にR、1つだけある色にGを選びましたが、色の選び方は他にもG・RやY・Bなど、4*3=12通りあります。
結局、6*12=72通りです。


(3)k=4となる順列
RRRR??の組み合わせ(?はR以外の任意の色で、1つ目の?と2つ目の?は同じ色とは限らない)を考えます。
2つの?を同一視した順列の数は、2つの?の位置を6箇所から2つ選ぶことを考えて、C(6,2)=15通り。
??の順列の数は、3^2=9通り。(どちらの?もR以外の任意の3色から選ぶため。)
また、今回は4つある色をRにしましたが、これを他の色にした場合も同じです。
したがって、15*9*4=540通り。


(4)k=3となる順列
RRR???の組み合わせを考えます。
???が全て同一色の場合、(3)と同様にするとRRRGGGとGGGRRRの組み合わせを重複して数えてしまうので、???が全て同一色かそうでないかで場合分けします。

(i)???が全て同一色の場合(RRRGGGのパターン)
Rと?は同等なので、順列を改めてaaabbbと表現します。
aaabbbの順列の数は3つのaの位置を考えて、C(6,3)=20通り。
aとbの色の組み合わせは4色から異なる2色を選ぶと考えて、C(4,2)=6通り。
(aが4通り、bが3通りで4*3通りと考えてしまうと、同じ順列を重複してカウントしてしまうことに注意。たとえば、aabbabでa=R、b=Gのときと、bbaabaでa=B、b=Rのときは同じ順列になってしまいます。)
したがって、20*6=120通りです。

(ii)???が全て同一色では無い場合
3つの?を同一視した場合のRRR???の順列の数は(i)と同様にC(6,3)=20通り。
???の色の組み合わせは3^3-3=24通り。(それぞれ赤以外の任意の3色なので3^3、そこから全て同一色になってしまう3通りを引きました。)
Rの部分は他の色でも良いので、色の組み合わせは4*24=96通り。
したがって、20*96=1920通り。

(i)と(ii)を合わせると、2040通りです。


(5)k=2となる順列
組み合わせは、aabbccとaabbcdの2通りがあります。

(i)aabbccの場合
aabbccの順列の数は、6!/(2!*2!*2!)=90通り。
色の組み合わせは、4色から異なる3色を選ぶことを考えて、4通り。
したがって、90*4=360通り。

(ii)aabbcdの場合
aabbcdの順列の数は、6!/(2!*2!)=180通り。
色の組み合わせは、1個しかない色を4色から2色選ぶことを考えて、C(4,2)=6通り。
したがって、180*6=1080通り。

(i)と(ii)を合わせると、1440通りです。


以上より、
P(k≧4)=616/4096 = 15.0%
P(k=3) = 2040/4096 = 49.8%
P(k=2) = 1440/4096 = 35.2%
となります。

この時点で分かるのは、15.0%の確率で相手は3手以内に発火できてしまうということです。
P(k=3)とP(k=2)から分かることは、次回の「結論」でまとめたいと思います。
posted by むうむ at 01:21 | Comment(0) | ぷよぷよ | このブログの読者になる | 更新情報をチェックする

2012年05月26日

おじゃま掘りで発火されない確率計算 第1回 問題編

最近、思いつきでまた確率計算をしたくなったので、多連結同時消し第2弾は後回しにして確率計算第2弾をやりたいと思います。
第2弾は、相手フィールドにおじゃまが降った場合に追い打ちのつぶしが刺さる確率計算がテーマです。
テーマ自体は第1弾の頃から考えてはいたのですが、おじゃまを掘って発火を狙う側の最善手がネクネクまで見て最もたくさん来ているぷよを発火色に使うということになるので、確率計算が面倒で見送っていました。
その上、地形がいい場合は下図のようにとりあえず2色発火(図の場合は赤と黄)を狙うこともでき、その場合はネクネクの次のツモまで考慮していかなくてはならないので面倒です。


しかし最近また時間ができたので、とりあえずできる範囲で計算をやって行きたいと思います。
第1弾とは違って最善手を考えながらの確率計算となるため、おじゃま掘りの最善手考察も同時にやっていくことになります。
そういう意味ではつぶす側としてだけでなく、掘る側としても勉強になるかもしれません。

今回は、ひとまず手計算でも結果が出せるような一番簡単な問題を解きます。
下図のように、相手がおじゃまが降った後に運良くハチイチが来て本線に繋がるキーぷよだけ置けている状況です。


こちら側は、追い打ちを狙っているとしましょう。
相手は、何色でもいいので4つぷよが来れば発火できます。
この状況(相手は伸ばす必要は無くとにかく早く発火したい場合)での相手の最善手は、現在手・ネクスト・ネクネクの3ツモ(6ぷよ)の中で一番多く含まれているぷよを発火色にする(キーが載っているおじゃまぷよを消すように置く)ことです。


左上図の通り発火色は青のラインにしか置けず、鉄ぷよの場所には発火色を置けないので、2色発火は狙えません。
(置いてしまうと、右上図のように最後にゾロが来ないと一発掘りできないので、明らかに悪手です。)

ということで今回考えたい問題は、4色のうちいずれかの色ぷよが4つ必要な場合(かつ現在手で発火色を決める必要がある状況)でn手以内に発火されない確率です。
相手が何を発火色にするかは現在手・ネクスト・ネクネクを見て決定されるので、まず3ツモ(=6ぷよ)の順列を考えます。
その中に同じ色のぷよが4つ以上含まれる場合は2手もしくは3手で発火されてしまい、3つの場合はp(a1*:n-3)の確率で発火されずに済み、2つの場合はp(a2*:n-3)の確率で発火されずに済みます。
p(a1*:n-3)などの記号は第1弾と同じです。
たとえば下図の場合でn手以内に右端緑発火の5連鎖を発火されない確率は、左から順にp(a1*:n)、p(a2*:n)、p(a2*-b1:n)と表記します。


a,b,c,dは色、横の数字は必要な数、「*」は発火色を表し、「:」で区切ってnが「n手以内」を表します。
C(n,m)は二項係数nCmを表します。
ただし、nが大きくなると他の発火ライン(逆発火など)ができる確率が無視できなくなるので、nはそんなに大きくない数だとします。
より詳しい設定は下記のページを参照して下さい。
http://space.geocities.jp/puyopuyo_muumu/sa_probabilities.html

p(a1*:n)、p(a2*:n)は第1弾で計算済みですので、残る問題として「4色からランダムに選ばれる6ぷよの中に存在する同色ぷよの最大数がk個(2≦k≦6)である確率」を考えることにします。
たとえば、赤青赤赤青緑という順列ではk=3、赤青赤青緑黄という順列ではk=2です。
そして、赤・青・緑・黄のぷよをランダムに6つ並べる重複順列について、k=2、k=3、4≦k≦6になる確率をそれぞれ求めろという問題です。(k=4以上はどれも発火できるのでまとめました。)
何だか普通の高校数学の問題集で出てきてもおかしくない確率の問題になりました。
問題集として出すなら、
「4人でじゃんけんをし、勝った1人が1個チョコをもらえます。これを6回繰り返した時、一番多くチョコをもらった人のチョコの数が2個になる確率、3個になる確率、4個以上になる確率をそれぞれ求めなさい。なお、じゃんけんの勝率は全員同じだとします。」
という感じの問題文になるでしょうか。
これなら手計算で十分に解けます。

さて、ここまでで既に長くなってしまったので、解答編はまた改めて書くことにします。
既に計算はしてあるので、間もなくの予定です。
posted by むうむ at 22:23 | Comment(0) | ぷよぷよ | このブログの読者になる | 更新情報をチェックする


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。