概要

麻雀のプログラムを作るには、和了形を求めるアルゴリズムが必要です。ネットを調べるといくつかのやり方があったので、どれが正しいのか気になりました。そこで本記事では、麻雀の和了形を求めるアルゴリズムをまとめ、それらの正当性を考察します。

結論

全探索¹ ² ³ ⁴か、EIKI法⁵を使えば良いです。

麻雀の和了形

麻雀の点数計算では手牌から和了形を構成し、役を判定します。
麻雀の和了形には以下の3種類があります。

一般形（4面子1雀頭）
七対子
国士無双

手牌から複数の和了形を構成できる場合は、最も点数が高いパターンを採用します(高点法)。したがって、可能な和了形をすべて列挙する必要があります。

七対子と国士無双は簡単なので、一般形のみ考えます。

一般形の求め方

ネットを調べると、だいたい共通して以下の流れになっています。

雀頭を2枚抜き出す。
残り12枚の手牌を4つの面子に分解する。

2で難しいのは刻子の扱いです。
もし刻子を無視して良いなら簡単です。手牌を昇順にソートして、小さい牌から順番に順子を抜き出せば良いです。

しかし、もしある牌が3枚以上あると、その牌を刻子として抜き出す場合と、順子として抜き出す場合の2通りが考えられます。

たとえば、雀頭を除いた手牌が 111333444555m のとき、刻子4つとみなすことも、刻子1つ順子3つとみなすこともできます。実際にはそれぞれの点数を計算し、高い方が採用されます。

面子分解のアルゴリズム

ネットを調べると、手牌を面子に分解する方法は主に3つあります。
ここで、ある牌が3枚以上あるときその牌を刻子候補といいます。

全探索¹ ² ³ ⁴: 全ての刻子候補に対して、刻子として抜き出す場合と順子として抜き出す場合の2通りを試す
山岡法⁶ ⁷: 刻子→順子の順番で抜き出すのと、順子→刻子の順番で抜き出す2通りを試す
EIKI法⁵: 山岡法に加えて、刻子を1つだけ抜き出した後、順子→刻子の順番で抜き出す3通りを試す

刻子候補は最大で4組あるので、1は最大で2^4=16通りを試す必要があります。それに対して2,3では少ない通り数で済ますことができます⁸。

これらのうちどれが正しいのでしょうか？結論を言うと1と3が正しいです。これからその理由を見ていきます。

面子分解のパターン

刻子候補に注目して、面子分解するにはどんなパターンを試す必要があるかを考察します。

雀頭を除くと手牌は12枚なので、刻子候補は0~4組のいずれかです。

なお、簡単のため1色の場合のみ考えます。また、手牌は昇順にソートされているとします。

刻子候補が0組の場合

順子だけ抜き出せば良いです。

刻子候補が1組の場合

刻子候補に対して以下の2通りを試す必要があります。

パターン	例
すべて刻子として抜き出す	`112233555789m`
すべて順子として抜き出す	`112233345789m`

刻子候補が2組の場合

刻子候補に対して以下の4通りを試す必要があります。

パターン	例
すべて刻子として抜き出す	`123555666789m`
すべて順子として抜き出す	`122233344789m`
小さい方のみ刻子として抜き出す	`111334455567m`
大きい方のみ刻子として抜き出す	`112233345777m`

刻子候補が3組の場合

刻子候補に対して以下の4通りを試す必要があります。

パターン	例
すべて刻子として抜き出す	`111333666789m`
すべて順子として抜き出す	`111222333789m`
一番小さい牌のみ刻子として抜き出す	`111344455566m`
一番大きい牌のみ刻子として抜き出す	`122233344666m`

刻子候補のうち、2組を刻子、1組を順子として抜き出すことはできません。

証明

刻子候補1組を順子として抜き出すには、順子が3つ、合計9枚必要です。刻子2つを抜き出すと、残りの手牌は6枚しかないので不可能です。

また、刻子候補を順子、刻子、順子の順番で抜き出すこともできません。

証明

刻子候補を $XXXYYYZZZ$ とします。ここで

\begin{align}
&Y \geq X + 1 \tag{1} \\
&Z \geq Y + 1 \geq X+2 \tag{2}
\end{align}

です。

$Y$ を刻子として抜き出すと、残りの面子は3つです。$X$ は順子として抜き出すので、残り3つの面子はすべて順子です。また、それらの順子はすべて $Z$ を含みます。したがって、$(1)(2)$ とあわせると

\begin{align}
&Z \leq X + 2 \tag{3} \\
&Y \leq X + 1 \tag{4}
\end{align}

であり、

