【ポケモンGO】ジムバトルにおける最適パーティを最短経路問題で考えます【バトルチーム】

(2023年5月28日追記) 最適ジム防衛パーティを最短経路問題で考察しました！
(2023年6月17日追記) 単騎ジムアタッカーおすすめランキング！【ポケモンGO】

ごごちと申します。

これまではポケモンGOのジム防衛に関する記事を
いくつか書いてきました。
【頑丈&長持ち】誰も知らないジム防衛おすすめポケモン３選！【ポケモンGO】【ジム防衛】
【ジム防衛】防衛ポケモンの集計とおすすめ評価ランキング！【ポケモンGO】

今回は、ジムバトルを攻撃側の視点から考えます。
ジムバトルを短時間で攻略できるパーティを最短経路問題で考えたいと思います。

(2024年5月5日追記)　格闘タイプ最強を考察しました！

かくとうタイプでジムバトルするときの
最適ポケモンの考察動画を作成しました！

シャドウカイリキー、ルカリオ、
ローブシン、テラキオン

の4匹を比較しています！

ジムバトルについて
結論から紹介！最適バトルパーティ！
今回の計算における仮定
討伐時間テーブルの作成
最短経路問題へ
18匹の攻撃側候補×6匹の防衛ポケモンに対する計算
- 経路図のイメージ
- 計算結果
もっといろんな計算をやってみます！

ジムバトルについて

ポケモンGOのジムバトルでは
相手チームが重複なしの6匹に対して、
こちらのジムバトルチーム6匹を繰り出し、
1対1の勝ち抜き形式でバトルを行います。

ジムバトルに勝利しジムを占領することで、
ポケコインという課金アイテムが手に入ります。

今は1ポケコイン=1.6円であり、
一日50ポケコイン=80円までは手に入るので、
地味ですが小遣い稼ぎになります。

ポケモンGOにおいて、
ジムバトルおよびジム防衛は
ユーザーの財布を助けるという意味で
重要な要素といえます。

今回は、そんなジムバトルで
最短時間で勝利するための
最適パーティを計算によって導き出しました！

結論から紹介！最適バトルパーティ！

ルカリオ
フェローチェ
デンジュモク
マンムー
レシラム
(自由枠)

以上が計算から導き出された
最適ジムバトルチームです。

見慣れないポケモンもいるかと思いますが、
計算仮定の元での結果ですのでご了承ください。

注目して頂きたいのはポケモンのタイプの特徴です。
最適バトルチームにはタイプの特徴がみてとれます。
わかりやすくするために、
・必須タイプ1
・必須タイプ2
・その他
に分けて考えます。

必須タイプ1

ジム置き可能なポケモンの中で
最高の耐久力を誇るハピナス&ラッキーを
最短で倒せるかくとうタイプは必須です。

今回はルカリオがピックアップされています。

ハピナス、ラッキーの討伐時間は
他のポケモンよりも長いので、
これらを短時間で倒せるかくとうタイプが重要です。

必須タイプ2

かくとうタイプに耐性のあるタイプ
(＝エスパー, ひこう,フェアリー)
に対して弱点を突ける、
以下の7タイプが必須タイプ2です。
・あく
・むし
・ゴースト
・でんき
・こおり
・いわ
・はがね

今回は、
・ソーナンス(エスパー)に対してフェローチェ(むし)
・トゲキッス(ひこう)に対してデンジュモク(でんき)
・カイリュー(ドラゴンひこう)に対してマンムー(こおり)
がピックアップされています。

ソーナンスに対してフェローチェは
筆者にとっても意外でしたが、
ゲンガーやダークライでも1秒差ぐらいなので
これらで代用しても良いと思います。

その他(自由枠)

必須タイプ1および2で
弱点が突けないタイプのポケモンに対して
有効なタイプのポケモンを選びます。
この最後の枠はある程度自由度があります。

想定防衛パーティのメタグロス(はがね)に対して、
レシラム(ほのお)がピックアップされています。

基本的に必須タイプ1と必須タイプ2で、
どの防衛ポケモンに対しても等倍以上がとれるので、
他のタイプはある程度自由に決めて良いと思います。
筆者はかくとうタイプを追加で入れています。

対戦数稼ぎのために好きなポケモンを
加えても良いでしょう。

今回の計算における仮定

計算を単純に行うために、３つの仮定を立てました。

仮定1 : 相手パーティ6匹と順番は固定

今回はモデルジムとして、
図のような防衛パーティを考えました。
個人的には相手にしたくない並びを想定しました。

仮定2 : こちらのポケモンは全18タイプから1種ずつ選択

候補ポケモンは全18タイプから代表的なポケモンを
1匹ずつピックアップしました。
伝説ポケモンやウルトラビーストは含みますが、
メガシンカ、シャドウポケモンは除外しました。

技について、
ノーマルアタックとスペシャルアタックを
一つずつだけ考えます。
技解放による２つめのスペシャルアタックは
考えないようにします。

仮定3 : 攻撃側はポケモンの交代が可能

攻撃側はポケモンを交代させることが出来ます。
ジムバトルは勝ち抜き形式で進むため、
攻撃ポケモンが相性の悪い防衛ポケモンと
対峙する盤面が発生します。
この場合、別の攻撃ポケモンに交代することで
より短時間で防衛ポケモンを撃破できます。

交代はバトル中何度でも出来ます。
ただし、交代にかかる時間として

