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

概要

前回の投稿では、手役(ユニット)の判定処理を書きました。
ただ、じっくり考えた結果、バックトラック(バックトラッキング)を実装するのがそこまで難しくないことが分かったので投稿します。

バックトラッキングとは

　ざっくり言いますと、「ある可能性を試す」→「駄目だったら手を戻す」→「別の可能性を試す」……といった行動により、探索していくアルゴリズムのことです。ここではミリジャンを例に説明してみましょう。

順番	1	2	3	4	5	6	7	8	9	10	11	12	13
アイドル	春香	千早	律子	あずさ	翼	まつり	星梨花	海美	志保	可奈	このみ	瑞希	ジュリア

例えばこんな手牌があったとして、例えば「春香・千早で『CRIMSON LOVERS』が組める」と考えたとします。
すると、その2枚のユニットを確定させ、残りの手牌でどういった組み合わせがあるかを考えます。

順番	1	2	3	4	5	6	7	8	9	10	11	12	13
アイドル	春香	千早	律子	あずさ	翼	まつり	星梨花	海美	志保	可奈	このみ	瑞希	ジュリア
確定？	○	○

すると、例えば「星梨花・海美・志保・可奈で『Clover』が組める」と考えられます。これを繰り返し、最終的に全部確定させられれば「アガリ」のパターン確定と言えます。

……ただ、賢明なミリジャン勢ならお気づきかと思いますが、このまま進めると律子・あずさに割り当てる役がありません。
つまり、どこかで「確定していたユニットを未確定の状態に戻す」操作が必要になります。この試行錯誤を図に書くとこんな感じ。

もちろんこのままだと「最初にVTB、次にClover」と「最初にClover、次にVTB」など重複が出まくりますが、消そうと思えばそういった重複も簡単に消せます(いわゆる枝刈り)。とにかく可能性を順に当たりつつ、駄目な時は戻ることを繰り返すのがバックトラッキングです。

どのように実装するのか？

前回と同じく、Pythonを例に実装してみます。
バックトラッキングではしばしば再帰関数が使われます。つまり、「可能性がある役を順に試す」操作がどの階層でも同じなので、自分自身を呼び出すようなコードを書けば簡潔に書けるわけです。いきなり答えを書いてしまうとこんな感じ。

def find_best_unit_pattern(hands: List[str]) -> Tuple[List[Dict[str, Union[str, Set[str]]]], int]:
    """handsから、最も点数を稼げる手牌の組み合わせを取り出す。
       戻り値は、(ユニットの一覧, 点数)
    """

    # 手牌がない＝使い切れたのでアガリとみなす
    if len(hands) == 0:
        return [], 1000000

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

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

    # ユニットを1つ選択し、それを取り去った残りで探索
    best_pattern = ([], 0)
    for unit in hand_unit_list:
        # 選択したユニット(unit)を、手牌(hands)から取り去った、新たな手牌(new_hands)を生成する
        temp = set()
        new_hands = []
        for hand in hands:
            if hand in unit['member'] and hand not in temp:
                temp.add(hand)
                continue
            new_hands.append(hand)

        # 新たな手牌を元に、最適なユニットの組み合わせを算出する(再帰関数)
        result = find_best_unit_pattern(new_hands)

        # result[1] + unit_scoreは、「handsからunitを選択した際の残りの手牌での点数＋unit自身の点数」
        unit_score = SCORE_DICT[len(unit['member'])]
        if result[1] + unit_score > best_pattern[1]:
            # ベストな点数、および組み合わせを更新する
            best_pattern = (result[0] + [unit], result[1] + unit_score)
    return best_pattern

まず最初に行うのが終了判定。手牌が再帰の途中で0枚になった＝余らずユニットを取り切れた＝アガリなので、あえて得点ボーナスを大幅に与えておきます。正しい点数は1000000との剰余を求めればいいだけなので簡単ですね。

    # 手牌がない＝使い切れたのでアガリとみなす
    if len(hands) == 0:
        return [], 1000000

