ゲーム木探索を用いたポケモンバトルAIの最も単純なアルゴリズムとして、原始モンテカルロ法を試します。 前回から長らく期間が空いてしまいましたが、再開していきます。
アルゴリズム
ここでは原始モンテカルロ法(pure Monte Carlo search)を試します。
原始モンテカルロ法は、現在の局面からランダムに手を選んで1ターン局面を進め、そこからプレイアウトするという処理を何度も行います。そして、現在の局面で選べる手のうちで勝率が最も高かった選択肢を選ぶ手法です。プレイアウトとは、ランダムに選択肢を選んでゲームの決着がつくまで局面を進めることです。ポケモンでは相手も同時に手を選ぶことになりますが、相手の手はプレイアウトの一部として、ランダムに決めることにします。 なおこの手法の重要な注意点として、相手のパーティ構成がわかっているという仮定が入ります。探索中に、相手の行動をランダムに選んでバトルを進めて勝敗を得るというステップが入っているためです。探索過程で具体的な選択肢を列挙せずランダムに選ぶというブラックボックス状態であっても、例えば相手が一撃必殺技を持っているかどうかによって、こちらが積み技を使う選択肢と攻撃技で目の前の相手をすぐ倒そうとする選択肢の勝率が変わると考えられます。当面はこの仮定が入った状態のアルゴリズムを考えることとなります。
実際のコードからコア部分をコメント付きで掲載します。
export class AIMC extends AIBase { playoutCount: number; // 行動決定のためのプレイアウト回数 // 局面を受け取り、最適な手を返す関数 go(sim: Sim /* 現在局面を表すシミュレータ */, sideid: SideID /* 自分がプレイヤー1か2か */): string | null /* 最適な手 */ { const choices = this.enumChoices(sim.getRequest(sideid)); // 選択肢を列挙(技1, 技2, ...) const playoutPolicy = new AIRandom2(); // プレイアウト中の行動決定ポリシー(ここではランダム) if (choices.length > 0) { const playoutPerAction = Math.floor(this.playoutCount / choices.length); // 1つの選択肢に割り当てるプレイアウトの回数を、単純に全プレイアウト回数を選択肢の数で割って定める const winCounts = (new Array(choices.length)).fill(0); // 各選択肢を選んだあとの勝利回数を入れる配列 for (let c = 0; c < choices.length; c++) { // 各選択肢ごとにループ for (let i = 0; i < playoutPerAction; i++) { // 選択肢1つに対する複数回のプレイアウト const copySim = sim.clone(); // シミュレータをコピーし、実際の状態を動かさずに思考できるようにする const opponentChoice = playoutPolicy.go(copySim, invSideID(sideid)); // 相手の行動をランダムに決める const bothChoice = sideid === 'p1' ? [choices[c].key, opponentChoice] : [opponentChoice, choices[c].key]; copySim.choose(bothChoice); // 1ターン進める const { winner } = playout(copySim, [playoutPolicy, playoutPolicy]); // プレイアウトして勝者を決める if (winner === sideid) { winCounts[c]++; // 自分が勝った回数を集計 } } } // 勝利回数最大の選択肢を、探索結果として返す const bestIdx = argsort(winCounts)[winCounts.length - 1]; return choices[bestIdx].key; } else { return null; } } }
実験
実験条件
プレイアウト回数(コード中playoutCount)を変えて強さを比較します。プレイアウト回数10, 30, 100, 300, 1000およびランダムに行動を選ぶアルゴリズムで合計6種類のポリシーを比較します。各ポリシーが10個のパーティを操作し、合計60プレイヤーでレーティングバトルを行います。各プレイヤーのレートをポリシーごとに平均してポリシーの強さとします。
プレイアウト中に使用する行動決定関数AIRandom2では、交代を選択する確率を10%に設定しました。
1プレイヤー当たり10回の対戦を行いました。
実験結果
実験結果を示します。
| プレイアウト回数 | 平均レート |
|---|---|
| ランダム | 1451 |
| 10 | 1415 |
| 30 | 1485 |
| 100 | 1507 |
| 300 | 1564 |
| 1000 | 1577 |
プレイアウト回数が増加するほど強くなることがわかりました。プレイアウト回数10の場合はランダムに行動するより弱いという結果になっています。この原因を考察します。ランダムの場合は交代確率を10%に設定しているのに対し、プレイアウトを行う場合は技を出す場合も交代する場合も選択肢として平等に扱っています。各選択肢を選んだ場合のプレイアウトの試行回数が少なすぎて選択肢の良し悪しがうまく推定できない（技の命中や相手の技選択に強く依存する）ため、効果の低い交代を選ぶ確率が上がっているのではないかと考えられます。
行動選択の考察
いくつかの実例をもとに、各行動の勝率がどのように見積もられたかを考察します。
下の例では、p2(プレイヤー2)がプレイアウト1000回の強いプレイヤーです(p1は10回)。技名の下および控えポケモン名の右の数値がプレイアウトにより得られた勝率を表します。この例では、おんがえしが勝率0.96で最も高く、探索結果として選ばれています。ばくれつパンチでも倒せるのは同じですが命中率が低いデメリットが勝率に反映されています。
下の例では、p1とp2両方がプレイアウト1000回のプレイヤーです。双方残りポケモン1体です。カビゴンのHPがほとんど減らず、ケンタロスのHPが減ることで勝率が変化していくことがわかります。ところで、ケンタロスのつのドリル（一撃必殺技）の最終ターンでの勝率が0.12となっています。命中率は30%なので勝率0.3になってほしいところですが、そうなっていません。これはシミュレータの乱数がバトル開始時に決定しており、同じ行動を選択すれば同じ結果になる仕様となっているためです。シミュレータの乱数の内部状態では、このターンでつのドリルを選択したら外れることになっているものと推測されます。この仕様もまた、技が当たるか当たらないかという乱数が間接的に探索アルゴリズムに漏れているということになります。
下の例では、p1とp2両方がプレイアウト1000回のプレイヤーです。双方ポケモン3体が生き残っている状態です。ブラッキーは体力満タンで無意味なねむるを選択してしまっています。バトルの決着がつくまでのターン数が多く、このターン以後の行動選択はすべてランダムであるためミスが生じる確率が高いので、ここで無駄な行動をしたとしてもあまり影響がないというのがこの選択の原因であると考えられます。
以上のように、バトル終盤であればある程度適切な行動選択ができていますが、序盤ではうまくいっていないということが確認できました。 次回は、より高度な探索手法を試そうと考えています。
