ポケモンチーム最適化

私は小さい頃から大きなポケモンファンでした――テレビでアニメ（映画も含む）を観、ゲームボーイカラー（ピカチュウテーマだったものもあり）でプレイし、カードを集めていました。フィギュア、ポスター、ブランケット、ぬいぐるみ―何でも揃えていたのです。本当は家族が私の好きなことに気づいたとき、クリスマスや誕生日の贈り物に無限に出てくる宝庫を発見したようなもので、6歳の私は全く文句を言いませんでした。

ゲーム自体は心に残っています。世代I〜IVまで熱心にプレイしましたが、V世代のソフトリブートには失望しました。思春期直前だった頃、やめる気持ちもありました。10年後、再び好きなゲームを大人として遊んでみたとき、その楽しさは再発見できました。

しかしすぐに気づいたのは、子供ではなくなったことで魔法が失われてしまっているということでした。ターゲットオーディエンスより年上で科学者として働く私は、ゲームを通じて常にミンマックス（最大化・最小化）を試みるようになり――能力の良いポケモンやタイプカバーリング、技間のシナジーを探し出す―。メインラインのポケモンゲームをプレイしたことがあるなら、この行為は完全に不要だとわかります。20年前であればブロスタイズやタイフロスニオンだけで突き進めたでしょう。大人の私はバランスの取れたチームを構築し、どんな遭遇にも備えたいので、この狂気のピークに小さなツールを作ることにしました。本記事ではその手順をご紹介します。

---

混合整数計画（MIP）として問題を定式化する

何を最適化しようとしているか？

ポケモンは基本的にターン制のゲームで、最大6体までの「ポケモン」を派遣して戦わせます。現在では9世代にわたる1,025種が存在します。各ポケモンは1つまたは2つのタイプ（炎、水、草など）を持ち、最大4つの技を覚えることができ、それぞれ独自のタイプがあります。タイプ同士には強弱関係があり、例えば水タイプは炎タイプに対して効果的で、火ポケモンへの水攻撃は2倍のダメージになります。

この記事では「基本ステータス合計」を強いポケモンの指標としてのみ考えます。目標は次のようなチームを見つけることです：

1. 目的関数 – 基本ステータスの総和を最大化する。
2. 制約条件 – 各タイプ A に対して、少なくとも1体のポケモンが耐性を持つ。

その他の制約：

• ポケモンは重複選択できない（各ポケモンは一度だけ選べる）。
• チームサイズは1〜6体の範囲であること。

意思決定変数は二値です：
(x_n = \begin{cases}1 &\text{ポケモン } n \text{ がチームに入っている}\0 &\text{それ以外}\end{cases})

簡単なモデルは次のようになります。

[ \max_{x};\sum_{n} b_n x_n ] 制約

[ 1 \leq \sum_{n} x_n \leq 6,\qquad x_n \in {0,1}. ]

---

線形計画（101）での最適化

整数から線形へ

整数制約を持つ問題は難解です。まず整合性を緩め、**線形プログラム（LP）**として解きます：

• 目的関数とすべての制約が意思決定変数に対する線形式。
• 実行可能解集合は超平面で境界づけられた凸多面体になります。

シンプレックス法はこの多面体の頂点を探索し最適点を見つけます。整数問題では、最適LP頂点が分数値になる場合があります。そのため 枝刈り（branch‑and‑bound） を用います：

1. 線形緩和版を解く。
2. すべての変数が整数なら終了。
3. そうでなければ非整数変数を選び、分岐させる（(x \leq 0) と (x \geq 1) の二つのサブプロブレム）。
4. 再帰的に整数解が見つかるまでまたは探索空間が尽きるまで繰り返す。

---

非線形制約を追加する

タイプ耐性制約は min 演算子を含み、非線形です：

[ \min_{n}\bigl(x_n t_{An}\bigr) \le 0.5, ]

ここで (t_{An}) はタイプ A がポケモン n に与えるダメージ係数です。
補助二値変数 (y_{An}) と十分大きな定数 (M) を導入します：

[ x_n t_{An} + M (y_{An}-1) \le 0.5,\qquad \sum_n y_{An} \ge 1. ]

(y_{An}=1) のときは最初の制約で (x_n t_{An}\le 0.5) が強制され、(y_{An}=0) のときは自動的に満たします。