\begin{align}
&Z = X + 2 \tag{5} \\
&Y = X + 1 \tag{6}
\end{align}

で、順子はすべて $XYZ$ の形です。
したがって、すでに抜き出した刻子と合わせて$Y$ は少なくとも6枚必要で、これは不可能です。

刻子候補が4組の場合

刻子4組で12枚なので、$AAABBBCCCDDD$の形です。

刻子候補に対して以下の3通りを試す必要があります。

パターン	例
すべて刻子として抜き出す	`111333555777m`
一番小さい牌のみ刻子として抜き出す	`111333444555m`
一番大きい牌のみ刻子として抜き出す	`111222333555m`

刻子3つ、順子1つを抜き出すことはできません。

証明

刻子候補1組を順子として抜き出すためには、3*3=9枚の牌が必要です。刻子3つを抜き出すと残りの手牌は3枚しかないので牌が足りません。

同様に、刻子2つ、順子2つを抜き出すこともできません。

すべて順子として抜き出すこともできません。

証明

$A$を順子として抜き出すので、順子は $ABC$ の形で、

\begin{align}
&B = A + 1 \\
&C = A + 2
\end{align}

です。残りは $D$ 3枚なので順子にできません。

順子、刻子、順子、順子の抜き出し方もできません。

証明

$A$を順子として抜き出すので、順子は $ABC$ の形で、

\begin{align}
&B = A + 1 \\
&C = A + 2
\end{align}

です。したがって小さい3つの刻子候補を順子、順子、順子として抜き出すことになり矛盾します。

同様に、順子、順子、刻子、順子の抜き出し方もできません。

まとめ

すべてのパターンを面子分解するには、以下の4通りを試す必要があります。

すべて刻子として抜き出す
すべて順子として抜き出す
一番小さい牌のみ刻子として抜き出す
一番大きい牌のみ刻子として抜き出す

アルゴリズムの正当性

先ほどまとめたアルゴリズムに戻ります。

全探索¹ ² ³ ⁴は明らかに正しいです。

山岡法⁶ ⁷は間違っています。たとえば 11123334445599m を和了判定できません⁹。

EIKI法⁵は正しいです。

証明

任意の手牌に対して、
面子分解される $\Leftrightarrow$ EIKI法で面子分解される
ことを示します。

$\Leftarrow$ は明らかです。

$\Rightarrow$ を示します。

今までの議論から、刻子候補に着目すると、すべての手牌は以下のいずれかの方法で面子分解されます。

すべて刻子として抜き出す
すべて順子として抜き出す
一番小さい牌のみ刻子として抜き出す
一番大きい牌のみ刻子として抜き出す

1,2,3については明らかにEIKI法でも面子分解されます。

4について、刻子候補が1組の場合は1と同様なので、刻子候補が2組以上の場合のみ考えます。

このとき、刻子候補のうち一番大きい牌を $X$ とすると、すべての順子に対して、一番小さい牌は $X$ 未満です。

証明

ある順子$ABC$が存在し、$A \geq X$ とします。

$X$以外の刻子候補が1組以上存在します。それらのうちの一つを$Y$とします。仮定より、

\begin{align}
&Y < X \tag{1} \\
&Y < A \tag{2}
\end{align}

です。

$XXX$と$ABC$を抜き出すと残りの手牌は6枚です。$(1)(2)$より、残りの手牌は$YYY$を含みます。
$Y$を順子として抜き出すには、手牌が9枚必要ですが、手牌が足りません。

したがって、EIKI法により順子→刻子の順番で抜き出すと面子分解できます。

なお、⁵ で以下のように書かれていますが、実際必要ありません。

最後の刻子取出しは未知なるケースに対応するための念押しであるが、要らないかもしれない

麻雀のアガリ判定アルゴリズムで苦戦したこと ↩ ↩² ↩³
麻雀の和了形を求めるには ↩ ↩² ↩³
【麻雀】【Python】アガリを判定するロジックを考える【アルゴリズム】 ↩ ↩² ↩³
和了と聴牌 ↩ ↩² ↩³
麻雀和了り判定 ↩ ↩² ↩³ ↩⁴
麻雀和了判定（役の判定）アルゴリズム ↩ ↩²
ピグ麻雀のアルゴリズム ↩ ↩²
16通りを試す時間はプログラム全体から言うと無視できるレベルなので、実際は実装が簡単なものを選ぶと良いと思います。 ↩
筆者は記事をざっと見ただけでコードを詳細に追ってないので、実際のプログラムがどうかはわかりません。また漏れるパターンはごく一部なので、「うちの麻雀はこういうルールです」で済まされるレベルだと思います。 ↩