Help us understand the problem. What is going on with this article?

数理最適化・(量子)アニーリングで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

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

github-nakasho
東北大天文博士(理論物理, スパコンでMHDシミュレーション)からエンジニアなどを経験し、なんやかんやあってJij inc. で量子アニーリングと組合せ最適化の研究開発。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした