2技関係によるパーティ強さの予測(初代全ポケモン参加)【PokéAI】
前回の記事で、山登り法によるパーティの最適化をポケモン3匹のパーティについて実験しました。
そこで生じた問題の1つは、探索空間が広すぎるためか最適化結果が芳しくないというものでした。 1匹のポケモンの構成パターンが仮に1億通り*1あるとして、3匹の組み合わせとなると1億の3乗となり、大幅に最適化が難しくなっている可能性があります。
解決策として、ランダムに探索を行うよりも有望なパターンに絞って探索を進める方法が考えられます。 例えば、現在の方法だと技「なみのり」を強力な「ふぶき」に置換した場合と明らかに弱い「みずでっぽう」に置換した場合を等確率で生成し、 ランダムに対戦させて強さを測る(それなりに時間がかかる)という方法になっています。 ここで明らかに良さそうな「ふぶき」のパターンを生成する確率を高めることで、探索の無駄を減らせるはずです。 そのための考え方として、経路探索におけるA*のように、解の良さを近似的に表現してくれるヒューリスティックの導入を考えます。 ここでは、パーティ構成を与えると、その強さの近似値を出力するような関数を作成します。 もともと山登り法で強いパーティを選択する方法は他のパーティと多数対戦させて勝率(レート)を計算するというものであり、 そのパーティ候補を作成するためのヒューリスティックなので、これより圧倒的に高速に計算できないと意味がありません。
そこで、パーティに含まれるポケモンや技に対して点数を与え、合計得点によって強さを予測(近似)する手法を提案します。 簡単に言えば、パーティにフーディンがいれば+10点、コイキングがいれば-10点、サイコキネシスを覚えていれば+5点…のようにパーティの要素それぞれに点数をつけることでその強さを予測しようという発想になります。
技術的には以前の記事の焼き直しになりますので、先にそちらをご覧ください。 以前との違いは、ポケモンの種類が20種類から151種類(初代全ポケモン)に拡張されたこと、回帰先が勝率から正規化されたレートに変更された点です。
特徴量は上の記事と変わりませんが、ポケモン・技の種類が増えているので次元数は大きく増えています。該当する要素が1、それ以外が0となるベクトルで、正規化はしていません。
- P
- 単独のポケモン (151次元)
- M
- 単独の技 (165)
- PP
- パーティ内のポケモン2匹 (151*(151-1)/2=11325)
- 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 | パウワウ,つのドリル |
上位はタイプ一致攻撃技が主です。同じ技でも運用するポケモンとの相性のような部分を取り出せていることが期待できます。 下位は有用でない技が出てきています。じわれは一見強そうですが、初代では相手より素早くないと命中しないため、素早さが低いヤドンでは有効でないということでしょう。
定性的にも面白い結果が得られました。定量的にもある程度うまくいっているようなので、今後このモデルを探索に組み込んでみようと思います。