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

# 概要

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

# バックトラッキングとは

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

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

例えばこんな手牌があったとして、例えば「春香・千早で『[CRIMSON LOVERS](https://columbia.jp/idolmaster/COCC-17325.html)』が組める」と考えたとします。
すると、その2枚のユニットを確定させ、残りの手牌でどういった組み合わせがあるかを考えます。

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

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29802/c2f8c190-f7d0-0227-97d8-57225f2746cc.png)

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

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

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

```py
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との剰余を求めればいいだけなので簡単ですね。

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

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

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

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

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

```py
        # 選択したユニット(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段深くしつつ、最適解の更新も実施します。コメントに書いてある通りですね。

```py
        # 新たな手牌を元に、最適なユニットの組み合わせを算出する(再帰関数)
        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倍近く高速化**したことになります。

# より高速にするには？

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

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


```py
# キャッシュ
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
```