次に、手牌から可能性があるユニットの一覧を取り出します。ここは幾らでも高速化の余地がありますが、再帰が無駄に深くなる方が高コストなので、簡潔に書いても実用上問題ないでしょう。

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

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

次に、可能性があるユニットそれぞれについて、「ユニットの分を取り除いた新たな手牌」を生成します。こういうのはどう書くのが一番エレガントなのでしょう？　「各アイドルの枚数を保持する型」を引数に入れて再起するのが速い？

        # 選択したユニット(unit)を、手牌(hands)から取り去った、新たな手牌(new_hands)を生成する
        temp = set()
        new_hands = []
        for hand in hands:
            if hand in unit['member'] and hand not in temp:
                temp.add(hand)
                continue
            new_hands.append(hand)

後は、再帰を1段深くしつつ、最適解の更新も実施します。コメントに書いてある通りですね。

        # 新たな手牌を元に、最適なユニットの組み合わせを算出する(再帰関数)
        result = find_best_unit_pattern(new_hands)

        # result[1] + unit_scoreは、「handsからunitを選択した際の残りの手牌での点数＋unit自身の点数」
        unit_score = SCORE_DICT[len(unit['member'])]
        if result[1] + unit_score > best_pattern[1]:
            # ベストな点数、および組み合わせを更新する
            best_pattern = (result[0] + [unit], result[1] + unit_score)

どれほどパフォーマンスが異なるのか？

上記のような例では、初手で考えられるユニットがたかだか9種類だけだったので、前回のようなゴリ押しでも組み合わせ総数は2^9＝512通りしかなく楽でした。

# パターン1
hands = ['志保', '星梨花', '海美', '可奈', 'まつり', 'このみ', '瑞希', '翼', 'ジュリア', '律子', '春香', '千早', 'あずさ']

hand_unit_list = [
 {'member': {'翼', '海美'}, 'name': 'マイティセーラーズ(2人)'},
 {'member': {'まつり', 'このみ'}, 'name': 'Decided'},
 {'member': {'志保', '可奈'}, 'name': 'メリー(デュオ)'},
 {'member': {'星梨花', '海美'}, 'name': 'Do-Dai(カバー)'},
 {'member': {'春香', '千早'}, 'name': 'CRIMSON LOVERS'},
 {'member': {'瑞希', 'ジュリア', '翼'}, 'name': 'アイル'},
 {'member': {'星梨花', '海美', '可奈'}, 'name': 'Dreaming!(カバー)'},
 {'member': {'あずさ', '春香', '千早', '律子'}, 'name': 'Vault That Borderline!'},
 {'member': {'志保', '星梨花', '海美', '可奈'}, 'name': 'Clover'}
]

best_pattern = (
  [
    {'member': {'志保', '海美', '星梨花', '可奈'}, 'name': 'Clover'},
    {'member': {'春香', 'あずさ', '千早', '律子'}, 'name': 'Vault That Borderline!'},
    {'member': {'翼', '瑞希', 'ジュリア'}, 'name': 'アイル'},
    {'member': {'まつり', 'このみ'}, 'name': 'Decided'}
  ],
 1018000
)

ただ、AS組が多いなどしてユニットの候補が多くなると話は一変します。16ユニットともなると2^16=65536通りもあるので、計算時間が遅くなるか、あるいは探索しきれずメモリ不足に陥ってしまうこともあります。しかしバックトラッキングだとサクサク計算できるわけですね。

# パターン2
hands = ['春香', '千早', '美希', '真', '貴音', 'やよい', 'まつり', '真美', 'エミリー', '亜美', '桃子', '伊織', '育']

