【ゲーム理論】ポケポケ「幻のいる島」環境における最適戦略は何だったか、解析してみた

はじめに

ポケポケ、楽しいです。最近では対戦の方はご無沙汰ですがログインは毎日ちゃんとしています。

筆者はこういうゲームが与えられると何とかしてハックできないかと考えてしまうタイプです。偶然にもコンピュータが多少触れるので、それを活かせるとなお良しです。

まあ対戦 AI を組むとかは大変なので、今回はメタゲームの観点からアプローチしてみます。メタゲームとは、その環境でどういうデッキがよく使用されているかを読み、その上でなるべく勝率が高そうなデッキを使用するという、各対戦より一段階上のレイヤーでの意思決定をゲームと捉えたものです。

本記事には特にポケポケのゲームシステムに依存する話はなく、ただオンラインで遊べるトレーディングカードゲーム (TCG) であることを知っていれば理解できると思います。一応、ポケポケは他の TCG と比べてプレイングスキルやデッキ構築力への依存度が低く、デッキコンセプト間の相性だけで論じるという多少強引な抽象化をしても許されるという肌感は持っています。しかし筆者は TCG についてもゲーム理論についてもニワカであるため、多少の粗はご容赦ください。

ポケポケは現状レート戦などは特にないわけですが、Limitless TCG というプラットフォームで非公式大会がよく開催されていて、ありがたいことに対戦データが公開されているので、それを元にした解析を行います。

既に多くの対戦データが蓄積されていることと、現環境における示唆を与えることが目的の記事ではないことから、最新弾の「時空の激闘」がまだ出ていなかった頃の「幻のいる島」環境を解析の対象とします。

最適戦略を考えるにあたっては、ナッシュ均衡というゲーム理論上の概念や線形計画問題という計算機科学上の概念が重要になります。まずはそのあたりの解説から入りましょう。

ナッシュ均衡

ナッシュ均衡とは、非協力ゲームにおける解概念の一つで、全プレイヤーの戦略の組であって、どのプレイヤーも、自身の戦略を変更しても利得が増えることがないものです。

ジャンケンは非協力ゲームの代表的な例です。✊ ✌️ ✋ みたいなものは純粋戦略と呼ばれます。二人のプレイヤーが純粋戦略を一つずつ選んで提出し、勝った方が利得 1、負けた方が利得 -1、あいこならば両者利得 0 を得るとします。
実はジャンケンには純粋戦略の範囲でのナッシュ均衡は存在しません。両者の純粋戦略の組はそれぞれが異なる場合と同じ場合に分けられますが、異なる場合は負けている側が、同じ場合はいずれか片側が相手に勝つ純粋戦略に変更することで利得が増えるからです。

あえて「純粋」戦略と呼び続けたのには理由があります。というのも、混合戦略という重要な拡張があるためです。混合戦略は、そのプレイヤーが取りうる各純粋戦略に確率の値を割り当てたものです。要は、ジャンケンを ✊ ✌️ ✋ から決定的に一つ選ぶゲームと捉えるのではなく、それぞれの選択確率を設定するゲームだと捉えるのです。そうすると、利得の期待値が関心の対象になります。
この拡張においては、両者ともに各純粋戦略に確率 1/3 を設定する、というのが唯一のナッシュ均衡です。相手が一様ランダムな選択をしてくるならば、こちらがどう工夫をしても期待利得が上がることはありません (下がることもありませんが)。一方、相手が偏りのある選択をしている場合、その裏をかいて期待利得を上げることができます。

実は、プレイヤー数が有限で、各プレイヤーがとりうる純粋戦略 (相異なってもよい) の数も有限、そして各プレイヤーの利得が単に純粋戦略の組によって決まるようなゲームであれば、混合戦略まで考慮すると必ず一つ以上ナッシュ均衡が存在することが知られています。これはナッシュの定理という偉大な定理で、不動点定理から導かれます。

線形計画問題

以下では、二人ゲームについて考えます。二人ゲームでは、プレイヤー 1 の混合戦略を実ベクトル $\bm{x}$、プレイヤー 2 の混合戦略を実ベクトル $\bm{y}$ としたとき、プレイヤー 1 の期待利得を実行列 $P$ を用いて $\bm{x}^\mathrm{T}P\bm{y}$ と表すことができます。

以下をプレイヤー 1 のマックスミニ戦略と呼びます。

$$\argmax_{\bm{x}} \left(\min_{\bm{y}} \left(\bm{x}^\mathrm{T}P\bm{y}\right)\right)$$

つまり、仮に相手に後出しでこちらの利得を最小化するよう戦略を決められてしまうとした場合に打てる最善の戦略です。
その状況における期待利得を $v$ とすると、任意の $\bm{y}$ について $\bm{x}^\mathrm{T}P\bm{y} \geq v$ が課されることになります。$\bm{y}$ は確率として正規化されているので、これは $P^\mathrm{T} \bm{x} \geq v \bm{1}$ と同値です。マックスミニ戦略を求める問題は、この条件のもと、$v$ を最大化する (確率として正規化された) $\bm{x}$ を求める問題であると言い換えられます。

$$\begin{array}{ll} \text{maximize} & v \\ \text{subject to} & P^\mathrm{T} \bm{x} \geq v \bm{1}, \\ & \bm{x} \geq \bm{0}, \\ & \bm{x} \cdot \bm{1} = 1 \end{array}$$

