15
17

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

組合せ最適化で麻雀のあがりを判定する

Last updated at Posted at 2016-04-18

はじめに

組合せ最適化を使うと、麻雀であがれるかどうかの判定もできます。
ここでは、簡単のため、あがり形(雀頭が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()
>>>


















きちんと雀頭と面子を見つけることができました。

以上

15
17
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
15
17

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?