はじめに

本記事では一人麻雀における和了確率を計算するアルゴリズムについて紹介します。本アルゴリズムでは和了確率だけでなく得点期待値を計算することも可能です。タイトルに「一人麻雀攻略」とあるのは、和了を重視するとか得点を重視するとかという目的に応じた最適な打牌を選択することが可能になるためです。

背景

一人麻雀における和了確率を求めるという問題には、あらの（一人）麻雀研究所で解説されているように既に答えがあります。しかし、この方法では高シャンテン数(大体4シャンテン以上)の手牌に対しては計算コストのせいで事実上和了確率を求めることができません。高シャンテン数の手牌を含め、すべての手牌に対して一貫した方法で和了確率を求めることはできないか、ということが本アルゴリズムの開発の動機です。

平均化された手牌の和了確率

具体的な手牌の和了確率を求めることは難易度が高いので、まずは平均化された手牌の和了確率を求めることから始めます。ここで言う平均化された手牌とは、シャンテン数と有効牌のみがわかっている手牌のことです。例えば、あるテンパイ形があって有効牌の枚数を$a^{(0)}$枚、壁牌の枚数を$S$枚とします。$t$巡目に有効牌を引く確率は

\frac{a^{(0)}}{S-t}

であるので、和了確率は以下のように表現できます。

