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. 参考資料