[DL輪読会]Grandmaster level in StarCraft II using multi-agent reinforcement learning

DEEP LEARNING JP [DL Papers] Grandmaster level in StarCraft II using multi-agent reinforcement learning 1 えるエル @learn_learning3 DL輪読会2019/12/13 http://deeplearning.jp/ 1

• http://deeplearning.jp/

書誌情報 ◼ 筆者 • Oriol Vinyals（ML界隈的にはseq2seqとかWaveNetとかの人），その他 David Silverなどによる 総勢40名近くのDeepMindチーム ◼ 掲載 • Nature 575, 350–354 (2019) 2

論文概要 3 ◼ Blizzard Entertainmentが運営するリアルタイムストラテジー(RTS) ゲームStarCraft2のゲームAIであるAlphaStarを開発 ◼ 人間と対戦する場合に公平になるよう仕様変更したAlphaStar (Final)を用い，SC2のオンラインマッチで人間のプレイヤー達と対戦 ◼ 複雑なNNアーキテクチャ，人のプレイデータを用いた教師あり学習， 強化学習，マルチエージェント学習により，SC2最高のプレイヤーで あるグランドマスターと同等のレートに到達

発表の前に ◼ ゲームのドメイン知識がないと理解できない事項が多すぎ，この 会に来てる人の興味分野と大分違うので，面白いかどうか微妙 ◼ 理論的にガチガチな論文かと思ったが，そうでもない ◼ 「Alpha」が付いているだけあって，手法的にはAlphaGo～AlphaZero 辺りのアルゴリズムと近い（最初の教師あり学習，自己対戦，強化 学習等） ◼ 敵対的学習っぽい？（個人的な感想） ◼ ゲーム理論はどこへ行った？ 4

目次 ◼ StarCraft2の基礎知識 ◼ AlphaStar • • • • • • 初代AlphaStarとFinalの違い 学習アーキテクチャ全体 人のプレイデータを用いた教師あり学習 強化学習 マルチエージェント学習と自己対戦 評価，分析 ◼ 所感・その他 5

