2023-07-08

ポケモン対戦の最適戦略解析ツールのご紹介

はじめに

本記事では、最近開発したポケモン対戦の最適戦略解析ツールを紹介いたします。本ツールが解析対象とするのはバトル中の戦略です。具体的には、バトル中の状況変化に応じて、どの技を選択＆どのポケモンに交代すればいいのかを解析します。

本ツールでは、ゲーム理論に基づいて、理論的に最適な戦略（正確には均衡戦略）を算出します。その分、計算量が多くなりますので、詳細な設定は反映できず、簡易的な設定のみを扱えます。扱える設定に制約はありますが、設定は変更できるように実装していますので、ご興味に合わせてカスタマイズいただけます。（例えば、最近目にした話題ですと、一撃技を使った方が良いか、不意打ちを使った方が良いか、などの解析にも使えそうです。）

本記事では、そのツールを用いて解析できるゲーム設定と解析例を紹介いたします。紹介を通して、このツールを使ってどのようなことができるのか＆どのような出力が得られるのかを知っていただき、興味を持っていただけると幸いです。

ツール

以下のレポジトリからご使用いただけます。使い方はまだ記載できておりません。私の体力的にいつ提供できるか分かりませんので、ご使用になりたい方はtwitterにて個別に連絡くださいますと幸いです。各々が解析したい設定へのモデリングについても、私の興味の持てる範囲であれば協力しますので、連絡くださいますと幸いです。

github.com

本記事で扱うゲーム設定

本記事で解析例として説明するゲーム設定を説明します。以下の設定はあくまで一例です。前述の通り、設定は変更できるように実装していますので、ご興味に合わせてカスタマイズいただけます。

一般的なシングルバトルを簡素化したもの
ポケモン
- 最大HPは固定（最大HP=1.00；計算量の都合で0.25区切り）
- タイプに応じた技を保持（草水タイプ→草タイプ技・水タイプ技）
選出
- 事前にポケモン3匹（うち先頭の1匹）を選出
- 相手がどの3匹を選択したかは互いに既知
バトル
- 各プレイヤは攻撃か交換を同時に選択
- 互いに攻撃の場合はランダムに先行後行が決定
- 攻撃のダメージ量は攻撃側の技タイプと防御側のポケモンタイプのみで決定
- 等倍の場合を0.5としてタイプの倍率を乗算
- どちらかのプレイヤのポケモンが全滅するまで繰り返し

解析例

一般的に良い選出であるといわれているサザンガルドマリルリを3匹に選出した解析例を紹介いたします*1。バトル開始時の対面はサザンドラｘギルガルドといたしました。

サザンドラ
- 技：ドラゴン、悪
ギルガルド
- 技：鋼、ゴースト
マリルリ
- 技：水、フェアリー

プレイヤ１：サザンドラ、ギルガルド、マリルリ（先頭：サザンドラ）
プレイヤ２：サザンドラ、ギルガルド、マリルリ（先頭：ギルガルド）

算出した最適戦略に基づくバトル例を通して、本ツールからどのような出力が得られるのかを説明いたします。

まずは、バトル例スライドの見方＆本ツールで得られる出力を説明いたします。

各盤面の情報は以下となります。

プレイヤ１（２）のポケモン：左（右側）のポケモン
戦闘に出ているポケモン：各プレイヤの先頭のポケモン
HP：ポケモンの下のバー

本ツールでは、各盤面の情報を入力とし、以下の情報を出力します。

各盤面の評価値（プレイヤ１がこの盤面から勝利する確率）：上のバー
各プレイヤの最適な行動選択割合：中央下の表
行動の組に対する評価値：中央下の表

中央下の表（利得表）の見方は以下です。

行（列）の行動：プレイヤ１（プレイヤ２）の行動
行動の右（下）に書かれている数値：最適戦略における行動の選択割合
行と列に対する利得表の値：選択の組に対する評価値
＊印の付いた選択：バトル例で選択された選択

１ターン目を例に、さらに本ツールの出力のイメージを膨らませます。１ターン目はサザンドラとギルガルドの対面です。サザンドラは悪技を持つのでギルガルドに対して有利です。具体的にはプレイヤ１の勝率が53%ということで、3%有利と分かります。プレイヤ１のサザンドラは悪技が第一候補に挙がりそうです。これに対して、プレイヤ２は悪技受けのマリルリへの交換も選択肢に入ってきます。これに対して、プレイヤ１はマリルリに有利なギルガルドへの交換も考えた方がよさそうです。このように、相手の各選択に対して有利となる自身の選択があるので、最適な行動は一つには定まらないことが多いです。ここで、本ツールを使えば、各選択の組に対して最適な選択割合が分かります。

