数日前の記事にて研究の構想を発表しました。まだご覧でない方は先にリンク先をご覧ください。
今後はブログで研究の進捗を掲載しつつ、1年に1～2回程度まとめ記事を作れたらよいなと考えています。
最適化手法の問題点
以前発表した手法では、パーティの構築とそのパーティを使った行動の学習の2つの最適化を交互に行うことが重要でした。 行動の学習は（深層）強化学習を用いているのに対し、パーティの構築は単純な山登り法でした。 その手法の概略は、
- ベースとなるパーティを用意する。（最初はランダム）
- パーティ内のポケモン・技をランダムに変えたものを多数用意する。
- 各パーティの行動選択方法を学習し、勝率が最大のパーティを選択する。
- 2に戻る。
というものでした。強化学習がそれなりにコストのかかる（1パーティにつき数分）処理なのに、学習対象のパーティがランダムというのは効率が良くありません。 ある程度有望なパーティに対してのみ強化学習を行ったほうが良いのではないでしょうか。 ここで、パーティを実際に対戦させなくても、強さがある程度予測できるのではないかという仮説を立てました。 例えば、「サイコキネシスを覚えたフーディン」がいるパーティと、「はねるを覚えたコイキング」がいるパーティなら、前者のほうが明らかに強そうです。 そこで、パーティ構成を入力とし、対戦シミュレーションをせずに勝率を予測する関数が作れるかどうかについて検討しました。
問題の定義
ここでは、パーティ構成を入力、勝率を出力とするような関数を機械学習で求めることにします。 今回は強化学習は用いずに、バトル中の行動選択はランダムとします。また、対戦相手はランダムに構築された100種類のパーティとします。 この条件下で、勝率の予測をできるだけ正確に行うことが課題となります。
この問題は教師あり学習で解くことができます。ランダムなパーティを生成して、実際にバトルを行った勝率を正解データとします。 パーティの勝率を、バトルなしに求める関数のパラメータを学習することが目的です。
ここで、勝率予測関数に入力する特徴量の設計が必要です。 ポケモンの種類・技の種類をシンプルに並べたベクトルを特徴量とし、深層学習で求めてしまうというのも1つの手です。 しかしこれだと、入出力関係がブラックボックスになってしまいあまり面白くありません。 今回は、特徴量を手動で設計し、線形モデルによって勝率を求めることとしました。
特徴量の設計
前述のように、今回は線形モデルでパーティの勝率を予測します。式で書けば、
となります。は勝率ですが、ここでは-1(全敗)～+1(全勝)の値域としました。
がパーティの構成を表す特徴量です。
は各特徴量に対する重みで、学習によって求めます。
はバイアスですが気にしなくて構いません。
特徴設計ですが、例えば次のような要素が必要と考えられます。
このように、単独のポケモンや技の強さのほか、いくつかのポケモンや技の組み合わせがパーティの強さの指標になると予想できます。
今回は、次のような特徴を考案しました。
P=Pokémon(ポケモン)、M=Move(技)を指しています。
例えば、PM特徴だと、=(ダグトリオ&ふぶき, ダグトリオ&10まんボルト, フーディン&ふぶき, フーディン&10まんボルト, ...)のように各要素が定義されます。
パーティ内にふぶきを覚えたダグトリオと10まんボルトを覚えたフーディンがいる場合、
=(1, 0, 0, 1, ...)という値になります。
現在実装されているポケモンは9種類、技は20種類なので9*20=180個の要素があり、そのうちいくつかが1になったベクトルとして表現されます。
実はこの考え方は、将棋AIで使われる「2駒関係」という特徴量のアナロジーになっています*1。 将棋では3駒関係が主流で、1億要素以上のベクトルで盤面を表現しています。
今回提案した特徴量を総称して「2技関係」と呼ぶことにします。将来的には、3つのポケモンや技の関係を考えることが可能です。ただしその分次元数が増加し、学習が難しくなるというのがデメリットです。 また、「ポケモンと、別のポケモンが覚えている技」という2要素の関係性を考えることも可能です。 金・銀バージョン以降だと「あまごい」や「まきびし」等、場に作用して後続のポケモンに影響を与える技があるため、特に有用な可能性があります。
実験結果は近日公開します。
(2017-12-30 続きを公開しました。)
*1:参考 金子 知適ら「駒の関係を利用した将棋の評価関数」 http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw03.pdf