交代ボタンを押す
> 交代ポケモンを選択する
> 戦闘中のポケモンが引っ込む
> 交代後のポケモンが飛び出す

という操作が発生します。
今回は交代に発生する時間を 3秒としました。

討伐時間テーブルの作成

ポケマピ様の計算ツールを使い
仮定1で設定した防衛ポケモンに対して、
仮定2のポケモンと技の組み合わせを入力し、
討伐時間を計算します。

防衛ポケモンと攻撃ポケモンとの組み合わせからなる
討伐時間テーブルができあがります。
(スマホだと表が見えにくいので注意。)

No.	タイプ	ポケモン	ノーマル技	スペシャル技	ハピナス	ソーナンス	ラッキー	トゲキッス	メタグロス	カイリュー
1	くさ	カミツルギ	はっぱカッター	リーフブレード	43.4	22.2	33.6	36	36	54.8
2	ほのお	レシラム	ほのおのきば	クロスフレイム	41.7	26.9	35	24.7	14.8	35
3	みず	カイオーガ	たきのぼり	こんげんのはどう	50.7	26.9	35.8	28.1	26.9	37
4	でんき	デンジュモク	でんきショック	ほうでん	45.3	25.1	34.9	15.3	25.1	25.1
5	こおり	マンムー	こなゆき	ゆきなだれ	54.3	30.5	42.9	18.1	48.6	12.4
6	かくとう	ルカリオ	カウンター	はどうだん	29.7	37.8	22.5	56.7	25.2	37.8
7	どく	ウツロイド	どくづき	ヘドロばくだん	53.8	27.7	40.3	18.2	65.6	26.9
8	じめん	グラードン	マッドショット	だんがいのつるぎ	51.7	26.2	41.6	58.3	20.8	60.1
9	ひこう	ファイヤー	つばさでうつ	ゴッドバード	52	26.4	39.2	26.4	41.6	26.4
10	エスパー	ミュウツー	サイコカッター	サイコブレイク	42.5	36.6	33.1	24.2	54.9	24.2
11	むし	フェローチェ	むしくい	むしのさざめき	47.2	15.9	35.3	55.4	23.6	39.5
12	いわ	ラムパルド	うちおとす	いわなだれ	49.2	25.8	40.8	18.3	40.8	17.1
13	ゴースト	ゲンガー	したでなめる	シャドーボール	118.5	16.5	86	29	16.5	29
14	ドラゴン	パルキア	ドラゴンテール	りゅうせいぐん	48.2	26.7	34.7	60.3	40.2	16.8
15	あく	ダークライ	バークアウト	あくのはどう	49.6	17	39.2	42.2	18.1	28.5
16	はがね	メタグロス	バレットパンチ	コメットパンチ	49.7	28.4	35.5	16	42.6	28.4
17	フェアリー	サーナイト	あまえる	マジカルシャイン	58	31.5	42.5	31.5	52	22
18	ノーマル	ポリゴンZ	ロックオン	はかいこうせん	52.8	26.4	35.9	26.4	40.4	26.4

これを基にジムを攻撃するための
最適パーティを考えます。

討伐時間テーブルを眺め、
防衛ポケモンを最短で倒せるポケモンを選んでいけば
自然と最適パーティは出来そうな気がします。

しかし仮定３の、ポケモン交代において、
「攻撃側のポケモン交代には 3秒かかる」
ことを考慮する必要があります。

仮に攻撃ポケモンが今対峙している防衛ポケモン1の
討伐時間が少し長くても、
次に戦うことになる防衛ポケモン2の
討伐時間が短いなら、
交代せずに戦い続けた方が、
交代に発生する時間をペイできて
トータルでは短時間になる状況も考えられます。

交代する、しないを含めて最適な攻撃パーティと
最短討伐時間を考える必要があります。

今回の場合は
18匹の攻撃ポケモンと
6匹の防衛ポケモンだけですが、
全ての討伐時間の組み合わせとして

18の6乗 = 34,012,224 通り

の討伐時間が考えられます。
少ない計算コストで計算できないでしょうか？

最短経路問題へ

今回の様な問題は、
計算アルゴリズムで良く扱われる
最短経路問題に帰着できます。

例えば、
相手の防衛ポケモンが２匹
こちらの攻撃ポケモンの候補が2匹
だとします。

この場合、
防衛ポケモンと攻撃ポケモンの組み合わせから、
下の図のような経路を書くことが出来ます。

この図はグラフといわれており、
○がノード、線をエッジといいます。
エッジの先に矢印がついているので、
このグラフは特に、有向グラフと言います。

エッジには数字がついており、重みを表します。
今回の場合では重みは、
攻撃ポケモンと防衛ポケモンの
組み合わせできまる討伐時間です。

防衛ポケモンは交代されることはなく、
倒したら復活することはないので、
逆方向に戻ることは考える必要はありません。
よって、有向グラフで考えて問題ありません。

先ほどの討伐時間リストのデータを基に、
経路のコストが決まっています。
ここで、水平方向のエッジのコストに対して
斜め方向のエッジのコストは 3 だけ
大きくなっています。
これは、ポケモンの交代が発生すると
３秒かかることを意味しています。
このように経路を定義して、
ダイクストラ法というアルゴリズムを使うだけで、
18の6乗 = 34,012,224 通りも計算することなく、
最短経路、すなわち最短討伐時間および
最適パーティを導くことができます

さきほどの例での
攻撃側候補2匹、防衛ポケモン2匹の
最適ルートは下の図のようになります。