概要
麻雀のプログラムを作るには、和了形を求めるアルゴリズムが必要です。ネットを調べるといくつかのやり方があったので、どれが正しいのか気になりました。そこで本記事では、麻雀の和了形を求めるアルゴリズムをまとめ、それらの正当性を考察します。
結論
麻雀の和了形
麻雀の点数計算では手牌から和了形を構成し、役を判定します。
麻雀の和了形には以下の3種類があります。
- 一般形（4面子1雀頭）
- 七対子
- 国士無双
手牌から複数の和了形を構成できる場合は、最も点数が高いパターンを採用します(高点法)。したがって、可能な和了形をすべて列挙する必要があります。
七対子と国士無双は簡単なので、一般形のみ考えます。
一般形の求め方
ネットを調べると、だいたい共通して以下の流れになっています。
- 雀頭を2枚抜き出す。
- 残り12枚の手牌を4つの面子に分解する。
2で難しいのは刻子の扱いです。
もし刻子を無視して良いなら簡単です。手牌を昇順にソートして、小さい牌から順番に順子を抜き出せば良いです。
しかし、もしある牌が3枚以上あると、その牌を刻子として抜き出す場合と、順子として抜き出す場合の2通りが考えられます。
たとえば、雀頭を除いた手牌が 111333444555m のとき、刻子4つとみなすことも、刻子1つ順子3つとみなすこともできます。実際にはそれぞれの点数を計算し、高い方が採用されます。
面子分解のアルゴリズム
ネットを調べると、手牌を面子に分解する方法は主に3つあります。
ここで、ある牌が3枚以上あるときその牌を刻子候補といいます。
- 全探索1 2 3 4: 全ての刻子候補に対して、刻子として抜き出す場合と順子として抜き出す場合の2通りを試す
- 山岡法6 7: 刻子→順子の順番で抜き出すのと、順子→刻子の順番で抜き出す2通りを試す
- EIKI法5: 山岡法に加えて、刻子を1つだけ抜き出した後、順子→刻子の順番で抜き出す3通りを試す
刻子候補は最大で4組あるので、1は最大で2^4=16通りを試す必要があります。それに対して2,3では少ない通り数で済ますことができます8。
これらのうちどれが正しいのでしょうか？結論を言うと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通りを試す必要があります。
- すべて刻子として抜き出す
- すべて順子として抜き出す
- 一番小さい牌のみ刻子として抜き出す
- 一番大きい牌のみ刻子として抜き出す
アルゴリズムの正当性
先ほどまとめたアルゴリズムに戻ります。
山岡法6 7は間違っています。たとえば 11123334445599m を和了判定できません9。
EIKI法5は正しいです。
証明
任意の手牌に対して、
面子分解される $\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法により順子→刻子の順番で抜き出すと面子分解できます。
なお、5 で以下のように書かれていますが、実際必要ありません。
最後の刻子取出しは未知なるケースに対応するための念押しであるが、要らないかもしれない