しかし耐性を持つポケモンが実際にチームに入っていることも保証しなければならないため、さらに変数 (z_{An}) を追加します：

[ \begin{aligned} z_{An} &\le x_n,\ z_{An} &\le y_{An},\ z_{An} &\ge x_n + y_{An} - 1. \end{aligned} ]

これにより (z_{An}=x_n \land y_{An}) が成立します。
(\sum_n y_{An}\ge 1) を (\sum_n z_{An}\ge 1) に置き換えることで、選択されたポケモンが耐性を持つことが保証されます。

---

PuLPで実装してみる

以下は PuLP（Google の OR‑Tools も優れた代替です）を使った簡潔な Python 実装例です。

import pulp

def solve_pokemon_team(number_pkmn, number_types,
                       types_matrix, pkmn_base_stat):
    prob = pulp.LpProblem("Pokemon_Team_Optimization",
                          pulp.LpMaximize)

    # 意思決定変数
    x = pulp.LpVariable.dicts("x", range(number_pkmn), cat="Binary")
    y = pulp.LpVariable.dicts("y",
                              (range(number_types), range(number_pkmn)),
                              cat="Binary")
    z = pulp.LpVariable.dicts("z",
                              (range(number_types), range(number_pkmn)),
                              cat="Binary")

    # チームサイズ制約
    prob += pulp.lpSum(x[i] for i in range(number_pkmn)) >= 1, "MinTeamSize"
    prob += pulp.lpSum(x[i] for i in range(number_pkmn)) <= 6, "MaxTeamSize"

    # 目的関数：基本ステータス合計を最大化
    prob += pulp.lpSum(pkmn_base_stat[i] * x[i]
                       for i in range(number_pkmn)), "TotalBaseStat"

    M = 1000   # 十分大きい定数

    # タイプ耐性制約
    for a, type_row in enumerate(types_matrix):
        # z が選択されたポケモンがタイプ a に耐性を持つことを強制
        prob += pulp.lpSum(z[a][i] for i in range(number_pkmn)) >= 1, f"Resist_{a}"
        for i in range(number_pkmn):
            # z = x ∧ y
            prob += z[a][i] <= x[i], f"z1_{a}_{i}"
            prob += z[a][i] <= y[a][i], f"z2_{a}_{i}"
            prob += z[a][i] >= x[i] + y[a][i] - 1, f"z3_{a}_{i}"

            # y が選択されているとき耐性を強制
            prob += (x[i] * pkmn_base_stat[i]
                     <= 0.5 + M * (1 - y[a][i])), \
                    f"Weakness_{type_row}_pkmn_{i}"

    # 問題を解く
    out_code = prob.solve()

    # 結果を抽出
    team_indices = [i for i in range(number_pkmn)
                    if pulp.value(x[i]) == 1]
    return team_indices, pulp.value(prob.objective)

---

結果とまとめ

得られるチームはどんなもの？

最適解のチームは、世代を問わずレジェンダリーや擬似レジェンダリー（最高基礎ステータス）で構成されます。タイプ面では「ドラゴン」と「鋼」が最もカバーされており、メタグロスとレックウザが多くの制約を満たします。残る弱点には：

• ゴースト耐性：ダークポケモン（例：タイラニタ）
• 岩耐性：ファイティングまたはグラウンドポケモン（例：グロウドン）

レジェンダリーを除外すると、擬似レジェンダリーが選ばれます。例えばタイラニタ・メタグロス・サルマセン・ガチョウムといった強力な非レジェンダリーが加わります。スレイキングは高基礎ステータスのため選択されますが、実際にはその能力により活性化率が50％になる点をモデルは考慮していません。

より現実的な制約

レジェンダリー・擬似レジェンダリーを除外し、スタートアップポケモンは最大1体に限定した場合、最良のチームは主に世代IIIから構成されます。これは世代IIIが高基礎ステータスかつバランスの取れたタイプを多数持っていたことを反映しています。

まとめ

このプロジェクトは OR（運用研究）手法の楽しいデモです。STAB、能力効果、技カバーリングなど多くの追加制約を入れることで「完璧な」ポケモンチームに近づけます。自分だけのチームを作りたい場合は GitHub リポジトリにある CLI ツールで部分的なチームを補完し、残りのスロットを最適化できます。

この記事に登場する全てのポケモン画像は pokeapi.co から取得しています。

---