ポケモン最適化 Vol. 1: 1 vs 1

この記事の概要

任天堂の大人気ゲーム「ポケットモンスター」を最適化問題として定式化し、それをOpenJijで解いてみようという趣旨の記事です。

この記事の概要
序章(先行研究)
逃げるんじゃねぇ！サシで勝負だ！
定式化
Pythonスクリプト
最適化結果
- 例1: 相手ポケモンとその技が単一タイプ
- 例2: 相手ポケモンのタイプと技タイプが一致しない場合
考察: これは現実的な1vs1のポケモンバトルとなっているか？
今後の課題
参考文献
文責

序章(先行研究)

世界初の商用量子アニーラーを開発したD-Wave。その会社がウェビナーで以下のような講演を行いました。

QUBO, I Choose You! Building an Optimal Pokemon Team with a Quantum Computer

6匹のポケモンを相手ポケモンのタイプ・技タイプに合わせて選出します。どのように選べば相手トレーナーに勝つことができるか、を最適化計算したという内容です。
上の動画では6匹のメンバーの中に「相手ポケモンの攻撃に対する弱点タイプは2匹まで」「相手ポケモンの攻撃に強いタイプは1匹まで」という制約を課しており、現実的なポケモンバトルとは言えません。
そこでこの記事を第一弾として、リアルなポケモンバトルを最適化するための数理モデル・QUBO定式化を考えていきましょう。最後にスクリプトを作成しその数値実験結果を考察する、ということを目標に掲げていきたいと思います。

逃げるんじゃねぇ！サシで勝負だ！

第一弾は簡単のため、自分と相手の手持ちポケモンはそれぞれ1匹ずつと仮定します。またそれらのポケモンは技を4つ持つとします。

定式化

バイナリ変数

自分のポケモンが $i$ タイプのとき $x_i = 1$ 、そうでないとき $x_i = 0$ となるようなバイナリ変数 $x_i$ を考えます。
自分のポケモンが持つ $j$ 番目の技が $k$ タイプのとき $y_{jk} = 1$ 、そうでないとき $y_{jk}=0$ となるようなバイナリ変数 $y_{jk}$ を考えます。
さらに固定変数として、相手のポケモンが $i$ タイプのとき $z_i = 1$ 、そうでないとき $z_i = 0$ となるようなバイナリ変数 $z_i$ を用意します。
そしてこちらも固定変数として、相手ポケモンが持つ $j$ 番目の技が $k$ タイプのとき $w_{jk} = 1$ 、そうでないとき $w_{jk} = 0$ となるようなバイナリ変数 $w_{jk}$ を用意します。

これらのバイナリ変数を用いて、制約と目的関数をQUBO表現することを考えましょう。

制約1: 自分のポケモンのタイプは1つか2つ

ポケモンはそれぞれがタイプを持ちます。しかしそのタイプは1つか多くても2つまで、というのが現行のポケモンのルールです。

$\displaystyle{ \sum_i x_i = 1 \ {\rm or} \ \sum_i x_i = 2 }$

これをQUBOで表現すると以下のようになります。

$\displaystyle{ H_a = \left( \sum_i x_i -1 \right) \left( \sum_i x_i -2\right) \tag{1} }$

制約2: 技のタイプは1つのみ

ポケモンが持つ技にもタイプがありますが、こちらは現行のポケモンでは1つしか許されていません。

$\displaystyle{ \sum_k y_{jk} = 1 }$

これをQUBOで表現すると以下のようになります。

$\displaystyle{ H_b = \sum_j \left( \sum_k y_{jk} -1 \right)^2 \tag{2} }$

目的関数: 与えるダメージ-くらうダメージを最大にする

簡単のため、今回は

$\displaystyle{ (自分のポケモンが相手ポケモンに与えるダメージ) - (相手ポケモンから自分のポケモンが受けるダメージ) }$

これを最大にすることを考えましょう。ポケモンのタイプに対する相性表は以下のようになります(行が攻撃技のタイプ、列が防御側ポケモンのタイプです)。

	ノーマル	ほのお	みず	でんき	くさ	こおり	かくとう	どく	じめん	ひこう	エスパー	むし	いわ	ゴースト	ドラゴン	あく	はがね	フェアリー
