和了確率

有効牌の枚数の変化に分岐がない場合

ある手牌が与えられ, どのように和了に向かっても有効牌の枚数の変化が 1 通りであるとする. ここで和了形は 1 通りでなくてもよい. この手牌の置換数を\(d\), 有効牌の枚数を\(a_0\)とする. この状態から有効牌を 1 枚引くごとに置換数が 1 ずつ減少し最終的に 0 になるが, この過程で有効牌の枚数が\(a_0, a_1, \ldots , a_{d-1}\)と変化する. 手牌の置換数が\(d\)のものから\(0\)のものまでの\(d+1\)個の状態が存在するから, 各状態間の遷移を表す確率行列\(A_u\)を考えれば和了確率を表せる.

\[ A_u = \begin{pmatrix} 1-\frac{a_0}{S-u} & 0 & \dots & 0 & 0 \\ \frac{a_0}{S-u} & 1-\frac{a_1}{S-u} & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1-\frac{a_{d-1}}{S-u} & 0 \\ 0 & 0 & \dots & \frac{a_{d-1}}{S-u} & 1-\frac{a_d}{S-u} \\ \end{pmatrix} \tag{1} \]

(1)式で\(u\)は巡目, \(S\)は 0 巡目での牌の総数を表す. また\(a_d = 0\)とする. \(t\)巡目における和了確率\(p_t\)は

\[ p_t = {}^t \boldsymbol{e}_d A_{t-1} A_{t-2} \cdots A_1 A_0 \boldsymbol{e}_0 \tag{2} \]

と書ける(行列やベクトルの添字の始まりが 0 であることに注意).

(2)式を計算する方法は 2 通りあり, ①\(\boldsymbol{e}_0\)に左から\(A_u\)を繰り返し作用させる方法と ②\({}^t \boldsymbol{e}_d\)に右から\(A_u\)を繰り返し作用させる方法がある. それぞれの方法は以下のように書ける.

\[ \boldsymbol{q}_0 = \boldsymbol{e}_0,\ \boldsymbol{q}_{u+1} = A_u \boldsymbol{q}_u \tag{3} \]

\[ \boldsymbol{p}_t = \boldsymbol{e}_d,\ {}^t\boldsymbol{p}_u = {}^t\boldsymbol{p}_{u+1} A_u \tag{4} \]

\(\boldsymbol{q}_u\)は\(u\)巡目での各状態の存在確率を表し, \(\boldsymbol{p}_u\)は\(u\)巡目での各状態の和了確率を表す. 存在確率と和了確率の関係は以下の式で表せる.

\[ p_t = {}^t\boldsymbol{p}_u \boldsymbol{q}_u = {}^t\boldsymbol{p}_0 \boldsymbol{e}_0 = {}^t\boldsymbol{e}_d \boldsymbol{q}_t \tag{5} \]

この例のように有効牌の枚数の変化が 1 通りであればどちらの方法も使えるが, そうではない場合和了へ向かう途中の状態の和了確率を最大化する打牌を選択する必要があるため後者の方法しか使うことができない.

有効牌の枚数の変化に分岐がある場合

有効牌の枚数の変化が 1 通りではなく引いた牌に応じて分岐する場合を考える. 和了へ向かう手牌の変化を表す有効非巡回グラフ(DAG, 以降手牌変化のグラフと呼ぶ)を導入する.

図1: 手牌変化のグラフ(黒実線は有効牌の自摸, 黒破線は不要牌の打牌, 赤実線は手替わり, 赤破線は向聴戻しを表す)

これは手牌方向と巡目方向の 2 つの方向への広がりを持つグラフである. 各頂点が各手牌, 各巡目の和了確率を表す. 番号が同じ頂点どうしは手牌としては同じ(巡目が異なる)である. なお簡単のため 0, 1 巡目の状態しか示していない. 先述のように和了確率を求めるには各状態の和了確率を知らなければならないため, 動的計画法(DP)を使って計算する際は矢印の向きを逆向きにたどって各状態を訪問する必要がある.

