数理最適化・(量子)アニーリングでFGO攻略 ~ 多数 v.s. 多数 編 ~

本記事の概要

以前紹介したFGO最適化 1 v.s. 1 編を発展させて、敵も自分のパーティも多数の場合に最適なパーティ編成をシミュレートしようというのが本記事の目標です。

定式化

バイナリ変数

以下のようにバイナリ変数を定めます。

x_{mk} = \{0, 1 \}

この変数は自分のパーティの$m$番目のメンバーがクラス$k$のときを1、そうでなければ0とする変数です。

コスト関数

前回の記事と同じく、こちらの攻撃ダメージが最大となるようにコストを選びます。

制約条件

マスターは限られた人数のサーヴァントしか召喚できない

マスターが召喚できるサーヴァントの数には限りがあります(FGO内ではパーティメンバーのコストとして表示されています)。パーティに入れられるサーヴァントの人数を$M$とすると、この制約条件は

\sum_{mk} x_{mk} = M

となります。これをQUBOの制約として表現すると

H_a 
= \left( \sum_{mk} x_{mk} -M\right)^2

サーヴァントは1つのクラスしか持ちえない

サーヴァントが複数のクラス(例えばセイバーとランサーのクラス)を同時に持つことはできません。よってこれを数式で表すと以下のようになります。

\sum_{k} x_{mk} = 1

これをQUBOで制約として入れようとすると

H_b 
= \sum_m \left( \sum_k x_{mk} -1\right)^2

となります。

Total QUBO

以上より、Total QUBOは以下のようになります。

{\rm Energy} 
= -{\rm damage} + \lambda_a H_a+ \lambda_b H_b

ここで$\lambda_a, \lambda_b$はハイパーパラメータです。

実際のスクリプト

make_energy.py

スクリプト

make_energy.py

import numpy as np
from pyqubo import Array, Constraint, Placeholder


def make_energy(my_member, enemy_member, kind, atk_matrix, enemy):
    # set placeholder (hyper parameters)
    lambda_a = Placeholder('h_a')
    lambda_b = Placeholder('h_b')
    # set binary variables
    x = Array.create('x', shape=(my_member, kind), vartype='BINARY')
    # convert to numpy array
    x = np.array(x)
    # set cost function
    atk_cost = sum([np.dot(x[m], 
                    sum([np.dot(atk_matrix, enemy[e]) for e in range(enemy_member)])) 
                    for m in range(my_member)])
    # set member constraint
    h_a = Constraint((sum([x[m][k] for m in range(my_member) for k in range(kind)])-my_member)**2, label='h_a')
    # set one-hot constraint
    h_b = Constraint(sum([(sum([x[m][k] for k in range(kind)])-1)**2 for m in range(my_member)]), label='h_b') 
    # compute total energy
    energy = -atk_cost + lambda_a * h_a + lambda_b * h_b
    # compile
    model = energy.compile()
    return model

スクリプト詳細

PyQUBOを用いてQUBOの自動生成を行なっています。バイナリ変数$x$を$M \times K$のArrayとして生成し、それらを用いてdamageと制約を計算しています。

結果

適当な計算例

試しに敵を1種類で統一してみましょう。

-----us-----
archer
archer
archer
-----enemy-----
saber
saber
saber

敵全員がセイバーのとき、こちらのパーティは全員アーチャーであれば有利であることがわかります。

ケーススタディ: 項羽・虞美人戦

第2部3章の「人智統合真国シン」の項羽(バーサーカー)と虞美人(アサシン)に最適な3人を求めてみましょう。すると以下のようになります。

-----us-----
caster
caster
caster
-----enemy-----
berserker
assassin

結果はみなさんのご想像の通り、全員キャスターになります。これは与えるダメージが最大になるように最適化を行なっているためです。しかし何度か実行すると、出力される結果が異なることもあります。

-----us-----
berserker
caster
caster
-----enemy-----
berserker
assassin

これはアニーリングによる解の求め方が、高速に解を出すが解の精度に保証がないアルゴリズム「ヒューリスティクス」と呼ばれるものだからです。