ポケモンの見せ合い選出のナッシュ均衡 part07 Double Oracleアルゴリズムの導入【PokéAI】

パーティ構築の2回目です。

以下のステップで進める予定です。

ランダムに構築したパーティ候補100個のうち最適なパーティを抽出する（続き）
ランダムに（ポケモンの種族・技を）生成したポケモン100体から3体選び、パーティを構築する
あらゆるポケモン・技の組み合わせでパーティを構築する

前回は、パーティ候補100個を戦略として100×100の利得行列を作成し、直接ナッシュ均衡を求めました。しかし、利得行列のサイズがこれ以上大きくなると計算時間が長くなり、実用的ではありません。そこで、効率的なアルゴリズムとしてDouble Oracle アルゴリズムを用いて、より効率的にパーティを構築します。

Double Oracle アルゴリズム

Double Oracle アルゴリズム *1は、今回のような戦略型ゲームにおいて、効率的にナッシュ均衡を求めるためのアルゴリズムです。少数の戦略からなる利得行列に対し、逐次的に戦略を追加していくことで、最終的にナッシュ均衡を求めることができます。具体的には、以下の手順で進めます。

すべての戦略(=パーティ)集合をSとします。ポケモンバトルにおいては、2人プレイヤーが対称であると考え、プレイヤー1もプレイヤー2も同じ戦略集合Sを持つとします。Double Oracle アルゴリズム自体はプレイヤーが非対称なケースにおいて提案されましたが、ここでは対称な特殊ケースで進めます。

初期戦略 $S_1 \subset S$ を選択する
for t = 1 to $\infty$ do
利用可能な戦略が $S_t$ として、利得行列（サイズは $|S_t| \times |S_t|$ ）を計算する
利得行列からナッシュ均衡を求め、得られた混合戦略を $P_t$ とする
$P_t$ に対して、利得が最大となる戦略 $s^*_t \in S$ を求める
もし $s^*_t \in S_t$ ならば、ループを抜ける
戦略 $s^*_t$ を $S_t$ に追加し、 $S_{t+1} = S_t \cup s^*_t$ とする
end for
$P_t$ を返す
end

ポケモンバトルに即して、簡単なケースで具体的な例を示します。戦略集合Sの要素として4種類のタイプ、草・炎・水・鋼があるとします。例えば草の場合だと、草タイプのポケモンであるメガニウムが草タイプの技はっぱカッターを覚えているという状況を考えます。そして、Sから求められる利得行列が以下のようになると仮定します。草は炎に弱く、水に強く、鋼に少し弱いといった関係を示しています。

	草	炎	水	鋼
草	0	-1	1	-0.5
炎	1	0	-1	1
水	-1	1	0	0.5
鋼	0.5	-1	-0.5	0

この戦略集合について、Double Oracle アルゴリズムを適用します。

Step 1. 初期戦略 $S_1={草}$ とします。これは何でもよいですが、説明のために草を選びます。

Step 2. 利用可能な戦略は草のみです。利得行列は以下のようになります。

	草
草	0

Step 3. 利得行列からナッシュ均衡を求め、混合戦略を求めます。当然、 $P_1=(1,0,0,0)$ となります。 $P_t$ は、(草,炎,水,鋼)の順番で戦略の選択確率を表し、 $P_1$ の場合は草の確率が1、他は0です。

Step 4. $P_1$ に対して、利得が最大となる戦略 $s^*_1 \in S$ を求めます。具体的に、それぞれの戦略の利得を計算します。

草: 0(草に対する利得) * 1(相手として草が選ばれる確率) = 0
炎: 1(草に対する利得) * 1 = 1
水: -1 * 1 = -1
鋼: 0.5 * 1 = 0.5

よって、炎が最大となります。

Step 5. 炎が $S_1$ に含まれていないため、炎を追加します。これで $S_2 = {草, 炎}$ となります。

Step 6. 利用可能な戦略は草と炎です。利得行列は以下のようになります。

	草	炎
草	0	-1
炎	1	0

Step 7. 利得行列からナッシュ均衡を求め、混合戦略を求めます。草と炎が選択肢であれば、常に炎を選ぶことが最適なので、 $P_2=(0,1,0,0)$ となります。

Step 8. $P_2$ に対して、利得が最大となる戦略 $s^*_2 \in S$ を求めます。具体的に、それぞれの戦略の利得を計算します。

草: 0(草に対する利得) * 0(相手として草が選ばれる確率) + -1(炎に対する利得) * 1(相手として炎が選ばれる確率) = -1
炎: 1 * 0 + 0 * 1 = 0
水: -1 * 0 + 1 * 1 = 1
鋼: 0.5 * 0 + -1 * 1 = -1

よって、水が最大となります。

Step 9. 水が $S_2$ に含まれていないため、水を追加します。これで $S_3 = {草, 炎, 水}$ となります。

Step 10. 利用可能な戦略は草、炎、水です。利得行列は以下のようになります。

	草	炎	水
草	0	-1	1
炎	1	0	-1
水	-1	1	0

Step 11. 利得行列からナッシュ均衡を求め、混合戦略を求めます。草と炎と水が選択肢であれば、じゃんけんと同様の対称な3すくみとなり、 $P_3=(0.33,0.33,0.33,0)$ となります。

Step 12. $P_3$ に対して、利得が最大となる戦略 $s^*_3 \in S$ を求めます。具体的に、それぞれの戦略の利得を計算します。

草: 0(草に対する利得) * 0.33(相手として草が選ばれる確率) + -1(炎に対する利得) * 0.33(相手として炎が選ばれる確率) + 1(水に対する利得) * 0.33(相手として水が選ばれる確率) = 0
炎: 1 * 0.33 + 0 * 0.33 + -1 * 0.33 = 0
水: -1 * 0.33 + 1 * 0.33 + 0 * 0.33 = 0
鋼: 0.5 * 0.33 + -1 * 0.33 + -0.5 * 0.33 = -0.33

よって、草、炎、水のいずれも利得が最大となります。

Step 13. 草、炎、水のいずれも $S_3$ に含まれているため、ループを抜けます。（実装上は、複数の利得が完全に一致することはないと考え、草・炎・水のうちいずれかが選ばれ、ループを抜けることになります。）

Step 14. アルゴリズムの結果は $P_3=(0.33,0.33,0.33,0)$ となります。

アルゴリズムのポイントは、全戦略の利得行列を計算する必要がないことです。この例では、鋼を含む4×4の利得行列の計算は不要でした。4×4程度であれば一瞬で解けるためこのような複雑な手順を用いる必要はありませんが、今後扱う事例では、戦略集合Sは非常に大きくなるため、全戦略の利得行列を計算することはできません。Double Oracle アルゴリズムでは、戦略集合Sを小さく保ちながら、ナッシュ均衡を求めることができます。

次回、このアルゴリズムの実装を行います。

*1:H. Brendan McMahan et al. Planning in the presence of cost functions controlled by an adversary. ICML 2003. https://dl.acm.org/doi/10.5555/3041838.3041906