ここで\(3n+1\)枚の手牌の集合を\(H_1\), \(3n+2\)枚の手牌の集合を\(H_2\), 巡目を\(u\)として各状態の和了確率は以下の漸化式で表せる.

\[ p^h_u = \left\{ \begin{aligned} & p^h_{u+1} + \sum_{h' \in \mathrm{adj}(h)} \frac{e(h, h')}{S-u} (p^{h'}_{u+1} - p^h_{u+1}) & (h \in H_1) \\ & \max_{h' \in \mathrm{adj}(h)} \left\{ p^{h'}_u \right\} & (h \in H_2) \end{aligned} \right. \tag{6} \]

(6)式で\(\mathrm{adj}(h)\)は隣接する手牌の集合を得る演算, \(e(h, h')\)は手牌\(h\)から手牌\(h'\)に変化するための牌の枚数である. 境界条件は和了している手牌の集合を\(W \subset H_2\)として

\[ p^h_u = \left\{ \begin{aligned} & 1 & (h \in W) \\ & 0 & (h \notin W) \end{aligned} \right. \quad (0 \le u \le t) \tag{7} \]

である. 以下(6)式について考察する.

緩和順

添字が手牌方向と巡目方向と 2 つあるため, どちらをループの外側にするのかが問題になる. 手牌変化のグラフを見ると巡目方向がトポロジカル順序になることがわかるため, 巡目をループの外側にすればよい. ここで手牌変化のグラフから赤色の矢印がないとすると手牌方向もトポロジカル順序になる. この場合再帰的に手牌を探索しながら各巡目での和了確率を計算でき計算速度・メモリ効率ともに向上する.

辺の重み

辺の重み\(e(h, h')\)を巡目によらず固定としてよいのかは, 和了確率を最大にする打牌をする場合 2 回以上同じ手牌を訪問しないため固定としてよい.

不整合

\(\sum_{h' \in \mathrm{adj}(h)} e(h, h') > S - u\)(ただし\(p^{h'}_{u+1} > p^h_{u+1}\))となる巡目で\(p^h_u\)を確率として解釈できなくなる. しかし, このとき対応する存在確率は 0 になっているためこの状態が途中の状態となることはない. ただし(6)式の第 2 式でこの状態が選択されないように工夫するか, 一度捨てた牌は山に戻ると仮定する必要がある.

得点期待値

和了確率ではなく得点期待値を求める場合, 基本的には(6)式で和了確率\(p^h_u\)を得点期待値\(s^h_u\)に置き換えればよい. ただし注意点が 2 点ある. 1 点目は得点は和了の状態に付属するのではなく聴牌から和了へ向かう辺に重みとして付属するということである. つまり辺は有効牌の枚数と得点の 2 種類の重みをもつことになる. 2 点目は和了の状態に到達したとして和了を宣言するか局を続行するか選択する必要があるということである. これらに注意して得点期待値を表す漸化式は以下のようになる.

\[ s^h_u = \left\{ \begin{aligned} & s^h_{u+1} + \sum_{h' \in \mathrm{adj}(h)} \frac{e_1(h, h')}{S-u} \left( \max \left\{e_2(h, h'),\ s^{h'}_{u+1} \right\} - s^h_{u+1} \right) & (h \in H_1) \\ & \max_{h' \in \mathrm{adj}(h)} \left\{ s^{h'}_u \right\} & (h \in H_2) \end{aligned} \right. \tag{8} \]

ここで\(e_1(h, h')\)は有効牌の枚数, \(e_2(h, h')\)は得点を表す. \(e_2(h, h')\)は手牌\(h'\)が和了のときだけ 0 以外の値をもち, それ以外では 0 となる. なお初期条件は

\[ s^h_u = 0 \quad (0 \le u \le t) \tag{9} \]

である.

和了確率の表式

(2)式の解の表式はB. 和了確率の表式を参照すること.

ソースコード

ソースコードはmahjong-win-probを参照すること.

七対子・国士無双の聴牌確率

七対子・国士無双の聴牌確率は有効牌の枚数の変化が数通りに限られるため容易に計算することができる. 七対子の聴牌確率はchitoi.cpp, 国士無双の聴牌確率はkokushi.cppを参照すること.