tomohxxの日記

麻雀プログラミング

一人麻雀における和了確率を書き下す(2)

はじめに

前回の記事で一人麻雀の和了確率を扱いました。当初2回目を書く予定はなかったのですが、行列を使った解き方のほうが見通しが良さそうなのでこの記事を書くことにしました。また前回は一向聴の手だったので今回は二向聴の手を扱うことにします。

二向聴形の和了確率

二向聴の手があって一向聴になるのに必要な牌の枚数を a_0枚、そこから聴牌するのに必要な牌の枚数を a_1枚、そこから和了するのに必要な牌の枚数を a_2枚とします。 S枚の牌があるとして、 t巡目に二向聴である確率を p^{(0)}_t、一向聴である確率を p^{(1)}_t、聴牌である確率を p^{(2)}_t、和了である確率を p^{(3)}_tとするとこれらは以下の連立確率漸化式で表せます。なお前回と同様に捨てた牌を再び引けるという復元抽出を想定しています。

\left\{ \begin{aligned} p^{(0)}_{t+1} &= \left( 1- \frac{a_0}{S} \right) p^{(0)}_t & p^{(0)}_0 &= 1 & (1) \\ p^{(1)}_{t+1} &= \left( 1- \frac{a_1}{S} \right) p^{(1)}_t + \frac{a_0}{S} p^{(0)}_t & p^{(1)}_0 &= 0 & (2) \\ p^{(2)}_{t+1} &= \left( 1- \frac{a_2}{S} \right) p^{(2)}_t + \frac{a_1}{S} p^{(1)}_t & p^{(2)}_0 &= 0 & (3) \\ p^{(3)}_{t+1} &= \frac{a_2}{S} p^{(2)}_t + p^{(3)}_t & p^{(3)}_0 &= 0 & (4) \end{aligned} \right.

ここで

\begin{aligned} & q^{(0)}_t = \frac{a_0 a_1 a_2}{S^3} p^{(0)}_t,\ q^{(1)}_t = \frac{a_1 a_2}{S^2} p^{(1)}_t,\ q^{(2)}_t = \frac{a_2}{S} p^{(2)}_t \\ & \alpha_0 = 1-\frac{a_0}{S},\ \alpha_1 = 1-\frac{a_1}{S},\ \alpha_2 = 1-\frac{a_2}{S} \end{aligned}

とすると、

\left\{ \begin{aligned} q^{(0)}_{t+1} &= \alpha_0 q^{(0)}_t & q^{(0)}_0 &= (1-\alpha_0) (1-\alpha_1) (1-\alpha_2) & (5) \\ q^{(1)}_{t+1} &= \alpha_1 q^{(1)}_t + q^{(0)}_t & q^{(1)}_0 &= 0 & (6) \\ q^{(2)}_{t+1} &= \alpha_2 q^{(2)}_t + q^{(1)}_t & q^{(2)}_0 &= 0 & (7) \\ p^{(3)}_{t+1} &= q^{(2)}_t + p^{(3)}_t & p^{(3)}_0 &= 0 & (8) \end{aligned} \right.

となります。(8)式を形式的に解くと

\displaystyle{ p^{(3)}_t = \sum_{u=0}^{t-1} q^{(2)}_u \qquad (t \ge 1) \tag{9} }

となるので q^{(2)}_tを求めればよいです。(5)式から(7)式を以下のように行列で表します。

Q_{t+1} = A Q_t,\ Q = \begin{pmatrix} q^{(0)}_t \\ q^{(1)}_t \\ q^{(2)}_t \\ \end{pmatrix},\ A = \begin{pmatrix} \alpha_0 & 0 & 0 \\ 1 & \alpha_1 & 0 \\ 0 & 1 & \alpha_2 \\ \end{pmatrix} \tag{10}

(10)式より Q_t = A^t Q_0となります。ここで a_0, a_1, a_2はそれぞれ異なるので行列 Aは対角化可能であり固有値は \alpha_0, \alpha_1, \alpha_2です。正則行列 Xと対角行列 Bが存在して B = X^{-1} A Xが成り立つので A^t = X B^t X^{-1}となります。よって Q_t = X B^t X^{-1} Q_0が得られます。 B^tは

B^t = \begin{pmatrix} \alpha_0^t & 0 & 0 \\ 0 & \alpha_1^t & 0 \\ 0 & 0 & \alpha_2^t \\ \end{pmatrix}

なので

q^{(2)}_t = c_0 \alpha_0^t + c_1 \alpha_1^t + c_2 \alpha_2^t \tag{11}

のように表せます。初期条件 q^{(2)}_0 = q^{(2)}_1 = 0,\ q^{(2)}_2 = q^{(0)}_0より各係数を決めると、

\begin{aligned} c_0 &= \frac{q^{(2)}_0}{(\alpha_0-\alpha_1)(\alpha_0-\alpha_2)} \\ c_1 &= \frac{q^{(2)}_0}{(\alpha_1-\alpha_0)(\alpha_1-\alpha_2)} \\ c_2 &= \frac{q^{(2)}_0}{(\alpha_2-\alpha_0)(\alpha_2-\alpha_1)} \\ \end{aligned}

となります。よって q^{(2)}_tは

\displaystyle{ q^{(2)}_t = (1-\alpha_0) (1-\alpha_1) (1-\alpha_2) \left\{ \frac{\alpha_0^t}{(\alpha_0-\alpha_1)(\alpha_0-\alpha_2)} + \frac{\alpha_1^t}{(\alpha_1-\alpha_0)(\alpha_1-\alpha_2)} + \frac{\alpha_2^t}{(\alpha_2-\alpha_0)(\alpha_2-\alpha_1)} \right\} \tag{12} }

これを(9)式に代入して計算すると p^{(3)}_tは

\displaystyle{ p^{(3)}_t = (1-\alpha_0) (1-\alpha_1) (1-\alpha_2) \left\{ \frac{1-\alpha_0^t}{(1-\alpha_0)(\alpha_0-\alpha_1)(\alpha_0-\alpha_2)} + \frac{1-\alpha_1^t}{(1-\alpha_1)(\alpha_1-\alpha_0)(\alpha_1-\alpha_2)} + \frac{1-\alpha_2^t}{(1-\alpha_2)(\alpha_2-\alpha_0)(\alpha_2-\alpha_1)} \right\} \tag{13} }

となります。なお(13)式では p^{(3)}_0 = 0となるので tの範囲の制限を削除しました。以上が求める和了確率です。

余談

以上の議論から一般に n-1向聴の手の和了確率 p^{(n)}_tが以下であると予想できます。

\displaystyle{ p^{(n)}_t = \left\{ \prod_{i=0}^{n-1} (1-\alpha_i) \right\} \times \sum_{i=0}^{n-1} \frac{1-\alpha_i^t}{1-\alpha_i} \prod_{j \neq i} \frac{1}{\alpha_i-\alpha_j} \tag{14} }

実際に n=1, 2, 3, 4の場合で(14)式が正しいことを確認しています。 n > 4の場合で(14)式が正しいのかは不明です。もし正しいかどうか証明できた方がいましたらぜひ教えてください。

おわりに

今回は行列を使った解法を説明しました。(12)式が \{a_i\}についての対称式になっているのがわかりやすくていいですね。(14)式が正しいのかどうか気になるところですが、非復元抽出を想定した場合の和了確率もまた \{a_i\}についての対称式になることがわかっています。その対称性を前面に押し出した表式も気になります。