【ポケモンAI】モンテカルロ法で"後悔"を学習する
たとえば次の2体のポケモンが1vs1でタイマン勝負をするとする。
ローブシン Lv.100 @くろおび
てつのこぶし
しんちょう
H252 D252 S4
・れいとうパンチ
・こらえる
ビーストブースト
いじっぱり
A252 S252 D4
・とんぼ返り
・どくづき
ローブシン側にはどのターンでどの技を打つかという戦略が存在する。
これをコンピュータで計算するには？？という記事。
結果だけ見る場合は下までスクロールしてください。
後悔(Regret)とは
ゲーム理論での用語になります。
参考文献[1]で紹介されている簡単な例だけ紹介したい。
(設定)
AくんとBくんがじゃんけんを連続でプレイする。
Aくんは勝ったら+1、負けたら-1点の得点がもらえ、得点が多いほど嬉しい。
～1戦目～
Aくん: グー、Bくん: パー
Aくんの負け (-1 点)
Aくんはこの試合を振り返って、
「チョキを出していたら勝っていたのになあ…」 とチョキを出さなかったことを激しく"後悔"した。一方でパーに対しては
「パーを出していたらあいこには持ち込めたなあ…」と少しだけ"後悔"した。
グーは実際に出している手なので後悔しなかった。
Aくんは「次はなるべくチョキを出そう」と決心した。
～2戦目～
Aくん: チョキ、Bくん: グー
Aくんの負け (-1 点)
Aくんは前の反省を生かしてチョキを出したが、相手の手が変わったのでまた負けてしまった。この試合を振り返って
「パーを出していったら勝っていたのになあ…」と激しく後悔し、
「グーを出していたらあいこだったなあ…」と少しだけ後悔した。
そして、「1戦目の結果と総合すると、パーを出しておけばあまり後悔しなさそうだ」と推理した。
注) 理想プレイヤーのじゃんけんではこのように計算しても結局グー・チョキ・パーを1/3ずつ出す戦略に落ち着きます。ただ、Bくんに「グーを出すのが好き」などのクセがある場合、そのクセに対応した非対称な戦略が求まるはずです。
説明:
戦略型ゲームの結果から「その行動を取っていたら改善できた利得の量」を後悔(regret)と定義し、
(その行動を取っていた場合の利得) - (実際の利得) でそれぞれ計算する。
この"後悔"を使って、以下の繰り返し計算で最適な混合戦略※1を求めることができる。
・均等な行動確率を初期値に設定
・後悔を0に設定
・行動確率にしたがってゲームを実行
・ゲーム結果から各行動の後悔を積算
・後悔に比例する行動確率を再計算※2
・行動確率にしたがってゲームを実行
・ゲーム結果から各行動の後悔を積算
… 繰り返し
さらに、上のゲームではAくんのみがこの方法を使用していたが、両プレイヤーが同時にこの繰り返し計算を行うと、最終的な戦略がナッシュ均衡(※3)に収束する と証明されている。Regret Matchingという。
※1 確率的に行動を決定する戦略。(例) グーを1/3の確率で出し、チョキを2/3の確率で出す
※2 たとえば下の表の結果では
1戦目終了時に(グー, チョキ, パー) = (0, 2/3, 1/3)、
2戦目終了時に(グー, チョキ, パー) = (1/6, 2/6, 3/6)
と更新される。
※3 お互いに相手の(混合)戦略がわかっていても、自分の戦略(の利得の期待値)を改善する余地が存在しない状態。
実際には最後に更新された行動確率ではなく、各繰り返し中で使用した行動確率の平均(→平均戦略)を最終的な戦略とする。
しかし、ポケモンのようにターン経過があり、終了までのターン数も行動結果によって異なるゲームの場合はどうすればいいだろうか？
そのような一般的な不完全情報ゲームに適用できる手法が、CFR(Counterfactual Regret)である。
正確な情報は参考文献[2]を参照されたい。
プログラムでの実装はこちらのブログと
こちらのリポジトリが参考になった。
終端ノードの利得を到達確率で減衰させながら前方ノードに伝搬させたりしている。ちょっと機械学習っぽさがある。
ゲームの結果を振り返って、「あそこはあの行動を取ってたら有利だったな」と後悔し続ける手法であることは変わりない。
上記のRegret Matchingをポケモン対戦に適用しようとしたとき、いくつか困ることがある。
(1) 特定の局面で行動を変えたときのゲームの結果は、同じ相手(の戦略)と同じ局面を再現できないとわからない。そしてこれは以下の理由で難しい。
- 普通の対戦相手なら、毎回同じ戦略で行動してくれる保証はない
- 技外し・追加効果・ダメージなどの確率的要素をすべて同一に再現するのは難しい
(2) 行動を変えたときのゲームの結果には確率的要素・非公開情報により膨大な分岐がある。
- これはゲームの情報集合※4の多さに由来している。言い換えると以下のようなゲーム木を完璧に作成できて、それぞれの終端の評価値を全部埋められれば理想。しかし、相手の持ち物、持っている技、特性、、、など想定しうるゲームの局面をすべてあらかじめ列挙しておくというのはほぼ不可能なので、現実的ではない。
そのため、実際には「とりあえずゲームをプレイしてみて、分かってる範囲の情報でCFRを行う」手法が必要であるが、そのときに用いられるのがモンテカルロ法である。(モンテカルロCFRと呼ばれる。)
説明は割愛するが、今回は参考文献[3]の中のOutcome Samplingというやつを使った。
※4 ゲーム理論で不完全情報ゲームを取り扱うとき、確率的な要素(プレイヤーに隠されている相手の情報も含む)はChanceプレイヤーという仮想的なプレイヤーの選択の結果として表現する。こうすると、プレイヤーからは区別できない複数のノードがゲーム木上に存在することになり、これをグループ化したものを情報集合と呼ぶ。この定義より、同じ情報集合に属するノードでは同じ行動を選択しなければならない。
poke_env
showdownクライアントとしてのWebsocket実装を強化学習用にラップしたようなもので、基本はローカルでshowdownサーバーを建てて一緒に使う。
ゲームの状態と勝敗からとりあえずディープラーニングする感じの強化学習ならすぐできます。うまく学習できた人が居るのかは知りません。
ゲーム理論的なパラメータはいくつか欠けていたので独自にサブクラスを作って頑張っているのだが、可能性を感じるライブラリなので、余力があったら別記事で紹介したい。
やったこと
冒頭に出したローブシンvsフェローチェ対面の後悔を計算してみた。
シミュレーション対戦のルール設定など
(Pokemon Showdownの[Gen 8 1v1]ルールを使用)
・第8世代環境
・1vs1シングルバトル
・ダイマックスは禁止
・お互いレベル100
CFRアルゴリズムの設定
・ローブシン側プレイヤーのみ後悔・戦略の更新を行う
・探索率=0.4 として、各ターンで40%の確率でランダム戦略を使用する
・1000回の繰り返し
・情報集合はshowdownサーバーから送られてくる対戦メッセージをそのまま使用する※
※ showdownサーバーからは以下のメッセージが各ターンに送られてくるが、これにはそのターンでの各プレイヤーの行動・行動結果としてプレイヤーに見えるゲームの状態がすべて含まれているので、これを蓄積したものをそのまま情報集合として利用できる(今のところは、一致判定さえできればいいので)
ただし、ダメージ乱数によるHPの増減で情報集合がいちいち分かれると学習効率が悪いので、HP表記の部分(自ポケは絶対値表示、相手ポケは%表示)だけ0/6 ~ 6/6 までの簡易的な割合表記に置き換えている
|move|p2a: Swampert|Power-Up Punch|p1a: Conkeldurr
|-damage|p1a: Conkeldurr|372/414 5/6
|-boost|p2a: Swampert|atk|1
|move|p1a: Conkeldurr|Hammer Arm|p2a: Swampert
|-damage|p2a: Swampert|50/100 3/6
|-unboost|p1a: Conkeldurr|spe|1
ダメージ計算など
結果の理解のためにダメージ計算を載せておきましょう。
※レベル100なので普段のダメージ感覚とは違うかもしれません
・アームハンマー 78.4 ~ 92.2 %
・れいとうパンチ 78.4 ~92.6 %
・マッハパンチ 31.4 ~ 37.1 %
・とびひざげり 61.6 ~ 72.5 %
結果(後悔に基づいた最終的な最適戦略)
局面1: 初手
予想: アムハンかれいパン
結果:
・明らかに悪手なマッパとこらえるは早々に選択確率が0になっている
・ダメージ量がほぼ同じなアムハンとれいパンはどっちがいいか迷い続けている。
局面2: 以下の行動の後の2ターン目
予想: 1回こらえても悪くはないが、マッパでいい
結果: きれいにマッパを選択している。
局面3: 以下の行動の後の2ターン目
予想: マッパで普通に落とせるが、ローブシンのHPはまだ満タン(飛び膝1回耐える)なので別にこらえる以外ならなんでもいい
結果:
・マッパ。
局面4: 以下の行動からの2ターン目
予想: マッパ1択
結果:
・れいパンになっているが、うまく計算されていない
・グラフの変化点が少ないため、試行回数が少なかった(この局面があまり発生しなかった)模様。
・ここを計算するには探索率を考慮する必要あり
まとめ
・だいたいうまく計算できている
・違いが分かりづらい技や、あまり発生しない局面は試行回数が足りなくなりがち(探索率の設定の難しさ)
次回(予定)
相手の戦略も変化させる(本来のCFR)と本当にナッシュ均衡に収束するか？
募集
おもしろい対面
参考文献
[1] Neller, Todd W., and Marc Lanctot. "An introduction to counterfactual regret minimization." Proceedings of Model AI Assignments, The Fourth Symposium on Educational Advances in Artificial Intelligence (EAAI-2013). Vol. 11. 2013.
[2] Zinkevich, Martin, et al. "Regret minimization in games with incomplete information." Advances in neural information processing systems. 2008.
[3] Lanctot, Marc, et al. "Monte Carlo sampling for regret minimization in extensive games." Advances in neural information processing systems 22 (2009): 1078-1086.