おわりに

計算時間とメモリ量を改善したい。

*1:サザンガルドはとても有名ですのでこの2匹を例として選んだことに異論は少ないかと思います。最後の1匹としてマリルリを選んだのは「サザンガルド」をgoogle検索するとオススメとして「マリルリ」が出てきたからです。あくまで一例としてお考えいただけますと幸いです。

2022-12-19

多面体描画ツールglipoのご紹介

はじめに

本記事は数理最適化 Advent Calendar 2022の20日目の記事です。最近作った多面体の描画ツールglipoを紹介します。また、glipoの活用例として、線形相補性問題の多面体を眺めてみます。

glipo

数理最適化erのみなさんは、実行可能領域の多面体がどんな形なのか、どんな特徴を持つのかに興味をお持ちかと思います。特に、出来合いの多面体を描画するだけでなく、形を動かしながら、良い特徴を持つ多面体を探しているのではないでしょうか？（簡単に解を計算できる、解の個数に特徴がある、など。）

一方で、三次元図形をただ描画するツールはあっても、インタラクティブに図形を動かせるツールは限られています。（私の知る限りgeogebraしかありません。）また、そのようなツールを使っても、数理計画問題で扱う形式の多面体をインタラクティブに動かすには、一手間も二手間もかかります。

glipoは数理最適化問題で扱う形式の多面体に特化して作成しやすいように設計された多面体作成ツールです。ぜひみなさんが扱っている多面体をglipoで可視化してみてください！そして良い特徴を持つ多面体を探してみてください！使い方はこちらからご確認ください。

では、glipoの活用例として、線形相補性問題の多面体を眺めてみます。

線形相補性問題

数理最適化erであっても、馴染みのない方がいらっしゃいますと思いますので、まずは線形相補性問題の定義を紹介します。

線形相補性問題（Linear Complementarity Problem; LCP）とは、以下で定義される数理最適化問題です。（この定義は表現力の高い形式で書かれており、一般的な定義とは異なることをご了承ください。）

$\displaystyle \begin{align} \begin{matrix} \text{find} & x & \\ \text{subject to} & y_{ij} = a_{ij}^\top x + b_{ij} \geq 0 & (1) \\ & \prod_{j} y_{ij} = 0 & (2) \end{matrix} \end{align}$

ここで、 $i \in \{ 1, ..., n \}, j \in \{ 1, ..., m_i \}$ は添え字、 $a_{ij} \in \mathbb{R}^{n}, b_{ij} \in \mathbb{R}$ は所与、 $x \in \mathbb{R}^n, y_{ij} \in \mathbb{R}$ は変数です。

正確には、条件を満たす解を探す問題であり、「最適化」問題ではないです。ただ、最適化問題を含む広い問題クラスであることが知られています。LCPについては、以前に書いたこちらの記事も読んでいただけると嬉しいです。

(1)は実行可能性条件、(2)は相補性条件と呼ばれています。実行可能性条件を構成する制約式は線形ですので、これを満たす点の集合は多面体を構成しています。したがって、LCPとは、多面体の中で相補性条件を満たす点を探す問題となります。

ここで、相補性条件を幾何の言葉に置き換えておきます。相補性条件は、各 $i$ に対して、 $y_{i1}, ..., y_{i m_i}$ のいずれかが $0$ であることと同値です。これを幾何的に解釈すると、解が $y_{i1} = a_{i1}^\top x + b_{i1} = 0, ..., y_{i m_i} = a_{i m_i}^\top x + b_{i m_i} = 0$ のいずれかの超平面上に乗っていることを意味しています。

したがって、LCPの解とは、多面体上の点のうち、すべての $i$ のいずれかの超平面上にある点のことです。

LCPの多面体の可視化

言葉での説明だけでは分かりにくいと思いますので、早速glipoを使って、LCPの多面体を可視化し、どのような点がLCPの解になるのかを見てみましょう。 $i$ は面の色で表しています。適当に多面体を作って、各面に色を付けてみます。（色を付ける機能はまだgithubには説明がありません。点を選択した状態で1,2,3の数字を選択することで変更できます。）

すべての色の面が重なっている点（赤点）がLCPの解です。このように、可視化することで理解が深まるということはよくあることかと思います。

解の個数の変化

