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

０．はじめに

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

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


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

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

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

１．フィールドの状態の分類

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

２．確率計算

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

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

２手目を引いたとき、各状態になる確率は、
状態①　(状態①から状態①)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 0 0)と表せる。

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

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

４．エクセルで行列を計算する

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

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

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

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

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

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

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

５．おわりに

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

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

ぷよキャンのカテゴリの「連鎖」は「マルコフ連鎖」のことかもしれない・・・（？）