ネット上の向聴数計算アルゴリズムの知見に勝手に補足する
概要
ネット上で公開されている麻雀の向聴数計算アルゴリズムの知見は初心者には難解な部分が多いと思われる。そこで、ネット上に転がっている向聴数計算の知見に対して、自分が初心者の頃に理解できなかった点を勝手に補足する。なお、本記事では七対子と国士無双の向聴数については触れない。
ついでに記事の最後でそれぞれの手法の長短をまとめる。
手牌の表現
本記事では手牌を以下のように表現することがある。ただし、簡単のために筒子・索子・字牌は無視。
これは左から順に1mの枚数、2mの枚数、…、9mの枚数を示している。
この例の場合は1m~4mが3枚ずつ、9mが2枚あることを表している。
1. あら氏の手法
向聴数計算を実装しようと思ったほとんどの人間が通ったことがあるであろうあら氏のサイトの手法を補足する。
1.1. 向聴数計算の数式はどこから来ているのか
あら氏は向聴数を求めるアルゴリズム3において、以下の向聴数計算の数式を導入した。
ただし、
とする。
なぜこのような数式が導出できるのかを説明する。
1.1.1. 4面子を作るのに必要な牌の枚数
まず、雀頭を無視して4面子を作ることだけを考える。
面子、面子候補、孤立牌のそれぞれについて、それらを面子に成長させるために必要な牌の数を考えると、それぞれ以下のようになる。
- 面子を面子に成長させるためには、0枚の牌が必要
- 面子候補を面子に成長させるためには、1枚の牌が必要
- 孤立牌を面子に成長させるためには、2枚の牌が必要
今、手牌の中に面子がA個、面子候補がB個あるとすると、4面子を作るためには、
- A個の面子をA個の面子に成長させる
- B個の面子候補をB個の面子に成長させる
- (4 - A - B)個の孤立牌を(4 - A - B)個の面子に成長させる
必要があることが分かる。したがって、4つの面子を作るために必要な牌の枚数は、
となる。
1.1.2. 1雀頭を作るのに必要な牌の枚数
つぎに、1雀頭を作ることを考える。
雀頭、孤立牌のそれぞれについて、それらを雀頭に成長させるために必要な牌の数を考えると、それぞれ以下のようになる。
- 雀頭を雀頭に成長させるためには、0枚の牌が必要
- 孤立牌を雀頭に成長させるためには、1枚の牌が必要
今、手牌の中に雀頭がC個、孤立牌が(1 - C)個あるとすると、1雀頭を作るためには、
- C個の雀頭をC個の雀頭に成長させる
- (1 - C)個の孤立牌を(1 - C)個の雀頭に成長させる
必要があることが分かる。したがって、1つの雀頭を作るために必要な牌の枚数は、
となる。
1.1.3. 向聴数の導出
4面子を作るために必要な牌の枚数と1雀頭を作るために必要な牌の枚数を足し合わせると、以下のようになる。
向聴数とは必要な牌の枚数 - 1のことなので、
となり、これは冒頭のあら氏の数式に対して雀頭に関する補正を加えたものと一致する。
なお、雀頭がある場合に1を引くことは向聴数を求めるアルゴリズム3でも説明されている。
1.1.4. 制約条件
4面子を作る時に孤立牌が(4 - A - B)枚、雀頭を作るときに孤立牌が(1 - C)枚あると置いたが、これが負の値にはなってはいけない。よって以下の制約条件を設ける。
すなわち
である。
したがって向聴数の数式に各数値を代入する前に、
といった調整を行えば良い。ちなみに、面子の数ではなく面子候補の数を調節しているのは、面子の方が面子候補に比べて向聴数を減らす効果が大きく、限界まで使いきりたいからである。
1.2. どのように面子の数、面子候補の数、雀頭の数の組み合わせを求めるのか
向聴数の計算の式は導出できたので、あとは手牌から面子の数、面子候補の数、雀頭の数の組み合わせとしてありえるものを全て列挙し、それぞれを上の向聴数を求める式に代入し、その中で最小となる向聴数を求めれば良い。
たとえば1223mは123mの面子1つと捉えることも、12mと23mの面子候補2つと捉えることも、13mの面子候補1つと22mの雀頭1つと捉えることもできる。面子の数、面子候補の数、雀頭の数の組み合わせは一つに定まらない。
全ての組み合わせを列挙する方法はあら氏のサイトには詳しく書かれていないが、一般的には再帰関数を使うことで簡単に求めることができる。プログラミング初心者にはやや難しいかもしれないので、再帰関数の典型的な練習問題であるハノイの塔などを解いてから取り組むと良いかもしれない。
あら氏とほぼ同じ手法の実装をしている小林氏がGitHubで公開しているコードを参考にするのも良いかもしれない。
ちなみに、字牌は順子と塔子を作ることができないという性質上、再帰関数を使わずとも瞬時に最善の面子の数、面子候補の数の数の組み合わせを求めることができる。
# tehaiは[東の枚数, 南の枚数, ..., 發の枚数, 中の枚数]という形式のリスト
def zihai_pattern(tehai):
mentsu = 0
mentsu_kouho = 0
for i in range(7):
if tehai[i] >= 3: mentsu += 1
if tehai[i] == 2: mentsu_kouho += 1
return (mentsu, mentsu_kouho)
1.3. なぜ面子の数と面子候補の数の組み合わせを事前に計算しておくのか
あら氏は向聴数の計算を高速化するために、1種類の数牌から構成される全ての手牌について、面子の数、面子候補の数の数の組み合わせを事前に計算して記録しておく方法を提案している。
向聴数を求めるときにボトルネックになるのは、面子の数と面子候補の数の組み合わせを全列挙する処理の部分なので、事前にその組み合わせを求めておくことで高速化できるというアイデアである。
たとえば、以下のようにして1種類の数牌で構成される手牌とその手牌から抜き出しうる面子の数、面子候補の数の数の組み合わせを再帰関数等を使って事前に計算しておく。ただし、面子の数と面子候補の数は(面子の数, 面子候補の数)という形式で表現している。
このようなテーブルを事前に作成しておけば、1.2.のzihai_patternと組み合わせることで
# tehaiは[1mの枚数, 2mの枚数, ..., 發の枚数, 中の枚数]という形式のリスト
# tableは事前計算したもの
def all_tehai_pattern(tehai):
for m_menstu, m_mentsu_kouho in table[tehai[0:9]]:
for p_menstu, p_mentsu_kouho in table[tehai[9:18]]:
for s_menstu, s_mentsu_kouho in table[tehai[18:27]]:
z_menstu, z_mentsu_kouho = zihai_pattern(tehai[27:34])
mentsu = m_menstu + p_menstu + s_menstu + z_menstu
mentsu_kouho = m_mentsu_kouho + p_mentsu_kouho + s_mentsu_kouho + z_mentsu_kouho
mentsu_kouho = min(mentsu_kouho, 4 - mentsu)
yield (mentsu, mentsu_kouho)
のようにして、手牌全体の面子の数と面子候補の数の組み合わせを一瞬で求めることができる。
向聴数の数式には雀頭の数も代入しないといけないので、雀頭の抜き出し処理だけは以下のコードのようにして、別で全探索を行う必要がある。
def calculate_shanten(tehai):
min_shanten = float('inf')
# 雀頭を抜かない場合の向聴数
for mentsu, mentsu_kouho in all_tehai_pattern(tehai):
shanten = 8 - mentsu * 2 - mentsu_kouho
min_shanten = min(min_shanten, shanten)
# 雀頭を抜く場合の向聴数
# 抜ける雀頭を全探索
for i in range(34):
# 雀頭を抜けなかったらスキップ
if tehai[i] < 2:
continue
# 雀頭を抜く
tehai[i] -= 2
for mentsu, mentsu_kouho in all_tehai_pattern(tehai):
shanten = 8 - mentsu * 2 - mentsu_kouho - 1
min_shanten = min(min_shanten, shanten)
# 雀頭を復元する
tehai[i] += 2
return min_shanten
1.4. なぜ事前に求める面子の数、面子候補の数の組み合わせは2パターンでよいのか？
1.3.では
のように面子の数、面子候補の数のすべての組み合わせをテーブルに保存しておく必要があるかのように書いたが、例えば(0, 2)は(0, 1)と(0, 0)よりも明らかに向聴数を減らす効果が大きいと分かる。
とするならば、記録しておくべき組み合わせの数はもっと減らせるのではないだろうか？
結論から言えば、向聴数を求めるアルゴリズム7で、
-
面子 * 2 ＋ 面子候補 -
面子 * 10 ＋ 面子候補
の2パターンだけ記録しておけば良いと述べられている。
パターン1は1.1.で求めた向聴数の式を最小化するような組み合わせなので、一見するとパターン1さえ求めておけば良いように見えるが、パターン1だけでは上手くいかない場合があることが向聴数を求めるアルゴリズム7で説明されている。
例えば133345557mをパターン1を最大化するように分解すると、345m、13m、35m、57mとなる。ところが、もし筒子や索子や字牌に面子候補が1つでも存在すれば、面子の数 + 面子候補の数が5つ以上(いわゆる6ブロックの形)になってしまい、13m、35m、57mの面子候補のどれか一つは向聴数を減らすことに寄与しなくなることが分かる。
つまり、6ブロック以上になる場合はパターン1の選び方が最善にならないことがあるため、そのような場合に備えてパターン2も記録しておく必要があるということである。
ところでパターン2の
とは一体何なんだろうか？10という数字はどこから来たのだろうか？
結論から言えば、パターン2は面子をなるべく多く抜き出そうという意図で作られた式である。パターン1だと無駄に面子候補を抜き出した場合に最善にならない可能性があるので、パターン2では面子候補よりも面子を優先して抜き出すようにしているのだ。
面子が面子候補より優先されて抜き出されさえすれば良いので、実は面子の係数は10でなくてもよくて、1億でも1兆でも良いし、実は4でも良い。
ちなみに、あら氏のサイトではこの2パターンだけを記録しておけばよいと説明されているが、本当にこの2パターンだけ記録すれば十分なのだろうか？2パターンだけで十分だと証明されているのだろうか？
おそらくだが、2パターンだけを記録しておけば十分ということは数学的には証明されていないと思う。一応、Pythonを使ってマシンパワーゴリ押しで2パターンで十分だということは検証できたが、もし数学に強い方がいるなら、ぜひ数学的な証明にも挑戦してほしい。
めちゃくちゃ汚い検証コード
import itertools
# 式1: mentsu * 2 + menstu_kouho * 1
# 式2: mentsu * 10 + mentsu_kouho * 1
# あら氏の手法でaがbより悪いと判定されるときにTrueを返す
def is_worse(a, b):
return (a[0] * 2 + a[1] <= b[0] * 2 + b[1]) and (a[0] * 10 + a[1] <= b[0] * 10 + b[1])
def shanten(menstu, mentsu_kouho):
mentsu_kouho = min(mentsu_kouho, 4 - menstu)
return 8 - menstu * 2 - mentsu_kouho
# 面子の数、面子候補の数としてありえるものを全探索
patterns = []
for i in range(5):
for j in range(5):
if i * 3 + j * 2 <= 14:
patterns.append((i, j))
# aがbより悪いと判定されるaとbのペアをpattern_pairsに格納
pattern_pairs = []
for a, b in itertools.product(patterns, repeat=2):
if is_worse(a, b):
pattern_pairs.append((a, b))
# aがbより悪いと判定されるけど、全体で見たときにaを採用したほうが良い場合を探す
for (ma, mb), (pa, pb), (sa, sb) in itertools.product(pattern_pairs, repeat=3):
a_mentsu = ma[0] + pa[0] + sa[0]
a_menstu_kouho = ma[1] + pa[1] + sa[1]
b_mentsu = mb[0] + pb[0] + sb[0]
b_menstu_kouho = mb[1] + pb[1] + sb[1]
if a_mentsu * 3 + a_menstu_kouho * 2 != b_mentsu * 3 + b_menstu_kouho * 2:
continue
if shanten(a_mentsu, a_menstu_kouho) < shanten(b_mentsu, b_menstu_kouho):
print("例外発見!", ma, pa, sa, '|', mb, pb, sb)
2. tomohxx氏の手法
数学の苦手な自分には数式が多くて理解するのが大変だったが、何度も読むうちにようやく理解することができた。
実は内容さえ理解できればとてもシンプルで、あら氏の手法よりも簡単と感じる方も多いのではないだろうか。
2.1. まずは清一色麻雀で理解する
話を簡単にするために、まず清一色麻雀(萬子)の向聴数を求める事を考える。
まずはdistance(距離)という概念を導入する。distanceとは「現在の手牌」を「目標とする手牌」に変換するために必要な牌の枚数のことである。
例えば、現在の手牌が
だったとして、これを
という4面子1雀頭の形にするためには、何枚の牌が必要だろうか？
答えは1mと9mを1枚ずつの合計2枚である。
これをプログラミングっぽく計算すると以下のようになる。
current = [2, 3, 3, 3, 0, 0, 1, 1, 1]
target = [3, 3, 3, 3, 0, 0, 0, 0, 2]
distance = 0
for i in range(9):
distance += max(target[i] - current[i], 0)
要するに、targetには存在していてcurrentには存在していない牌の枚数の和を求めているだけである。これがtomohxx氏が導入したdistanceの計算方法である。
以上のことから、清一色麻雀において「現在の手牌」を「目標とする手牌」に変換するために必要な牌の枚数(= distance)は一瞬で計算することができると分かった。
次に「現在の手牌」の向聴数を求めることを考える。「現在の手牌」を「目標とする手牌」にするまでに何枚の牌が必要かは計算できるようになったので、全ての和了形を列挙して「目標とする手牌」に逐一代入し、その中で「現在の手牌」とのdistanceが最小になるものを選べば良い。
コードでは以下のようになる。
def distance(current, target):
d = 0
for i in range(9):
d += max(target[i] - current[i], 0)
return d
def all_agari_pattern():
(...すべての和了形を列挙する処理...)
# tehaiは[1mの枚数, 2mの枚数, ..., 9mの枚数]という形式のリスト
def calculate_shanten(tehai):
min_distance = float('inf')
for agari in all_agari_pattern():
d = distance(tehai, agari)
min_distance = min(min_distance, d)
return min_distance - 1
向聴数を求めるために、毎回全ての和了形を列挙してdistanceを計算するのは大変なので、あら氏の手法と同じく事前に全ての手牌について最小distanceの計算を済ましておきたいというモチベーションが生まれる。
清一色麻雀において手牌のパターンは118,800通り、和了形のパターンは13,259通りあるので、118800 * 13259 = 1,575,169,200通りの計算を事前に終えておけば、瞬時に向聴数を求めることができる。
Pythonでは
事前計算を行うコードは以下のようになる。
def distance(current, target):
(...略...)
def all_agari_pattern():
(...すべての和了形を列挙する処理...)
def all_pattern():
(...すべての手牌を列挙する処理...)
def pre_calculate():
all_patterns = all_pattern()
all_agari_patterns = all_agari_pattern()
table = dict()
for pattern in all_patterns:
for agari_pattern in all_agari_patterns:
d = distance(pattern, agari_pattern)
if pattern not in table:
table[pattern] = d
else:
table[pattern] = min(table[pattern], d)
return table
table = pre_calculate()
# 好きな形式でtableの内容を出力する
上記のコードを実行したところ、自分のMacでは30分ほどかかった。
以上のことから、清一色麻雀においては全ての手牌と全ての和了形の組み合わせを列挙してdistanceを事前に計算しておくことで、一瞬で向聴数を求めることができると分かった。次は通常の麻雀へと拡張していく。
2.2. 通常の麻雀に拡張する(calculate_shanten編)
通常の麻雀に拡張するとはいっても、実はやることはそこまで変わらない。基本的には手牌を各種の牌に分解して、清一色麻雀でdistanceを求めたときと同じ要領でそれぞれのdistanceを求めていくだけである。
例えば、現在の手牌が1223m135p2468s111zだったとしたら、これを1223m、135p、2468s、111zに分解し、それぞれの種類の牌のdistanceを清一色麻雀のときと同じ要領で求めて、それを足し合わせれば全体のdistanceとなる。
清一色麻雀と異なるのは、清一色麻雀では和了形で萬子を14枚使うことが確定していたのに対し、通常の麻雀では最終的に萬子を何枚使うかが確定していないということである。
例えば1223m135p2468s111zという手牌で、最終的に萬子を3枚使うのであれば萬子の最小distanceは0になる(例えば1223mを123mに変換する場合)が、最終的に萬子を6枚使うのであれば萬子の最小distanceは2になる(例えば1223mを112233mに変換する場合)。
このように通常の麻雀では最終的に各種の牌を何枚使うかによって最小distanceが変化する。
逆にいえば、和了形で使う各種の牌の枚数さえ固定してしまえば、各種の牌の最小distanceを決めることができる。
つまり、
- 和了形が萬子14枚、筒子0枚、索子0枚、字牌0枚だと仮定
- 和了形が萬子12枚、筒子2枚、索子0枚、字牌0枚だと仮定
- 和了形が萬子12枚、筒子0枚、索子2枚、字牌0枚だと仮定
- 和了形が萬子12枚、筒子0枚、索子0枚、字牌2枚だと仮定
- ...
- 和了形が萬子2枚、筒子0枚、索子0枚、字牌12枚だと仮定
- 和了形が萬子0枚、筒子2枚、索子0枚、字牌12枚だと仮定
- 和了形が萬子0枚、筒子0枚、索子2枚、字牌12枚だと仮定
- 和了形が萬子0枚、筒子0枚、索子0枚、字牌14枚だと仮定
のようなそれぞれの仮定のもとでdistanceを求め、その中で最小となるものを求めればよい。
和了形において、使われる各種の牌の枚数が
これをコードにすると以下のようになる。
def calculate_shanten(tehai):
suuhai_table = load_suuhai_table()
zihai_table = load_zihai_table()
min_distance = float('inf')
nums = (0, 2, 3, 5, 6, 8, 9, 11, 12, 14)
for m_num, p_num, s_num, z_num in itertools.product(nums, repeat=4):
if m_num + p_num + s_num + z_num != sum(tehai):
continue
md = suuhai_table[(tehai[0:9], m_num)]
pd = suuhai_table[(tehai[9:18], p_num)]
sd = suuhai_table[(tehai[18:27], s_num)]
zd = zihai_table[(tehai[27:34], z_num)]
min_distance = min(min_distance, md + pd + sd + zd)
return min_distance - 1
上記のコードについて以下の点に注意する。
-
tableのキーがtehaiから(tehaiの一部, 和了形で使う枚数)の形式に変わった
最終的にその種類の牌を何枚使うかによってdistanceが異なるため。Python以外だったらtable[tehai][n]みたいな書き方になりそう。
- 数牌のテーブルと字牌のテーブルは別々に存在する
数牌と字牌では列挙できる和了形のパターンが異なるため、別々に事前計算をする必要がある。
2.3. 通常の麻雀に拡張する(pre_calculate編)
次はdistanceを事前計算するpre_calculate.pyのコードを通常の麻雀用に拡張していく。こちらも清一色麻雀のときとやることはほぼ同じだが、以下の相違点には注意する。
-
all_patternでは手牌の一部としてありえるものをすべて列挙する。
例えば1223m135p2468s111zの1223mなど。
-
all_agari_patternでは和了形の一部としてありえるものをすべて列挙する。
例えば112233m456s789m11zの112233mなど。
-
tableのキーを(tehai, n)の形式に変更する
理由は2.2で述べた通りである。
以上の相違点に注意しながら、事前計算を行うコードを通常の麻雀用に拡張したものが以下である。
def distance(current, target):
(...略...)
def all_suuhai_agari_pattern():
(...数牌の和了形の一部としてありえるものを列挙する処理...)
def all_zihai_agari_pattern():
(...字牌の和了形の一部としてありえるものを列挙する処理...)
def all_suuhai_pattern():
(...数牌の手牌の一部としてありえるものを列挙する処理...)
def all_zihai_pattern():
(...字牌の手牌の一部としてありえるものを列挙する処理...)
def pre_calculate()
all_suuhai_patterns = all_suuhai_pattern()
all_agari_suuhai_patterns = all_agari_suuhai_pattern()
suuhai_table = dict()
for suuhai_pattern in all_suuhai_patterns:
for agari_suuhai_pattern in all_agari_suuhai_patterns:
d = distance(suuhai_pattern, agari_suuhai_pattern)
n = sum(agari_suuhai_pattern)
key = (suuhai_pattern, n)
if key not in table:
suuhai_table[key] = d
else:
suuhai_table[key] = min(suuhai_table[key], d)
(...字牌についても同様...)
return suuhai_table, zihai_table
suuhai_table, zihai_table = pre_calculate()
# 好きな形式でsuuhai_tableとzihai_tableの内容を出力する
ちなみに清一色麻雀では手牌としてありえるパターンは118,800通り、和了形のパターンは13,259通りだったが、今回の拡長で14枚未満の手牌や和了形も許容したことによって、数牌の場合、手牌としてありえるパターンは405,350通り、和了形のパターンは21,743通りにまで増える。
組み合わせでは405350 * 21743 = 8,813,525,050通りの計算をする必要があり、これは拡張前の1,575,169,200通りの6倍近くになる。
実際に自分のMacで事前計算を行ったところ、4時間半ほどかかった
3. それぞれの長短
3.1. あら氏の手法
長所1. 事前計算にかかる時間が短い
自分の場合は10分もかからなかった。
長所2. 事前計算をしなくても十分高速
実際、上述した小林氏のコードでは事前計算を行っていない。
短所1. コードが複雑になる
向聴数の数式のようなパッと見ただけでは理解が難しい数式が出てくるので初心者には難解になりがち。
面子の数と面子候補の数の組み合わせが2パターンだけで十分というのも、おそらく数学的には証明されていないので、初心者にはハテナマークが拭えない。
面子と面子候補を抜き出す処理の前に、雀頭がある場合と雀頭がない場合の条件分岐が必要だったり、面子と面子候補の数の合計が4を超えたときは面子候補の数の調整が必要だったりと、例外の処理も多い。
短所2. 5枚目の牌を待つ聴牌を許可する
例えば11119999m111p111sのような手牌に対してあら氏の手法を適用すると聴牌だと判定される。ルールにもよるが、一般的には純手牌で4枚使い切っている牌を待つ聴牌は許可しないことが多いと思う。
聴牌と判定された場合に待ちの枚数が残り何枚あるかをカウントして0枚の場合は向聴数1を返すという処理を挟むことで補正は可能だが、コードはさらに複雑になるだろう。
ちなみに天鳳の牌理ツールでは1向聴と判定される。
3.2. tomohxx氏の手法
長所1. コードがシンプルになる
distanceを求める処理は、人間が向聴数を数えるときとほぼ同じロジック(頭に実際の和了形をイメージして牌が何枚足りないかを数える)なので、初心者でも分かりやすい。例外処理も少なくて、if文がほとんど出てこない。
長所2. 5枚目の牌を待つ聴牌を許可しない
和了形の列挙の際に同じ牌を5枚持つものを列挙しない限り、何も工夫せずとも自動で5枚目の牌を待つ聴牌を許可しなくなる。
短所1. 事前計算にかかる時間が長い
自分のコードも良くないのかもしれないが、4時間半は長かった。
参考
つるくもによるあら氏の手法での実装例 つるくもによるtomohxx氏の手法での実装例
Discussion