glipoでは多面体の面を自由に移動できるので、面が移動したときに、解がどのように変化するのかを調べることができます。このメリットを使って、LCPの解の個数の変化を見てみましょう。LCPの面白い性質の一つに、（特殊な条件を除き、）面の傾き（ $a_{ij}$ ）を固定したときに、面の位置（ $b_{ij}$ ）をどんなに変えても、解の個数の偶奇は変わらない、というものがあります。例えば、特定の $b_{ij}$ で解の個数が偶数（奇数）であるとすると、 $b_{ij}$ をどんなふうに変えても、解の個数は偶数（奇数）となるのです。

先ほどのケースの続きで、このことを確かめてみましょう。（解がきれいに配置されるように位置を若干調整しています。これが気軽にできるのもglipoの良さ！）先ほどのケースでは解は7個でしたので、どんなに面の位置を変えても解の個数は奇数になるはずです。では、いろいろと試してみましょう。（時間の都合で一つの面しか動かせませんでした。。）

面の位置を移動すると、解が移動したり、消えたり、増えたりしますが、個数が奇数で保たれていることが見えました。さらに、解の変化の様子を見ていくことで、解の偶奇が変わらないのは、解が増える（減る）ときに、2個ずつ増える（減る）からだ、ということも分かりました。（実際、この性質の証明ではこの性質を使っています。）このようなことを確認できるのは、インタラクティブな描画ツールならではかと思います。

おわりに

数理最適化では他にも多面体を図示することで理解が深まるテーマがたくさんあります。特に、線形計画問題に対するシンプレックス法に関するテーマで力を発揮するのではと思います。シンプレックス法の挙動を確認したり、シンプレックス法（の特定のピボット規則）で最悪計算時間のインスタンスとして知られるKlee-Minty cubeなどを図示したりするなどです。みなさまの勉強・研究で役立つことがありましたら、とても幸せです。

おまけ

もともとglipoはLCPの多面体を見るために開発したツールでして、解の個数以外にもたくさんの性質をglipoを使って調べることができます。glipoで遊ぶおもちゃとして、いくつかネタを記載しておきます！

任意の $b_{ij}$ で実行可能解が存在する $a_{ij}$ がある
任意の $b_{ij}$ で解が存在する $a_{ij}$ がある
任意の $b_{ij}$ で解が唯一となる $a_{ij}$ がある
任意の $b_{ij}$ で解が存在＆個数が偶数となる $a_{ij}$ がある

2022-02-12

ポケモンで最強のタイプはどれか？～ゲーム理論的アプローチ～

注意

筆者はポケモン対戦未プレイ勢であり、本解析にはポケモン対戦の実体が充分に反映されておりません。そもそも、この記事は、最強のタイプを求めることよりも、ポケモンという身近な題材を理論的に解析して楽しむことを目的としています。

はじめに

本記事では、ポケモンで最強のタイプを、ゲーム理論的な観点から求めてみます。ゲーム理論は、相手の行動を考慮した上で、自身の最適な行動を解析する理論です。これをポケモン対戦に適用すると、相手が繰り出すポケモンのタイプを考慮した上で、こちらが繰り出すべき最適なタイプを導けるようになります。

例えば、一般に強いとされるタイプ（例えば鋼タイプ）があり、こちらはそのタイプを繰り出したいとします。一方で、相手はそのタイプに相性の良いタイプ（例えば炎タイプ）を繰り出したいはずです。同様に、こちらもそのタイプに相性の良いタイプ（例えば水タイプ）を繰り出したくなります。同様の議論は延々と繰り返され、特定のタイプには落ち着かないのですが、ゲーム理論を使えば、最終的に落ち着くタイプ（正確には各タイプを繰り出す割合）を求めることができます。そして、本記事では、そのタイプを「最強のタイプ」と呼ぶことにします。

分析方法

本記事では以下の状況を扱います。

お互いにポケモン1匹を同時に繰り出す
ポケモンはタイプを1つのみ持つ
タイプ相性で有利なポケモンの勝ち
攻撃効果率－防御効果率がポイントとして勝者に与えられる（効果率と呼びます）

例えば、プレイヤ1が炎タイプ、プレイヤ2が草タイプを出した場合、炎→草が2倍で、草→炎が0.5倍であり、炎タイプ（プレイヤ1）の勝ちになります。そして、2-0.5=1.5ポイントがプレイヤ1に与えられます。

ポケモン対戦においては「このタイプを繰り出せば必ず勝てる」というタイプはありません。したがって、特定のタイプに固執せず、繰り出すタイプをある程度ランダムに決めることが最善の戦略となります。例えば、「炎タイプ10%、水タイプ15%、・・・」といった感じです。繰り出す割合を「使用率」と呼ぶことにします。本記事では、使用率が最も高いタイプを「最強のタイプ」と解釈します。

