汎用行動選択モデルの学習 part10 Q関数を用いたパーティ生成【PokéAI】

前回、強化学習によって得たQ関数を用いてパーティの強さを定量化する指標（パーティ評価関数）を定義しました。今回はこれを用いて強力なパーティを生成する手法を説明します。

ここでの目的は、パーティ評価関数R(X)の値が比較的大きいパーティXを多数求めることです。上位の目的は強化学習中に対戦させるパーティを生成することであり、強化学習エージェントは様々なパーティを受け持ち、様々な相手への立ち回り方を学習する必要があります。そのためR(X)が厳密な最大値をとる唯一のパーティを生成するのではなく、R(X)をできるだけ大きくしつつ、パーティごとにポケモン・技が異なるような多様性のあるパーティ群 $X_G = \{{X}^1, {X}^2, {X}^3,...\}$ を生成します。

ペナルティ項つき山登り法による多様なパーティ生成

手法は以前提案した山登り法ベースですが、それだけだと同一のパーティが大量にできてしまうため、今回新たにペナルティ項を加えることとしました。 select766.hatenablog.com

山登り法を用いたパーティ生成手法について、第3巻から必要な部分を変更して再掲します。

パーティ評価関数 $R(X)$ の値が最大となるようなパーティ $X$ を生成するために、単純な離散最適化手法である山登り法を用います。山登り法の概要を下図に示します。最初にランダムなパーティ $X_0$ を生成し、これを少しだけ変更した近傍パーティ候補 $N(X_0) = \{{C_1}^1, {C_1}^2, ...\}$ を生成します。そして、これを $R$ で評価し、最も強いパーティを選択します。この処理を1世代とします。選択されたパーティを $X_1$ とし、次の世代では再度これを少しだけ変更したパーティ候補 $N(X_1)=\{{C_2}^1, {C_2}^2, ...\}$ を生成します。そして、これを $R$ で評価し、最も強いパーティを選択します。これを繰り返すことで徐々に強いパーティへと変化させていきます。ここで、パーティを少しだけ変更する手段は2通り用意しています。(1)ポケモンを1匹完全に別のものにし、技もランダムに設定する、(2)1匹のポケモンを選び、その技を1つ選び、別のものにする。(1)が選ばれる確率はそれぞれ10%、それ以外では(2)が選ばれ、パーティが変更されます。

f:id:select766:20200821082434p:plain — 山登り法の概要

山登り法は以前から使用しています。第1巻では、パーティ構成1匹の条件で用いており、パーティ変更の手段(1)を使いませんでした。ポケモンによって覚える技が違うため、ポケモンを別のものに変更すると技はランダムに設定しなおすこととなり、1匹しかいないポケモンを変更すると近傍ではなくなってしまうという考え方で変更を避けました。しかしその場合、初期値としてランダムに選んだポケモンが弱いと改善の余地がないという状態になります。現在の条件で強いとされているフォレトスやサイドンと、極端に弱いレディアンやヤンヤンマが同じ頻度で現れるというのは強いパーティの生成として不十分と考えられます。第3巻では、パーティ構成3匹の条件で用いて、ポケモン変更ありで強いパーティを得ました。今回はパーティ構成1匹で、単純に同様の手法をとると同一のパーティが大量にできてしまうという結果になりました。山登り法は局所最適解が出る手法なので、初期値によって違う結果がある程度得られますが、探索範囲が狭いと同じ解に収束する可能性が高くなります。

この問題に対して、すでに生成されたパーティと類似のパーティが生成されにくくするための明示的なペナルティ項 $S(X)$ を設けることにしました。パーティ群に含まれるパーティは、 ${X}^1, {X}^2, ...$ の順に1つずつ山登り法で生成します。 ${X}^i$ を生成する際は、それまでに生成したパーティと類似するパーティのパーティ評価関数の値を小さくし、今までに生成されていないパーティの生成を促進します。ペナルティ項は

$S(X_i)=\frac{1}{i-1}\sum_{j=1}^{i-1} K(X_j, X_i)$

と定義します。ここで、 $K(X_j, X_i)$ はパーティ間の類似度を表す関数です。過去に提案したパーティを表す特徴量(P,M,PM,MM)の内積として定義しました。パーティ間でポケモン1匹、技1つ、ポケモンと技の組み合わせ、技と技の組み合わせがいくつ一致するかで算出されます。パーティ間で一切一致がない場合は0、ポケモンも技もすべて一致する場合は1+4+4+6(4つの技から2つを選ぶ組み合わせ)=15になります。 select766.hatenablog.com

このペナルティ項を用いて、山登り法でパーティを評価する際の計算式を $R(X_i) - \lambda S(X_i)$ とします。ペナルティの強さは負でないスカラー定数 $\lambda$ で制御します。

実験結果

ペナルティの強さを変えつつパーティを生成して比較します。