ノーマル	1.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0	0.5	0.0	1.0	1.0	0.5	1.0
ほのお	1.0	0.5	0.5	1.0	2.0	2.0	1.0	1.0	1.0	1.0	1.0	2.0	0.5	1.0	0.5	1.0	2.0	1.0
みず	1.0	2.0	0.5	1.0	0.5	1.0	1.0	1.0	2.0	1.0	1.0	1.0	2.0	1.0	0.5	1.0	1.0	1.0
でんき	1.0	1.0	2.0	0.5	0.5	1.0	1.0	1.0	0.0	2.0	1.0	1.0	1.0	1.0	0.5	1.0	1.0	1.0
くさ	1.0	0.5	2.0	1.0	0.5	1.0	1.0	0.5	2.0	0.5	1.0	0.5	2.0	1.0	0.5	1.0	0.5	1.0
こおり	1.0	0.5	0.5	1.0	2.0	0.5	1.0	1.0	2.0	2.0	1.0	1.0	1.0	1.0	2.0	1.0	0.5	1.0
かくとう	2.0	1.0	1.0	1.0	1.0	2.0	1.0	0.5	1.0	0.5	0.5	0.5	2.0	0.0	1.0	2.0	2.0	0.5
どく	1.0	1.0	1.0	1.0	2.0	1.0	1.0	0.5	0.5	1.0	1.0	1.0	0.5	0.5	1.0	1.0	0.0	2.0
じめん	1.0	2.0	1.0	2.0	0.5	1.0	1.0	2.0	1.0	0.0	1.0	0.5	2.0	1.0	1.0	1.0	2.0	1.0
ひこう	1.0	1.0	1.0	0.5	2.0	1.0	2.0	1.0	1.0	1.0	1.0	2.0	0.5	1.0	1.0	1.0	0.5	1.0
エスパー	1.0	1.0	1.0	1.0	1.0	1.0	2.0	2.0	1.0	1.0	0.5	1.0	1.0	1.0	1.0	0.0	0.5	1.0
むし	1.0	0.5	1.0	1.0	2.0	1.0	0.5	0.5	1.0	0.5	2.0	1.0	1.0	0.5	1.0	2.0	0.5	0.5
いわ	1.0	2.0	1.0	1.0	1.0	2.0	0.5	1.0	0.5	2.0	1.0	2.0	1.0	1.0	1.0	1.0	0.5	1.0
ゴースト	0.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0	1.0	2.0	1.0	1.0	2.0	1.0	0.5	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	1.0	1.0	1.0	2.0	1.0	0.5	0.0
あく	1.0	1.0	1.0	1.0	1.0	1.0	0.5	1.0	1.0	1.0	2.0	1.0	1.0	2.0	1.0	0.5	1.0	0.5
はがね	1.0	0.5	0.5	0.5	1.0	2.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.5	1.0	1.0	1.0	1.0	2.0	0.5	1.0	1.0	1.0	1.0	1.0	1.0	2.0	2.0	0.5	1.0

この行列を $A_{ij}$ のように書くことにしましょう。すると

$\displaystyle{ (与えるダメージ) = \sum_k \sum_i \left\{ y_{ki} \left( \sum_{j}A_{ij} z_j \right) \right\} }$

$\displaystyle{ (受けるダメージ) = \sum_k \sum_i \left\{ w_{ki} \left( \sum_{j}A_{ij} x_j \right) \right\} }$

と書くことができます。最大化したいものから、目的関数は

$\displaystyle{ {\rm obj} = - \sum_k \sum_i \left\{ y_{ki} \left( \sum_{j}A_{ij} z_j \right) \right\} + \sum_k \sum_i \left\{ w_{ki} \left( \sum_{j}A_{ij} x_j \right) \right\} \tag{3} }$

のようになります。

全ハミルトニアン

以上の(1), (2), (3)より、求めたい問題のハミルトニアンは、未定乗数 $\lambda_a, \lambda_b$ を用いて

$\displaystyle{ H = {\rm obj} + \lambda_a H_a + \lambda_b H_b \tag{4} }$

となります。

Pythonスクリプト

GitHubにリポジトリを作成しました。ぜひクローンして実行してみてください。
Pokemon_optgithub.com

最適化結果

例1: 相手ポケモンとその技が単一タイプ

例として、相手のポケモンが「ほのお」タイプで4つの技も全て「ほのお」タイプという簡単な場合を最適化してみましょう。結果は以下のようになります。

