機械学習周りのプログラミング中心。 ポケモンバトルAI本通販中(4/5まで)

2技関係によるパーティ強さの予測(初代全ポケモン参加)【PokéAI】

前回の記事で、山登り法によるパーティの最適化をポケモン3匹のパーティについて実験しました。

select766.hatenablog.com

そこで生じた問題の1つは、探索空間が広すぎるためか最適化結果が芳しくないというものでした。 1匹のポケモンの構成パターンが仮に1億通り*1あるとして、3匹の組み合わせとなると1億の3乗となり、大幅に最適化が難しくなっている可能性があります。

解決策として、ランダムに探索を行うよりも有望なパターンに絞って探索を進める方法が考えられます。 例えば、現在の方法だと技「なみのり」を強力な「ふぶき」に置換した場合と明らかに弱い「みずでっぽう」に置換した場合を等確率で生成し、 ランダムに対戦させて強さを測る(それなりに時間がかかる)という方法になっています。 ここで明らかに良さそうな「ふぶき」のパターンを生成する確率を高めることで、探索の無駄を減らせるはずです。 そのための考え方として、経路探索におけるA*のように、解の良さを近似的に表現してくれるヒューリスティックの導入を考えます。 ここでは、パーティ構成を与えると、その強さの近似値を出力するような関数を作成します。 もともと山登り法で強いパーティを選択する方法は他のパーティと多数対戦させて勝率(レート)を計算するというものであり、 そのパーティ候補を作成するためのヒューリスティックなので、これより圧倒的に高速に計算できないと意味がありません。

そこで、パーティに含まれるポケモンや技に対して点数を与え、合計得点によって強さを予測(近似)する手法を提案します。 簡単に言えば、パーティにフーディンがいれば+10点、コイキングがいれば-10点、サイコキネシスを覚えていれば+5点…のようにパーティの要素それぞれに点数をつけることでその強さを予測しようという発想になります。

技術的には以前の記事の焼き直しになりますので、先にそちらをご覧ください。 以前との違いは、ポケモンの種類が20種類から151種類(初代全ポケモン)に拡張されたこと、回帰先が勝率から正規化されたレートに変更された点です。

select766.hatenablog.com

特徴量は上の記事と変わりませんが、ポケモン・技の種類が増えているので次元数は大きく増えています。該当する要素が1、それ以外が0となるベクトルで、正規化はしていません。

  • P
  • M
    • 単独の技 (165)
  • PP
  • MM
    • あるポケモンが覚えている2つの技の組 (165*(165-1)/2=13530)
  • PM
    • ポケモンと、それが覚えている技の組 (151*165=24915)

合計で50086次元となります。

データ

データは、ランダムに生成された10,000パーティを相互に対戦させて得たレートです。 パーティから対戦なしにレートを予測するモデルをリッジ回帰で学習します。 ライブラリはscikit-learnです。

入力となるパーティとレート(上に表示)の例を示します。上位、下位を抜粋しています。

2038.1734179741654
* ゲンガー (LV 50 HP 167/167)
  のしかかり ちきゅうなげ 10まんボルト メガトンキック 
  タッツー (LV 50 HP 137/137)
  みずでっぽう あわ スピードスター すてみタックル 
  カイリュー (LV 55 HP 216/216)
  のしかかり だいもんじ りゅうのいかり ふぶき 

2036.6117272435956
* サンダー (LV 50 HP 197/197)
  ドリルくちばし 10まんボルト かみなり ふきとばし 
  プテラ (LV 55 HP 204/204)
  つばさでうつ ねむる すてみタックル はかいこうせん 
  ゲンガー (LV 50 HP 167/167)
  さいみんじゅつ あやしいひかり ナイトヘッド どくどく 

2023.1601683063693
* バタフリー (LV 50 HP 167/167)
  ふきとばし サイコウェーブ ねんりき しびれごな 
  アーボック (LV 50 HP 167/167)
  あなをほる すてみタックル じわれ はかいこうせん 
  ゲンガー (LV 55 HP 182/182)
  サイコキネシス サイコウェーブ あやしいひかり かみなり 

