はじめに
組合せ最適化を使うと、麻雀であがれるかどうかの判定もできます。
ここでは、簡単のため、あがり形(雀頭が1つ、面子が3つ)かどうかだけ、考えることにします。また、槓子も対象外とします。
用語
- 雀頭(ジャントウ): 2つの同じ牌
- 面子(メンツ): 順子、刻子、槓子のいずれか
- 順子(シュンツ): 同じ種類で順番に並んだ3つの牌
- 刻子(コーツ): 3つの同じ牌
- 槓子(カンツ): 4つの同じ牌
- あがり形: 1つの雀頭と4つの面子
考え方と定式化
- 条件を満たすかどうかを考えますので、目的関数はなしとします。
- 与えられた牌を使って、雀頭または順子または刻子となる組合せを列挙し、候補とします。
- 候補を上手く選んで、全ての牌がちょうど1回あらわれるようにします。
- 雀頭をちょうど1つ選びます。
| 変数 | $ x_i \in \{0, 1\} $ | $x_i$: $i$番目の候補を選ぶかどうか |
| 制約条件 | $\sum_i{a_{ij} x_i} = 1 ~ ~ \forall j \le 13$ | $a_{ij}$: $i$番目の候補に牌$j$が含まれるかどうか |
| $\sum_{i \in H}{x_i} = 1$ | $H$: 雀頭の候補 |
なお、この問題は、集合分割問題となります。
Pythonによる実行例
- 麻雀の牌を萬子(マンズ)(0-8)、筒子(ピンズ)(10-18)、索子(ソーズ)(20-28)、風牌(かぜはい)(30,32,34,36)、三元牌(さんげんぱい)(38,40,42)の数字で表すことにします。こうすることにより、順子は必ず連続し、連続するならば順子になります。
- 14枚の牌(変数 hai)を入力とし、5つの雀頭または面子を返す関数 calc を定義します。
python3
def calc(hai):
import pandas as pd
from itertools import combinations, product
from pulp import LpProblem, LpBinary, LpVariable, lpSum, value
cand = [] # 候補
a = pd.DataFrame(sorted(hai), columns=['v'])
b = a.v.value_counts()
for i in b[b >= 2].index: # 雀頭候補作成
cand.extend(combinations(a[a.v == i].index, 2))
n2 = len(cand)
for i in b[b >= 3].index: # 刻子候補作成
cand.extend(combinations(a[a.v == i].index, 3))
c = a.v.unique()
for i in range(len(c)-2): # 順子候補作成
if c[i+1] - c[i] == c[i+2] - c[i+1] == 1:
cand.extend(product(a.index[a.v==c[i]],
a.index[a.v==c[i+1]],
a.index[a.v==c[i+2]]))
m = LpProblem() # 数理モデル
v = [LpVariable('v%d'%i, cat=LpBinary) for i in range(len(cand))] # 変数
m += lpSum(v[:n2]) == 1 # 雀頭は1つ
d = [[] for _ in range(14)] # 牌別候補番号リスト
for i, ca in enumerate(cand):
for j in ca:
d[j].append(v[i])
for i in d:
m += lpSum(i) == 1 # 全ての牌がどれかの候補に1つ存在
if m.solve() != 1: return None
return [[a.v[j] for j in cand[i]] for i, vv in enumerate(v) if value(vv) > 0.5]
実際に計算してみましょう。
python3
def show(n):
if n < 30:
return chr(ord('１')+n%10)+'萬筒索'[n//10]
return '東西南北白発中'[n//2-16]
hai = [0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8] # 14枚の牌
for i in calc(hai):
for j in i: print(show(j))
print()
>>>
１萬
１萬
９萬
９萬
９萬
１萬
２萬
３萬
４萬
５萬
６萬
７萬
８萬
９萬
きちんと雀頭と面子を見つけることができました。
以上