数理最適化・(量子)アニーリングでFGO攻略 ~1ターンに1人ずつサーヴァントが惨殺される 編~

# 本記事の概要

以前の記事

[FGO最適化 1 v.s. 1 編](https://qiita.com/github-nakasho/items/0d3cc464a6d9342f13f3)
[FGO最適化 多数 v.s. 多数 編](https://qiita.com/github-nakasho/items/07aabc5a050736196a1b)
[FGO最適化 数ターン経過 編](https://qiita.com/github-nakasho/items/3dffbac82e78279ff78f)

を発展させて、今回は自分のサーヴァントがやられていく場合をシミュレートしたいと思います。具体的には以下のような状況です。

>敵が毎ターン強力な単体宝具を使って、必ずパーティメンバー1人を惨殺してくるよ〜ぴえん(><)

敵としてかなり厄介な相手です。この状況下で敵に最大ダメージを喰らわすにはどうすればよいかをシミュレートしてみましょう。

# 定式化

## バイナリ変数

### サーヴァントの状態を表す変数

以下のようなバイナリ変数を用います。

```math
x_{tmc} = \{0, 1\} \\
y_{tmc} = \{0, 1\}
```

$x$は自分のパーティを表し、$y$は敵パーティを表す変数です。$t$はターン、$m$はメンバー、$c$はサーヴァントのクラスを表す変数です。例えば自分のパーティに、1ターン目に2番目のメンバーがキャスターのサーヴァントのとき$x_{1, 2, 術}=1$という風になります。

## コスト関数

### サーヴァントのクラス相性行列

||死|剣|弓|槍|騎|術|殺|狂|秤|讐|月|分|降|盾|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|死|0.0|0.0|0.0|0.0|0.0|0.0|0.0|0.0|0.0|0.0|0.0|0.0|0.0|0.0|
|剣|0.0|1.0|0.5|2.0|1.0|1.0|1.0|2.0|0.5|1.0|1.0|1.0|1.0|1.0|
|弓|0.0|2.0|1.0|0.5|1.0|1.0|1.0|2.0|0.5|1.0|1.0|1.0|1.0|1.0|
|槍|0.0|0.5|2.0|1.0|1.0|1.0|1.0|2.0|0.5|1.0|1.0|1.0|1.0|1.0|
|騎|0.0|1.0|1.0|1.0|1.0|2.0|0.5|2.0|0.5|1.0|1.0|1.0|1.0|1.0|
|術|0.0|1.0|1.0|1.0|0.5|1.0|2.0|2.0|0.5|1.0|1.0|1.0|1.0|1.0|
|殺|0.0|1.0|1.0|1.0|2.0|0.5|1.0|2.0|0.5|1.0|1.0|1.0|1.0|1.0|
|狂|0.0|1.5|1.5|1.5|1.5|1.5|1.5|1.5|1.5|1.5|1.5|1.5|0.5|1.0|
|秤|0.0|1.0|1.0|1.0|1.0|1.0|1.0|2.0|1.0|0.5|2.0|1.0|1.0|1.0|
|讐|0.0|1.0|1.0|1.0|1.0|1.0|1.0|2.0|2.0|1.0|0.5|1.0|1.0|1.0|
|月|0.0|1.0|1.0|1.0|1.0|1.0|1.0|2.0|0.5|2.0|1.0|1.0|1.0|1.0|
|分|0.0|0.5|0.5|0.5|1.5|1.5|1.5|2.0|1.0|1.0|1.0|1.0|2.0|1.0|
|降|0.0|1.0|1.0|1.0|1.0|1.0|1.0|2.0|1.0|1.0|1.0|0.5|2.0|1.0|
|盾|0.0|1.0|1.0|1.0|1.0|1.0|1.0|1.0|1.0|1.0|1.0|1.0|1.0|1.0|

行が攻撃側、列が防御側です。戦闘不能は誰にもダメージを与えることもなければ誰からもダメージを受けない空気のような存在として扱います。この表を行列$(A_{ij})$と書きましょう。

### 与えるダメージとコスト関数

味方のサーヴァントが敵のパーティに、$t$ターン目に与えるダメージは以下のように計算されます。

```math
{\rm damage}_t 
= \sum_i \left( \sum_m x_{tmi} \right) \left( \sum_{j} A_{ij} \sum_{m} y_{tmj} \right)
```

よってこれを全てのターンで足し合わせた

```math
{\rm damage} 
= \sum_t {\rm damage}_t
```

が最大となるように最適化を行います。

## 制約条件

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

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

```math
\sum_c x_{tmc} = 1
```

これをQUBOとして書き表すと

```math
H_a = \sum_{tm} \left( \sum_c x_{tmc} -1\right)^2
```

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

パーティに入れられるサーヴァントの人数を$M$とすると、この制約条件は

```math
\sum_{mc} x_{tmc} = M
```

となります。これをQUBOで書き表すと

```math
H_b 
= \sum_t \left( \sum_{mc} x_{tmc} -M \right)^2
```

### 毎ターン1人ずつ戦闘不能になる

添字の0が戦闘不能状態を表す状態だったので、これが1人ずつ増えていくことを数式にします。

```math
\sum_m x_{tm0} = \sum_m x_{t-1, m0} + 1
```

これを変形して、制約は

```math
H_c =
\sum_t \left\{ \sum_m (x_{tm0}-x_{t-1, m0})-1\right\}^2
```

となります。

### サーヴァントの状態を維持する

1ターン目にフォーリナークラスで召喚したサーヴァントが2ターン目に突然バーサーカーになっていては困ります。また一度戦闘不能になったサーヴァントが、次のターンに復活することは(令呪を除いて)ありません。これを数式で表すことを考えましょう。
あるターン$t$に$m$番目のサーヴァントがクラス$c$で召喚されているときの状態は$x_{tmc}$で表されるのでした。このとき、次のようなものを考えます。

```math
x_{t-1, mc} (x_{t-1, mc} - x_{tmc})
```

これは$x_{t-1, mc}=1, x_{tmc}=0$のときのみ、1となるようなものです。これはスイッチがoffとなるときに1の値をとり、それ以外では0となるような変数であることがわかります。このスイッチoffの回数が

```math
\sum_t \left\{ x_{t-1, mc} (x_{t-1, mc} - x_{tmc}) \right\} = x_{0mc}
```

右辺は$t=0$ターンで出現しているサーヴァントに関しては1回だけスイッチoffを認める(戦闘不能への状態変化を許す)、という意味を込めています。そのほかに関してはサーヴァントのクラスが変化したりするような状態変化を認めないことを意味しています。
これをQUBO制約にすると

```math
H_d 
= \sum_{mc} \left[ \sum_t \left\{ x_{t-1, mc} (x_{t-1, mc} - x_{tmc}) \right\} - x_{0mc}\right]
```

## Total QUBO

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

```math
{\rm Energy} 
= -{\rm damage} + \lambda_a H_a + \lambda_b H_b + \lambda_c H_c + \lambda_d H_d
```

ここで$\lambda_a, \lambda_b, \lambda_c, \lambda_d$はそれぞれハイパーパラメータです。

# 実際のスクリプト

## make_energy.py

### スクリプト

```python:make_energy.py
import numpy as np
from pyqubo import Array, Constraint, Placeholder


def make_energy(max_turn, my_member, enemy_member, kind, atk_matrix, enemy):
    # set placeholder (hyper parameters)
    lambda_a = Placeholder('h_a')
    lambda_b = Placeholder('h_b')
    lambda_c = Placeholder('h_c')
    lambda_d = Placeholder('h_d')
    # set binary variables
    x = Array.create('x', shape=(max_turn, my_member, kind), vartype='BINARY')
    # convert to numpy array
    x = np.array(x)
    # set cost function
    damage = sum([np.dot(x[t][m], sum([np.dot(atk_matrix, enemy[e]) for e in range(enemy_member)])) for m in range(my_member) for t in range(max_turn)])
    cost = damage
    # set my menber one-hot constraint
    h_a = Constraint(sum([(sum([x[t][m][k] for k in range(kind)])-1)**2 for t in range(max_turn) for m in range(my_member)]), label='h_a') 
    # set my member constraint
    h_b = Constraint(sum([(sum([x[t][m][k] for m in range(my_member) for k in range(kind)])-my_member)**2 for t in range(max_turn)]), label='h_b')
    # set 1 kill per 1 turn constraint
    h_c = Constraint(sum([(sum([x[t][m][0]-x[t-1][m][0] for m in range(my_member)])-1)**2 for t in range(1, max_turn)]), label='h_c')
    # set maintaining state constraint
    h_d = Constraint(sum([sum([x[t-1][m][k]*(x[t-1][m][k]-x[t][m][k])-x[0][m][k]+1 for t in range(1, max_turn)]) for m in range(my_member) for k in range(kind)]), label='h_d')
    # compute total energy
    energy = -cost + lambda_a * h_a + lambda_b * h_b + lambda_c * h_c + lambda_d * h_d
    # compile
    model = energy.compile()
    return model
```

### スクリプト詳細

[PyQUBO](https://pyqubo.readthedocs.io/en/latest/index.html)を用いてQUBOの自動生成を行なっています。バイナリ変数$x$を$T \times M \times K$のArrayとして生成し、それらを用いてdamageと制約を計算しています。

# 結果

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

第2部3章の「人智統合真国シン」の項羽(バーサーカー)と虞美人(アサシン)に最適な3人を求め、そのパーティが1人ずつ惨殺されていく場合に、最大ダメージを叩き出すことができるパーティ編成を見てみましょう。結果は以下のようになります。

```
/*****turn0*****/
-----us-----
alterego
berserker
berserker
-----enemy-----
berserker
assassin

/*****turn1*****/
-----us-----
alterego
berserker
x
-----enemy-----
berserker
assassin

/*****turn2*****/
-----us-----
x
berserker
x
-----enemy-----
berserker
assassin

/*****turn3*****/
-----us-----
x
x
x
-----enemy-----
berserker
assassin
```

**アルターエゴ・バーサーカー・バーサーカー**で3ターンの間に多くのダメージを与えることを目標とすることが良さそうです(キャスターx3のパーティではない？直感に反する？)。

# 結言

項羽・虞美人のケーススタディでは、キャスターx3のパーティよりもダメージが出せるパーティを見つけることができました。次回もご期待ください。