tomohxxの日記

麻雀プログラミング

一人麻雀和了確率計算アルゴリズム まとめ

はじめに

今回はこれまでに議論してきた一人麻雀和了確率についていくつかの問題点・疑問点を解消します。

諸問題

存在確率と和了確率の再定義

前々回の記事のトップダウンボトムアップの関係についての記述が不十分なので補足します。

tomohxx.hatenablog.com

 n-1向聴の手牌を想定し、 0から nまでの n+1個の状態(手牌)があるとします。状態間の遷移確率を表す以下の確率行列 A_tを定義します。


A_t =
\begin{pmatrix}
1-\frac{a_0}{S-t} & 0 & \dots & 0 & 0 \\
\frac{a_0}{S-t} & 1-\frac{a_1}{S-t} & \dots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \dots & 1-\frac{a_{n-1}}{S-t} & 0 \\
0 & 0 & \dots & \frac{a_{n-1}}{S-t} & 1-\frac{a_n}{S-t} \\
\end{pmatrix}
\tag{1}

 t = 0巡目に S枚の牌があるとして t = \tau巡目に和了する確率は \prod_{t=0}^{\tau-1} A_t (n, 0)成分なので


\displaystyle
p = {}^t \boldsymbol{e}_n \left\{ \prod_{t=0}^{\tau-1} A_t \right\} \boldsymbol{e}_0
\tag{2}

と書けます。なお行列とベクトルの添字は0始まりとします。また \boldsymbol{e}は単位ベクトルです。これを計算する方法は2通りあり、① \boldsymbol{e}_0に左から A_tを繰り返し作用させる方法と② {}^t \boldsymbol{e}_nに右から A_tを繰り返し作用させる方法があります。①がトップダウンで②がボトムアップです。それぞれの方法は以下のように書けます。

ボトムアップ


\begin{aligned}
{}^t\boldsymbol{p}_t &= {}^t\boldsymbol{p}_{t+1} A_t \\
\boldsymbol{p}_\tau &= \boldsymbol{e}_n
\end{aligned}
\tag{4}

このとき和了確率は


p = {}^t\boldsymbol{p}_t \boldsymbol{q}_t = {}^t\boldsymbol{p}_0 \boldsymbol{e}_0 = {}^t\boldsymbol{e}_n \boldsymbol{q}_\tau
\tag{5}

です。

 \boldsymbol{q}_t t巡目での状態の存在確率を表し、 \boldsymbol{p}_t t巡目での和了確率を表します。この例のように打牌を考えなければどちらの方法を使っても構いませんが、打牌を考える場合は各状態で和了確率が最大となる打牌を選択する必要があるのでボトムアップの方法しか使えません。

基底変換(パラメータ変換)

手牌変化が一通りではなく分岐する場合、確率行列として A_tではなく以下の B_tを考えます。


B_t =
\begin{pmatrix}
1-\frac{a_0}{S-t} & 0 & \dots & 0 & 0 \\
\frac{b_0}{S-t} & 1-\frac{a_1}{S-t} & \dots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \dots & 1-\frac{a_{n-1}}{S-t} & 0 \\
0 & 0 & \dots & \frac{b_{n-1}}{S-t} & 1-\frac{a_n}{S-t} \\
\end{pmatrix}
\tag{6}

これを A_tと同じように扱いたいので以下の対角行列 D_iを導入して基底を変換します。


D_i =
\begin{pmatrix}
1 & & & & \\
& \ddots & & \huge{0} & \\
& & \frac{b_i}{a_i} & & \\
& \huge{0} & & \ddots & \\
& & & & 1 \\
\end{pmatrix}
\tag{7}

ここで例えば D^{-1}_i B_t D_iを考えると i行目は A_tと同じになります。よって


\displaystyle
A_t = \left\{\prod_{i=0}^{n} D_i^{-1} \right\} B_t \left\{\prod_{i=0}^n D_i \right\}
\tag{8}

が成り立ちます。 \boldsymbol{p}_t \boldsymbol{q}_tのかわりに D_iによって基底を変換した \boldsymbol{p'}_t \boldsymbol{q'}_tを使えば、手牌変化が一通りの場合と分岐する場合の確率の計算をほとんど同じようにできます。