山登り法のパラメータは、近傍パーティ生成数10、世代数100とし、パーティ群の大きさは871としました。871は、1000-129=871で算出しています。129は今回対象にする全ポケモンの種族数で、山登り法で生成したパーティ群に、各種族のポケモンが含まれるパーティを1つずつ足して合計で1000パーティとし、今後の強化学習の対象とするためです。この追加の129パーティは本稿の実験結果には含まれません。

$\lambda=0$ で生成した871パーティからランダムに10パーティ抽出した結果を示します。

ヤドラン,LV55,じしん,すてみタックル,だいもんじ,ふみつけ
ガルーラ,LV55,かえんほうしゃ,ちきゅうなげ,かみなり,だいもんじ
ヤドラン,LV55,じしん,だいもんじ,のしかかり,でんじほう
サイドン,LV55,だいもんじ,じしん,でんじほう,１０まんボルト
フォレトス,LV55,ころがる,すてみタックル,とっしん,ギガドレイン
ガルーラ,LV55,だいもんじ,かえんほうしゃ,かみなり,ちきゅうなげ
サイドン,LV55,じしん,１０まんボルト,だいもんじ,でんじほう
サイドン,LV55,だいもんじ,１０まんボルト,じしん,でんじほう
ガルーラ,LV55,かみなり,かえんほうしゃ,だいもんじ,ちきゅうなげ
フォレトス,LV55,とっしん,ころがる,ギガドレイン,すてみタックル

$\lambda=0.1$ の場合を下に示します。

スイクン,LV55,れいとうビーム,なみのり,いわくだき,たきのぼり
ガルーラ,LV55,れいとうパンチ,だいもんじ,いわくだき,かみなり
プテラ,LV55,だいもんじ,はがねのつばさ,げんしのちから,じしん
エアームド,LV55,そらをとぶ,ゴッドバード,すなあらし,どろかけ
フォレトス,LV55,とっしん,ころがる,ギガドレイン,ソーラービーム
フォレトス,LV55,かいりき,ころがる,おんがえし,ギガドレイン
サイドン,LV55,ふぶき,じしん,でんじほう,ほのおのパンチ
ケンタロス,LV55,かみなり,ふみつけ,つのドリル,すてみタックル
フォレトス,LV55,ソーラービーム,かいりき,すてみタックル,ギガドレイン
ガルーラ,LV55,なみのり,かえんほうしゃ,かみなり,ちきゅうなげ

$\lambda=1$ の場合を下に示します。

ドードリオ,LV55,のしかかり,どくどく,ゴッドバード,はがねのつばさ
ミルタンク,LV55,かみなりパンチ,ふみつけ,ちきゅうなげ,ずつき
カイリキー,LV55,かいりき,ほのおのパンチ,すてみタックル,ちきゅうなげ
ツボツボ,LV55,じしん,ヘドロばくだん,いわくだき,ころがる
カメックス,LV55,ころがる,たきのぼり,ハイドロポンプ,れいとうパンチ
フーディン,LV55,ほのおのパンチ,れいとうパンチ,サイケこうせん,かみなりパンチ
エアームド,LV55,はがねのつばさ,そらをとぶ,スピードスター,すなあらし
ラプラス,LV55,サイコキネシス,はかいこうせん,つのドリル,いわくだき
サイドン,LV55,つのドリル,ころがる,どろかけ,かみなり
エアームド,LV55,おんがえし,はがねのつばさ,ゴッドバード,どくどく

$\lambda=10$ の場合を下に示します。

マリルリ,LV55,ふぶき,ハイドロポンプ,ばくれつパンチ,ずつき
プテラ,LV55,げんしのちから,ゴッドバード,はがねのつばさ,とっしん
ライコウ,LV55,すなあらし,いあいぎり,かみなり,スピードスター
ハガネール,LV55,いあいぎり,じしん,はかいこうせん,ロケットずつき
スイクン,LV55,バブルこうせん,いわくだき,スピードスター,なみのり
スイクン,LV55,たきのぼり,いあいぎり,なみのり,かげぶんしん
ピクシー,LV55,はなびらのまい,すてみタックル,ふぶき,ほのおのパンチ
ゴルダック,LV55,ハイドロポンプ,スピードスター,はなびらのまい,れいとうパンチ
デンリュウ,LV55,かみなりパンチ,とっしん,かみなり,いわくだき
ガルーラ,LV55,すなあらし,かえんほうしゃ,ほのおのパンチ,はかいこうせん

各々のパーティの良さは直観的にはどの条件でもあまり変わらない一方、 $\lambda=0$ ではポケモンの種類が偏っています。実際、「フォレトス,LV55,ころがる,すてみタックル,とっしん,ギガドレイン」のパーティは219回も生成されてしまいました。別の側面では、ランダムな初期値から開始して同じ解に収束しているので、山登り法の世代数などのパラメータは十分であると考えられます。 $\lambda$ が大きくなるにつれてパーティの多様性が増していますが、直観的に異常な（極端に弱そうな）内容にはなっていません。