\left\{
\begin{aligned}
p^{(0)}_{t+1} &= \left( 1-\frac{a^{(0)}}{S-t} \right) p^{(0)}_t  & p^{(0)}_0 &= 1 \\
p^{(1)}_{t+1} &= \frac{a^{(0)}}{S-t} p^{(0)}_t + p^{(1)}_t & p^{(1)}_0 &= 0
\end{aligned}
\right.
\tag{1}

ここで$p^{(0)}_t$は$t$巡目でテンパイのままの確率、$p^{(1)}_t$は$t$巡目までに和了する確率です。(1)式はいわゆる連立確率漸化式というものです。(1)式を形式的に解くと以下のようになります。

p^{(1)}_t = 1 - \frac{_{S-a^{(0)}}C_t}{_{S}C_t}
\tag{2}

おそらく(1)式よりも(2)式の方がなじみがあると思います。(2)式は$t$巡までに有効牌を一枚も引かない確率(右辺第2項)を1から引くこと(余事象の確率)で和了確率を表していると解釈できます。ではなぜ(1)式を最初に紹介したかというと、こちらの方が1シャンテン以上の手牌や、手牌の変化が一通りではなく複数に分岐するような場合でも簡単に対応できるためです。

次のような1シャンテンの手牌を考えます。シャンテン数が1から0に変化するのに必要な牌の枚数を$a^{(0)}$枚、0から-1(和了)に変化するのに必要な牌の枚数を$a^{(1)}$枚とします。また$t=0$巡目での壁牌の枚数を$S$枚とします。

\left\{
\begin{align}
p^{(0)}_{t+1} &= \left( 1-\frac{a^{(0)}}{S-t} \right) p^{(0)}_t  & p^{(0)}_0 &= 1 \\
p^{(1)}_{t+1} &= \left( 1-\frac{a^{(1)}}{S-t} \right) p^{(1)}_t + \frac{a^{(0)}}{S-t} p^{(0)}_t & p^{(1)}_0 &= 0 \\
p^{(2)}_{t+1} &= \frac{a^{(1)}}{S-t} p^{(1)}_t + p^{(2)}_t & p^{(2)}_0 &= 0
\end{align}
\right.
\tag{3}

$t$巡目までの和了確率は$p^{(2)}_t$です。このようにシャンテン数が増えても、連立させる確率漸化式を増やすことで和了確率を表現することができます。一方、(2)式のようにコンビネーション(nCr)を使って考えると、どうしても総和記号(シグマ)を入れ子にすることを避けられず式が複雑になってしまいます。¹

一般に(d-1)シャンテンの手牌の和了確率$p^{(d)}_t$は以下のd元連立確率漸化式の解として表現できます。

\left\{
\begin{align}
p^{(0)}_{t+1} &= \left( 1-\frac{a^{(0)}}{S-t} \right) p^{(0)}_t  & p^{(0)}_0 &= 1 \\
p^{(i)}_{t+1} &= \left( 1-\frac{a^{(i)}}{S-t} \right) p^{(i)}_t + \frac{a^{(i-1)}}{S-t} p^{(i-1)}_t & p^{(i)}_0 &= 0 & (0 \le i < d) \\
p^{(d)}_{t+1} &= \frac{a^{(d-1)}}{S-t} p^{(d-1)}_t + p^{(d)}_t & p^{(d)}_0 &= 0
\end{align}
\right.
\tag{4}

ここで$a^{(i)}$は(d-i-1)シャンテンの手牌の有効牌の枚数です。

以上、手牌の変化が一通の場合の手牌の和了確率を求める方法を解説しました。

具体的な手牌の和了確率

一般的に、具体的な手牌の和了確率を求める場合は手牌の変化の分岐を考慮しなければなりません。例えば「2478m111999p11s東」という手牌の和了確率を考えます。リャンメン-カンチャンの1シャンテンの手牌です。この手牌の変化を以下のように木で表現します。見やすさのためマンズ以外の部分を省略しています。

この手牌の和了確率は経路(パス)が実現する確率で表されます。例えば図中の経路$l_0$が実現する確率$p^{(0, 2)}_t$は以下のようになります。

\left\{
\begin{align}
p^{(0,0)}_{t+1} &= \left( 1-\frac{12}{S-t} \right) p^{(0,0)}_t  & p^{(0,0)}_0 &= 1 \\
p^{(0,1)}_{t+1} &= \left( 1-\frac{8}{S-t} \right) p^{(0,1)}_t + \frac{4}{S-t} p^{(0,0)}_t & p^{(0,1)}_0 &= 0 \\
p^{(0,2)}_{t+1} &= \frac{4}{S-t} p^{(0,2)}_t + p^{(0,2)}_t & p^{(0,2)}_0 &= 0
\end{align}
\right.
\tag{5}

経路$l_1$が実現する確率$p^{(1, 2)}_t$は$p^{(0, 2)}_t$と等しいです。

また経路$l_2$が実現する確率$p^{(2, 2)}_t$は以下のようになります。

\left\{
\begin{align}
p^{(2,0)}_{t+1} &= \left( 1-\frac{12}{S-t} \right) p^{(2,0)}_t  & p^{(2,0)}_0 &= 1 \\
p^{(2,1)}_{t+1} &= \left( 1-\frac{4}{S-t} \right) p^{(2,1)}_t + \frac{4}{S-t} p^{(2,0)}_t & p^{(2,1)}_0 &= 0 \\
p^{(2,2)}_{t+1} &= \frac{4}{S-t} p^{(2,1)}_t + p^{(2,2)}_t & p^{(2,2)}_0 &= 0
\end{align}
\right.
\tag{6}

経路$l_3$が実現する確率$p^{(3, 2)}_t$は$p^{(2, 2)}_t$と等しいです。

求めたい和了確率$P_t$はこれらの和となります。

P_t = p^{(0, 2)}_t + p^{(1, 2)}_t + p^{(2, 2)}_t + p^{(3, 2)}_t
\tag{7}

このように具体的な手牌の和了確率を求めるには経路の数だけ連立確率漸化式を解けばよいことがわかります。なお、説明を簡単にするためカンチャンからリャンメンへの手替わりを無視していることに注意してください。以降も手替わりを無視します。

この例のように手牌の変化は木の経路として表現されます。経路$l$の実現する確率は一般的に以下のように書くことができます。

\left\{
\begin{align}
p^{(l, 0)}_{t+1} &= \left( 1-\frac{a^{(l, 0)}}{S-t} \right) p^{(l, 0)}_t  & p^{(l, 0)}_0 &= 1 \\
p^{(l, i)}_{t+1} &= \left( 1-\frac{a^{(l, i)}}{S-t} \right) p^{(l, i)}_t + \frac{b^{(l, i-1)}}{S-t} p^{(l, i-1)}_t & p^{(l, i)}_0 &= 0 & (0 \le i < d) \\
p^{(l, d)}_{t+1} &= \frac{b^{(l, d-1)}}{S-t} p^{(l, d-1)}_t + p^{(l, d)}_t & p^{(l, d)}_0 &= 0
\end{align}
\right.
\tag{8}

ここで$a^{(l, i)}$は経路$l$の深さ$i$の節点の手牌の有効牌の枚数、$b^{(l, i)}$は経路$l$の深さ$i-1$の節点の手牌から子節点の手牌に変化するのに必要な牌の枚数です。必ず$b^{(l, i)} \le a^{(l, i)}$で、等号が成立するのは子節点が1つの場合に限ります。経路のすべての節点に対して子節点が1つの場合の連立確率漸化式を直線型、そうでないものを分岐型と呼ぶことにします(直線型: 手牌の変化が一通り、分岐型: 手牌の変化が分岐する)。後でこの2つの型の関係について考察しますので覚えておいてください。

和了確率$P_t$は経路が実現する確率((8)式の解)の和となります。$L$はすべての経路の集合です。

P_t = \sum_{l \in L} p^{(l, d)}_t
\tag{9}

以上のように和了確率を求めるには、(1)まず手牌変化の木を構築し、(2)次にその木を(深さ優先)探索して経路が実現する確率を求めて足し合わせていくことになります。

ここでいくつか補足をしておきます。これまでは手牌変化が事前に与えられるとしてきましたが、手牌変化は自明ではありません。この手牌変化の木の構築には有効牌と不要牌(または余剰牌)を求めるアルゴリズムが必要です。また、変化途中の手牌の打牌選択をどのように行うかということも問題です。変化途中の手牌の打牌選択については、和了確率を最大にする牌を捨てることが一般的な感覚と一致すると思われます。余談ですが和了確率は事前条件なしに決まるものではありません。打ち筋が事前に与えられて初めて和了確率を求めることができます。極端な話、常にランダムに牌を捨てるという打ち筋の下では和了確率がほぼ0になることは想像に難くないでしょう。このように和了確率は打ち筋によって変わりえます。

和了確率を近似的に求める方法

前章の(8)式と(9)式を計算すればすべての手牌の和了確率を理論上は計算することができます。しかし高シャンテン数の手牌の場合、手牌変化の木のサイズが非常に大きくなってしまい事実上計算することは不可能です。ところで、手牌変化の木の経路をすべて探索しなければ和了確率を計算することは不可能なのでしょうか。言い換えると、(相対的に)実現する確率が低い経路については探索しないで和了確率を計算することは可能なのでしょうか。天下りですが、この目論見を達成するために(8)式の分岐型を直線型に変換することを考えます。

(8)式中の$b^{(l, i)} (0 \le i < d)$を無理やり$a^{(l, i)} (0 \le i < d)$で置き換えてみます。

\left\{
\begin{align}
q^{(l, 0)}_{t+1} &= \left( 1-\frac{a^{(l, 0)}}{S-t} \right) q^{(l, 0)}_t  & q^{(l, 0)}_0 &= 1 \\
q^{(l, i)}_{t+1} &= \left( 1-\frac{a^{(l, i)}}{S-t} \right) q^{(l, i-1)}_t + \frac{a^{(l, i-1)}}{S-t} q^{(l, i-1)}_t & q^{(l, i)}_0 &= 0 & (0 \le i < d) \\
q^{(l, d)}_{t+1} &= \frac{a^{(l, d-1)}}{S-t} q^{(l, d-1)}_t + q^{(l, d)}_t & q^{(l, d)}_0 &= 0
\end{align}
\right.
\tag{10}

(8)式の$p_{t}^{(l,i)}$と(10)式の$q_{t}^{(l,i)}$には以下の関係式が成立します(証明は省略)。

\begin{align}
p^{(l, i)}_t &= q^{(l, i)}_t \prod_{j = 0}^{i-1} \frac{b^{(l, j)}}{a^{(l, j)}} & (0 \le i \le d)
\end{align}
\tag{11}

これを(9)式に代入すると以下の式が得られます。

P_t = \sum_{l \in L} q^{(l, d)}_t \prod_{j = 0}^{d-1} \frac{b^{(l, j)}}{a^{(l, j)}}
\tag{12}

(12)式は、すべての経路について(9)式を解いて得られた$q_{t}^{(l,d)}$に重み

\prod_{j = 0}^{d-1} \frac{b^{(l, j)}}{a^{(l, j)}}

をかけて足し合わせていると解釈できます。先ほどの「2478m111999p11s東」の手牌では、各経路の重みは$l_0: 1/6, l_1: 1/6, l_2: 1/3, l_3: 1/3$となります。よって和了確率は以下のように書き換えられます。

\begin{align}
P_t &= p^{(0, 2)}_t + p^{(1, 2)}_t + p^{(2, 2)}_t + p^{(3, 2)}_t \\
&= \frac{1}{6} q^{(0, 2)}_t + \frac{1}{6} q^{(1, 2)}_t + \frac{1}{3} q^{(2, 2)}_t + \frac{1}{3} q^{(3, 2)}_t
\end{align}
\tag{13}

和了確率を近似的に計算する方法は次のようになります。手牌変化の木に含まれるすべての経路から、経路ごとの重みに従ってランダムに経路を選択します。その経路について(10)式の解を求め、その値を一時変数に足します。この操作を繰り返し行い、一時変数を繰り返し回数で割ればその値が和了確率の近似値となります。

(12)式中の重みは「その経路が和了確率にどれだけ寄与するか」の割合といえます。寄与の大きい経路を優先的に探索する一方で寄与の小さい経路を探索しないことにより、和了確率のおおよその値を見積もることができるのです。

なお、得点期待値を計算したい場合は次のように解くべき式を書き換えます。得点は経路$l$によって一意的に決まるので得点を求める関数を$V(l)$とします。$t$巡目における得点期待値を$\overline{V}_t$とすると、

\overline{V}_t = \sum_{l \in L} q^{(l, d)}_t V(l) \prod_{j = 0}^{d-1} \frac{b^{(l, j)}}{a^{(l, j)}}
\tag{14}

となります。

サンプルプログラム

(12)式に基づいて和了確率を計算するプログラムをGitHubで公開しています。C++17で実装してあります。使い方はGitHubを見ていただくとして、ここでは実行例を紹介します。下記は「2478m111999p11s東」の和了確率とテンパイ確率を計算したものです。手牌を入力した後に最大ツモ回数を入力しています。出力結果から和了確率(Prb)は0.325134であることとテンパイ確率(Rdy)が0.864314であることがわかります。

なお、近似値を求めたい場合は4シャンテン以上の手牌を入力しても大丈夫です。

$ ./calc1-prob
Enter 13 tiles.
2478m111999p11s1z
Enter Range
18

The shanten number is 1

Prb     Rdy
0.325134        0.864314

Time (msec.)    0

付録

すべての経路について、それが実現する確率が等しい場合、シャンテン数に関わらず和了確率の厳密値を簡単に計算することができます。なぜなら

\begin{align}
P_t &= \sum_{l \in L} q^{(l, d)}_t \prod_{j = 0}^{d-1} \frac{b^{(l, j)}}{a^{(l, j)}} \\
&= q^{(d)}_t \sum_{l \in L} \prod_{j = 0}^{d-1} \frac{b^{(l, j)}}{a^{(l, j)}} \\
&= q^{(d)}_t
\end{align}
\tag{15}

となるため、1組の連立確率漸化式を解けば和了確率を計算することができるからです。²

例えば七対子$n$シャンテンの手牌からまっすぐ七対子の和了を目指す(途中で面子手/国士無双に向かわない)場合の和了確率は以下のグラフのようになります。手牌の枚数を13、壁牌の枚数を123として最大18回のツモを想定しています。

おわりに

和了確率を計算するアルゴリズムについて解説しました。プロフィールにも書いているのですが、現在麻雀AIを開発しています。このアルゴリズムは主に打牌選択で活用する予定です。今後、何か進展があったらまた記事を書きたいと思います。