[DL輪読会]AlphaStarとその関連技術

DEEP LEARNING JP [DL Papers] AlphaStarとその関連技術 @learn_learning3 DL輪読会2019/05/28 http://deeplearning.jp/ 1

• http://deeplearning.jp/

本発表について 2  1月に発表されたDeepMindのAlphaStarについて，強化学習とStarCraft2を やっている人間の視点から，公開情報を元にした技術的詳細，関連論文に ついて解説します  AlphaStar本体の論文は発表されていないので，予習的な内容の発表です  結構詰め込みましたが適度に飛ばしながらの発表になると思います 情報源は以下の通り DeepMind公式ブログ：https://deepmind.com/blog/alphastar-mastering-real-time-strategy-game-starcraft-ii/ RedditでのAlphaStarチームの質問回答： https://www.reddit.com/r/MachineLearning/comments/ajgzoc/we_are_oriol_vinyals_and_david_silver_from/ YouTubeでのDeepMind公式配信：https://www.youtube.com/watch?v=cUTMhmVh1qs&t=7760s Lex Fridman×Oriol Vinyalsのインタビュー動画：https://www.youtube.com/watch?v=Kedt2or9xlo Demis HasabbisによるMITでの講演：https://www.youtube.com/watch?v=3N9phq_yZP0 David SilverによるCambridge大学での授業:https://sms.cam.ac.uk/media/2932533 【発表者Twitter】 えるエル @learn_learning3 https://twitter.com/learn_learning3 以前，”強化学習における好奇心”というサーベイ 資料を公開したので，よければそちらも… https://speakerdeck.com/learn_learning3/qiang-hua-xue-xi-niokeruhao-qi-xin

• https://deepmind.com/blog/alphastar-mastering-real-time-strategy-game-starcraft-ii/
• https://www.reddit.com/r/MachineLearning/comments/ajgzoc/we_are_oriol_vinyals_and_david_silver_from/
• https://www.youtube.com/watch?v=cUTMhmVh1qs&t=7760s
• https://www.youtube.com/watch?v=Kedt2or9xlo
• https://www.youtube.com/watch?v=3N9phq_yZP0
• https://sms.cam.ac.uk/media/2932533
• https://speakerdeck.com/learn_learning3/qiang-hua-xue-xi-niokeruhao-qi-xin
• https://twitter.com/learn_learning3