873.1324613556571
* コイキング (LV 55 HP 138/138)
  はねる たいあたり 
  コクーン (LV 50 HP 152/152)
  かたくなる どくばり いとをはく 
  パラス (LV 50 HP 142/142)
  キノコのほうし つるぎのまい すてみタックル しびれごな 

869.9415352355768
* マルマイン (LV 55 HP 182/182)
  だいばくはつ ソニックブーム リフレクター はかいこうせん 
  タマタマ (LV 50 HP 167/167)
  さいみんじゅつ リフレクター どくのこな テレポート 
  コイキング (LV 50 HP 127/127)
  はねる たいあたり 

868.9717116445033
* コイキング (LV 50 HP 127/127)
  たいあたり はねる 
  ドガース (LV 50 HP 147/147)
  どくどく ヘドロこうげき じばく だいもんじ 
  トランセル (LV 55 HP 171/171)
  かたくなる たいあたり いとをはく 

リッジ回帰の精度

各特徴を用いた場合に、回帰精度がどう変化するかを調べました。 リッジ回帰のパラメータ"C"は、{1e-4, 1e-3, 1e-2, 1e-1, 1e0}の中から5-fold cross validationで最善のものを選択しました。特徴の組み合わせごとに別の値になっている場合があります。

精度は決定係数で表示しています。1に近いほど良い結果を意味します。

P M PP MM PM 決定係数
Y 0.509
Y 0.480
Y Y 0.749
Y 0.217
Y Y 0.482
Y 0.432
Y Y 0.494
Y Y Y Y 0.737
Y Y Y Y Y 0.769

すべての特徴量を使用した場合が一番いい結果となりました。PP特徴だけの場合は極端に精度が悪いことがわかりました。 PPはポケモンの組み合わせなので、10000次元ほどあるうちで1パーティでは3つしか要素がありません。10000パーティあっても各次元は平均3回程度しか使用されず、学習データ不足だといえます。

学習結果の観察

学習したモデルは線形モデルなので、各要素の重みから重要度を読み取ることができます。ここでは、正の値ならパーティを強くする方向に、負の値なら弱くする方向に作用している要素だとみなすことができます。

全特徴を利用して学習したモデルについて、特徴の種類ごとにtop10, worst10を表示しました。

P特徴

重み 意味
0.394 ゲンガー
0.362 ケンタロス
0.333 ギャラドス
0.314 ラプラス
0.310 カイリュー
0.268 スターミー
0.268 フリーザ
0.263 サンダー
0.259 カブトプス
0.256 オムスター
-0.312 プリン
-0.259 ニョロモ
-0.241 コラッタ
-0.237 ミニリュウ
-0.227 ヒトカゲ
-0.224 ゼニガメ
-0.217 コダック
-0.215 ケーシィ
-0.214 コンパン
-0.211 ズバット

ゲンガー・ケンタロスなどおなじみのポケモンが強いという結果です。5位にカイリューが来ています。ランダムに生成したパーティなので、ふぶきが多用されないことが上位に来られた理由だと思われます。 逆に言えば、強いパーティばかりの環境においてモデルを学習すれば違う値になるだろうと予想できます。 下位のほうは意外な結果です。コイキングトランセルが来るわけではないようです。

M特徴

重み 意味
0.339 ふぶき
0.281 サイコキネシス
0.259 ハイドロポンプ
0.241 ナイトヘッド
0.237 れいとうビーム
0.217 はなびらのまい
0.198 はかいこうせん
0.198 なみのり
0.195 10まんボルト
0.193 かえんほうしゃ
-0.361 じばく
-0.281 いとをはく
-0.236 だいばくはつ
-0.218 はねる
-0.214 ふきとばし
-0.204 テレポート
-0.203 こうそくいどう
-0.185 なきごえ
-0.181 にらみつける
-0.177 せいちょう