手牌変化のグラフの正確な記述

前回の記事で手牌変化のグラフを導入しました。

tomohxx.hatenablog.com

一人麻雀和了確率は2次元確率DPで計算できます。それならばグラフは無向グラフではなくDAGとして記述すべきなような気がします。

手牌変化のグラフ(DAG)

上の図では簡単のため2つの巡目しか記載していません。また矢印の色と線種については後述します。先述のように和了確率を求めるには各状態での和了確率を知らなければならないので、DPを使って計算する際は矢印の向きを逆向きにたどって各状態を訪問することになります。

緩和順

各状態での和了確率を表す漸化式は以下のようになります(前回の記事を参照)。


p^v_t =
\left\{
\begin{aligned}
& p^v_{t+1} + \sum_{v' \in \mathrm{adj}(v)} \frac{e(v, v')}{S-t} (p^{v'}_{t+1} - p^v_{t+1}) & (v \in V_1) \\
& \max_{v' \in \mathrm{adj}(v)} \left\{ p^{v'}_t \right\} & (v \in V_2)
\end{aligned}
\right.
\tag{9}

添字が手牌方向と巡目方向と2つあるので、どちらをループの外側にするのかが問題になります。手牌変化のグラフを見ると巡目方向がトポロジカル順序になることがわかるので巡目をループの外側にすればよいことがわかります。ここで手牌変化のグラフから赤色の矢印がないとすると手牌方向もトポロジカル順序になります。赤色実線矢印は向聴戻し、赤色破線矢印は手替わりを表していると思ってください。この場合再帰的に手牌を探索しながら各巡目での和了確率を計算できるので、計算速度・メモリ効率ともに向上します。

辺の重み

辺の重みを巡目によらず固定としてよいのかは、和了確率を最大にする打牌をする場合2回以上同じ手牌を訪問しないので固定としてよいです。

不整合

手牌変化のグラフで辺の重みを巡目によらず固定すると、(6)式で  \sum_{v' \in \mathrm{adj}(v)} e(v, v') > S - t(ただし p^{v'}_{t+1} > p^v_{t+1})となる巡目で p^v_tを確率として解釈できなくなります(前回の記事を参照)。このとき対応する存在確率は0になっているので和了確率は不定です。強いて言えば無効値として0や-1を割り当てるのがよいのかもしれません。あるいは捨てた牌は河ではなく山に戻るという仮定を受け入れてこの事態を回避するべきです。

得点期待値

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


s^v_t =
\left\{
\begin{aligned}
& s^v_{t+1} + \sum_{v' \in \mathrm{adj}(v)} \frac{e(v, v')}{S-t} \left( \max \left\{f(v, v'),\ s^{v'}_{t+1} \right\} - s^v_{t+1} \right) & (v \in V_1) \\
& \max_{v' \in \mathrm{adj}(v)} \left\{ s^{v'}_t \right\} & (v \in V_2)
\end{aligned}
\right.
\tag{10}

ここで f(v, v')は得点を表します。状態(頂点) v'和了のときだけ0以外の値をもち、それ以外の状態では0となります。なお初期条件は


s^v_t = 0 \quad (0 \le t \le \tau)
\tag{11}

です。

おわりに

一人麻雀和了確率についての問題点・疑問点をほぼ解消できたのではないかと思います。

一人麻雀和了確率計算アルゴリズム グラフ探索

今回は前回の記事の続きです。
tomohxx.hatenablog.com

これまで手牌変化の木は与えられたものとして和了確率を求めてきました。基本的にシャンテン数が下がれば和了確率は上がると考えられるので、実装上は一方的にシャンテン数を下げる手牌変化の木を扱ってきました。しかし手替わりやシャンテン戻しを考慮すると、この手牌変化の木以外により高い和了確率を与える木が存在する可能性があります。つまり和了確率を最大にする手牌変化の木は自明ではありません。そこで手牌変化の木を構築することも含めた和了確率を計算するアルゴリズムを紹介します。

今回は手牌変化の木ではなく手牌変化のグラフを考えます。以下のような重み付き無向グラフ G(V_1, V_2, E)が与えられるとします。 V_1は13枚の手牌、 V_2は14枚の手牌を表し、異なる枚数の手牌を表す頂点同士は隣接するが同じ枚数を表す頂点同士は隣接しません。また辺 e(v_1, v_2)  \in Eは13枚の手牌から14枚の手牌に変化するための牌の枚数を表します。なお、手牌の枚数をより一般に 3n+1枚、 3n+2枚としても構いません。

手牌変化のグラフのイメージ(白色の頂点が13枚の手牌、赤色の頂点が14枚の手牌を表す)

ここで和了確率を次のように定義します。

和了確率 p^v_t
 t巡目に頂点 vにいるとして、別のある頂点を2回以上訪問しないで和了する確率

以下の連立確率漸化式を解いて和了確率を求めます。 \mathrm{adj}(v) vの隣接する頂点の集合を得る演算です。

p^v_t =
\left\{
\begin{aligned}
& p^v_{t+1} + \sum_{v' \in \mathrm{adj}(v)} \frac{e(v, v')}{S-t} (p^{v'}_{t+1} - p^v_{t+1}) & (v \in V_1) \\
& \max_{v' \in \mathrm{adj}(v)} \left\{ p^{v'}_t \right\} & (v \in V_2)
\end{aligned}
\right.
\tag{1}
初期条件は和了している手牌の集合を W \subset V_2として

p^v_t =
\left\{
\begin{aligned}
& 1 & (v \in W) \\
& 0 & (v \notin W)
\end{aligned}
\right.
\quad (0 \le t \le t_{\mathrm{max}})
\tag{2}
です。

式の意味を簡単に説明します。まず(1)式の第2式は簡単で、手牌の枚数が14枚のときの和了確率をそこからある牌を捨てたときの和了確率の最大値とすることを意味します。次に(1)式の第1式ですが具体例を用いて説明します。現在頂点 v_0 \in V_1にいるとして頂点 v_1, v_2 \in V_2に隣接しているとします。前回の記事の要領で p^{v_1}_tを計算すると次のようになります。
 \displaystyle
p^{v_0}_t = \left( 1-\frac{e(v_0, v_1)+e(v_0, v_2)}{S-t} \right) p^{v_0}_{t+1} + \frac{e(v_0, v_1)}{S-t} p^{v_1}_{t+1} + \frac{e(v_0, v_2)}{S-t} p^{v_2}_{t+1}
\tag{3}
これを変形すると
 \displaystyle
p^{v_0}_t = p^{v_0}_{t+1} + \frac{e(v_0, v_1)}{S-t} (p^{v_1}_{t+1} -  p^{v_0}_{t+1}) + \frac{e(v_0, v_2)}{S-t} (p^{v_2}_{t+1} - p^{v_0}_{t+1})
\tag{4}
となるので、隣接する頂点数を一般化して(1)式の第1式になります。ここでもし p^{v_2}_{t+1} <  p^{v_0}_{t+1}であれば v_0から v_2への変化を考えない方が和了確率が高くなると言えますが(1)式の第2式より p^{v_2}_{t+1} \ge  p^{v_0}_{t+1}が保証されるので(1)式の第1式はそのままでよいことがわかります。つまり(1)式は不要牌をツモったときのツモ切りを内包していると言えます。

ところで巡目によって辺の重みが変化することは考えなくてよいのでしょうか?これは特定の計算条件の下では考える必要はありません。実は先の手牌変化のグラフの図には自己ループ e(v_1, v_1)が省略されています。これは自明な不要牌をツモ切りすることを意味していてその重みは S-t-\sum_{v' \in \mathrm{adj}(v)} e(v, v')で巡目によって変化します。自明な不要牌とは例えばタンヤオテンパイに対する字牌ホンイツに対する本命ではない色の数牌のような絶対にいらない牌です。自己ループを含めて辺の重みの合計が S-tであればよく、辺の重みの巡目依存性を自己ループに押し付けていることになります。逆に自明な不要牌が存在せず自己ループが存在しない場合(あらゆるツモを考慮して和了確率を計算する場合)(1)式は破綻することになります。*1*2

以上の議論を踏まえると和了確率を計算するには対象の手牌から変化可能な手牌の集合が必要でそれは手牌の全体集合ではないことがわかります。その集合の部分集合を得るのは簡単ですが、漏れなく効率的にこの集合の全要素を得る方法は現在検討中です。まあ、これについては和了確率とあまり関係ないような気がするので正直なところやる気が起きません。そこで、変化可能な手牌の集合を簡単に得られる場合として一色手の手牌の和了確率を計算してみました。
github.com
一色手の場合14枚の手牌のパターンは118800通り、13枚の手牌のパターンは93600通りなので時間的にも空間的にも計算可能な範囲です。

前述の通り、和了確率についてはもうやる気が起きないので新規に何かをするとしてもかなり先になると思います。あとこれまでに各所で公開したトップダウンの方法は今となっては人に勧められるものではなくなったので前回と今回の記事で扱ったボトムアップの方法に置き換えないといけないですね。面倒くさい……。

*1:一回捨てた牌は再び山に戻るという反則技の仮定を導入すれば自明な不要牌は考えなくてよくなります。

*2:仮に辺の重みの合計が S-tを超えたとしても p^{v'}_{t+1} = p^v_{t+1}であれば破綻しません。

一人麻雀和了確率計算アルゴリズム トップダウン vs ボトムアップ

トップダウンボトムアップの定義を逆にしました。(2022/09/23追記)
実装例を追記しました。(2022/09/23追記)


このブログでは度々一人麻雀の和了確率を計算するアルゴリズムを取り上げてきました。ところでこのブログ以外でも一人麻雀の和了確率や期待値の計算方法を解説しているサイトがあります。

これらのサイト、そしてこのブログは一人麻雀の和了確率や期待値を計算しているはずですが、すべて同じ値を計算できているのでしょうか?言い換えればこれらのサイトで用いられているアルゴリズムはすべて等価なのでしょうか?今回はこれらのアルゴリズムの関係を明らかにしたいと思います。なお先に結論を述べておくとすべて等価です。


先に言及したアルゴリズムに共通するのは手牌変化の木を探索するということです。手牌変化の木とは以下の図のように手牌の変化を木で表現したものです。なお、議論を簡単にするため以降では引いた牌に対してどの牌を捨てるかが事前に決まっているものとします。

手牌変化の木(4枚形の場合)

それぞれのアルゴリズムで求める値は次のように決定的に異なります。手牌変化の木の根を上としたときにそれらの値を上から下へ求めるか下から上へ求めるかによって、これらのアルゴリズムトップダウンボトムアップに分かれます。このブログでこれまで取り上げてきたアルゴリズムトップダウンに、それ以外はボトムアップになります。

トップダウン
 t巡目にノード Nの状態である確率 q^{N}_tを求める。
ボトムアップ
 t巡目にノード Nの状態であるとしたとき t_{max}巡目までに和了する確率 p^{N}_tを求める。

簡単な問題を使って2つの違いを見ていきます。

 t = 0巡目に S枚の牌がある。聴牌の手牌 Oから和了の手牌 Aに変化するための有効牌が a枚であるとする。 t=t_{max}巡目までに和了する確率を求めよ。

トップダウンの解法

次の連立確率漸化式を解く。


\left\{
\begin{aligned}
q^O_{t+1} &= \left( 1-\frac{a}{S-t} \right) q^O_t  & q^O_0 &= 1 \\
q^A_{t+1} &= q^A_{t} + \frac{a}{S-t} q^O_t & q^A_0 &= 0
\end{aligned}
\right.
\tag{1}

ボトムアップの解法

次の連立確率漸化式を解く。


\left\{
\begin{aligned}
p^O_t &= \left( 1-\frac{a}{S-t} \right) p^O_{t+1} + \frac{a}{S-t} p^A_{t+1} & p^O_{t_{max}} &= 0 \\
p^A_t &= p^A_{t+1} & p^A_{t_{max}} &= 1
\end{aligned}
\right.
\tag{2}

どちらも似たような形式ですが行列で表現すると違いがはっきり見えます。

ボトムアップの解法


\begin{pmatrix}
p^O_t \\
p^A_t
\end{pmatrix}
=
\begin{pmatrix}
1-\frac{a}{S-t} & \frac{a}{S-t} \\
0 & 1
\end{pmatrix}
\begin{pmatrix}
p^O_{t+1} \\
p^A_{t+1}
\end{pmatrix}
\tag{4}

(3)式と(4)式を見ると違いは2点あり、①時間発展の方向が互いに逆である②行列が互いに共役転置の関係にあることがわかります。計算過程は省略しますがこれらを解くと

 
p^O_0 = q^A_{t_{max}}
\tag{5}

の関係が得られます。よってトップダウンボトムアップのどちらでも同じ和了確率を得られます。

では手牌の変化の行先が複数の場合について考えてみます。例えば O \rightarrow Aの変化の他に O \rightarrow Bの変化がある場合、ボトムアップでは以下の連立確率漸化式を解きます。なおトップダウンについては https://tomohxx.github.io/mahjong-algorithm-book/ を参照してください。


\left\{
\begin{aligned}
p^O_t &= \left( 1-\frac{a+b}{S-t} \right) p^O_{t+1} + \frac{a}{S-t} p^A_{t+1} + \frac{b}{S-t} p^B_{t+1} & p^O_{t_{max}} &= 0 \\
p^A_t &= p^A_{t+1} & p^A_{t_{max}} &= 1 \\
p^B_t &= p^B_{t+1} & p^B_{t_{max}} &= 1
\end{aligned}
\right.
\tag{6}

(6)式のように行先の分だけ項が増えます。ここまでに解説したボトムアップアルゴリズムがおそらくcritter氏のアルゴリズムに相当すると思います。

ここで(2)式に戻ってこれを形式的に解いてみます。


\begin{aligned}
p^O_t &= \left( 1-\frac{a}{S-t} \right) p^O_{t+1} + \frac{a}{S-t} p^A_{t+1} \\
&= \left( 1-\frac{a}{S-t} \right) \left\{ \left(1-\frac{a}{S-t} \right) p^O_{t+2} + \frac{a}{S-t-1} p^A_{t+2} \right\} \\
&= \dots \\
&= \left( 1-\frac{a}{S-t} \right) \left( 1-\frac{a}{S-t-1} \right) \dots \left( 1-\frac{a}{S-t_{max}+1} \right) p^O_{t_{max}} \\
&\quad + \left( 1-\frac{a}{S-t} \right) \left( 1-\frac{a}{S-t-1} \right) \dots \left( 1-\frac{a}{S-t_{max}+2} \right) \frac{a}{S-t_{max}+1} p^A_{t_{max}} \\
&\quad + \left( 1-\frac{a}{S-t} \right) \left( 1-\frac{a}{S-t-1} \right) \dots \left( 1-\frac{a}{S-t_{max}+3} \right) \frac{a}{S-t_{max}+2} p^A_{t_{max}-1} \\
&\quad + \dots + \left( 1-\frac{a}{S-t} \right) \frac{a}{S-t-1} p^A_{t+2} + \frac{a}{S-t} p^A_{t+1} \\
&= \sum^{t_{max}-1}_{u=t}  \left( 1-\frac{a}{S-t} \right) \left( 1-\frac{a}{S-t-1} \right) \dots \left( 1-\frac{a}{S-u+1} \right) \frac{a}{S-u} p^A_{u+1} \\
&= \sum^{t_{max}-1}_{u=t} \prod^{u-1}_{v=t} \left( 1-\frac{a}{S-v} \right) \frac{a}{S-t} p^A_{u+1}
\end{aligned}
\tag{7}

念のため途中式を記載しました。さて(7)式は「 t巡目の和了確率は、 u-1巡目まで有効牌を引かず u巡目に有効牌を引く確率に u+1巡目の和了確率をかけたものを u \in [t, t_{max}-1]に渡って足したものである」と解釈できます。この(7)式を使うアルゴリズムがあら氏とnekobean氏のアルゴリズムに相当すると思います。

以上の議論から冒頭で言及した3つのサイトとこのブログで用いられたアルゴリズムはすべて等価であることが簡単には(厳密ではない)説明できました。

最後にどのアルゴリズムを使うべきか考えてみます。素朴に実装すれば計算量はどれも同じですが、ボトムアップでは途中のノードの和了確率をキャッシュする(メモ化再帰)ことで訪問するノード数を減らせるので計算速度を追求するならボトムアップを使うべきです。また(2)式と(7)式は等価ですが、(7)式はループカウンタの分変数が増えるので(2)式の方が実装が簡単だと思います。つまりcritter氏のアルゴリズムが一番おすすめです。


ここまで完全に机上の議論しかしてきませんでしたが、ボトムアップを実装したものがこちらです。

github.com

手替わりなし・シャンテン戻しなしの条件付きですが、5シャンテンまでなら1秒以下、6シャンテンでは10秒から20秒程度で和了確率を計算することができます。6シャンテンの計算はキャッシュを使うからこそできるのであって、キャッシュの使えないトップダウンでは時間がかかりすぎて事実上計算不可能です。というわけでボトムアップの優位性は明白です。また一般の5シャンテンや6シャンテンの高シャンテン数の手牌の和了確率を計算できるプログラムは他にないと思われます。なお高シャンテン数であっても対称性が高い特殊な手牌では以前から計算可能でした。

vs Mortal

最近Equimさんの開発したMortalという麻雀AIが話題になっています。

mjai.ekyu.moe

天鳳や雀魂の牌譜をレビューする機能と、天鳳の個室に呼び出して同卓する機能があります。話題になっているのは主に前者ですが、ここでは後者を使って自作の麻雀AIと対戦させてみます。目的は評価ではなく人気に便乗お試しです(おそらく評価目的で多試合打たせることはサーバーのリソースを専有することになるのでダメかと)。Mortalは開発者の検証によりAkochanよりも強いことがわかっています。Akochanの強さは天鳳の段位において七~九段相当とされているので、Mortalが天鳳鳳凰卓レベルであることは間違いないと思われます。

自作の麻雀AI用に以下の2つのアカウントを用意しました。

  • Mar1422
  • Mar1422'

1つ目は以前に天鳳自動打ちで使用したものです。

tomohxx.hatenablog.com

もちろん名前が違うだけでそれぞれはまったく同じです。これら2体のAIとMortal 2体を個室で対戦させました。以下が牌譜です。

簡単に気になった場面をピックアップしてみます。

1試合目Mar1422'視点です。上家・下家がMortal、対面がMar1422です。親番ということで立直しなくてもまくれるので立直しないほうがいいと思います。

2試合目Mar1422'視点です。上家・対面がMortal、下家がMar1422です。立直後あと5枚のところまで引っ張られると相対的に愚形待ちの割合が高まるので、ダブルワンチャンスかつションパイではない1pを選択したと思われます。私なら安易に9sを切りそうです(これが正解かはわかりません……)。ちなみにその後Mortalから跳満を出あがりました。満貫以上で得点上昇効率が悪いのでダマで正解ですかね。

全体的な感想になりますがすごく攻撃的な試合だったと思います。私自身これらのAIのように押すタイプではなく、真似できないような行動もありました。あとAIはミスしないので一局の中での展開が速いですね。正直同卓したくはないです……。

さて、最後になりますが麻雀AI開発を引き続き頑張っていこうと思います。

配牌時有効牌の枚数

配牌時(手牌の枚数が13枚のとき)有効牌の枚数を計算するアルゴリズムを以下のページにまとめました。ここでは結果について簡単に記載します。

tomohxx.github.io

向聴数 場合の数 割合 有効牌の枚数の平均値
0 39270395383132 8.1175e-05 4.5843
1 3006175115638776 0.006214 12.2671
2 45249205945148216 0.0935337 23.3215
3 175141291509958900 0.362031 40.4909
4 192909046305573888 0.398758 60.6136
5 63384201353756672 0.13102 77.8174
6 4045365540028416 0.00836209 100.154

向聴数を区別しないで有効牌の枚数の平均値を計算すると52.1202になります。

ちなみに計算時間は私の環境で5分弱でした。正直、このデータが何の役に立つか不明です。とりあえず計算できるということを強調しておきます。

牌の危険度予測ツール

牌の危険度予測ツールを開発しました。

github.com

ここで述べる危険度は以下の式で定義されます。この式はすべての聴牌形の出現確率が等しいという最も単純な仮定の下で危険度を求めます。


(\text{ある牌を待つ確率}) = \frac{(\text{その牌を待つ聴牌形の数})}{(\text{すべての聴牌形の数})}
\tag{1}

どのように聴牌形を数え上げるかについては以下のページを参照してください。大雑把には天和の確率を求めたり配牌時向聴数を求めたりすることと同じようなこと(動的計画法)をやっています。

tomohxx.github.io

この式では切り順や手出し・ツモ切りは考慮されません。上級者にはもの足りないかもしれませんが初・中級者には十分有用だと思われます。

簡単に使い方を説明します。例えば以下の場面で立直をかけている対面に対して牌の危険度を求めてみます。なお、このツールは対象者が聴牌しているという前提で牌の危険度を求めます。よって対象者が立直をかけているか、三副露以上している、連続でツモ切りしているというように聴牌していることを確信できる必要があります。

まず以下のファイルを作成します。

4
1m 1 1
2m 1 1
3m 4 0
4m 3 0
5m 3 0
6m 3 1
7m 3 0
8m 2 0
9m 2 1
1p 0 1
2p 2 0
3p 2 0
4p 3 0
5p 3 0
6p 4 0
7p 1 0
8p 1 1
9p 2 0
1s 3 0
2s 3 1
3s 3 0
4s 3 0
5s 3 0
6s 1 0
7s 1 1
8s 3 0
9s 2 0
1z 4 0
2z 1 0
3z 2 0
4z 3 1
5z 1 1
6z 1 1
7z 2 1

1行目に手牌の面子数を、2行目以降に各牌の残り枚数と振聴かどうかのフラグを入力します。このファイルをwall_river.txtという名前で保存します。次に以下のコマンドでDockerのイメージを作成、コンテナを作成・実行して危険度の計算とグラフの出力を行います。計算時間は環境によりますが私の環境では2~3ミリ秒です。

$ docker build . -t predictor
$ docker run -v $PWD/output:/output -v $PWD/wall_river.txt:/wall_river.txt --rm predictor

次のグラフが出力されます。

このグラフから36s、47m、3pから7pが危険だとわかります。中らずと雖も遠からずという感じでしょうか。


最後に補足事項があります。このツールで計算された牌の危険度が本当に正しいのか、つまり(1)式を正しく計算できているのか客観的に証明することができていません。アルゴリズムによって聴牌形を数え上げている人が他にいないことと、私自身これ以外の方法で聴牌形を数えたことがないためです。もちろんアルゴリズムは正しいと確信していますが実装に誤りがある可能性を否定できません。また証明しようにもどのようなテストケースを作成すればよいかという問題もあります。

統計やシミュレーションではなく、厳密に聴牌形を数え上げることで危険度を予測するというツールは他にはないはずです。統計やシミュレーションでは誤差が避けられませんがこのツールには誤差がないことが魅力ではないかと思います。厳密に危険度を議論したいという状況がどれくらいあるのかわかりませんが、そのようなときにはぜひ活用していただきたいと思います。

配牌時向聴数

気分転換にブログを更新します。最近は強化学習について勉強していて、今後の麻雀AI開発に生かしたいと考えています。こちらについてまだブログに書くだけの結果がないので、今回は麻雀アルゴリズムについて書きます。少し前に、配牌時向聴数を計算するアルゴリズムを以下のページにまとめました。

(簡易版) https://tomohxx.github.io/mahjong-algorithm-book/shanten/
(完全版) https://gist.github.com/tomohxx/036d814e5099ce972ba9683826b9d41e

配牌時向聴数については、このブログでこれまで言及してこなかったのでここで言及(宣伝)しておきます。「麻雀の数学(http://www10.plala.or.jp/rascalhp/mjmath.htm#12)」というサイトがありますが、そのサイトの計算を追試したようなものです。そのアルゴリズム競技プログラミングに通じるものを感じます。麻雀をテーマに自分の知らなかったアルゴリズムを勉強することができてよかったです。

最近は麻雀AIに注力していますが、ときどき麻雀アルゴリズムについて理解を深めていければと思います。