定量的に、全パーティでのポケモンや技の出現回数を算出した結果を示します。各要素出現回数上位20件を表示しています。

$\lambda=0$

要素	出現回数
フォレトス	223
ガルーラ	162
ケンタロス	91
サイドン	86
ヤドラン	85
ミルタンク	68
エアームド	50
スイクン	38
ラプラス	29
プテラ	29
マンタイン	2
カイリキー	2
ハッサム	2
レアコイル	2
ツボツボ	1
カビゴン	1

要素	出現回数
だいもんじ	360
かみなり	287
じしん	271
すてみタックル	260
かえんほうしゃ	252
ギガドレイン	223
とっしん	222
ころがる	221
ちきゅうなげ	220
のしかかり	148
れいとうビーム	140
でんじほう	139
ふみつけ	119
１０まんボルト	85
すなあらし	82
かみなりパンチ	71
おんがえし	61
そらをとぶ	50
ドリルくちばし	50
はかいこうせん	41

$\lambda=0.1$

要素	出現回数
フォレトス	159
ガルーラ	150
ヤドラン	99
サイドン	91
ミルタンク	81
ケンタロス	73
エアームド	67
スイクン	53
ラプラス	51
プテラ	31
カビゴン	6
ハッサム	4
レアコイル	3
ランターン	1
カイリキー	1
ドードリオ	1

要素	出現回数
じしん	223
かみなり	179
ギガドレイン	144
れいとうビーム	138
だいもんじ	126
おんがえし	112
すなあらし	106
かえんほうしゃ	103
すてみタックル	98
ちきゅうなげ	96
なみのり	89
のしかかり	88
１０まんボルト	87
とっしん	83
かみなりパンチ	83
はかいこうせん	82
かいりき	80
でんじほう	79
れいとうパンチ	79
ずつき	79

$\lambda=1$

要素	出現回数
ガルーラ	72
フォレトス	63
サイドン	62
ケンタロス	62
ミルタンク	58
ヤドラン	51
エアームド	48
スイクン	43
ラプラス	42
プテラ	38
ハッサム	29
ドードリオ	26
カビゴン	23
マンタイン	18
カイリキー	18
フーディン	17
レアコイル	17
メガニウム	12
ツボツボ	11
ゴルダック	10

要素	出現回数
じしん	114
かみなり	97
だいもんじ	93
おんがえし	89
れいとうビーム	89
のしかかり	83
サイコキネシス	83
すなあらし	81
どくどく	81
すてみタックル	79
はかいこうせん	79
かげぶんしん	77
ずつき	77
でんじほう	76
かえんほうしゃ	75
とっしん	75
かいりき	75
なみのり	75
いわくだき	75
ハイドロポンプ	74

$\lambda=10$

要素	出現回数
サイドン	21
ガルーラ	19
ケンタロス	19
ミルタンク	17
プテラ	17
フォレトス	16
ヤドラン	16
エアームド	16
ラプラス	16
メガニウム	16
ドードリオ	15
ゲンガー	15
フシギバナ	14
カビゴン	14
カイリュー	14
ハッサム	14
スイクン	12
ヤミカラス	12
マンタイン	12
ネイティオ	12

要素	出現回数
じしん	79
おんがえし	76
れいとうビーム	75
どくどく	75
だいもんじ	74
かげぶんしん	74
かみなり	73
のしかかり	73
サイコキネシス	73
スピードスター	73
すてみタックル	72
とっしん	72
はかいこうせん	72
ずつき	72
どろかけ	72
いわくだき	72
すなあらし	71
ロケットずつき	71
ハイドロポンプ	71
ギガドレイン	70

ペナルティ項が大きくなるほど出現回数の偏りが小さくなっていることが確認できます。 $\lambda=0$ では最大出現回数のポケモンはフォレトスでしたが $\lambda=1$ ではガルーラに変わっています。これは、フォレトスよりガルーラのほうが覚える技の種類が多いため、フォレトスを含むパーティ同士よりガルーラを含むパーティ同士のほうが類似度を抑えつつ多く生成できたものと考えられます。 $\lambda=10$ まで大きくすると、分布が平準化されすぎて強さの評価が失われていると考えられます。分布の広がりの必要性は、生成されたパーティ群を用いた行動の強化学習フェーズの要請から来たものであり単体でその有効性を定量評価することは困難です。 $\lambda=1$ の場合に生成されたパーティが定性的に悪くないので、今後はこのパラメータでパーティ生成をすることとします。

今回までで、バトル中の行動選択のために学習した強化学習エージェントのQ関数を用いることで、強いパーティを生成する手法を提案しました。次回は強化学習のハイパーパラメータ調整について書く予定です。