hand_unit_list = [
 {'member': {'伊織', 'エミリー'}, 'name': 'little trip around the world'},
 {'member': {'エミリー', 'まつり'}, 'name': 'Charlotte・Charlotte'},
 {'member': {'真美', 'やよい'}, 'name': 'わんつ→ているず'},
 {'member': {'千早', '春香'}, 'name': 'CRIMSON LOVERS'},
 {'member': {'美希', '伊織'}, 'name': "始めのDon't worry"},
 {'member': {'育', '伊織', '桃子'}, 'name': 'きゅんっ！ヴァンパイアガール'},
 {'member': {'真', '伊織', 'やよい'}, 'name': '待ち受けプリンス'},
 {'member': {'美希', '伊織', '貴音'}, 'name': '99 Nights'},
 {'member': {'真', '真美', '春香'}, 'name': '咲きませ！！乙女塾'},
 {'member': {'美希', '千早', '春香'}, 'name': 'Fate of the World'},
 {'member': {'真美', '亜美', 'やよい'}, 'name': 'Funny Logic'},
 {'member': {'美希', '真美', '亜美', '伊織'}, 'name': '星彩ステッパー'},
 {'member': {'美希', '春香', '真', '千早', 'やよい'}, 'name': 'メリー'},
 {'member': {'美希', '春香', '真', '千早', 'エミリー'}, 'name': 'World changer'},
 {'member': {'伊織', '春香', '真', '真美', '亜美'}, 'name': 'Miracle Night'},
 {'member': {'美希', '貴音', '真', '真美', 'やよい', '亜美'}, 'name': 'ザ・ライブ革命でSHOW!'}
]

best_pattern = (
  [
    {'member': {'真', 'やよい', '美希', '真美', '貴音', '亜美'}, 'name': 'ザ・ライブ革命でSHOW!'},
    {'member': {'伊織', '育', '桃子'}, 'name': 'きゅんっ！ヴァンパイアガール'},
    {'member': {'千早', '春香'}, 'name': 'CRIMSON LOVERS'},
    {'member': {'エミリー', 'まつり'}, 'name': 'Charlotte・Charlotte'}
  ],
 1018000
)

ちなみに当環境(Core i7-4790K、Windows 10 64bit、Windows上のPython 3.7)で計測したところ、パターン2を100回判定するのに掛かった時間が、前回の手法だと69.5秒だったところ、今回の手法では2.49秒……30倍近く高速化したことになります。

より高速にするには？

そもそもユニット判定のコストが高いので、「前段のユニット判定で得られたユニットリストを再利用」するのが分かりやすく効きます。
また、同一の手牌から得られる判定結果は同一なので(副作用がない)、戻り値をメモ化してキャッシュするのも効きます。実験した結果、前回より600倍以上、単なるバックトラッキングより20倍以上高速になりました。つよい。

方式	1回当りの時間[s]
前回(ほぼ全探索)	0.695
今回(バックトラッキング)	0.0249
今回＋ユニットリスト再利用	0.00217
今回＋キャッシュ化	0.00570
今回＋再利用＋キャッシュ	0.00113

# キャッシュ
cache: Dict[str, Tuple[List[Dict[str, Union[str, Set[str]]]], int]] = {}

def find_best_unit_pattern_2(hands: List[str], pre_unit_list=None) -> Tuple[List[Dict[str, Union[str, Set[str]]]], int]:
    # キャッシュに登録されていれば、その値を返す
    hands_key = ','.join(hands)
    if hands_key in cache:
        return cache[hands_key]

    if pre_unit_list is None:
        pre_unit_list = UNIT_LIST

    # 手牌がない＝使い切れたのでアガリとみなす
    if len(hands) == 0:
        return [], 1000000

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

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

    # 役を1つ選択し、それを取り去った残りで探索
    best_pattern = ([], 0)
    for unit in hand_unit_list:
        temp = set()
        new_hands = []
        for hand in hands:
            if hand in unit['member'] and hand not in temp:
                temp.add(hand)
                continue
            new_hands.append(hand)
        result = find_best_unit_pattern_2(new_hands, hand_unit_list)
        unit_score = SCORE_DICT[len(unit['member'])]
        if result[1] + unit_score > best_pattern[1]:
            best_pattern = (result[0] + [unit], result[1] + unit_score)

    # キャッシュに登録する
    cache[hands_key] = best_pattern
    return best_pattern