今まで私が開発してきたポケモンバトルAIは、モデルフリー強化学習に基づいてバトル中の行動を選択するものでした。
先日まで1vs1バトルでうまくいった強化学習手法を3vs3に拡張する実験をしていたのですが、学習結果がいまいちという問題に苦労しており（忘れないうちに記事を書いておきたいですが）、ゲームAIの実現方法として全く違う手法を試してみようと思い立ちました。
select766.hatenablog.com
- ゲーム木を探索するタイプのゲームAI技術をポケモンバトルに応用したい
- 囲碁でうまくいった「モンテカルロ木探索」を応用したいが、ゲームの性質の違い（同時手番ゲーム）に対応する必要がある
- Lanctotらによる比較的単純な手法を実装したい
- ゲームのシミュレータにおいて、上記手法を実装するために必要な機能が使えることを確認した
モデルフリー強化学習では、現在の状態からある技を選んだ時の勝率を単純に回帰するようなモデルを学習していました。今回からしばらくは、「もし技Aを選んだとき、相手が技Xなら状態s1になって、相手が技Yなら状態s2になって…」というように将来の状態を明示的に考えて最適な行動を選ぶ方法を考えます。ゲームAIの内部でバトル中の状態をノード、行動（技または交代）をエッジとしたゲーム木を考え、その木に対する処理を行うことでどの行動が最適なのか決定します。より具体的には、囲碁で2000年代後半から使われているモンテカルロ木探索に近いものを実現したいと考えています。AlphaGoはモンテカルロ木探索に機械学習ベースの評価関数を組み合わせたものですが、その登場以前の機械学習不要の手法にまずは取り組む予定です。
囲碁とポケモンバトルの大きな違いは、ポケモンバトルが不完全情報ゲームである点です。ポケモンバトルにあって囲碁にない要素として、相手側のパーティ構成が不明であること、全プレイヤーが同時に行動を決定すること（同時手番ゲーム）、プレイヤーの行動が同じでも乱数により結果が変わることがあります。モンテカルロ木探索ベースの手法をポケモンバトルに応用するにあたりこれらの課題に対応する必要があるのですが、最初に問題になるのは同時手番ゲームであるという点です。パーティ構成や乱数は最初は固定してしまえばいいのですが、手番が交互である囲碁の手法そのままだと、先手として扱うプレイヤーの手に応じて後手として扱うプレイヤーは都合のいい手を選べてしまうという仮定を置くことになり非対称性が生じてしまうという問題が生じます。
この点は不完全情報ゲームでのモンテカルロ木探索を扱う"Information Set Monte Carlo Tree Search" (Cowling et al.)でも論じられています。
Under a simple determinization approach, the first player is overly pessimistic (assuming the opponent can observe the chosen move and select the best response to it) while the second player is overly optimistic (assuming the first player’s move is fixed at the point of the second player’s decision, and thus determinizing it randomly)
この問題の対応策についてサーベイした中で、Lanctotらによる比較的単純な手法("Monte Carlo Tree Search for Simultaneous Move Games: A Case Study in the Game of Tron"(Marc Lanctot et al.))がありましたのでまずはそれを試してみたいと考えています。手法説明は次回以降に行います。この手法を実装するうえで課題となるのが、ゲームのルールを実装したシミュレータ上で状態を行ったり来たりする必要がある点です。今までの強化学習の際のシミュレータは、ゲーム開始時点から行動を選んでいって勝敗を得る、という通常のゲームプレイに沿った動作ができれば十分でした。しかしこの手法を含めモンテカルロ木探索系の手法を実装するためには、実際に選択する最適な行動を選ぶために、現在の状態から仮に行動Aをとった場合の次の状態や、仮に行動Bをとった場合の次の状態など複数の将来の状態を生成する必要があります。このために最低限必要なシミュレータの機能は、ゲームの状態をコピーする機能です。実際のゲームの状態を変化させることなく、そのコピーに対して様々な行動パターンを試したうえで最善の行動を選び、実際のゲームはその行動によって進めるという流れになります。
実装方法の概略を述べます。
完全なコードはリンク先をご覧ください。Pokemon Showdownでシミュレータの状態を復元するテスト ライブラリバージョン4cecf1117 · GitHub
従来実験に使用していたポケモンバトルシミュレータPokémon-Showdownで状態のコピー機能があるか探したところ、シリアライズ機能を用いることで実現可能なことがわかりました。Pokémon-ShowdownはTypeScript(JavaScriptに型定義を付与した言語)で実装されています。
以下のようにBattleクラスのメソッドを使うことで、現在のバトルの状態をコピーできます。乱数のシードを含めた内部状態のコピーが可能です。関数オブジェクト等も含まれていないため、JSON.stringify()を使って文字列化し、ファイルに保存することも可能です。（2020-12-12修正：ディープコピーライブラリを使用）
const clone = require('rfdc')();
const serialized = clone(battle.toJSON());
const copied = Battle.fromJSON(serialized);
rfdcはオブジェクトのディープコピーを行うライブラリです。ディープコピーしないと、コピー元とコピー先でBattleオブジェクト内の配列が共有されてしまい問題があります。JSON.parse(JSON.stringify(obj))でも実装可能ですが、実行回数が非常に多いため速度ベンチマークを参照し、高速なライブラリを選びました。
JavaScriptのディープコピー速さ比較 〜7つの手法/ライブラリを比べてみた〜 - Qiita
また、従来はシミュレータ本体であるBattleクラスをラップして文字列入出力によりゲームを進めることができるBattleStreamクラスを使い、この入出力をpythonで実装したエージェントへプロセス間通信で接続する実装を用いていました。しかしこの手段のままでは状態のコピーが使えないので、自前のコードでBattleクラスを直接制御するようにしました。特に難しい点はなく、むしろ文字列のパースなどが不要になりシンプルになったといえます。従来エージェント部分はpythonで実装していましたが、しばらくニューラルネットワークは使用しないため、プロセス間通信が不要となるようTypeScriptのみで実装してみることにします。モンテカルロ木探索では一度の行動選択のためにシミュレータを膨大な回数呼び出す必要があるため、プロセス間通信がボトルネックになる可能性があると考えたためです。
まずはシミュレータの操作方法確認を兼ねて、ランダムプレイヤーとレーティングバトルの機構をTypeScriptで実装しました。コードはリンク先を参照ください。
pokeai/ratingBattle.ts at 6e5369b78cac3c7f81487874d7b22b723fc5c105 · select766/pokeai · GitHub
AI間での強さの比較の簡単な例として、ランダムプレイヤーが技と交代を選ぶ比率を変えた場合を実験できるようにしました。技と交代の両方が選べる場面において、まず技か交代のどちらかを設定された確率により選択し、技の場合は技の候補から等確率に選択、交代の場合は交代先の候補から等確率に選択するという仕様です。ランダムに生成した(ポケモン3匹からなる)パーティ1,000個に対し、交代選択確率0%, 10%, 50%の3種類のエージェントを組み合わせて3000個のプレイヤーを生成し、これらを相互に対戦させてレートを得ました。
レート最上位、最下位プレイヤーを5個ずつ示します。
---
レート: 1974
交代確率0%
レアコイル ['とっしん', 'どくどく', '１０まんボルト', 'かげぶんしん']
エンテイ ['はかいこうせん', 'ふみつけ', 'かえんほうしゃ', 'かげぶんしん']
ゴローニャ ['どろかけ', 'どくどく', 'ほのおのパンチ', 'ばくれつパンチ']
---
レート:1949
交代確率0%
サンダー ['どろかけ', 'そらをとぶ', '１０まんボルト', 'スピードスター']
シャワーズ ['バブルこうせん', 'ずつき', 'なみのり', 'ロケットずつき']
レアコイル ['はかいこうせん', 'かみなり', '１０まんボルト', 'とっしん']
---
レート: 1936
交代確率10%
カイリュー ['だいもんじ', 'かえんほうしゃ', 'スピードスター', 'おんがえし']
ドククラゲ ['ロケットずつき', 'おんがえし', 'ギガドレイン', 'どくどく']
ゲンガー ['かみなりパンチ', 'はかいこうせん', '１０まんボルト', 'でんじほう']
---
レート: 1935
交代確率10%
ベトベトン ['かみなりパンチ', 'どろかけ', 'どくどく', 'はかいこうせん']
ゲンガー ['ナイトヘッド', 'ロケットずつき', 'ばくれつパンチ', 'おんがえし']
バンギラス ['ずつき', 'だいもんじ', 'れいとうビーム', 'ほのおのパンチ']
---
レート: 1934
交代確率0%
ライチュウ ['かみなり', 'ころがる', '１０まんボルト', 'なみのり']
ゲンガー ['ギガドレイン', 'おんがえし', 'ずつき', 'でんじほう']
カイロス ['いあいぎり', 'のしかかり', 'どくどく', 'とっしん']
---
レート: 958
交代確率50%
フシギバナ ['かげぶんしん', 'どろかけ', 'いあいぎり', 'とっしん']
ヨルノズク ['はがねのつばさ', 'スピードスター', 'どくどく', 'かげぶんしん']
ラッタ ['かみなり', 'ふぶき', 'すてみタックル', 'いわくだき']
---
レート: 986
交代確率50%
バタフリー ['かげぶんしん', 'どくのこな', 'はかいこうせん', 'ギガドレイン']
ギャラドス ['すなあらし', 'ロケットずつき', 'かげぶんしん', 'ふぶき']
アリアドス ['ギガドレイン', 'ナイトヘッド', 'サイケこうせん', 'サイコキネシス']
---
レート: 1000
交代確率50%
カイロス ['ずつき', 'いあいぎり', 'かげぶんしん', 'とっしん']
デリバード ['どくどく', 'スピードスター', 'ずつき', 'かげぶんしん']
デンリュウ ['スピードスター', 'いわくだき', 'とっしん', 'でんじほう']
---
レート: 1002
交代確率50%
ウツボット ['どくのこな', 'ソーラービーム', 'はかいこうせん', 'のしかかり']
トゲチック ['いわくだき', 'かげぶんしん', 'どくどく', 'はがねのつばさ']
エンテイ ['かいりき', 'すなあらし', 'どくどく', 'どろかけ']
---
レート: 1028
交代確率50%
ニョロボン ['たきのぼり', 'れいとうパンチ', 'おんがえし', 'バブルこうせん']
ツボツボ ['かいりき', 'かげぶんしん', 'いわくだき', 'どろかけ']
アーボック ['のしかかり', 'ロケットずつき', 'はかいこうせん', 'かげぶんしん']
レート上位プレイヤーは比較的良い技を覚えているパーティおよび交代確率0%,10%のエージェントの組み合わせになっています。最下位は交代確率50%のエージェントが並んでいます。
各エージェントを用いたプレイヤーの平均レートを算出しました。
| エージェント |
平均レート |
| 交代確率0% |
1631 |
| 交代確率10% |
1570 |
| 交代確率50% |
1297 |
相手との相性などを考慮せずランダムに交代するのは実質的にパスと同じなので、交代はできるだけ選ばないほうがいいという当たり前の結果が得られたといえます。
気づいた点として、シミュレータの計算がかなり遅いです。ランダムプレイヤー同士の対戦1回に20~30ms程度かかります。モンテカルロ木探索ベースの手法では1回の行動を決めるのに百回以上のシミュレーション（現在の状態からゲームの決着がつくまでの試行）が必要なので、ごく弱いエージェントでも数秒かかってしまいそうです。ポケモンバトルはもともと8bitCPUのゲームボーイで実装されており、（メッセージ表示に数秒かかるので正確なことはわかりませんが）1ターンの計算は0.1秒もかかっていないはずです。その1万倍オーダーの性能がある現代のCPUで計算しているにしては遅すぎると思われます。アルゴリズムの実装ができたとして、計算時間をかければかけるほど強くなるという状況であれば速度を重視したシミュレータを自作することが大事になってくるかもしれません。
次は、モンテカルロ木探索の実装に着手したいと思います。