{}
**********
じぶんのポケモン: みず
わざ0: じめん
わざ1: じめん
わざ2: じめん
わざ3: みず
**********
あいてのポケモン: ほのお
わざ0: ほのお
わざ1: ほのお
わざ2: ほのお
わざ3: ほのお

最初の空の辞書は、制約が満たされていることを示しています(制約が破れている場合には何らかの要素を持つ辞書が表示されます)。
相手ポケモンが「ほのお」タイプなので、それに2倍のダメージを与えることができる「じめん」「みず」が選択されていることがわかります。また相手ポケモンの技が全て「ほのお」タイプなので、その技のダメージが0.5倍となる「みず」タイプポケモンが自分のポケモンとして選ばれています。

例2: 相手ポケモンのタイプと技タイプが一致しない場合

もう少し複雑なインスタンスを用意します。今度は「ほのお」タイプのポケモンが、なぜか「みず」「くさ」の技を使えるとした場合、どうなるでしょうか。

{}
**********
じぶんのポケモン: ドラゴン
わざ0: じめん
わざ1: いわ
わざ2: じめん
わざ3: みず
**********
あいてのポケモン: ほのお
わざ0: ほのお
わざ1: くさ
わざ2: くさ
わざ3: みず

相手ポケモンが「ほのお」タイプであることは変わりないので、それに2倍ダメージを与える「じめん」「いわ」「みず」の技が選択されています。そして自分のポケモンのタイプは、相手ポケモンの「ほのお」「みず」「くさ」のダメージが0.5倍となる「ドラゴン」タイプになっています。
相手が上の結果を踏まえて、「ドラゴン」タイプに対する対策をしてくるとどうでしょうか。試しに、相手ポケモンのわざ2を「フェアリー」に変えて実験してみましょう。

{}
**********
じぶんのポケモン: どく
わざ0: みず
わざ1: じめん
わざ2: いわ
わざ3: みず
**********
あいてのポケモン: ほのお
わざ0: ほのお
わざ1: くさ
わざ2: フェアリー
わざ3: みず

今度は、「くさ」「フェアリー」のダメージが0.5倍となる「どく」タイプが自分のポケモンタイプになりました。

考察: これは現実的な1vs1のポケモンバトルとなっているか？

今回の定式化では、ポケモンが使える技タイプに対して制約を施していません。すなわち、この解法では「ほのお」タイプのヒトカゲが「みず」タイプのみずでっぽうを使えるような解も出現します。実際にはポケモンタイプと技タイプに相関が存在します。このように変数に相関がない簡単な最適化問題は貪欲法で解けてしまいます。しかし、現実のポケモンバトルは、貪欲法では最適解を導けないような複雑な問題設定(今後の課題を参照)が多数存在します。よって現実のポケモンバトルの最適解を導くためには

より詳細な問題の定式化
それを解くためにOpenJijで採用されているのようなアニーリングアルゴリズム

が必要になるでしょう。

今後の課題

ポケモンバトルは1ターンの間に自分と相手のポケモンが1回ずつ技を使います。このようなターン経過を最適化問題に組み込むことで、どちらのポケモンが勝つかを明確にすることができます。
ダメージ計算にも様々あります。あるポケモンのタイプと技のタイプが同じ属性のときにはダメージが1.5倍になります。またポケモンの攻撃が急所にあたった場合にもダメージが1.5倍です。さらに技によってはバトルフィールドの天候を変え、ポケモンの技の威力を上下させるものがあります。このような効果を入れて計算を行うことで、より現実みのあるダメージ量の最適化が行えるでしょう。
よくある対戦ルールとして、ポケモンバトルは3対3で行われます。相手ポケモンの3匹が持つ技タイプを考慮しての最適化が必要となるでしょう。さらに複数のポケモンを所持している場合には、闘うポケモンの入れ替えを行うことができます。
このようにポケモンには細かなルールがあるため、これらを追加してより現実のポケモンバトルに近いものを最適化できればと考えています。

参考文献

文責

中村翔、株式会社 Jij
Sho K. NAKAMURA, Jij Inc.
憂いの篩 -Pensieve-

※ 疑問点や間違いなどございましたら、お気軽にブログ上でご質問ください。

Jij Tech Blog

Jij inc.の開発日記です