このように、目的関数や制約が変数間の線形な式で記述できるものを線形計画問題といいます。

以下ではさらに、ゼロ和ゲームであるという仮定を追加します。ゼロ和とは、二人のプレイヤーの利得の和が常に 0 になる、すなわちプレイヤー 2 の期待利得が $-\bm{x}^\mathrm{T}P\bm{y}$ であるということです。

プレイヤー 2 について先のマックスミニ戦略に対応するのが、以下のミニマックス戦略です。

$$\argmin_{\bm{y}} \left(\max_{\bm{x}} \left(\bm{x}^\mathrm{T}P\bm{y}\right)\right)$$

ミニマックス戦略を求める問題は、以下の線形計画問題に言い換えられます。

$$\begin{array}{ll} \text{minimize} & u \\ \text{subject to} & P \bm{y} \geq u \bm{1}, \\ & \bm{y} \geq \bm{0}, \\ & \bm{y} \cdot \bm{1} = 1 \end{array}$$

先の問題と非常に似た見た目をしています。実は、これら二つの線形計画問題は双対と呼ばれる関係にあるため、強双対定理により、なんと二つの問題の最適値は一致します。それはすなわち、

$$\max_{\bm{x}} \left(\min_{\bm{y}} \left(\bm{x}^\mathrm{T}P\bm{y}\right)\right) = \min_{\bm{y}} \left(\max_{\bm{x}} \left(\bm{x}^\mathrm{T}P\bm{y}\right)\right)$$

が成り立つことを意味します。このことはフォン・ノイマンのミニマックス定理と呼ばれます。

以上から、マックスミニ戦略とミニマックス戦略の組はナッシュ均衡であることがわかります。このように、二人ゼロ和ゲームの場合は、ナッシュの定理を直接用いることなく、むしろより強い結果が得られます。

具体的なナッシュ均衡戦略を得るには、ただ線形計画問題を解けばよいです。線形計画問題を解く多項式時間アルゴリズムは残念ながら知られていませんが、実用上多項式時間と思ってもいい程度に速く解くことは可能です。

Limitless TCG データとの対応づけ

Limitless TCG には、「幻のいる島」環境における 119453 対戦分のデータが記録されており、それらはプレイヤー名、対戦日時、デッキコンセプト、勝敗などの情報を含んでいます。デッキコンセプトは、基本的にメインポケモン、サブポケモンによって定まります。

今回は、プレイヤーが誰であるかということや、対戦がいつ行われたかということは無視して、単純なデッキコンセプト間の勝率に焦点を当てます。つまり、(勝利数 - 敗北数) / 対戦数 のように利得を設定します。また、使用数 51 位以下のデッキコンセプトは「その他」というデッキコンセプトにまとめ、対戦データのないデッキコンセプトの組については利得を互いに 0 とします。

実際には、おそらく各プレイヤーは確率的にデッキを使い分けているというよりは、そのときに一番勝てそうなデッキを使っているものと思われます。ただ、十分多くのプレイヤーについて各個人の意思決定が確率的なものであるとすれば、混合戦略ナッシュ均衡をメタゲームの定常状態と考えて概ね問題ないでしょう。

なお、Limitless TCG ではデータを取得するためのAPI が公開されていますが、今回はサマリ的なものを使うだけなのでこのページ以下からスクレイピングによって取得しました。念のためスクレイピングのコードは非公開として、主に解析部分の実装をこのリポジトリに置いています。

解析結果

以下のようなナッシュ均衡戦略が得られました。確率が非ゼロであるもののみ示しています。

純粋戦略	確率
ミュウツーex × サーナイト	0.1685
ギャラドスex × ゲッコウガ	0.1538
ウインディex × ファイヤーex	0.1301
リザードンex × ファイヤーex	0.1164
ピカチュウex × ゼブライカ	0.1106
ナッシーex × セレビィex	0.0862
ゲッコウガ × カモネギ	0.0843
プテラex × カモネギ	0.0654
プテラex × ミュウex	0.0472
ゲッコウガ × ミュウex	0.0333
フリーザーex × ゲッコウガ	0.0042

筆者は ギャラドスex × ゲッコウガ が最強だと思ってよく使っていましたが、ミュウツーex × サーナイト の方がナッシュ均衡戦略において確率が高いということで、意外でした。まあ、個人レベルで考えれば、確率が非ゼロであるようなものはどれを使っても勝率は変わらないので、ここにあるデッキコンセプトはどれもトップレベルの強さを持つということにはなります。それにしても、一番高くても確率 0.2 を超えないというのは、かなりちゃんとバランス調整がされているということのように思います。

また、Limitless TCG の Web ページでは実際の使用率も確認することができて、ミュウツーex × サーナイト が 1 位で 0.1769、ギャラドスex × ゲッコウガ が 2 位で 0.1178 と、そこまで遠からずな結果になっていました。世の中の TCG プレイヤーは意識してかせずか最適戦略を体現しているようで、頭が上がりません。

まとめ

今回は「幻のいる島」環境における最適戦略を得ることを試み、初歩的な解析ながらなかなか面白い結果が得られたと思います。

これからもポケポケ楽しんでいきましょう。筆者は早く新弾のダークライex を引きたいです。