Edited at

「ミリジャン」の手役を自動で判定するアルゴリズムを発明しました


1. 概要

「ミリジャン」とは、アイドルマスターミリオンライブの同人ゲームの一つです(作者:電子レンジさん)。

ルールはドンジャラに近いですが、アイマスらしい仕様なので超気になっています。

……ただ、麻雀にしてもドンジャラにしてもミリジャンにしても、相手がいないと打てない問題がつきまといます。

そこで、一人でコツコツ練習できるサイトを作成しました。その時、どんなアルゴリズムを使ったのかについて解説します。


2. 基本ルール


  • 同一札は3枚で、765プロのアイドル52人+詩花+早坂そら の計54種。つまり全部で162枚

  • 手牌はツモった際に13枚。牌を切った際は12枚になる

  • 役は1~5枚組の「アイドルのユニット(楽曲で一緒になったペアも含む)」。13枚組も大丈夫らしい?

  • 完成した役の組み合わせで13枚を構成できた際に「アガリ」。ツモ・ロンどちらもOK。ロン時の発声は「ティーンときた!

  • ポンは無いがチーはある(3枚以上使う役に限る)。チー時の発声も「ティーンときた!」

  • 事前に自分の「担当アイドル」を宣言する。得点計算時に絡む

  • アガった際の点数は、役の組それぞれの点数の合算。1~5枚組で1000・2000・4000・6000・8000点。鳴いているとその組の点数が半分になり、担当アイドルが含まれている組の点数は倍になる

  • 「詩花」は1枚で役とみなす。「早坂そら」は、ツモる代わりに切ることで、「控え室」(麻雀で言うところの河)から好きな牌を持ってこれる


3. 判定アルゴリズムについて

いやね、ゲーム自体のプログラミングはまだ簡単なんですよ。役の判定をどうするかが最大の関心事でした。

麻雀と違い前例がないので、自分でイチからひねり出す必要があります。思いつくまでマジで本当に辛かった……!


3-1. 手牌に含まれる役の一覧を抽出する

Pythonでコードを書いてみるとこんな感じです。実際のサイトはJavaScriptで書きましたが

from typing import List, Dict, Union, Set

UNIT_LIST: List[Dict[str, Union[str, Set[str]]]] = [
{'name': '(詩花)', 'member': {'詩花'}},
{'name': 'ハルカナミライ', 'member': {'春香', '未来'}},
{'name': '成長Chu→LOVER!!', 'member': {'杏奈', '百合子'}},
{'name': 'Light Year Song', 'member': {'やよい', '真', '亜美', '真美', '響'}},
]

# 手牌
hands = ['春香', '未来', '杏奈', '百合子', 'やよい', '真', '亜美', '真美', '響', '詩花', 'あずさ', '伊織', '貴音']

# 手牌をあらかじめSetしたものを用意する
hands_set = set(hands)

# 役のそれぞれにアクセスし、当てはまるものを抽出する
hand_unit_list = [x for x in UNIT_LIST if len(x['member'] & hands_set) == len(x['member'])]


3-2. どの役とどの役を組み合わせるかを判定する

どう考えても難しいでしょこれ。麻雀と違って「4面子+対子」みたいなパターンすらないし……」

そう思っていた時期が私にもありました。事実、複雑なバックトラック組まされるんちゃうかとビビっていました。

ただ、数日考えた結果、比較的簡単なコードで書けることに気づきました。

まず、手牌および役に、各アイドルが何枚入っているかを調べます。なお、そらさんへの対応は後述します

def tile_info(hands: List[str]):

count: Dict[str, int] = {}
for hand in hands:
if hand not in count:
count[hand] = 0
count[hand] += 1
return count

# 手牌におけるカウント
hands_info = tile_info(hands)

# 役それぞれのカウント
unit_info_list = [tile_info(list(x['member'])) for x in hand_unit_list]

次に、それぞれの役が、手牌の中で何回使えるかを確認します。例えば詩花を複数枚ツモったとしても大応できるように……。

def unit_count_in_hands(hands_info: Dict[str, int], unit_info: Dict[str, int]):

list_h = []; list_u = []
for key in unit_info:
list_h.append(hands_info[key])
list_u.append(unit_info[key])
max_count = 1
for count in range(2, 4):
list_u2 = [x * count for x in list_u]
if list_h >= list_u2:
max_count = count
else:
break
return max_count

