616

連鎖発火確率をマルコフ連鎖を利用してExcelで計算する手順

by
めと
めと
0.はじめに

問題
あと2個で連鎖が打てる状況です。
これを5手以内に赤、緑と引いて発火できる確率は?

A.約59%
B.約69%
C.約79%
D.約89%


直感的にどれくらいだと思いますか?
対戦中に潰しが刺さりそうかとかで
確率が気になる場合多いんじゃないですか?

この記事では確率の計算方法を簡単に書きます
(発火に必要な数が4個以上になるととても大変なので)

この記事の決まり
ネクストぷよは一切考慮しない(3個発火からネクスト考慮すると確率が上がるパターンがあるがとても複雑)
不要なぷよは連鎖の邪魔にならないところに置ける

1.フィールドの状態の分類

これは3つの状態に分けることができる
①初期状態 発火するには赤と緑が必要な状態
②中間状態 赤が来たので、発火には緑が必要な状態
③完成状態 赤と緑が来たので発火できる状態 

2.確率計算

組ぷよが1手来るときを考える。
状態①から②に移行する確率は
赤を含み、緑を含まない組ぷよが来る確率なので 5/16
状態①から③に移行する確率は
赤と緑を両方含む組ぷよが来る確率なので 2/16
状態②から③に移行する確率は
緑を含む組ぷよが来る確率なので 7/16
残りの場合は状態移行しない(同じ状態)

1手目を引いたとき、各状態になる確率は
状態① 9/16
状態② 5/16
状態③ 2/16

2手目を引いたとき、各状態になる確率は、
状態① (状態①から状態①)9/16×9/16 = 81/256
状態② (状態①から状態②)9/16×5/16+(状態②から状態②)5/16×9/16 = 90/256
状態③ (状態③から状態③)2/16+(状態①から状態③)9/16×2/16+(状態②から状態③)5/16×7/16 = 85/256
ここで、既に(1手目で)発火できている場合も状態③とする。

このように計算するのはとても大変・・・
なので、行列を用いて計算する。

3.推移行列

確率計算により以下の状態遷移図が描けた。
(このような状態遷移図で表せるものを「マルコフ連鎖」という。)


これを行列の形で計算する。
1手目のぷよを引く前の確率は状態①なので
(1 0 0)と表せる。

これに、遷移行列を右から掛ける。(行列の掛け算はA×BとB×Aが一致するとは限らない)
遷移行列はこのように作ることができる。
1行目 状態①から状態① 状態①から状態② 状態①から状態③
2行目 状態②から状態① 状態②から状態② 状態②から状態③
3行目 状態③から状態① 状態③から状態② 状態③から状態③
のように3×3行列を書く。
(9/16 5/16 2/16
   0    9/16 7/16
   0      0      1    )
これを計算すると・・・
(9/16 5/16 2/16)となる。
これは1手目を引いたときの各状態の確率と一致している。

今度は、(9/16 5/16 2/16)に遷移行列を右から掛ける。
これを計算すると・・・
(81/256 90/256 85/256) となる。
これは2手目を引いたときの各状態の確率と一致している。
以下、3手目、4手目、・・・と計算できそうだ!
しかし、手で計算するのは大変・・・

4.エクセルで行列を計算する

繰り返し計算はコンピュータが得意とするところ。
今回はエクセルで計算する。

手順①
遷移行列を打ち込む。今回はB2~D4の3×3セルの部分。
分母の16はE7セルに避けておいた。

手順②
初期状態(1 0 0)を打ち込む。今回はB6~D6の部分。

手順③
手数を打ち込む。今回はA7~A11の部分。
分母の手数乗の値をE7~E11に書いておく。

手順④
行列を計算する。
・※B7~D7を3セルまとめて選択する。(答えの領域を選択)
・「=MMULT(」と打ち込む。(行列の掛け算をするということ)
・※B6~D6を3セルまとめて選択する。(掛けられる行列を選択)
・「,」と打ち込む。(掛けられる行列の確定)
・B2~D4を9セルまとめて選択する。(掛ける行列を選択)
・「)」と打ち込む。(掛ける行列の確定)
・ Ctrlキー・Shiftキーを押しながらEnterキーを押す。(答えの出力)
これを下の行で繰り返す。※のある部分を1つ下のセルにずらしていく。
失敗するとエクセルが固まりやすいのでこまめに保存する。

手順⑤
確率を計算する。
・F7セルを選択し、「=D7/E7」と入力して確定する。
・F8セルを選択し、「=D8/E8」と入力して確定する。
これを下の行で繰り返す。(オートフィルを使うと便利)

これで5手以内に発火できる確率が求まった。
F11セルの「0.78726」

5.おわりに

冒頭の答えは C.約79%
直感と一致していましたか?
応用すれば他の場合も計算できます。
一度計算しておくと潰しが決まるか考えやすいかも?

詳しい数学的背景が知りたい方は「マルコフ連鎖」で検索してみてください

ぷよキャンのカテゴリの「連鎖」は「マルコフ連鎖」のことかもしれない・・・(?)
作成日時:2021/05/13 20:03
コメント( 0 )
コメントするにはログインが必要です
シェア