以前の記事で、バトルなしにパーティの強さを予測する関数（以下では静的評価関数と呼ぶことにします）を学習しました。今回はこれを山登り法によるパーティ構成の最適化に組み込みます。
山登り法でのパーティ構築は次のような手順でした。
- ランダムなパーティXを生成する
- Xのポケモンや技を1つ変更した近傍パーティY1,...,Ynを生成する
- Y1,...,Ynを評価用パーティ群と対戦させ、強さ（レーティング）を計算する
- 最も強いパーティをXに代入し、2に戻る
ここでの問題は、ステップ3でパーティの評価に多数のバトル（今は100回でやっています）が必要で、時間がかかるということです。 例えば、「ふぶき」を「たいあたり」に変更した明らかにダメそうなパーティにも時間を割く必要が生じ、時間効率が悪いです。 そこで、有望なパーティに限ってバトルでの評価を行うことで改善を試みます。改良後のアルゴリズムは次のようになります。
- ランダムなパーティXを生成する
- Xのポケモンや技を1つ変更した近傍パーティY1,...,Ym (m > n)を生成する
- Y1,...,Ymに静的評価関数を適用し、上位nパーティをY1,...,Ynに代入する
- Y1,...,Ynを評価用パーティ群と対戦させ、強さ（レーティング）を計算する
- 最も強いパーティをXに代入し、2に戻る
これは最良優先探索の考え方を応用したものになっています。
実装して実験してみました。ランダムなパーティを初期値として、近傍生成数はm=100,n=10、山登り法の繰り返し10回としました。比較対象は、静的評価関数を使わないで山登り法を行ったもの(n=10とし、バトルでの評価を行うパーティ数を同数とする)、ランダムなパーティ、静的評価関数自体を最大にするパーティを用いました。
静的評価関数自体の最大化は、同様に山登り法で実現できます。対戦によって強さを測定する代わりに静的評価関数の結果をそのまま強さとして使えば実装できます。他と合わせて繰り返し10回のものと、とにかく評価関数を最大化するということで繰り返し1000回のものを作成しました。
各条件で初期値を変えて各100パーティ生成し、これらを混ぜてレーティング戦を行いました。行動戦略はすべてランダムで、強化学習は入っていません。
| 最適化条件 | 平均レート |
|---|---|
| (A)ランダム | 1162 |
| (B)バトル | 1381 |
| (C)静的評価関数+バトル | 1655 |
| (D)静的評価関数のみ(繰り返し10) | 1588 |
| (E)静的評価関数のみ(繰り返し1000) | 1711 |
BとCを比較すると、静的評価関数を使うことで、バトルでの評価部分についてほぼ同じ計算コストでより強いパーティが生成できています。 また、CとDは途中で生成されるパーティ候補の数は同じですが、バトルで強さを評価したほうが強い傾向にあるといえます。 一方、最も強かったのはEでした。バトルを一切せず、静的評価関数の値が最大となるようなパーティを生成すれば十分強いという結果です。
対戦で上位レートを得たパーティをグループごとに示します。
↓(A)ランダム
1479.7354283838638 * シードラ (LV 50 HP 162/162) こうそくいどう バブルこうせん にらみつける みずでっぽう ゲンガー (LV 55 HP 182/182) サイコウェーブ じごくぐるま さいみんじゅつ 10まんボルト フーディン (LV 50 HP 162/162) ロケットずつき サイコキネシス トライアタック すてみタックル 1447.0239174401538 * ニドキング (LV 55 HP 205/205) ちきゅうなげ じしん にらみつける ふぶき ペルシアン (LV 50 HP 172/172) すてみタックル ひっかく どくどく かげぶんしん カメックス (LV 50 HP 186/186) あわ メガトンキック あなをほる ハイドロポンプ 1443.0889755952132 * ゲンガー (LV 55 HP 182/182) ねむる したでなめる サイコウェーブ サイコキネシス スリープ (LV 50 HP 167/167) さいみんじゅつ トライアタック どくどく のしかかり ダグトリオ (LV 50 HP 142/142) じしん ねむる いあいぎり いわなだれ
↓(B)バトル
1644.178954863615 * ゴースト (LV 55 HP 166/166) ナイトヘッド 10まんボルト サイコキネシス ニョロボン (LV 50 HP 197/197) じしん ふぶき さいみんじゅつ かいりき プテラ (LV 50 HP 187/187) かみつく つばさでうつ はかいこうせん 1632.4251737361622 * リザードン (LV 55 HP 202/202) じしん きりさく だいもんじ フシギバナ (LV 50 HP 187/187) ソーラービーム やどりぎのタネ のしかかり ねむりごな ジュゴン (LV 50 HP 197/197) なみのり れいとうビーム 1607.3417191119063 * ラプラス (LV 55 HP 259/259) りゅうのいかり うたう サイコウェーブ れいとうビーム ニドクイン (LV 50 HP 197/197) いわなだれ なみのり れいとうビーム ひっかく サンダース (LV 50 HP 172/172) かみなり のしかかり どくどく
↓(C)静的評価関数+バトル
1864.7585210905622 * ゲンガー (LV 55 HP 182/182) サイコキネシス ちきゅうなげ さいみんじゅつ ナイトヘッド ライチュウ (LV 50 HP 167/167) のしかかり 10まんボルト はかいこうせん かみなり フリーザー (LV 50 HP 197/197) ふぶき れいとうビーム そらをとぶ かげぶんしん 1861.053481729282 * プテラ (LV 50 HP 187/187) はかいこうせん そらをとぶ ゴッドバード だいもんじ ルージュラ (LV 50 HP 172/172) バブルこうせん のしかかり メガトンキック ふぶき ゲンガー (LV 55 HP 182/182) さいみんじゅつ サイコキネシス ナイトヘッド 10まんボルト 1852.1999935932283 * ルージュラ (LV 55 HP 188/188) ふぶき あくまのキッス れいとうビーム ウインディ (LV 50 HP 197/197) かえんほうしゃ はかいこうせん だいもんじ あなをほる ゲンガー (LV 50 HP 167/167) 10まんボルト さいみんじゅつ ちきゅうなげ サイコキネシス
↓(D)静的評価関数のみ(繰り返し10)
1789.8176242017867 * フシギバナ (LV 50 HP 187/187) ねむりごな はっぱカッター やどりぎのタネ のしかかり ラプラス (LV 55 HP 259/259) ハイドロポンプ れいとうビーム かみなり ふぶき ゲンガー (LV 50 HP 167/167) 10まんボルト サイコキネシス ナイトヘッド さいみんじゅつ 1778.564922781992 * ラプラス (LV 50 HP 237/237) ハイドロポンプ かいりき バブルこうせん れいとうビーム フシギバナ (LV 50 HP 187/187) のしかかり メガドレイン はっぱカッター ねむりごな スターミー (LV 55 HP 182/182) サイコキネシス ねむる じこさいせい ふぶき 1778.3059349935693 * サンダー (LV 55 HP 215/215) かみなり はかいこうせん ドリルくちばし 10まんボルト プテラ (LV 50 HP 187/187) そらをとぶ ゴッドバード だいもんじ すてみタックル ニョロボン (LV 50 HP 197/197) ふぶき さいみんじゅつ れいとうビーム のしかかり
↓(E)静的評価関数のみ(繰り返し1000)
1924.0833346696368 * サンダー (LV 55 HP 215/215) 10まんボルト かみなり はかいこうせん ドリルくちばし ラプラス (LV 50 HP 237/237) ふぶき ハイドロポンプ れいとうビーム バブルこうせん ゲンガー (LV 50 HP 167/167) メガドレイン ナイトヘッド さいみんじゅつ サイコキネシス 1866.9876553669278 * サンダー (LV 55 HP 215/215) かみなり ドリルくちばし でんきショック 10まんボルト ケンタロス (LV 50 HP 182/182) かいりき れいとうビーム ふぶき はかいこうせん ゴースト (LV 50 HP 152/152) サイコキネシス ナイトヘッド さいみんじゅつ メガドレイン 1864.5993017504716 * ドククラゲ (LV 50 HP 187/187) ふぶき ハイドロポンプ なみのり れいとうビーム ゲンガー (LV 50 HP 167/167) メガドレイン ナイトヘッド サイコキネシス さいみんじゅつ サンダー (LV 55 HP 215/215) ドリルくちばし かみなり 10まんボルト はかいこうせん
前回はランダムに生成した100,000パーティのうちから静的評価関数が高いものを表示し、最強ではなさそうという結果でした。その時の予測レートは最大で2100程度（対戦相手が違うので、上の表との数値の互換性はありません）でした。しかし、静的評価関数が最大となるようパーティを最適化した結果、2400程度のパーティが得られています。実際、(E)の上位パーティはかなり強そうといって差し支えないのではないでしょうか。
ランダムに行動する条件下では、静的評価関数を学習したうえでそれを最大化するパーティを探索するという手法がかなり良さそうということがわかりました。 パーティ特徴量が1万次元ほどあり、それを1万種類のパーティで学習しているため、このパーティ数を増やすともう少し改善するかもしれません。
行動を強化学習する手法との組み合わせは悩みどころです。ランダムな行動では無意味な技の組み合わせが、強化学習した場合は有効なコンボとなる可能性があり、今の静的評価関数でそのような候補を弾いてしまうのは良くない可能性があります。しかし1万種類のパーティの行動をそれぞれ強化学習するというのは計算時間的に不可能で、その強さをベースに強化学習での戦略を考慮した静的評価関数を学習するのは困難かと思われます。引き続き手法を検討していきます。