基礎知識/StarCraft2 6 この辺は以前の輪読会の資料(https://www.slideshare.net/DeepLearningJP2016/dlalphastar)にも 書いてあるので，さらっと解説 ◼ 3つの種族から一つを選び，俯瞰的な視点からリアルタイム（ターン性ではない）に，複数のユ ニットと戦闘手段を駆使して相手と戦うゲーム ◼ プレイヤーはフィールド内の資源を回収し，それをもとに建物，戦闘ユニットを生産し，相手の ユニットと対戦 ◼ プレイ中に同時に見れるのはマップ全体の一部のみで，自分のユニットがいないマップは見る ことができない不完全情報ゲーム

• https://www.slideshare.net/DeepLearningJP2016/dlalphastar

基礎知識/ベンチマークとしてのSC2 ◼ ◼ ◼ ◼ ◼ 7 環境内には複数の操作対称，敵が存在 状態空間，行動空間ともに非常に大きい 不完全情報ゲーム 時間的に一貫した意味のある行動が必要 大きく分けてマクロとマイクロの戦略的要素がある • マクロ：大局的な戦略（建物の建造純順，攻め込むタイミング等） ←AlphaStarはこちら重視 • マイクロ：正確かつ多量の細かいユニット操作 複数の行動主体が存在し，行動や観測も極めて多様，行動主体は不完全な情報しか 得られない，過去の情報を使った効果的な行動が必要という現実世界の性質を StarCraftは反映している

今までのスタークラフトAI 8 ◼ スタークラフトをベンチマークとしたAIはいくつか開発されてきたが， ほとんどはミニゲームでマルチエージェント学習の有効性を示した りする程度にとどまり，フルゲームできるものは少数 ◼ 僕の知る限りだと，2018年に出たTStarBotsという手法が最強で， ゲーム内bot最上位のチートクラス相手にフルゲームで勝利 →少し強いプレイヤーなら最上位botにも簡単に勝てるので，微妙

SC2における強さの評価 9 ◼ オンライン対戦でマッチングを決定するMMR (Match Making Rate)を基準としてプレイヤーの 強さを評価（ただし，グランドマスター以上はあまりMMRを気にしない傾向） ◼ 99.8%のプレイヤーがグランドマスターの次のマスターレベルまでで，グランドマスタークラスの MMRのプレイヤーは上位0.2% →AlphaStarはこの0.2%に到達

AlphaStar（初代）とAlphaStar(Final)の違い 10 ◼ 今年の1月にデモを行ったAlphaStar（初代）と今回の論文で用いら れたAlphaStar（Final）にはいくつかの違いが存在 ◼ 初代をさらに強化してFinalにしたわけではなく，プロのプレイヤー 監修のもと，人間と対戦を行うときに公平になるように学習や行動 に制限をかけて仕様変更 ◼ 特に論文内で言及されている仕様変更は， • 初代ではプロトスという種族にしか対応してなかったが，今回は他の2種族 にも対応 • 入力としてゲームの内部情報を直接受け取るのではなく，人間と同じ視点の カメラインタフェースから入力を得る • コンピュータは人間にはできない高速操作ができてしまうため，これを制限

3体全ての種族で学習 ◼ AlphaStar（Final）では，プロトス以外のザーグ，テランでもメイン エージェントを学習 ◼ 特性は違っても，基本的に同じくらいの強さになるような設定だが， AlphaStarの場合はプロトスが微妙に他より強い ◼ 論文内の分析では結局プロトスのデータをほとんど使っており， DeepMindのプロトスへのこだわりがうかがえる 11

エージェントへの入力の違い AlphaStar（初代）の入力 →学習環境PySC2から得た生データ AlphaStar（Final）の入力 →カメラインタフェースで得た画像 ◼ 人間の視点では本来見えないものが移って いた ◼ 人間がプレイ中に見てる画面とまったく同じ ものを入力として受け取る ◼ 人間の視点と比べて重要な情報が集約され すぎ PySC2から得たFeature Layers 12

行動数(APM)の制限 AlphaStar（初代）の行動数 →制限なし ◼ DeepMind側は，試合中の平均のAPM （Action Per Minute, 一分間の行動数）は人 間と同じくらいと主張していた ◼ 実際には，ユニットの交戦時は，AlphaStar側 が滅茶苦茶なAPMで押し切っていた AlphaStar（Final）の行動数 →Monitoring Layerによる行動数制限導入 ◼ 人間ではありえない行動回数にならないよう， 専用の機構で調整 ◼ DeepMind側としては，マシンパワーのマイク ロ行動ではなく，大局的な戦略で勝てること を主張したい感じ まともなAPM 交戦時に1500 近いAPMをたた き出す 13

人間とAlphaStarのAPM分析 ◼ Finalと人間のゲームでは，全体的に人間の方がAPMが大きくなっている ◼ 平均APM，ゲーム中の最大APM共に人間の方が上 →初代のときとは違い，人間以下の条件でもグランドマスターレベルに到達 14

AlphaStarのエージェント AlphaStarの行動回数を，5秒 で22回（同じ行動の繰り返し は除く）に制限する機構 15 行動の出力．どの種類の行動を, どのユニットに対して，どこに向けて 行うか選択 AlphaStarのニューラルネッ ト本体．次のページで紹介 LSTM, Transformer, ResNet, PointerNetwork 等からなるエージェント本体 カメラインタフェースの画像 から得たユニットその他 諸々の入力

エージェントNNへの入力，行動の詳細 ◼ 今までのDeepな手法のオールスター感 ◼ 入力や出力の特性に合わせて，いろいろな手法を使っているが， 中心となるのは長いSC2ゲームのシーケンスを処理する巨大LSTM コアのLSTM 16

エージェントの入力と出力 入力 17 出力 その他に，方策更新に用いる観測のValue出力も含む ・・・ゲームやってない人からするとあまり気にしないところかも

AlphaStarの学習インフラ 18 ◼ 計算資源：8コアのTPUv3を32個，28コアの CPU150個に相当 ◼ エージェントの学習構造 • • • • Learner: 勾配降下で方策学習するNN本体 Actor: Leanerから受け取った方策で環境から経験収集 Environment: SC2でエージェント同士対戦 Coordinator: エージェント集団の利得行列を保持し， マッチング決定 • Evaluator: 利得行列の補完？（あまりよくわからない） ◼ その他：各Learnerのバッチサイズは512, 1秒間に 50000の経験サンプルを処理，LearnerからActorへの パラメータコピーは10秒ごと 学習時間は上記の計算資源で44日（！！！）

AlphaStarの学習概要 19 1. 人間のプレイデータを用いた教師あり学習 • 971,000個のリプレイデータを仕様 • 入力に対して，NNの出力行動分布が人間のものに近くなるよう学習 AlphaZeroとかでは人間の教師データなしだったのに，AlphaGoの時代に逆戻り？ →StarCraft2は，行動空間が大きすぎるのと，誰がやっても必須な「常識」の型が存在するため 2. 教師あり学習したエージェント同士のマルチエージェントのリーグ戦で 自己対戦+強化学習 • エージェント同士で対戦して強化学習．過去のエージェントのパラメータは凍結しつつ，学習 によるパラメータ更新を行ったエージェントを生成し，過去と最新エージェントが混ざった環 境でマチング • メインの学習エージェントの他に，Main ExploiterやLeague Exploiterと呼ばれる特殊なエー ジェントが存在 • 自己対戦自体は，他のAlpha Zero系と同じだが，AlphaStarはゲーム理論の観点（たぶん） から，戦略の多様性が増すような仕掛けになっている

人間のプレイデータからの教師あり学習 ◼ SC2のリプレイデータを用い，AlphaStarのエージェ ントの出力が人間の行動の分布と近くなるよう教 師あり学習 ◼ AlphaStarと人間の行動分布のKLダイバージェンス をとって最適化 ◼ AlphaStarの方策は𝜋𝜃 (𝑎𝑡 |𝑠𝑡 , 𝑧)で表され，条件付 けのzは人間のデータから得た統計量 20

強化学習 ◼ リーグ戦の中でマッチングしたエージェント同士対戦し，強化 学習を行う ◼ ベースRLアルゴリズムはオフポリシー分散型強化学習の IMPALA（V-trace）と，この論文で提案したSelf Imitation Learningの改良型であるUPGO（Upgoing policy update） ◼ 強化学習による方策更新中も，教師あり学習直後のモデル を用いて，方策蒸留を行う ◼ RL中も人間のデータからの統計量zで条件付けを行う ◼ 報酬 • 対戦結果による報酬𝒓𝑻 ：勝ち負けでプラスorマイナス1 • 疑似報酬𝒓𝒑：人のビルドオーダー(ユニットの生産順序)や あるユニットを建築したかどうかなど，ランダムでサンプル された条件を満たしているかどうかで報酬 • 最終的な報酬は𝑟𝑇 と𝑟𝑇 の合計 21

強化学習/UPGO 22 ◼ 既存の模倣学習アルゴリズムであるSelf Imitation Learningを改良 したアルゴリズム ◼ おさらい：Self Imitation Learning • 過去のエージェントの行動を保存し，学習中の価値推定値よりも，過去の経 験で得た収益の方が高かった場合，その行動を選択するように方策更新 • SILでは以下のようにロスを計算する SILの方策ロス，価値のロス共に， RよりVが大きい場合はR-Vの部 分が0となって ，(1)のロスによる 更新が行われない

強化学習/UPGO ◼ UPGOの方策更新では，方策を以下の方向へ更新 • SILの時は収益Rを使用したが，今回は収益の代わりにGを導入 • Gは，𝑠𝑡+1における行動𝑎𝑡+1 の行動価値が状態価値（Vから派生する行動全 体の価値平均）より高ければ再帰的に求める．そうでなければ，ただの報酬 プラス次の状態価値 • 𝜌𝑡 は，元々V-traceで用いられる重みづけの計数． 23

マルチエージェント学習の前提知識/推移的な ゲームと非推移的なゲーム 24 ◼ 推移的（transitive）ゲーム:プレイヤーA, B, Cがいた場合，AがBに勝利し， BがCに勝利するなら，AはCにも勝利するという条件が満たされるゲーム ◼ 非推移的（non-transitive）ゲーム：プレイヤーA, B, Cがいた場合，AがB に勝利し，BがCに勝利する場合でも，AがCに勝利するという条件が満た されないゲーム．つまり循環があるゲーム（じゃんけんが代表的） スタークラフトは，「基本的に」非推移的なゲームで，ある戦略AがBに勝ち， BがCに勝つ場合でも，そのまま強さの序列がA>B>Cにはならない．従って， ただ単に最新モデルvs直前のモデルの自己対戦を繰り返した場合，昔の 戦略に勝てなくなる可能性 →AlphaStarでは，自己対戦の時に工夫して，過去の複数戦略と自己対戦

マルチエージェント学習 ◼ リーグ全体で多様な戦略を保持し，学習の対象となるメイン エージェントがそれら多くの戦略に勝てるロバストな方策を 得るよう， マルチエージェントのリーグ戦を行う ◼ エージェントの構成 • Main agent： 実際にテストで用いる方策を学習するエージェント．対戦 相手は過去の凍結された方策パラメータのエージェントで，全体の35% をただの自己対戦，50%をPFPS (後で解説)，15%を最新モデルに一切 勝てなくなった過去のエージェントや過去のMain Exploiterと対戦 • League exploiter: リーグ全体の弱みを突くエージェント．全てのエー ジェントに勝利でき，勝率が70%を超えた時点でパラメータを凍結して， リーグ内に放流（上記条件を満たさなかった場合は別の制限時間で凍 結）．たまにパラメータリセット • Main exploiter: Main agentの弱みを突くエージェント．3体のメインエー ジェントに勝ち，勝率が70%を超えたらパラメータを凍結して放流 25

単純な自己対戦の欠点の克服 ◼ じゃんけんのようなゲームでは，グーチョキパーの戦略の種類だけで勝敗が決まるが，スター クラフトでは，戦略の種類が同じでも，強さが違う（例えばユニット量が単純に多いなど） ◼ 自己対戦で循環を避けて強くなろうとした場合，同じ種類の戦略でひたすら強くなり続ける局 所解に陥る可能性 26 →AlphaStarで導入しているExploiterエージェントにより，上記の問題を回避して戦略に多様性 ←たぶんこの図はゲームをしてない人 にはわかりづらい 航空ユニット(Void ray)>装甲ユニット(immortal>軽量 対空ユニット(Stalker)>航空ユニット・・・ という強弱の循環関係がある場合に起こることを 解説している

PFPS (Prioritized Fictionius Self Play) ◼ 仰々しい名前だが，大したことは言っていない ◼ 循環を避けるため，原則AlphaStarのマルチエージェント学習では過去の全てのエー ジェントと自己対戦させたいが，例えば明らかに勝率が高いエージェントなどと戦わ せるのは無駄 →対戦相手のマッチング確率を勝率に合わせて選択 Aを学習対象のエージェント，Cを対戦相手候補全体の集合，Bを対戦相手の候補とした場合，Bとの対 戦確率を以下のように計算 ここで，fは勝率により，マッチング確率を調整する関数で，今回の場合は二種類存在 𝒇𝒉𝒂𝒓𝒅 𝒙 = (𝟏 − 𝒙)𝒑 ：勝率が低い対戦相手とマッチングしやすくなる．例として，勝率が1なら，0となり マッチングしない．0.1とかだと大きくなる．pはでマッチングのランダム度合いを調整 𝒇𝒗𝒂𝒓 (𝒙) = 𝒙(𝟏 − 𝒙)：勝率が半分近い=実力が同じくらいの相手とマッチングしやすくなる．例として勝率 0.1や0.9だと，0.09に，勝率0.5だと0.25で大きくなる 27

分析/エージェントの利得行列 ◼ 青色は行エージェントの列エー ジェントに対する勝利，赤は負け， 白はドロー ◼ 後半のMain agentは過去のエー ジェントの大半に勝利 →推移的で，学習により勝敗が 循環していない 28

分析/構成手法の効果 ◼ AlphaStarに使用されている手法でどれが 効いているのか分析 ◼ APM制限については，制限をゆるくすると， 逆にパフォーマンスが低下する場合あり →エージェントがマイクロ戦略に頼りすぎて， 大局的なマクロ戦略の学習がうまくいかない から 29

分析/AlphaStarの勝敗分布 ◼ 緑はAlphaStarの勝利，赤は負け，青は勝敗から算出したAlphaStar の強さの分布 ◼ グランドマスター級の最上位プレイヤーにはかなり負けている 30

所感 ◼ プレイヤー視点からでも，この論文の条件でグランドマスター級に なれたのは普通にすごい ◼ 1月のデモ時は，明らかに条件が平等ではないとプレイヤーから 結構批判があったので，かなり改善されている ◼ ただ，リプレイでは一部の条件で異常な行動をしたり，奇襲に弱 かったりと，欠点がないわけではない ◼ 再現実装をしたいが，この規模の計算資源は… 31

まとめ/プレイヤー視点から （注）まだプロトスのリプレイしか見てないので，PvXの感想 ◼ 学習データに以上のMMR3500以上のプレイヤーのリプレイしか 使っていないためチーズ（いわゆる奇襲，常識外の戦略）に弱そう →ブロンズ，シルバー周辺はチーズだらけなので，この辺のリプレイ 使った方が奇襲には強くなりそう ◼ リプレイを見たところ，クローク（透明）ユニットへの対応が怪しく， 感知するDetectorがいない状態だと滅茶苦茶な行動をしている ◼ 初代AlphaStarと比べると，ハラス（相手に対する嫌がらせ）を絡め た戦略が中心で，人間のプロに近い 32