# 含まれる役の個数
unit_count_list = [unit_count_in_hands(hands_info, x) for x in unit_info_list]

次に、「それぞれの役を何個使うか」の全組み合わせを求めます。例えば役A~Dがそれぞれ1・1・1・2回使えた場合、2×2×2×3=24通りを展開します。再帰して枝刈りするとかの方が恐らく効率的ですが、 普段そこまで大量に役が入ってこない ので、CPUを信頼してざっくり行ってしまいます。

# 組み合わせを展開

unit_patterns: List[List[int]] = []
for count_size in unit_count_list:
temp = list(range(0, count_size + 1))
if len(unit_patterns) == 0:
unit_patterns = [[x] for x in temp]
else:
new_unit_patterns = []
for unit_pattern in unit_patterns:
for val in temp:
temp2 = [x for x in unit_pattern]
temp2.append(val)
new_unit_patterns.append(temp2)
unit_patterns = new_unit_patterns

最後に、「組み合わせXを用いて役を決定した場合、それが手牌の中に収まるか・得点は幾らか」を計算します。

ハッキリ言ってゴリ押しですのが、システマティックにIPソルバーを使うよりかは実用上高速かと。

(修正:得点とアガリとではアガリを優先させるようにした)

# 組み合わせunit_patternを用いてunit_info_listから役を決定した一覧(各アイドルの枚数)

def calc_units_info(unit_info_list: List[Dict[str, int]], unit_pattern: List[int]) -> Dict[str, int]:
output: Dict[str, int] = {}
for i in range(0, len(unit_info_list)):
if unit_pattern[i] > 0:
for key, val in unit_info_list[i].items():
if key not in output:
output[key] = 0
output[key] += val * unit_pattern[i]
return output

# 手牌と役の組み合わせとを比較して、その組み合わせが妥当かを判断する
def judge_info(hands_info: Dict[str, int], units_info: Dict[str, int]) -> bool:
for key, val in units_info.items():
if key not in hands_info:
return False
if hands_info[key] < val:
return False
return True

# 役それぞれの点数
SCORE_DICT: Dict[int, int] = {1: 1000, 2: 2000, 3: 4000, 4: 6000, 5: 8000}
unit_score_list = [SCORE_DICT[len(x['member'])] for x in hand_unit_list]

# 各組み合わせについて、実現可能かを判定し、最大スコアのものを選択する
max_score = 0
max_unit_pattern = []
for unit_pattern in unit_patterns:
selected_units_info = calc_units_info(unit_info_list, unit_pattern)
if judge_info(hands_info, selected_units_info):
score = 0
index = 0
for p, s in zip(unit_score_list, unit_pattern):
score += p * s
tile_count += s * len(hand_unit_list[index]['member'])
index += 1
if tile_count == 13:
score += 10000000
if score > max_score:
max_score = score
max_unit_pattern = unit_pattern
max_score = max_score % 10000000

# 結果を出力する
print(f'点数:{max_score}点')
for pattern, unit in zip(max_unit_pattern, hand_unit_list):
if pattern > 0:
print(f'[{pattern}回] {unit["name"]} {unit["member"]}')

"""出力例:
点数:13000点
[1回] (詩花) {'詩花'}
[1回] ハルカナミライ {'未来', '春香'}
[1回] 成長Chu→LOVER!! {'百合子', '杏奈'}
[1回] Light Year Song {'響', '真', 'やよい', '真美', '亜美'}
"""


3-3. 早坂そらさんはどう処理するか

再帰でカードを53通りに置き換えて一番点数が高いものを採用します

……とだけ書くと不親切なので補足を。

早坂そらさんも他のカード同様に牌山に3枚ありますので、最悪の場合53×52×51通りの役判定およびスコア計算が必要になります。

当然高コストなので、「手牌の組み合わせとスコアをキャッシュする」といった細工が必要になります。

また、スコア計算も上記のようなものではチューニングが甘いため、前述の本番用コードではビット演算(ビットボード)を駆使して高速化しています。ビット演算の魅力については、次の記事も参考になるかと。

 ビットボードの凄さをざっくりと解説してみる - Qiita


4. 参考資料