ゲーム理論を用いた最適な使用率の計算方法の説明は省略します。分かる人向けに簡潔に書きますと、ポイントを利得行列とした行列ゲームを線形計画法で解きました。

最強のタイプ

それでは、結果を発表します。参考に、一般にタイプの強弱を評価する指標となっている、有利なタイプ数、不利なタイプ数、それらの差分、効果率の合計も記載しました。また、本記事の最後に、付録として複合タイプありの解析結果も載せています。興味のある方はご参照下さい。

順位	タイプ名	有利数	不利数	差分	効果率	使用率[%]
1	水	5	3	2	1.5	16.40
2	ドラゴン	4	3	1	-1.5	10.40
3	草	4	7	-3	-3.5	9.82
4	電気	3	3	0	0	9.07
5	炎	5	4	1	2	8.98
6	地面	5	5	0	2	8.65
7	鋼	10	5	5	4	7.93
8	フェアリー	4	3	1	2	6.17
9	ゴースト	4	1	3	1.5	6.17
10	氷	4	5	-1	-1.5	5.82
11	飛行	4	4	0	1	4.70
12	毒	4	5	-1	-0.5	4.41
13	悪	2	3	-1	-0.5	1.47
14	格闘	5	5	0	0	0.00
15	岩	6	5	1	-0.5	0.00
16	ノーマル	0	3	-3	-2	0.00
17	虫	4	7	-3	-2	0.00
18	エスパー	2	4	-2	-2	0.00

最強のタイプは「水タイプ」であることが分かりました。ただし、その理由を読み取ることは難しいです。いろいろ考えてみましたが、いいアイデアが浮かびませんでした。

さらに、特筆すべき点は以下かと思います。

ドラゴンタイプが2位

効果率の合計で言えば決して優秀ではありませんが、おそらくメジャーなタイプ（草・炎・水・電気）に有利であることが理由で、上位にランクインしたのではないでしょうか。

草タイプが3位

一般的に草タイプは不遇タイプとして知られているので意外かと思います。 1位である水タイプに攻撃2倍かつ防御0.5倍をとれる唯一のタイプであることが理由かと思います。

格闘・岩・ノーマル・虫・エスパーは使用率0%

ポケモンはタイプ相性が複雑であり、どのタイプにも活躍の場があると考えていたので、使用率が0%である（使うと損してしまう）タイプがあることは意外でしたし、同時に残念でした。

おわりに

本記事では、ポケモンで最強のタイプを、ゲーム理論的な観点から求めてみました。その結果、最強のタイプは水タイプであることが分かりました。また、意外な結果として、一般には不遇なタイプであるとされる草タイプが3位になりました。ゲーム理論的な弱点の付き合いの結果が反映されていることが分かり、面白い解析となりました。

そして、残念なことに、5つのタイプについて、使用率が0%になってしまうことも分かりました。これはゲームとしては致命的で、自分の好きなポケモンがそれらのタイプに含まれると、自分の好きなポケモンではトップを取れないということであり、プレイすることへのモチベーションを下げしまいます。この状況は何としてでも解決しなければいけません。次回の記事では、どのタイプにも活躍の場を与えるためのタイプ相性バランスの調整について検討してみようと思います。

謝辞

ポケモン対戦のことを教えてくれた友人に感謝いたします。教えていただいたポケモン対戦の実体を充分に反映できなかったので、別の機会に検討してみたいです。

付録：最強のタイプ（複合タイプ編）

参考に複合タイプありについても分析を行いました。概要だけ以下に記載します。全データはこちらをご覧ください。 26位以降の使用率は0%でした。

特筆すべきこととして、単タイプの分析で使用率0％であったタイプも、タイプを組み合わせることで、活躍の場ができることが分かりました。

順位	タイプ1	タイプ2	使用率[%]	順位	タイプ1	タイプ2	使用率[%]
1	電気	フェアリー	9.14	14	格闘	エスパー	3.47
2	ドラゴン	鋼	8.10	15	炎	氷	3.31
3	電気	飛行	7.78	16	格闘	ゴースト	3.15
4	水	草	6.82	17	炎	ドラゴン	3.13
5	ゴースト	悪	5.55	18	飛行	鋼	2.70
6	氷	地面	5.49	19	電気	地面	2.43
7	氷	虫	5.46	20	草	岩	2.38
8	水	ドラゴン	5.34	21	地面	飛行	2.16
9	草	鋼	4.72	22	地面	鋼	1.98
10	毒	地面	4.24	23	ノーマル	ゴースト	1.15
11	毒	悪	4.23	24	格闘	毒	0.05
12	電気	氷	3.65	25	格闘	飛行	0.04
13	水	地面	3.56