上位は強い技、下位は弱い技が順当に出ています。じばく・だいばくはつは適切なタイミングで使えば強力ですが、ランダムに発動しているため最悪です。 ここでトランセルが覚えるいとをはくや、コイキングが覚えるはねるがかなり負の大きな係数になっているので、 技だけで十分予測ができてしまいポケモンの側ではこれらの係数があまり大きくならなかったのかもしれません。

PP特徴

重み 意味
0.060 ニョロボン,ベトベター
0.060 オニスズメ,ペルシアン
0.059 ラッキー,ヒトデマン
0.056 リザードン,カメックス
0.055 コダック,アズマオウ
0.052 ガルーラ,ハクリュー
0.052 ピカチュウ,ウツボット
0.050 マルマイン,ナッシー
0.050 トランセル,サイドン
0.050 マタドガス,カビゴン
-0.068 ゼニガメ,アーボ
-0.060 ディグダ,ニャース
-0.060 スリープ,ミニリュウ
-0.057 エビワラー,ドガース
-0.056 トランセル,パラス
-0.056 ダグトリオ,スリープ
-0.051 ズバット,タマタマ
-0.050 リザード,ポッポ
-0.050 バタフリー,トサキント
-0.050 ニドラン♀,プリン

ポケモン同士の相性補完などが表現されることを期待したのですが、解釈しづらい結果です。係数が小さく、ほとんど役に立っていないという状況です。 ポケモンの行動がランダムなので、相性が悪いときに交代するなどの戦略が加味されていないという原因もありそうです。

MM特徴

重み 意味
0.161 だいばくはつ,じばく
0.142 ナイトヘッド,サイコキネシス
0.132 さいみんじゅつ,メガドレイン
0.129 サイコキネシス,でんじは
0.123 はかいこうせん,つるぎのまい
0.117 メガドレイン,ねむりごな
0.112 かげぶんしん,ナイトヘッド
0.112 さいみんじゅつ,サイコキネシス
0.112 いあいぎり,ちきゅうなげ
0.109 サイコウェーブ,10まんボルト
-0.188 はねる,たいあたり
-0.172 だいばくはつ,ナイトヘッド
-0.163 どくばり,いとをはく
-0.163 いとをはく,たいあたり
-0.157 さいみんじゅつ,じばく
-0.151 メガドレイン,じばく
-0.148 かげぶんしん,ふきとばし
-0.148 サイコウェーブ,じばく
-0.145 だいばくはつ,ねむる
-0.123 にらみつける,ふきとばし

意外にも、だいばくはつ,じばくの組が最上位です。M特徴でどちらも非常に大きい負の値ですが、両方覚えていたとしても片方を覚える以上に悪くならないということで補正がかかっているようです。 上位では有力な攻撃技と補助技の組み合わせが良く出てきているようです。

PM特徴

重み 意味
0.195 フリーザー,れいとうビーム
0.193 サンダー,10まんボルト
0.184 ゴースト,ナイトヘッド
0.183 フーディン,サイコキネシス
0.180 サンダー,ねむる
0.169 サンダース,かみなり
0.166 フリーザー,ふぶき
0.165 ナッシー,サイコキネシス
0.160 ファイヤー,ゴッドバード
0.159 ファイヤー,だいもんじ
-0.191 ゴースト,だいばくはつ
-0.182 ゲンガー,じばく
-0.181 ゴースト,じばく
-0.179 コイキング,たいあたり
-0.179 コイキング,はねる
-0.163 ゲンガー,だいばくはつ
-0.152 キャタピー,たいあたり
-0.152 キャタピー,いとをはく
-0.150 ヤドン,じわれ
-0.147 パウワウ,つのドリル

上位はタイプ一致攻撃技が主です。同じ技でも運用するポケモンとの相性のような部分を取り出せていることが期待できます。 下位は有用でない技が出てきています。じわれは一見強そうですが、初代では相手より素早くないと命中しないため、素早さが低いヤドンでは有効でないということでしょう。

定性的にも面白い結果が得られました。定量的にもある程度うまくいっているようなので、今後このモデルを探索に組み込んでみようと思います。

*1:ポケモン150種類×技候補30種類の4乗ぐらい