関連する手法・論文 以下がAlphaStarの関連手法・論文 （有名な手法，手法名が論文名そのままのものは論文記載を割愛）  学習するニューラルネットのアーキテクチャ • • • •  ResNet Transformer LSTM Pointer Networks 方策学習アルゴリズム • IMPALA 論文：IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures • Self Imitation Learning • Policy Distillation • Counterfactual Multi-Agent Policy Gradients(COMA)  マルチエージェント学習 • FTW(For The Win) agent 論文：Human-level performance in first-person multiplayer games with population-based deep reinforcement learning • PSRO(Policy-Space Response Oracles） 論文：A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning • Nash Distribution 論文：Re-evaluating Evaluation 3

目次     AlphaStarの概要 StarCraft2について PySC2 AlphaStarの使用技術 • NNアーキテクチャ • 方策学習 • マルチエージェント学習  SC2プレイヤーの視点から見たAlphaStar  余談/OpenAI Five 4

AlphaStarの登場  2019年1月24日にDeepMindが生放送で，RTSゲーム「StarCraft2」で プロ級のプレイヤーを打倒可能なAIとして公開  SC2はAlphaGo系統が取り組んできた囲碁，将棋などのゲームと違 い，ゲームがリアルタイム進行，不完全情報，極めて広大な行動 空間を持つなどの特徴があり，人間のプロ打倒はかなりの ブレークスルー 開発者のOriol VinyalsとDavid Silver 5

AlphaStar/その強さ  SC2のプレイヤーで，世界最強レベルの「グランドマスター」と呼ば れる称号を持つ二人，Team LiquidのスタープレイヤーであるTLO， MaNaと計10回対戦し全勝  今までも，SC2を対象としたBotなどが存在したが、世界レベルの プロに勝つのは初 TLO MaNa 6

AlphaStar/ざっくりとした説明 7  SC2をプレイするエージェントとなるニューラルネットワークを用意し， マルチエージェント設定の強化学習を行う  エージェントはLSTM，Transformer，ResNetなど，様々な手法を組み 合わせたアーキテクチャで学習を行う  エージェントは最初に人間のSC2プレイデータから模倣学習を行う  模倣学習後のエージェントから分岐したエージェント同士が自己対 戦するAlphaStar Leagueを行い，多様な学習環境からSC2のプロに 対抗可能なエージェントを生み出す

StarCraft2  Brizzard Enterainmentが開発したPCゲーム  RTS(Real-time Strategy)というゲームジャンルに属するゲームで，プレイヤー がゲームに関する全ての情報を観測できない不完全情報ゲーム  RTSの特徴 • ゲームがリアルタイムで進行（ポケモンやドラクエのようなターン制ではない） • プレイヤーは第三者視点（俯瞰的視点）からステージ全体を見渡し，複数の戦闘手段を駆使して対戦 8

SC2対戦の流れ 9  一般的には２プレイヤーによる１対１の戦争ゲーム  プレイヤーは３つの種族から一つを選んで対戦する．各種族にはユニットの技 や特性に大きな違いあり  極端な言い方をすれば，たくさん資源を集めて，素早く凄い建物を作って， その建物から強いユニットを生み出して，敵地に攻め込むゲーム プロトス 超テクノロジーを持つ超知的生命体 DeepMindのお気に入り ザーグ 進化した寄生生命体 テラン 遺伝子操作，人体改造を行った人類の 末裔

StarCraft2/対戦画面 基ス 本ク 的リ にー こン の｜ 画プ 面レ をイ 見ヤ なー がが ら注 プ目 レし イて い る エ リ ア ミニマップ：対戦フィールド全体の地形図．自分 のユニットがいない部分は詳細を見れない 10 獲 得 資 源 数 ， ユ ニ ッ ト 生 産 数 プレイヤーが選択可能な行動．現在選択している ユニットのスキルや建造可能物が表示される

SC2の要素  資源 建造物やユニットの製造の源となる．ミネラルとガスが存在する．これをワーカーと呼ばれる小型ユニットで マップから採取し，消費することで建造物やユニットを作成  建物 ユニットを生み出したり，ユニット能力の研究を行う施設．ミネラルを消費して作成され，一度作れば壊される までは稼働を続ける．建物建造には順番があり，下位の建物建造後でなければ上位の建物は建造不可  ユニット SC2の対戦で，実際に戦闘を行う兵士，戦車，戦闘機，超生物など．特定の建造物からミネラルとガスを消費 して生み出される．上位の建造物からは上位のユニットが作成可能 11

建物の建造順 12 上位の建物からは強いユニットを生み出せるが，上位の建物を作るためには下位の建物作成の 条件がある (例)プロトスの場合 Cybernetics Core建造後に解 禁．中～大型の空中ユニッ トを建造できるようになる． 大型空中ユニットの建造の ためには，他の研究施設の 建造が必要 Stargate Gateway 最初から建造できる生 産施設．小型の地上戦 力を建造可能 Cybernetics Core建造後に解 禁．研究を行うことでユニッ トの強化ができる他，建造す るだけで，Stargateの大型ユ ニットが解禁 Cybernetics Core Gateway建造後に建造可能． この施設がないと上位施設 が建造できない．ユニット生 産はできないが，ユニット強 化の研究可能 Fleat Beacon

テックツリー 13 建物がグレードアップすると，生み出されるユニットも強くなる．生産に特殊な条件 が必要なものも Void Ray 生産 かなり強いプロトスの主 力空中ユニット．空中か ら強力なレーザー攻撃 を行う Stargate 生産 Gateway 生 産 Cybernetics Core Fleat Beacon Zealot プロトスの基本歩兵 敵に近づいて直接攻撃 するのみ Carrier SC2最強の強さを誇る大型空中ユニット．複数の小型戦闘機を 艦内に持ち，それらを射出して攻撃

MMR(Match Making Rating)  プレイヤーの強さに応じて割り当てられる数字で，オンライン対戦時のマッチ ングで使用される  5000ちょっとより上がグランドマスターという最上位の称号を持つTLOは6549， MaNaは7468で，グランドマスターでも相当に強い，世界最強レベルのプレイ ヤー(ASとの対戦ではTLOは得意種族を使用しなかったので，もう少し低い) 14

PySC2  DeepMindが開発した，PythonでSC2のAPIを叩けるSC2の機械学習 環境  AlphaStarはこの環境からSC2のデータを直接取得して学習・対戦 している （つまりプレイヤーと違って画面を見ながらのプレイではない） 論文： ”StarCraft II: A New Challenge for Reinforcement Learning” https://arxiv.org/pdf/1708.04782.pdf GitHub: https://github.com/deepmind/pysc2 15

• https://arxiv.org/pdf/1708.04782.pdf
• https://github.com/deepmind/pysc2

Feature Layers  PySC2経由で受け取れる，SC2内のゲーム要素集  通常のSC2のゲーム画面を抽象化した画像のみならず，画面内のユニットの HP，敵味方の区別，ユニットタイプなどを取得可 16

AlphaStar League  模倣学習後のエージェントから分岐増殖させつつエージェント(リーグ内では Competitorと呼ばれる)同士で対戦・強化学習を行う  各イテレーションで，エージェントを元に別のエージェントがLeague内に追加 され,多様性向上のため，過去のエージェントも方策更新を凍結して残す 17

技術的な話・関連論文紹介

模倣学習  SC2では，特に前半はほぼ必須な戦略（自分のベースの基地にワーカーで資源収集）が存在  エージェントは膨大な探索空間でランダム探索すると，常識外の行動をしてしまう（前半から ワーカーがバラバラに散ってしまう）  この辺の「常識」や，ある程度確立された戦略を学ぶため，SC2プレイヤーのプレイデータを 用いて模倣学習（アルゴリズムは明言されていない）  模倣学習だけで、大体ゴールド～ダイヤモンド（中級者）相当に到達可能 19

AlphaStar League/もう少し詳しく  各イテレーションで，エージェントを元に 分岐した別のエージェント がLeague内に追加され,多様性向上のため，過去のエージェントも 方策更新を凍結して残す  各エージェントはAlphaStar League内で個別の目的をもっており， これによる多様性を生み出している  AlphaStar League内では，SC2の強化学習によるエージェントのパラ メータ更新だけでなく，ハイパーパラメータ，対戦のマッチング確率 なども更新されていく  14日間AlphaStar Leagueを続けた後，後述の評価基準に従い， 人間のプロプレイヤーと戦うエージェント決定 20

AlphaStarエージェントの 学習アーキテクチャ MITでのHsabbisの講演のスライドから 21

Observations 22  Spatial 先ほど説明したfeature layres．どのlayerを使用しているかは不明だが， 普通に考えれば全部使用  Economy 自軍の資源、手持ちユニットの充実度を指す．少し曖昧な表現なので 具体的に何を入力しているか不明  Units これまでに作成したユニットをリスト形式で渡している（はず）

Networks  ResNet 画像処理最強だからとりあえずResNetを使用している感じ（特に ResNetである必要はないはず）．feature layersを入力  Feed Forward 具体的なアーキテクチャは不明．Economyから特徴抽出をしていると 思われる  Transformer 系列情報の処理を行う．ここでは,SC2ユニットを要素としたリストを入 力とし， ユニットの生産順を考慮した埋め込みを行っている 23

Core:Deep LSTM Core 24  複数のLSTMブロックで構成される深層ニューラルネット  開発者のVinyalsによると，３層，LSTMブロックが384個，7000万パ ラメータのものを使用している  開発者のVinyals曰く，Transformerでunitの処理をしなくとも，LSTM の部分だけでなんとかなるらしい 入力 LSTM LSTM LSTM LSTM LSTM LSTM ・ ・ ・ ・ ・ ・ ・ ・ ・ LSTM LSTM LSTM 出力

Heads  Function Heads PySC2の関数呼び出しを行う．建物作成，ユニット作成などの指示  Arguments Heads 上記の関数の引数を出力．具体的にどんな建物，ユニットを作るか等の指定 この辺には恐らくPointer Networksが用いられている 25

Pointer Networks seq2seqの改良系．入力の変化に応じて出力も変化する場合に使用 26

方策学習アルゴリズム AlphaStarのエージェントの方策学習には以下の手法を用いている  IMPALA  Policy Distillation  Self Imitation Learning  Counterfactual Multi-Agent Policy Gradients(COMA) 27

IMPALA  方策オフ型の分散深層強化学習アルゴリズム(経験を集める方策と学習方策 が違っていても大丈夫．Experience Replay使用可)  複数の環境を並列に動かし，各環境のActorの軌道を集め，集めた経験で中 央のMasterパラメータ（方策）を更新→Actorに同期…を繰り返す  本来，Masterと各Actorで方策が生じるため，Actorの方策で集めた軌道では 方策更新ができないが，V-trace（Importance Samplingに近い）という手法で効 率的な学習可 Actor:それぞれの環境内で軌道(状態，行動，報酬の列)を 生成し，LSTMの初期状態と共にLearnerに送る．方策 はLearnerと同期して更新 Learner:Actorが集めた軌道を用い，V-traceを使用して方策 更新．更新したパラメーターは各Actorに送る 28

IMPALA for AlphaStar（イメージ） エージェント 29

Policy Distillation(方策蒸留)  蒸留 • あるニューラルネットの出力を別のニューラルネットで真似る手法 • 一般的には，大きなネットワークの出力を小さなネットワークで蒸留するモデル圧縮で用い られる  深層強化学習でも似たような文脈で使用されるが，各エキスパートDQNの方策を一つのネット ワークに移して，最初からマルチタスク学習するよりも高性能なマルチタスクDQNを作成可  恐らくAlphaStar Leagueで新規エージェントを生成，または特別に良い方策を持ったエージェン トの出力を共有している 1対1で方策蒸留．AlphaStarの分岐図を見るとこちらを使用（？） 複数のエキスパートDQNから一つのDQNに方策蒸留 30

Policy Distillation for AlphaStar たぶんこの辺で使用 （これは私の想像に過ぎないので注意！） 31

Self Imitation Learning(SIL) 32  エージェントの過去の行動で良かったものを再現できるように模倣学習を行う （つまり自分自身の過去行動をデモンストレーションとして用いる）  リプレイバッファに(状態，行動，収益)を保存し，学習中に推定値𝑉𝜃 よりも，過 去の行動aをした場合の方が高い収益を得ていた場合(R>𝑉𝜃 )に，過去の行動a を選択しやすくなるよう方策更新 例えば，Montezuma’s Revengeの場合，左の鍵を取る→左のド アを開ける，という手順をこなす必要がある．鍵を取るという 行動については，明らかにいい行動であるため，ランダム要 素が入る探索で地道に方策更新を目指すよりも，過去に一度 鍵を取る行動をしたら，その行動を再生できるよう模倣学習し た方が手っ取り早い．鍵を取る行動を早期に学習すれば，ド アへ到達する確率が高まる

SIL for AlphaStar そこまで特殊な使い方はしていないと思うので割愛 33

Counterfactual Multi-Agent Policy Gradients （COMA）  マルチエージェントの環境で複数のエージェントの行動の結果とし て報酬に到達する場合に，各エージェントの方策更新のため全体 の基準となる価値評価器を使用 𝒂:各エージェント u:複数エージェントの行動の組み合わせ 各エージェントの方策を考慮し 全エージェントの行動 た，評価対象以外のエージェン の価値 トの行動価値の期待値 式全体の意味としては，全体の行動価値から評価対象となる アクター以外分の価値を引いて，評価対象のアクター1体の行動 価値を計算している ↑で求めたAを用いて，あるアクター aの勾配を計算（普通の方策勾配法とほぼ同じ） 34

COMA for AlphaStar 35  本論文の実験ではStarCraft(初代．SC2ではない)をベンチマークとして使用  SC2を深層強化学習で操作する場合，ゲーム操作のニューラルネットは一つ （一つのNNが全てのユニットを操作）  AlphaStarのマルチエージェント学習というのは，ゲーム内でなく，ゲーム外の AlphaStar League内での話（のはず）  COMAの実験では，ゲーム内の複数ユニットを複数NNで操作しているため， AlphaStarで同じ設定の利用はできないはず COMAの実験設定 ALphaStar

マルチエージェント学習 紹介手法/論文  FTW(For The Win) agent 論文：Human-level performance in first-person multiplayer games with population-based deep reinforcement learning  PSRO(Policy-Space Response Oracles)&DCH(Deep Cognitive Hierarchies) 論文：A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning  Nash Distribution 論文：Re-evaluating Evaluation 先ほどまでのNNアーキテクチャや方策学習アルゴリズムと違い，あくまで「参考にしている」 くらいの言及なので，論文のアルゴリズムをそのまま使用しているかは微妙 36

複数エージェントのゲームで自己の方策と 集団に対する学習の二重強化学習 37 Human-level performance in first-person multiplayer games with population-based deep reinforcement learning [Jaderberg+] 論文概要  一人称視点で，複数の敵エージェント，味方エージェントが存在する チーム対戦ゲームにおける方策学習手法  学習過程を，エージェント個別の方策学習（エージェント自身の報酬和を 最大化）する内ループと，エージェント個別の方策の元でチーム勝率を あげるためのハイパラ学習を行う外ループに分ける.この学習を行う エージェントをFTW(For The Win)エージェントと呼ぶ  学習環境としてQuake III ArenaのCTF(Capture the Flag)という環境を使う が，環境自体はあまり重要ではなく，学習手法の概念が重要 5月31日，本論文がサイエンス誌に掲載 https://science.sciencemag.org/content/364/6443/859

• https://science.sciencemag.org/content/364/6443/859

（一応）学習環境解説  複数の障害物などから構成されるエリア内で，エージェント同士の チーム対抗戦を行う（この論文では2vs2を想定）  エリア内のどこにランダムに発生する旗を持って自チームの陣地 内まで運べば得点が入る  旗を持っているチームに対する妨害も可能で，この辺は自チーム のエージェントとの協力が効いてくる  各エージェントは自分のニューラルネットを持ち，学習された方策 で操作される  各エージェントの視点は一人称視点（マップ全体は見れない） 38

エージェントの学習プロセス 39  それぞれ違うハイパラを持ったエージェント（論文では30体）がそれぞれ複数のプロセスを作り， ゲーム内で得た経験から，それぞれ方策学習を行う（学習アルゴリズムはIMPALA）  各エージェントは，自分の獲得報酬（ゲーム内スコア）のみを意識した内ループの方策学習と， チームの勝利を意識した外ループのハイパラ学習を行う 各プロセス， エージェント1&エージェント22 vs エージェント16&エージェント28 のようなチーム戦のゲームが行わ れ，それぞれのエージェントが学 習している

（一応）各エージェントの学習アーキテクチャ このゲーム用に作られたアーキテクチャなので，あまり重要ではない が一応 40

エージェントの目的関数 41 各エージェントは，自己の獲得スコアを意識した目的 関数𝐽𝑖𝑛𝑛𝑒𝑟 と𝐽𝑜𝑢𝑡𝑒𝑟 を最大化 するよう学習を行う innnerループ ゲーム内スコアΡを報酬変換則𝑊𝑝 で変換した報酬で強化学習を行う outerループ 現在の方策で所属チームの勝率が最大になるよう，報酬変換𝑊𝑝 や学習率などのハイパラΦの学 習をPBT(Population Based Training)で行う このような学習を行うエージェントをFTW(For The Win)エージェントと呼ぶ

PBT(Population-Based Training) Population Based Training of Neural Networks [Jaderberg+](2017)  深層（強化）学習における，ハイパーパラメータ最適化の論文  それぞれ別のハイパラを設定したエージェントの学習プロセスを並 列に走らせ，学習途中の評価結果から良いハイパラを採用し別 エージェントにも移す，ハイパラに摂動，ハイパラの再サンプルを 繰り返す  著者は，今ここで紹介してる論文Human-level～と同じJaderberg 42

PBTの詳細 各エージェントにそれぞれ ハイパラを設定し，並列に 学習開始 43 学習のある段階で，各エージェントの評価を行い，ある基 準より良かったエージェントのハイパラを別のエージェント にも設定(exploit) 良かったハイパラに対して ノイズを与える(explore)

本論文の実験結果 この論文自体の実験結果は重要ではないが一応 FTW:提案手法 Self-play + RS:↓に加え，ゲーム内スコアの 報酬変換則を学習 Self-play:内ループの自己報酬最適化のみ パフォーマンスはAgent Eloで測定 Elo(イロ)rating：本来はチェスで使用され る相対評価の実力指標．後で少し 説明 ハイパラの 変化過程 44

FTWエージェント in AlphaStar  AlphaStarにおいても，AlphaStar League内で各エージェントが他のエージェントと 1vs1のSC2対戦プロセスを複数作りながら学習  他のエージェントとの関係を考慮したouterの部分の学習は，AlphaStar League内 での総合的な勝率を挙げる学習となると思われる  outerの学習対象は，ハイパラ，エージェントの好むゲーム内ユニット，特定の他 エージェントに強い戦略など  innerは，SC2ゲーム内でただ単に相手に勝つための方策を学習（innerで個別の 相手に対して強くなってもリーグ内全体では勝率が上がらない） この部分が本論文の手法FTW エージェントと関係がある感じ 45

参考：Bi-Level Reinforcement Learning 46  ケンブリッジでの講演でDavid Silverが言及  AlphaStarの学習過程でループと内ループが存在する 外ループ：AlphaStar League内での勝率を挙げるために行う学習．各エージェントの好むユニット， ゲーム内スコアの変換則等を学習PBT(Population Based Training)を用いる（と思う） 内ループ：こちらは，SC2のゲーム内での学習．外ループでの目的を元にゲーム内での方策を学習 実際には，外ループの学習は遺伝 的アルゴリズムに近いはずなので， 二重”強化”学習と言っていいのか は微妙・・・

余談/disentangleな内部表現の可視化  本論文は，マルチエージェント学習に関するものだが，複雑な状況把握と行動が要求される ゲームではエージェントのスキルがいい感じにdisentangleされた内部表現で獲得されている のでは？というお話が出てくる  DeepMindのAlphaStarブログの図に出てくる”Neural Network Activations”の部分はこれと同じ 可視化 この辺のことはJaderbargの動画https://www.youtube.com/watch?v=dltN4MxV1RIを見るとわかりやすい 47

• https://www.youtube.com/watch?v=dltN4MxV1RI

マルチエージェント学習におけるゲーム理論的な視点 48 からの方策学習とメタ戦略 A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning [Lanctot+](NIPS2017) 論文概要  複数の方策を持ったエージェントが同時に存在するマルチエージェント強化学 習(MARL)の一番簡単な形は，他のエージェントを無視して（環境の一部とみな す）学習するInRL(Independent RL)だが，環境が非定常であるため，うまく学習 できない  複数の方策を持つプレイヤー同士のメタゲームを考え，方策の分布を表す「メ タ戦略」を計算，そのメタ戦略下における最適方策（オラクル）の導出を繰り返 すことで，良い方策の獲得を目指す

予備知識 ゲーム理論基礎，純粋戦略ナッシュ均衡 49  プレイヤー１とプレイヤー２の戦略と利得の関係によって定義されるゲームを戦略ゲームとい い，下のような利得行列で表される．以降，この戦略形ゲームに絡む話が出てくる  特にここではプレイヤー1と２の全ての戦略の組に対して（プレイヤー１の利得）＝－（プレイ ヤー２の利得）となるゼロサムゲームを考える プレイヤー１の戦略：x1,y1 プレイヤー２の戦略：x2,y2 ナッシュ均衡：どのプレイヤーも，その戦略の組から自分一人だけが他のどんな戦略に変えても， 自分の利得が高くならないような戦略の組 詳しい計算は省くが，ここでは(x1, y2)の組 み合わせがナッシュ均衡 ここでは，お互いに一つの戦略を取り続け ることが最適となる純粋戦略ナッシュ均衡 1 x2 y2 x1 (4, -4) (1, -1) y1 (-3, 3) (-1, 1) 2 利得行列(payoff matrix) 1 x2 y2 x1 4 1 y1 -3 -1 2 = ゼロサムゲームの場合はこう書いてもよい

予備知識 ゲーム理論/混合戦略ナッシュ均衡  先ほどの例では，各プレイヤーが一つの戦略を取り続けることが ナッシュ均衡だったが，利得の構成によっては，そうでない場合も  プレイヤーが複数の戦略を確率的に選ぶことがナッシュ均衡にな る場合も→混合戦略ナッシュ均衡 1 右の利得行列では，プレイヤー１が x1を3/4, y1を1/4, プレイヤー2がx2 を2/3,y2を1/3の確率で選ぶ混合戦 略をとる場合にナッシュ均衡 x2 y2 x1 4 1 y1 0 9 2 50

DO(Double Oracle Algorithm) 2プレイヤーのゼロサムゲームで，ナッシュ均衡（混合戦略）を導 出→その均衡下で最適応答となる戦略を各プレイヤー追加→ ナッシュ均衡導出・・・を繰り返し，最適応答が改善されなくなるま で， 互いの戦略を改善し追加し合うアルゴリズム →後ほど紹介する，本論文の提案手法の 原型アルゴリズム 51

メタゲームとメタ戦略  メタゲーム 複数の方策（この方策は例えば囲碁AIなど対戦ゲームの方策）を持つプレイヤー同士が，自分の 方策と相手の方策を戦わせるゲームで，各プレイヤーはどの方策を選ぶのが最適か？を考える  メタ戦略(meta-strategy) プレイヤーが持つ方策の中から，どれくらいの確率でどの方策を選択するかの分布．先ほど説明 した混合戦略の選択対象を方策にしたもの プレイヤー2のメタ戦略例 (1/2, 1/6, 1/3) プレイヤー１のメタ戦略例 (1/3, 1/6, 1/6) 方策 1-1 方策 1-2 方策 プレイヤー１ 1-3 ＶＳ 方策 2-1 方策 2-2 方策 2-3 プレイヤー２ 52

じゃんけんで例えると・・・ 混合ナッシュ均衡やメタ戦略はじゃんけんを考えるとわかりやすい  ジャンケンをする人間：プレイヤー  グー，チョキ，パー：３つの方策  メタ戦略：グー，チョキ，パーをそれぞれどれくらいの確率で選択す るか →当然各1/3の確率が最適 53

PSRO(Policy-Space Response Oracles)  先ほどのDOを方策が複数存在するメタゲームに応用したもの ←各プレイヤーが持つ方策を初期化 ←上記の方策を実際に使用して，各方策の組み合わせ で各プレイヤーがどれくらいの利得を得るのか計算 ←各プレイヤーのメタ戦略（方策の選択確率の分布）を， 一様選択で初期化 n人のプレイヤーに関してループを回す． プレイヤーiは，自分以外の敵の方策を敵の メタ戦略の分布からサンプリングし，それら を相手に現在の敵のメタ戦略下で最適な方 策𝜋𝑖′ を学習 ←各プレイヤーのループ後，学習した方策𝜋𝑖′ を，プレイヤーiの持つ方策に追加する ←全プレイヤーの最適方策学習後，各方策の組み合わせによ る利得を計算 ←追加された方策も考慮し，各プレイヤーのメタ戦略を更新 直感的には，複数の方策がある環境で，現在 の状況下での最適方策を生み出し合い，どん どん強い方策を生み出している 54

PSRO for AlphaStar  AlphaStar League内には，それぞれ別の方策を持ったエージェント が多数存在  AlphaStar League内に存在する方策を全て持つプレイヤー同士（つ まり両方とも選択肢となる方策は同じ）を考え，PSROで新しい方策 を生んでいる（？）  具体的にどう使っているかは本体の論文を見ないとわからなさそう … 55

機械学習手法の評価法を評価 56 Re-evaluating Evaluation [Balduzzi+](NeurIPS2018) 論文概要 今 回 重 要 な の は こ ち ら  機械学習には様々なベンチマークが存在するが，どのベンチマークで評価すれば手法の妥当 性が示せるか？という問題は割と無視されがち（強化学習だと，Atariゲームの一部ゲームで 高スコアがどれくらい凄いのか）  論文では，エージェント（機械学習アルゴリズム）の評価を行うタスクについての検討と，複数 エージェントでエージェントVSエージェントの対戦ゲーム（囲碁やSC2等）をする場合に各エー ジェントの強さの評価をどうしたらいいか検討している  AlphaStar Leagueの最後で人間と戦うエージェントを選択する部分に関連  学習手法というよりは，エージェントの強さを評価する考え方の話

どこの話をしているか AlphaStar Leagueにおける最後のエージェント選択のお話 つまり，最終的に人間と戦うエージェントをどのように選択す るかの基準について 従来の手法でエージェントの実力を評価すると，正確に強いエージェント が選ばれなくなるため，別の選び方を提案している 57

対戦ゲームの実力評価システム  囲碁などの対戦型ゲームで，各プレイヤーの強 さをどう評価すればいいのか？というお話（ポケ モンだとレーティングバトル，スプラトゥーンだとウ デマエシステムに近い話）  50mのように競技の数値的記録を競う競技なら 記録の絶対値で実力評価可能だが，囲碁やポケ モン，SC2のような対戦型ゲームではそのような 絶対的指標はない  単なる勝率で実力を表すこともできるが，弱い対 戦相手に無双している場合などは正確に実力が 評価できない 複数プレイヤー間の相対評価で実力を表せる指標が必要 58

イロレーティング  対戦型の競技（２対２または，２チームの対戦）で，相対評価で実 力を表すために用いられる指標  元々はチェスの実力を示すために使用されていた  数理的な背景まで話すと長くなるため割愛（Wikipediaなどでどう ぞ）  とりあえず，イロという指標があって，今までの対戦型ゲームでは 機能していた，ということを覚えていただければ レーティングについては この本が詳しい 59

イロレーティングの欠陥 準備  例えば，ジャンケンで出せる手が一つ（一つ以上でもいい）増える 場合を考える  ここでは，チョキと同じく，パーに勝ってグーに負ける手が増えたと する（人差し指一本だけ立てる手）  このとき，グーが勝てる手は２つ，パーが負ける手も２つになった が，だからといってグーが強くなって，パーが弱くなったと言える か？ →そんなことはない．（常識的に）ジャンケンをすれば，今まで通りチョ キの効果を持つ手が出てくる確率は三分の一で，ただ見た目が複数 に増えただけ 60

イロレーティングの欠陥  イロレーティングでは，先ほどのじゃんけんの例のように，あるプレ イヤー（エージェント）とまったく同じ強さのプレイヤーが現れると， レーティングが狂う 元々のゲーム 表に書かれているのは勝率． A→B→C→A・・・の三すくみの関係に なっており，レーティング上は全員 同じ強さ Cのコピーを追加したゲーム元々のゲーム Cのコピーを追加 Aは勝てる相手が増えたのでレート が上昇，Bは負ける相手が増えた のでレートが減少．不当に高く/低く 評価されてしまう AlphaStarの視点からだと，AlphaStar League内に同じような方策を持ったエージェント が複数いた場合，イロレーティングによる評価を用いると正当な評価ができない 61

対戦型ゲームで求められる評価指標 本論文では，以下の３要素を評価指標に求められる 重要 事項としている 1. Invariant:同じような実力を持つエージェントが集団に混 ざっても正当に評価できる 2. Continuous:多少のデータ変更に対してロバスト 3. Interpretable:やっていることが直感的にわかる（？） 62

大まかな評価の流れ 1. プレイヤーが持つ各方策が別の方策と対戦した場合の勝率のロ ジット関数を計算し，このロジット関数を利得とするゲームの行列 を作成 2. この行列をもとに，メタ戦略のナッシュ均衡の中で，メタ戦略のエン トロピーを最大化する一つの均衡「Max Entropy Nash Equilibrium(Maxent Nash)」を求める 3. Maxent Nashのメタ戦略に対してNash Averagingと呼ばれる操作を 加え，最終的に得られるNash Distributionという方策の分布から， 最も強い方策を求める 63

勝率のロジット関数を利得とする行列 先ほど出てきた勝率の表の勝率をロジット関数にする 𝑝 𝑙𝑜𝑔𝑖𝑡 𝑝 = log = log 𝑝 − log 1 − 𝑝 1−𝑝 すると，先ほどのような勝率の行列は，以下のような反対称行列となる ※反対称行列：元の行列と，元の行列を転 置した行列を足すと０になるような行列  ここで，A, B, Cはそれぞれ別々の方策を表す  この反対称行列Aは，同じ方策A, B, Cを持ったプレイヤー同士の対 戦としてみることができ（先ほど説明したメタゲーム），各プレイヤー は方策選択の分布を考える 64

Max Entropy Nash Equilibrium 先ほど求めた行列のゲームにおけるナッシュ均衡は複数あるが，ここ ではユニークなナッシュ均衡として，メタ戦略のエントロピーが最大に なるような（つまり，できるだけランダムに方策を選択するような）均衡 を考える →Max Entropy Nash Equilibrium (Maxent Nash) なお，この均衡はソルバを使って求めるため，計算は省略 方策Aの選択確率：1/3 方策Bの選択確率：1/3 方策Cの選択確率：1/3 がMaxent Nash 65

Nash Averaging 66 先ほど求めたMaxent Nashと元のロジット関数の行列Aのドット積をとる操作 「Nash Averaging」により，最終的な方策の評価の分布を得る ・ (1/3, 1/3, 1/3) = (0, 0, 0) 今回評価している方策の組み合わせは，3すくみの 関係にあるため，全部同じ強さとして0の評価

本当にこの方法でうまくいくのか 67 例えば，先ほど評価した方策の組み合わせにCとまったく同じ方策を 新たに加え，A, B, C1, C2の評価をすると．・・・ (1/3, 1/3, 1/6, 1/6) Maxent Nash を求める Cが２つになり，C1, C2が 追加された行列 Maxent Nash Nash Averaging ・ (1/3, 1/3, 1/6, 1/6) ＝ (0, 0, 0, 0) 余計なコピーが加わった後も， Aが不当に弱くなったりBが不 当に強くなったりせず，すべて の評価が同じなので，評価が 正当

方策評価例２ 68 ３すくみとは違い，方策の強さに偏りがある場合でも正当な評価がで きるかどうか試してみる Maxent Nash を求める B A' A B C1 C2 0 1.75 0.5 0.5 B -1.75 0 1.75 1.75 C1 -0.5 -1.75 0 0 (1, 0, 0, 0) C2 -0.5 -1.75 0 0 Maxent Nash • • 既に勝率をロジット関数にしたものの行列 Aは全体的に強く，BはC1, C2に対して強い，C1, C2は全部 に弱く，同じ強さ →正当な評価であれば，Bは同じ方策C1, C2に対する強さが1 つの方策に対する強さとして評価され，Aが一番強くなるはず Nash Averaging B A B C1 C2 A' 0 1.75 0.5 0.5 B -1.75 0 1.75 1.75 C1 -0.5 -1.75 0 0 C2 -0.5 -1.75 0 0 ・ (1, 0, 0, 0)＝ (0, -1.75, -0.5, -0.5) Nash Averagingを行うことで，正当な 評価がされている （BがC1, C2より弱いのは違和感があ るかもしれないが，これは，一番強い Aに対してBが非常に弱いため）

Nash distribution for AlphaStar 69  前述の通り，AlphaStarLeagueにおける最後のエージェント選択に 使用している  なお，論文内であまり正確な言及がなかったと思うが，たぶんNash Averagingの分布を”Nash Distribution”と呼んでいる リーグ後半のエージェント（最終的には600番 台）の方が高い評価となっており，AlphaStarの 学習手法で時間をかければかけるほど強い エージェントが生み出されていることがわかる

SC2プレイヤーとしての視点 からAlphaStarの考察

AlphaStar StarCraft2プレイヤーの視点から 71  生放送で行われたMaNaとの最終戦では，MaNaによる子供だまし のような陽動戦略に引っかかるなどの脆さも見せる  AlphaStarが利用しているFeature Layerには恐らく透明状態の敵（人 間には見えないし，攻撃対象にもできない）の情報が含まれている． MaNaとの対戦では即座に反応した(MaNa第4戦の9分7秒～)  勝因は一部の機動力に優れたユニットによる精緻なマイクロ操作 で，囲碁などのように，複雑な長期予測によるマクロな戦略で勝っ てるとは言い難い…気がする

MaNaの陽動   AlphaStarは人間との対戦で１度だけMaNaに敗北 Warp Prismという輸送ユニット（地上戦闘ユニットを何体か収容できる空中ユ ニット）を使用した陽動に引っかかっている（エキシビジョンマッチのReplay８分 20秒あたりから） 参考：DeepMind公式生放送(https://www.youtube.com/watch?v=cUTMhmVh1qs&t=7760s)の2:09:45から 具体的には， 1.地上ユニットを乗せたWarp Prismが，AlphaStarベースの上空まで移動．敵に攻撃されな い安置エリアで待機 2.敵の地上部隊ユニットがベースから離れたら，Warp Prismを敵ベースの真上に移動 3.敵ベースに地上部隊をWarp Prismから降下させ，前線ユニットがいない間にベース攻撃 4.これに気づいたAlphaStarの前線ユニットは進行をやめ，ベースに引き返し始める 5.AlphaStarのユニットがベース近くまで戻ったところで，地上ユニットをWarp prismに再収納 し，安置へ．敵前線ユニットは再び前進を始める 陽動で時間稼ぎしている間にMaNaは施設拡大＆Archonという地上最強ユニットを複数含 む地上軍を編成し，AlphaStarでも勝てないレベルに 2～5を繰り返すと，敵の地上部隊はベースを行ったり来たりで，まったく侵攻がで きなくなる．人間であればWarp Prism対処用のユニットだけベースに残せばいいと 気づくが，AlphaStarはこれに気づかない 72

• https://www.youtube.com/watch?v=cUTMhmVh1qs&t=7760s

安置にWarp Prismを移動 AS ベ | ス 方 向 73 Warp Prism

ASベース上空までWarp prismを移動 地上ユニット降下のため、 AlphaStarのベース上空 まで移動 一方その頃，ひたすら前進を 続けるAlphaStarの地上軍 74

Warp Prismから地上ユニットを降下 Warp Prismから降 下した地上ユニット 異変に気付いたAlphaStarの地上 軍が前進をやめ，ベースに引き 返し始める 75

ASの地上軍を引き付けて撤退 地上ユニットを収納して 撤退するWarp Prism 異変に気付いてやってき たAlphaStarの地上軍 危機は去ったと言わんばかりに再び 前進を始めるAlphaStarの地上軍 後は繰り返し 76

一方その頃・・・ 77 Archon 地上最強ユニットArchonを複数作り，進軍の準備を進めるMaNa

どうしてこうなった？  前述の通り，AlphaStarはあるレベル以上のプレイヤーのプレイ データ教師データをして用い模倣学習を行う  一定レベル以上だと，前述のような「あまりにも見え見え」な陽動は まったく意味をなさないため教師データにはあのような陽動はない  AlphaStarはリーグ内で複数エージェントで対戦し、多様な戦略の出 現を狙うが，根本は人間のプレイデータに従っている  StarCraft2はあまりにも探索空間が大きすぎるため，教師データに ないような「特殊すぎる」行動は，リーグ中でも出現しない 78

クローク(透明化)発動中の敵への反応 79  SC2のユニットの中には，敵プレイヤーが視認できず，攻撃もできない”ク ローク（透明化）”のスキル持つユニットが存在  “ディテクター”というスキルを持つユニットを使用することで，クローク発 動中の敵が見えるようになり，対処可能  本来，クロークユニットは相手が生産しても気づかないが，AlphaStarは MaNaがDark Templerというクロークユニットを作成した直後に反応し， Observerというディテクターユニットの生産を開始  結局，MaNaがDark Templerで攻撃を始める頃にはAlphaStarのディテク ターユニットの生産が完了しており，MaNaは返り討ち  たぶん，PySC2のfeature layersから，クロークユニットの情報も受け取っ ているため，超人的な反応をしている この辺の流れは，MaNa対AlphaStar第４戦の9分7秒～を見てもらえば

超人的なマイクロと良いのか微妙なマクロ 80  SC2の対戦では，ユニット生産や建築物生産などの大局的な要素 を指す「マクロ」と，相手ユニットの交戦中に自軍ユニットを細かく動 かして有利に戦う「マイクロ」の要素が存在  AlphaGOなどの囲碁AI，その他天候予測AIなどで示しているように， DeepMindの開発するAIが目指しているものは，大局的，長期的な 予測に基づく「マクロ」であるはず  が，個人的な意見では，AlphaStarはかなり「マイクロ」の要素が強 いように見える  この辺は，DeepMindも相当意識しているようで，ブログ，インタ ビュー，その他色々なところで，「AlphaStarはマイクロじゃなく，マク ロで勝ったんだ！！（超意訳）」と繰り返している

大量のStalkerとマイクロ  AlphaStarはSC2のプロトスが使えるユニットの内”Stalker”というユニットを非常 に好む Stalker  Stalkerの特徴 • • • • • 高い機動力 短距離の瞬間移動スキルblinkによる更なる機動力の確保 地上・空中両方への攻撃性能 優秀な射程 攻撃力は微妙  本来，Stalker自体は単体で圧倒的な強さを持つユニットではないが，Stalkerの 高い軌道力とAlphaStarの超人的なマイクロが合わさることで非常に大きな戦 力となっており，Stalkerの大量生産とこれらのマイクロがAlphaStarの強さの核 ※ただし，TLO第2戦とMaNa第5戦で用いられたAlphaStarのエージェントは他のものと仕様がかなり異なるので，全部に当てはまるわけではない. 特に TLO第2戦のエージェントは，Carrier，Mothershipなどの超大型空中ユニットによる物量作戦に近い  AlphaStarの超人的マイクロにより，ゲーム内のユニット間の相性を無視するレ ベルのアドバンテージを生み出してしまっている（Immortalという相性最悪の ユニットの集団相手に，Stalker側が勝ってしまう） 81

SC2におけるAPM 82  APM(Actions Per Minute)はその名通り，SC2における１分間の操作数の平均を 表し，プレイヤーの強さの指標ともなる  右下の図を見ると，AlphaStarのAPMは大体280程度で，機械特有の実質無限 の操作量で圧倒したわけでないように見える ※TLOは操作をまとめたキーバインドを使用しているためAPM異常に多くなっている  しかし，あくまでこれは交戦時以外の平時も含めたAPM．実際，交戦時には瞬 間的に人のプロでも到底届かない1500にも達するAPMで圧倒しているので， フェアかどうかは微妙

まとめ  現在の機械学習界隈では注目を浴びにくいゲーム理論，マルチ エージェント学習が技術的中心で，個人的には嬉しい  法外な計算資源を使用しているため，グランドマスターを打倒でき るエージェントの再現は難しそう  近いうちにAlphaStarと同じアーキテクチャでIMPALAを使用してSC2 のミニゲームを強化学習する実装を公開予定 83

余談/OpenAI FiveとDota2  OpenAI が開発したOpenAI FiveというゲームAIも，「Dota2」というRTSゲームで， 世界的なプレイヤーに勝利している  Dota2はRTSの中でも「MOBA(Multiplayer online battle arena)」というサブジャン ルに属し，SC2とは違った要素が多数存在  DoTA2とSC2の大きな違い • Dota2は5vs5のチーム戦/SC2は（基本的に）1vs1 • Dota2ではプレイヤー（エージェント）一人が一つのゲーム内キャラ(ヒーロー)を操作/SC2は プレイヤー（エージェント）が自軍全てのユニットを操作 （ OpenAI Fiveの名前も操作のNNを5つ使うことから） つまり，Dota2では，勝つために 操作主体が違うエージェント同士の協調プレイ が必要 84

余談/OpenAI Fiveの技術     85 方策学習アルゴリズムはPPO(Proximal policy optimization) AlphaStarとは違い，最初に模倣学習はしない 現在の自分8:過去の自分2の割合のself-playで学習 エージェント個々の報酬とチームとしての報酬の重視具合を調整する“Team spirit”と呼ばれるハイパーパラメータを用いて，チームプレイをうまく学習 その他学習に関わる数字  以下の論文も参考になる 学習システム”Rapid”の構成 EMERGENT COMPLEXITY VIA MULTI-AGENT COMPETITION (https://arxiv.org/abs/1710.03748)

• https://arxiv.org/abs/1710.03748

OpenAI Fiveエージェントのアーキテクチャ 86

Dota2プレイヤーとしての視点から見た OpenAI Five  長いゲームの中で事実上クリックミスとダメージ等の計算間違いを しないというのは非常に大きなアドバンテージで，この辺はAI（機械 学習）技術というよりは，機械であるからこその強さが活きている  一応，ゲームに制限がある状態での戦いなので，世界的プレイ ヤーが負けた今でも，完全にDota2というゲームで人間が負けたわ けではない（が，これも時間の問題）  人間のプレーの常識である，操作の正確さ，数の優位，というもの を徹底してプレーしている感じで，AlphaGoなどに見られたような人 外の価値観に基づくプレーというよりは，超凄い人間という印象 87