パーティ構築の3回目です。
以下のステップで進める予定です。
- ランダムに構築したパーティ候補100個のうち最適なパーティを抽出する（続き）
- ランダムに（ポケモンの種族・技を）生成したポケモン100体から3体選び、パーティを構築する
- あらゆるポケモン・技の組み合わせでパーティを構築する
前回、大きな戦略集合に対して効率的にナッシュ均衡を求める方法として、Double Oracleアルゴリズムを紹介しました。今回は、その実装を行います。まずはすでに直接解けているパーティ候補100個に対してアルゴリズムを適用することで、解が一致することを確認します。
パーティ候補100個に対するDouble Oracleアルゴリズムの適用結果
実際にPythonコードでDouble Oracleアルゴリズムを実装し、パーティ候補100個に対して適用した結果を示します。パーティ同士の利得は事前に計算されているため、追加するパーティ候補に対応する行のベクトルと、現在の混合戦略の内積を計算することで利得を簡単に計算できます。以下のように、（ランダムに選ばれた）最初のパーティと各反復で追加されたパーティの情報が出力されました。
initial party (44): レアコイル,LV55,１０まんボルト,どくどく,スピードスター,すてみタックル ニョロボン,LV55,ばくれつパンチ,のしかかり,かいりき,ちきゅうなげ バンギラス,LV55,れいとうビーム,はかいこうせん,すなあらし,だいもんじ added party (22) payoff=0.35902439: サンダー,LV55,はかいこうせん,どくどく,すてみタックル,かみなり ゲンガー,LV55,おんがえし,でんじほう,かみなり,かみなりパンチ シャワーズ,LV55,バブルこうせん,おんがえし,なみのり,ハイドロポンプ added party (3) payoff=0.27296875: カビゴン,LV55,おんがえし,サイコキネシス,とっしん,１０まんボルト カビゴン,LV55,かげぶんしん,のしかかり,とっしん,ちきゅうなげ ゴローニャ,LV55,ばくれつパンチ,じしん,のしかかり,すてみタックル added party (64) payoff=0.32028986: ドククラゲ,LV55,バブルこうせん,はかいこうせん,ヘドロばくだん,なみのり バンギラス,LV55,どくどく,じしん,かげぶんしん,れいとうビーム ポリゴン２,LV55,はかいこうせん,とっしん,１０まんボルト,おんがえし added party (8) payoff=0.21301101: スイクン,LV55,どくどく,なみのり,ふぶき,いあいぎり バンギラス,LV55,れいとうビーム,かえんほうしゃ,かいりき,おんがえし カビゴン,LV55,かいりき,れいとうビーム,ちきゅうなげ,じしん added party (32) payoff=0.03625: ムウマ,LV55,でんじほう,かみなり,サイコキネシス,どくどく ニドクイン,LV55,すなあらし,れいとうパンチ,ちきゅうなげ,かみなりパンチ スイクン,LV55,ふぶき,れいとうビーム,なみのり,どくどく added party (56) payoff=0.04154654: カビゴン,LV55,かげぶんしん,のしかかり,とっしん,ちきゅうなげ ゲンガー,LV55,おんがえし,でんじほう,かみなり,かみなりパンチ スイクン,LV55,ふぶき,れいとうビーム,なみのり,どくどく added party (88) payoff=0.00052149: バンギラス,LV55,どくどく,じしん,かげぶんしん,れいとうビーム ベトベトン,LV55,ギガドレイン,だいもんじ,かえんほうしゃ,ヘドロばくだん カビゴン,LV55,かいりき,れいとうビーム,ちきゅうなげ,じしん
括弧の中はパーティの番号で、数値に意味はありません。payoffは、現在の混合戦略に対する利得を示しています。これはログの冒頭ではなく、これですべてです。つまり、100個のパーティ候補に対して、その部分集合である8パーティが選ばれた時点で、もう追加できるパーティがなく、ループが終了しました。
最終的なパーティ選択の混合戦略は以下のようになります。初期パーティとして選択した44番の選択確率が0になることは、ランダムに選んだパーティが最適でなければ当然発生します。また、途中で追加されたパーティについても、選択確率が0になることがあります。これは、そのあとに追加されたパーティの組み合わせによっては必要がなくなる場合もあるためです。計算結果は、100×100行列を用意して計算した場合と一致しており、Double Oracleアルゴリズムの実装が正しいことが確認できました。
party=88 probability=0.4732014954129639 バンギラス,LV55,どくどく,じしん,かげぶんしん,れいとうビーム ベトベトン,LV55,ギガドレイン,だいもんじ,かえんほうしゃ,ヘドロばくだん カビゴン,LV55,かいりき,れいとうビーム,ちきゅうなげ,じしん party=8 probability=0.26550235080245216 スイクン,LV55,どくどく,なみのり,ふぶき,いあいぎり バンギラス,LV55,れいとうビーム,かえんほうしゃ,かいりき,おんがえし カビゴン,LV55,かいりき,れいとうビーム,ちきゅうなげ,じしん party=56 probability=0.15739501152200677 カビゴン,LV55,かげぶんしん,のしかかり,とっしん,ちきゅうなげ ゲンガー,LV55,おんがえし,でんじほう,かみなり,かみなりパンチ スイクン,LV55,ふぶき,れいとうビーム,なみのり,どくどく party=32 probability=0.09842871943734022 ムウマ,LV55,でんじほう,かみなり,サイコキネシス,どくどく ニドクイン,LV55,すなあらし,れいとうパンチ,ちきゅうなげ,かみなりパンチ スイクン,LV55,ふぶき,れいとうビーム,なみのり,どくどく party=22 probability=0.005472422825236909 サンダー,LV55,はかいこうせん,どくどく,すてみタックル,かみなり ゲンガー,LV55,おんがえし,でんじほう,かみなり,かみなりパンチ シャワーズ,LV55,バブルこうせん,おんがえし,なみのり,ハイドロポンプ party=64 probability=0.0 ドククラゲ,LV55,バブルこうせん,はかいこうせん,ヘドロばくだん,なみのり バンギラス,LV55,どくどく,じしん,かげぶんしん,れいとうビーム ポリゴン２,LV55,はかいこうせん,とっしん,１０まんボルト,おんがえし party=44 probability=0.0 レアコイル,LV55,１０まんボルト,どくどく,スピードスター,すてみタックル ニョロボン,LV55,ばくれつパンチ,のしかかり,かいりき,ちきゅうなげ バンギラス,LV55,れいとうビーム,はかいこうせん,すなあらし,だいもんじ party=3 probability=0.0 カビゴン,LV55,おんがえし,サイコキネシス,とっしん,１０まんボルト カビゴン,LV55,かげぶんしん,のしかかり,とっしん,ちきゅうなげ ゴローニャ,LV55,ばくれつパンチ,じしん,のしかかり,すてみタックル
次回は、Double Oracleアルゴリズムを導入する目的であった、ランダムに生成したポケモンから3体選び、パーティを構築する方法を実装します。
