2019-12-05

MuZeroの論文を読むその４（結論）

MuZero

本文の残り、結論の部分です。

結論

人工知能のブレークスルーの多くは、高パフォーマンスプランニングまたはモデルフリー強化学習方法に基づいている。
この論文では、両方のアプローチの利点を組み合わせた方法を紹介した。
私たちのアルゴリズムMuZeroは、論理的に複雑なドメイン（チェスや囲碁などのボードゲーム）での高パフォーマンスプランニングアルゴリズムの超人的なパフォーマンスと、視覚的に複雑なドメイン（Atariゲーム）で最先端のモデルフリーRLアルゴリズムを上回った。
重要なのは、私たちの方法はゲームのルールや環境のダイナミクスに関する知識を必要とせず、強力な学習およびプランニング方法を完璧なシミュレーターが存在しない現実世界の多くのドメインに適用する可能性を秘めていることである。

感想

結論では、ゲームのルールを必要としないで（環境から返されるデータだけで）学習できるという点が強調されています。
以前のAlphaZeroでは、MCTSのシミュレーションでゲームのルールを使用していましたが、環境（ボードゲームの場合は遷移確率）をニューラルネットワークでモデル化することで、ゲームのルールが不要となっています。
シミュレーションの結果を使って実際に着手する際は合法手のチェックは必要なので、まったくルールを使っていないかというと微妙ですが。

読み始める前は私が開発しているdlshogiに応用できるかもという期待はありましたが、チェスと将棋ではパフォーマンスはAlphaZeroと同程度で、AlphaZeroより学習ステップ数が増えているので、そのまま取り入れるメリットはなさそう。
ただしAlphaZeroのメソッドと併用するなど応用の可能性はありそうなので、技術的な興味もあるので一度実装してみたいと思っています。

次回は、付録を読んでいきます。

2019-12-04

AlphaStarの論文を読むその１３（分析、AlphaStarの一般性）

AlphaStar 強化学習

分析

エージェントセット

検証エージェント：メインエージェントのみを使用し、エクスプロイターを使用せずに訓練された17の戦略セットに対するリーグの堅牢性を検証し、zを手で精選された興味深い戦略セット（例：キャノンラッシュや初期飛行ユニット）に修正した。

アブレーションテストエージェント：アブレーションテストエージェントには、検証エージェント、および完全なリーグトレーニングによって作成された最初の（つまり弱い）20のメインおよび20のリーグエクスプロイトプロトスエージェントが含まれる。

固定相手：RLアルゴリズムを評価するために、リーグトレーニングによって作成された最初の10人のリーグエクスプロイトプロトスエージェントで構成される均一な混合戦略に対する最良の応答を計算した。

図で使用されるメトリック

Eloレーティング：リーグの内部Eloレーティングを計算するために、組み込みのボットを追加し、それを使用して次のモデルでEloを推定した。

$\displaystyle \mathbb{P}[\mathrm{r}_{1} \text { beats } \mathrm{r}_{2}]=\frac{1}{1+e^{-\left(\mathrm{r}_{1}-\mathrm{r}_{2}\right) / 400}} \approx \Phi\left(\frac{\mathrm{r}_{1}-\mathrm{r}_{2}}{400}\right)$

ここで、 $\mathrm{r}_{1}$ と $\mathrm{r}_{2}$ は両方のプレイヤーのEloレーティングである。
Eloレーティングには固有の絶対スケールがないため、組み込みのEliteボットのレーティングを0に設定することにより、Eloレーティングを接地する。

相対集団パフォーマンス

相対集団パフォーマンス（Relative Population Performance; RPP）は、2つの集団(population)がナッシュ均衡に達した後の2つの集団間のメタゲームの予想される結果である*1。
リーグAとBの、それぞれサイズNとMのすべてのエージェント間の利得行列が与えられた場合、 $P_{A B} \in[0,1]^{N \times M}$ ：

$\displaystyle \operatorname{RPP}\left(P_{A B}\right)=\operatorname{Nash}\left(P_{A B}\right)^{T} P_{A B} \operatorname{Nash}\left(P_{B A}\right)$

ここで、 $\operatorname{Nash}(X) \in[0,1]^{K}$ は、サイズKのリーグXにおけるナッシュ均衡で各エージェントをプレイするために割り当てられた確率のベクトルである。
RPPが高いということは、リーグAがBからのエージェントを活用できる混合戦略を形成できるエージェントで構成されていることを意味する。

AlphaStarの一般性

StarCraftの複雑さとゲーム理論上の課題に対処するために、AlphaStarは、ニューラルネットワークアーキテクチャ、模倣学習、強化学習、およびマルチエージェント学習のための新規および既存の汎用技術の組み合わせを使用する。
これらの手法とその組み合わせは広く適用できる。

ニューラルネットワーク アーキテクチャ コンポーネント

新しいスキャッター接続を含むニューラルネットワークアーキテクチャコンポーネントは、一般に、観測がStarCraftに存在する画像、リスト、およびセットの組み合わせで構成されるすべてのドメインに適用できる。

行動空間の定義

AlphaStarの行動空間は、型指定された引数を持つ関数のセットとして定義される。
同様のAPIを定義するドメインはすべて、複雑で構造化された行動空間の同じ分解に取り組むことができ、その結合確率はチェーンルールによって分解される（たとえば、言語モデリング *2や定理証明に似ている）。

模倣学習

AlphaStarでの模倣学習には、効果的な人間による大量のデモンストレーションが必要であるため、このようなデモンストレーションセットを提供するドメインにのみ適用できる。
潜在変数zを使用して探索を誘導することはStarCraftに固有ではないが、統計の特定の選択にはドメインの知識が必要だった。
特に、StarCraftで序盤とユニットをエンコードするためにzを選択した。
擬似報酬は、編集距離やハミング距離など、これらの統計の適切な距離メトリックに基づいている。

強化学習 アルゴリズム

AlphaStarの基礎となる強化学習アルゴリズムは、どのRL環境にも適用できる。
また、より低い分散のベースラインと新しいコンポーネント（例えば、ハイブリッド方策オフ学習、UPGO、模倣ポリシーに向けた蒸留など）のために敵の観測を使用することも広く適用できる。

マルチエージェントトレーニング

最後に、メインエージェントを強化することを目的とするさまざまな種類のエクスプロイターを使用した新しいマルチエージェントトレーニング体制を提案する。
優先順位付きFSPとともに、これらはすべてマルチプレイヤードメインに適用可能な汎用技術である。

コードおよびデータの可用性と声明

プロフェッショナルプレーヤーの声明

次の引用は、StarCraft IIプロプレイヤーであるDario “TLO” Wünsch（チームの一員であり、この論文の著者でもある）によるもので、インターフェイスと制限について説明している。

Dario “TLO” Wünschの声明

AlphaStarに設定されている制限は、1月の最初のショーマッチとは非常に異なると感じる。
- AlphaStarには優れた正確な制御機能があるが、超人間的な感覚はない。
- 人間が理論的に達成できないレベルではない。
- 人間よりもいくつかの面で優れており、他の面でも悪化しているが、もちろんAlphaStarと人間のプレイヤーの間には避けられない違いがある。

DeepMindのシステムが人間のプレイヤーよりも不公平に優位にならないようにするために、AlphaStarチームに相談できることを嬉しく思った。
全体として、StarCraftの「本物の」ゲームをプレイしており、非現実的な機能を備えているためにバランスが完全に失われておらず、非常に公平に感じる。
カメラの表示が制限されているため、マルチタスクを実行するときに常にすべてを同時に捕捉できるとは限らないため、その側面も非常に公平で人間らしく感じられる。

リプレイデータ

AlphaStarがオンラインでプレイしたすべてのゲームはファイルreplays.zip（Supplementary Data Replays）にあり、Battle.netの実験の生データはbnet.json（Supplementary Data Battle.net）にある。

コード

StarCraft II環境は、BlizzardとDeepMindによって2017年にオープンソース化された。
模倣学習に使用される人間のリプレイはすべて、https://github.com/Blizzard/s2client-protoにある。
AlphaStarの教師あり学習、強化学習、およびマルチエージェント学習コンポーネントの擬似コードは、ファイルpseudocode.zip（Supplementary Data Pseudocode）にある。
すべてのニューラルアーキテクチャの詳細とハイパーパラメータは、detailed-architecture.txt（Supplementary Data Architecture）ファイルにある。

感想

全体を読んでみて、個人的にポイントと思ったのは以下の点です。

不完全情報ゲームのサイクル問題を回避するためリーグマッチによるマルチエージェントで学習している
リーグの対戦相手の選択を優先順位付きFSPで効率化している
複雑な長期戦略を強化学習では学習できない
そのため人間のリプレイを利用する
ニューラルネットワークはLSTMを使用する
入力は、トランスフォーマーでユニットを埋め込み表現にしている
埋め込み表現にしたユニットを、畳み込みにスキャッター接続することで空間情報を保持して入力する
行動の出力は、複数のアクション引数をネットワーク構成で表現している
引数の出力に応じて、ポインターネットワークやアテンションが使用されている
強化学習アルゴリズムは、アクタークリティックがベース
方策の学習にはリプレイバッファを使用してV-Traceで方策オフで学習する
加えてUPGOで自己模倣学習を行う
価値の学習はTD(λ)を使用し方策オフの補正は行わない
対戦条件は、操作頻度やカメラ操作を人間の条件に近づけて公平にしている

*1:[1901.08106] Open-ended Learning in Symmetric Zero-sum Games

*2:https://www.fit.vutbr.cz/research/groups/speech/publi/2010/mikolov_interspeech2010_IS100722.pdf

2019-11-30

MuZeroの論文を読むその３（結果）

MuZero 強化学習

結果

MuZeroアルゴリズムを、挑戦的なプランニング問題のベンチマークとしての古典的なボードゲーム囲碁、チェス、将棋、および視覚的に複雑なRLドメインのベンチマークとしてAtari Learning Environmentの57のゲームすべてに適用した。

測定条件

それぞれのケースで、K = 5の仮想ステップでMuZeroを訓練した。
ボードゲームではサイズ2048、アタリではサイズ1024の100万ミニバッチで訓練した。
訓練と評価の両方で、MuZeroはボードゲームの各探索に800回のシミュレーションを使用し、Atariの各探索に50回のシミュレーションを使用した。
表現関数は、AlphaZeroと同じ畳み込みおよび残差アーキテクチャを使用するが、20ではなく16の残差ブロックを使用する。
ダイナミクス関数は表現関数と同じアーキテクチャを使用し、予測関数はAlphaZeroと同じアーキテクチャを使用する。
すべてのネットワークは256の隠れプレーンを使用する（詳細については、「Methods」を参照）。

各ゲームの訓練全体のパフォーマンス

図2は、各ゲームの訓練全体のパフォーマンスを示している。
囲碁では、MuZeroはAlphaZeroのパフォーマンスをわずかに上回ったが、探索木のノードごとの計算量は少なくなった（AlphaZeroの20ブロックと比較して、MuZeroの評価ごとに16残差ブロック）。
これは、MuZeroが計算を探索木にキャッシュし、ダイナミクスモデルの各追加適用を用いて局面をより深く理解できることを示唆している。

図2：チェス、将棋、囲碁、Atariの訓練全体でのMuZeroの評価

f:id:TadaoYamaoka:20191125231748p:plain

X軸は、数百万の訓練ステップを示している。
チェス、将棋、囲碁の場合、y軸はEloレーティングを示す。これは、両プレイヤーが1手につき800シミュレーションを使用してAlphaZeroに対してゲームをプレイすることによって確立される。
MuZeroのEloは青い線で、AlphaZeroのEloはオレンジ色の水平線で示されている。
Atariの場合、57のゲームすべてにわたる人間の正規化された平均（実線）および中央値（破線）がy軸に表示される。
R2D2のスコア（モデルフリーRLに基づいたこのドメインの従来技術）は、オレンジ色の水平線で示されている。
Atariのパフォーマンスは、4タイムステップごとに50回のシミュレーションを使用して評価され、その後、以前の研究*1と同様に、選択されたアクションを4回繰り返した。

Atariの結果

Atariでは、MuZeroはArcade Learning Environmentの57のゲームで平均および中央値の両方の正規化スコアの最先端を達成し、57のゲームのうち42で以前の最先端のメソッドR2D2 *2（モデルフリーアプローチ）を上回り、すべてのゲームで以前の最高のモデルベースのアプローチSimPLe*3を上回った（表S1を参照）。

表S1：30のランダムなノーオペレーションスタートの個々のゲームのAtariでのMuZeroの評価

f:id:TadaoYamaoka:20191126231615p:plain:w200

太字で強調されているのは各ゲームの最高の結果。
各エピソードは、最大30分のゲーム時間（108kフレーム）に制限されている。
SimPLeは57ゲームのうち36ゲームでのみ評価され、利用できない結果は「-」で示されている。
人間の正規化スコアは次のように計算される。 $s_{normalized}=\frac{s_{a g e n t}-s_{r a n d o m}}{s_{h u m a n}-s_{r a n d o m}}$

サンプル効率を向上したバージョン

また、サンプルの効率を高めるために最適化されたMuZeroの2番目のバージョンも評価した。
具体的には、最新のネットワークパラメータを使用してMCTSを再実行し、新しいターゲットを提供することにより、古い軌跡を再分析する（付録Hを参照）。
ゲームごとに2億フレームの経験を使用して、57のAtariゲームに適用した場合、MuZero Reanalyzeは以前の最先端のモデルフリーアプローチであるIMPALA*4、Rainbow*5およびLASER*6がそれぞれ192％、231％、431％であるのに対して、731％の正規化スコアの中央値を達成した。

表1：MuZeroとAtariの以前のエージェントとの比較

f:id:TadaoYamaoka:20191225084442p:plain

大規模（上）および小規模（下）のデータ設定で訓練されたエージェントと個別に比較する。
MuZero以外のすべてのエージェントは、モデルフリーRLテクニックを使用した。
人間のテスターと比較した平均および中央値のスコアを示す。
最良の結果は太字で強調されている。
MuZeroは、両方の設定で最先端(SOTA)を更新した。
脚注a：ハイパーパラメータはゲームごとに調整された。

MuZeroでのモデルの役割を理解するための実験

MuZeroでのモデルの役割を理解するために、囲碁のボードゲームとMs.PacmanのAtariゲームに焦点を当てて、いくつかの実験も行った。

囲碁でのプランニングのスケーラビリティ

まず、囲碁の標準的なプランニングの問題で、プランニングのスケーラビリティをテストした（図3A）。
完全なモデルを使用したAlphaZeroの探索のパフォーマンスと、学習したモデルを使用したMuZeroの探索のパフォーマンスを比較した。
特に、完全に訓練されたAlphaZeroまたはMuZeroのMCTSを異なる思考時間で比較することにより評価した。
MuZeroは、モデルが訓練されたとき（思考時間約0.1秒、図S3Aも参照）よりもはるかに大きな探索（思考時間10秒まで）を行った場合でも、完全なモデルのパフォーマンスと一致した。

図3：囲碁（A）、57すべてのAtariゲーム（B）、Ms.Pacman（C-D）におけるMuZeroの評価

f:id:TadaoYamaoka:20191126233406p:plain

（A）囲碁での着手ごとの探索時間によるスケーリング、学習したモデルと正解シミュレータとの比較。
- 両方のネットワークは、探索ごとに800回のシミュレーションで訓練され、探索ごとに0.1秒に相当する。
- 驚くべきことに、学習したモデルは、訓練中に見られるよりも最大2桁長い探索まで拡張できる。
（B）Atariの最終的な人間の正規化された平均スコアと、探索ごとのシミュレーション数のスケーリング。
- ネットワークは、探索ごとに50回のシミュレーションで訓練された。
- 暗い線は平均スコアを示し、影付きの領域は25〜75および5〜95パーセンタイルを示す。
- 学習したモデルのパフォーマンスは、探索ごとに最大100シミュレーションまで向上する。
- さらに、訓練中よりもはるかに長い探索にスケーリングする場合でも、学習したモデルのパフォーマンスは安定したままで、わずかに低下するだけである。
- これは、おそらく囲碁（A）よりもAtariのモデルの不正確さが大きいため、囲碁のスケーリングがはるかに優れていることとは対照的である。
（C）Ms.PacmanのMuZeroフレームワークでのMCTSベースの訓練とQ学習の比較（ネットワークのサイズと訓練量は一定）。
- 最先端のQ学習アルゴリズム R2D2がベースラインとして示されている。
- Q学習の実装は、R2D2と同じ最終スコアに達するが、MCTSベースの訓練と比較して、より遅く改善され、最終パフォーマンスは大幅に低下する。
（D）移動ごとに異なる数のシミュレーションで訓練された異なるネットワークだが、すべての移動ごとに50シミュレーションで評価された。
- 移動ごとのシミュレーションを増やして訓練されたネットワークは改善が速くなり、アブレーション（B）と一致して、移動ごとのシミュレーションを多く使用すると方策の改善が大きくなる。
- 驚くべきことに、Mu.Pacmanで可能な8つの行動すべてをカバーするのに十分な数よりも少ないシミュレーションで、MuZeroは効果的に学習できる。

図S3：MuZero評価（A-B）および方策改善アブレーション（C-D）の詳細

f:id:TadaoYamaoka:20191129000011p:plain

（A-B）図3A-Bの評価の学習モデルの探索木での評価の深さの分布。
- ネットワークは、赤い線で示されているように、5つの仮想ステップで訓練された。
- 濃い青色の線は、ルートからの深さの中央値を示し、濃い色の領域は25〜75パーセンタイル、薄い色の領域は5〜95パーセンタイルを示す。
（C）Ms.Pacmanの方策の改善 - 単一のネットワークが探索ごとに50回のシミュレーションで訓練され、生の方策ネットワークのargmaxに従ってプレイすることを含め、探索ごとに異なる数のシミュレーションで評価される。
- 生の方策ネットワークを介した探索の方策改善効果は、訓練全体ではっきりと見える。
- 探索ありと探索なしのパフォーマンスのこの一貫したギャップは、方策の改善に向けて継続的に更新することにより、MuZeroが活用する方策の改善を強調しており、最適な方策に向けて効率的に前進している。
（D）囲碁の方策の改善 - 単一のネットワークが探索ごとに800回のシミュレーションで訓練され、探索ごとに異なる数のシミュレーションで評価される。
- 囲碁では、長い探索による強さの向上は、Mr.Pacmanよりもはるかに大きく、訓練全体を通じて持続し、AlphaGo Zero *7の以前の結果と一致している。
- 直感的に予想されるように、これは、モデルの恩恵が正確なプランニングの分野で最大となることを示唆している。

Atariでのプランニングのスケーラビリティ

また、すべてのAtariゲームにわたるプランニングのスケーラビリティを調査した（図3Bを参照）。
完全に訓練されたMuZeroを使用して、MCTSをさまざまな数のシミュレーションと比較した。
プランニングによる改善は、おそらくモデルの不正確さが大きいため、囲碁の場合よりも顕著ではない。
探索時間でパフォーマンスはわずかに向上したが、100回程度のシミュレーションで停滞した。
MuZeroは1回のシミュレーション（つまり、方策ネットワークのみに従って移動を選択する場合）でも良好に機能し、訓練の終わりまでに、生の方策が探索の恩恵を内部化することを学習したことを示唆している（図S3Bも参照）。

モデルフリーアルゴリズムとの比較

次に、モデルベースの学習アルゴリズムを、比較可能なモデルフリーの学習アルゴリズムに対してテストした（図3Cを参照）。
MuZeroの訓練目標（式1）をモデルフリーのQ学習目標（R2D2で使用）に置き換え、デュアル価値ヘッドと方策ヘッドをQ関数 $Q\left(\cdot | s_{t}\right)$ を表す単一のヘッドに置き換えた。
その後、探索を使用せずに新しいモデルを訓練および評価した。
Ms.Pacmanで評価した場合、モデルフリーのアルゴリズムはR2D2と同じ結果を達成したが、MuZeroよりも大幅に遅く学習し、はるかに低い最終スコアに収束した。
MuZeroの探索ベースの方策改善ステップは、Q学習で使用される高バイアス、高分散の目標よりも強力な学習信号を提供すると推測される。

訓練中の探索量のスケーラビリティ

MuZeroの学習アルゴリズムの性質をよりよく理解するために、MuZeroの訓練が訓練中に使用する探索の量に対してどのようにスケーリングするかを測定した。
図3Dは、訓練中の動きごとに異なるシミュレーションカウントのMCTSを使用した際のMs.Pacmanのパフォーマンスを示している。
驚くべきことに、以前の研究*8とは対照的に、MuZeroは1動作につき6回のシミュレーションでさえ、効果的な方策を学び、急速に改善した。

驚くべきことに、かつての作業とは対照的に、MuZeroは1動作につき6回（行動数より少ない）のシミュレーションでさえ、効果的な方策を学び、急速に改善した。

より多くのシミュレーションにより、パフォーマンスが大幅に向上した。
各反復中の方策改善の分析については、図S3 CおよびDも参照。

感想

チェス、将棋では、AlphaZeroと同等の強さになっており、囲碁ではAlphaZeroを上回っています。
ただし、チェス、将棋では、AlphaZeroと同等になるのに1.0Mステップかかっているため、AlphaZero（0.7Mステップ）よりもより多くの訓練ステップが必要になるようです。ネットワークのブロック数は20から16と計算量は少なくなっています。
f:id:TadaoYamaoka:20191130223634p:plain

Atariでは、既存のモデルフリーのSOTAアルゴリズム（R2D2）を大幅に上回っています。

プランニング（MCTS）のスケーラビリティは、囲碁では思考時間に対してほぼ線形に伸びています。ただし、AlphaZeroの方がより線形に近く伸びておりスケーラビリティはAlphaZeroの方がよさそうです。

Atariではスケーラビリティは、囲碁ほど伸びていません。囲碁に比べてモデルの不正確さが大きいためと説明されています。
逆にAtariではシミュレーション回数が1回でもR2D2を上回る良好なパフォーマンスがでています。

Mr.Packmanでのモデルフリーアルゴリズムとの比較では、MuZeroが圧倒的に良い結果になっています。
今までモデルベースが使えなかった領域に適用した場合に、効果があるアルゴリズムと言えそうです。

訓練時の探索数については、Mr.Packmanでは訓練時の探索数を増やすほどより改善されるという結果がでています。
行動数よりも少ないシミュレーション回数でも学習するようです。

(続く)

*1:Human Level Control Through Deep Reinforcement Learning | DeepMind

*2:Recurrent Experience Replay in Distributed Reinforcement Learning | DeepMind

*3:[1903.00374] Model-Based Reinforcement Learning for Atari

*4:https://arxiv.org/abs/1802.01561

*5:https://arxiv.org/abs/1710.02298

*6:https://arxiv.org/abs/1909.11583

*7:Mastering the game of Go without human knowledge | Nature

*8:[1806.05780] Surprising Negative Results for Generative Adversarial Tree Search

2019-11-30

リバーシ(オセロ)で深層強化学習

creversi リバーシオセロ強化学習

先日作成した高速なリバーシライブラリを使って、深層強化学習のアルゴリズムをいろいろ試してみたいと思っている。

DQNの実装

将棋でDQNによる強化学習を試したときはまったく学習しなかったので、まずは教師ありでDQNのネットワークが学習できるか試すことにした。
DQNのネットワークは、状態(局面)が入力となり、行動(着手)ごとに行動価値を出力する。
AlphaGoのバリューネットワークのような状態価値ではなく、行動ごとの行動価値を出力するため、価値の学習の方法がAlphaGoとは少し異なる。
f:id:TadaoYamaoka:20191130150316p:plain

エピソードには、状態で取りうるどれか一つの行動しか記録されていないため、損失を計算する行動価値はどれか一つになる。
Pytorchのチュートリアルでは、gatherを使って出力をどれか一つのノードにして損失を計算している。これと同じ方法で実装することにする。

リバーシの場合、行動価値は盤の座標対応する64ノードに対応させる（中央の4マスは実際には着手できないが64とした方が処理の都合がよい）。

入力は、黒と白に対応する2値画像2枚で表す。

ネットワーク構成

3×3フィルタ128の5層のCNNとした。
AlphaGoと同様にパディングを行い、各層で画像サイズが変わらないようにする。
出力層はAlphaGoの方策ネットワークと同様に1×1の畳み込みに位置ごとに異なるバイアスとした。
（ソースはこちら）

教師あり学習

DQNは強化学習でエピソードを作成するが、ここでは強化学習を行わず棋譜データをエピソードとして学習できるか確認を行った。
DQNではQ学習を使用するが、ここではQ学習は行わず、エピソードの終端の報酬を使用して学習を行う。

リバーシの棋譜

GGSから大量の棋譜がダウンロードできる。
棋譜を処理するため、creversiにGGSの棋譜を読み込む機能を実装した。

GGSからダウンロードした棋譜をレーティング2000以上、手数45以上でフィルタリングして、9,831,855局面の学習データを作成した。
（処理に使用したコードはこちら）

学習結果

学習データをすべてリプレイバッファに格納し、ミニバッチ256をランダムにサンプリングして、10万イテレーションの学習を行った。
サンプリング時に1/2の確率で局面を180度回転する処理も行っている。
f:id:TadaoYamaoka:20191130154808p:plain

20,000イテレーション(グラフのx軸200)あたりからlossが横ばいで、学習しているように見えない。
しかし、将棋AIでも価値の学習は、lossが横ばいになる傾向があるので、学習できているかもしれない。

ランダムプレイヤーと対局

lossだけでは学習できているか分からないので、ランダムプレイヤーと対局させてみた。
ランダムプレイヤーは、合法手から一様ランダムに手を選択して、着手する。

学習したモデルを使用するプレイヤーは、局面から行動価値を予測し、最大の行動価値の行動を選択する（グリーディー戦略）。
モデルの出力には、盤の座標に対応する64のノードがあるため、合法手に絞る必要がある。
そのため、gatherを使用して、合法手に対応するインデックスのみ出力するようにした。

ランダムプレイヤーと1000局対局した結果、680勝280敗40分となった。
信頼区間95%の勝率は73.6%～67.9%で、有意にランダムプレイヤーに勝ち越している。

ランダムに対する勝率としては低いように思うが、リバーシでもDQNのネットワークが学習できることが確かめられた。
これで、DQNを強化学習した場合にネットワーク構成が原因で学習できないということはないだろう。

なお、ソフトマックス戦略にした場合、温度0.1でも532勝424敗44分となり、勝率がかなり落ちた。

学習時間

10万イテレーションの学習には、GeForce2080Tiを使用して12時間かかった。

ネットワークサイズを変えて実験

リバーシでは、着手による駒の反転は盤の端から端まで影響するので、直感的には層数が多い方がよさそうなので、層数を10層、フィルタを192にして、1万イテレーション学習してみた。
（ソースはこちら）

ランダムプレイヤーとの1000局対局した結果、766勝196敗38分となった。
少ないイテレーションで、5層CNNよりも良い結果になった。
リバーシを学習するには、ある程度のネットワークサイズが必要そうだ。

次は、教師ありでTD学習(Q学習)を試してみたい。

続き

リバーシ(オセロ)で深層強化学習その２（教師ありQ学習） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その３（DQN） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その４（並列実行） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その５（DDQN） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その６（Dueling Network） - TadaoYamaokaの開発日記
 リバーシ(オセロ)で深層強化学習その７（Prioritized Experience Replay） - TadaoYamaokaの開発日記

2019-11-30

AlphaStarの論文を読むその１２（評価）

AlphaStar 強化学習

評価

AlphaStar Battle.netの評価

AlphaStarエージェントは、StarCraft IIバランスパッチ4.9.3で、MMRレーティングに基づくBlizzardのオンラインマッチメイキングシステムBattle.netで人間に対して評価された。
AlphaStar Finalは、グランドマスターレベル（過去数か月でヨーロッパのサーバ（約90,000人のプレイヤー）のリーグで十分アクティブだった人間プレイヤーの99.8％を超える）と格付けされた。

対戦相手、匿名アカウント、ハードウェア、評価時点

AlphaStarは、実験への参加を選択した対戦相手（大半のプレイヤーが参加した）*1のみと対戦し、匿名のアカウント名を使用し、サイバーフォレスト、カイロスジャンクション、キングスコーブ、ニューリピュニャンの4つのマップで対戦した。
また、人間は少なくとも4つのマップを選択し、匿名のアカウント名で頻繁にプレイする必要がある。
各エージェントは、単一のハイエンドコンシューマGPUで実行された。
訓練中に、教師あり、中間点、最終の3つのポイントで評価した。

教師ありおよび中間点の評価の開始ランク

教師ありおよび中間点の評価のために、各エージェントは新しいランク付けされていないアカウントで開始した。

MMR

それらのMMRは、人間と同様にBattle.netで更新された。
教師ありおよび中間点の評価では、それぞれ30ゲームと60ゲームをプレイした。
まだ増加していたが、50ゲーム後に匿名性の制約が損なわれたため、中間点の評価は中止された。

複数のアカウントでのMMRの推定

Battle.netの最終評価では、複数のアカウントを使用してゲームを並列化し、識別を回避した。
私たちのアカウントのMMRは、結合して推定された中間点MMRの分布からランダムにシードされた。
その結果、Battle.netで提供される反復MMR推定を使用しなくなった。代わりにブリザードが提供する基本的な確率モデルを使用した：不確実性uの評価rと不確実性 $u_i \in[0.1,1.0$ ]の対戦相手の評価 $r_i$ が与えられたとき、結果 $o_i \in[-1,1$ の確率は、

$\displaystyle \mathbb{P}[o_{i}=1 | r, u, r_{i}, u_{i}] \\ =1-\mathbb{P}[o_{i}=-1 | r, u, r_{i}, u_{i}]=\Phi\left(\frac{r-r_{i}}{400 \sqrt{2+u^{2}+u_{i}^{2}}}\right) \approx \Phi\left(\frac{r-r_{i}}{568}\right)$

ここで、 $\Phi$ は標準のガウス分布のCDFであり、Battle.netの最小不確実性を使用した場所 $u = u_i = 0.1$ である。
対戦結果のi.i.d.およびMMRの均一な事前分布の仮定で、評価を

$\displaystyle \operatorname{argmax}_{\mathrm{r} \in \mathbb{N}} \mathbb{P}[\mathrm{r} | \text { results }] \\ =\operatorname{argmax}_{\mathrm{r} \in \mathbb{N}} \mathbb{P}[\mathrm{results} | \mathrm{r}] \mathrm{U}(\mathrm{r})=\operatorname{argmax}_{\mathrm{r} \in \mathbb{N}} \prod_{i=1}^{N} \mathbb{P}[\mathrm{o}_{\mathrm{i}} | \mathrm{r}, \mathrm{r}_{\mathrm{i}}]$

として計算できる。

MMR推定値

Battle.netが報告した平均MMRは6336でしたが、プロのStarCraft IIプレイヤーであるDario “TLO” Wünschの最新の200試合でMMR計算を検証したところ、MMR推定値は6334でした。

StarCraftデモンストレーションでの評価

2018年12月、私たちはStarCraft IIプロプレイヤーGrzegorz “MaNa” KominczとDario “TLO” Wünschに対して5つのゲームシリーズを2回プレイしましたが、TLOは彼がプロとしてプレイするのと同じStarCraft II種族でプレイしなかった。
これらのゲームは、AlphaStarの別の予備バージョンで行われた*2。
特に、エージェントはカメラが制限されておらず、また行動の頻度が制限されておらず、1つのマップに1つのStarCraft II種族で対戦していた。
AlphaStarは両方の5ゲームシリーズで10ゲームすべてに勝利したが、初期のカメラプロトタイプはMaNaに対するフォローアップゲームを失った。

感想

最終的な結果は、グランドマスターレベル(人間の上位99.8%)に達しています。

人間と同じ条件で強さを測定するための測定条件の詳細が述べられています。
人間にはAlphaStarだとわからないように匿名アカウントでプレイされています。
中間点の評価では途中で特定されてしまったようです。

人間との対戦では、ハイエンドコンシューマGPU1枚で実行されています。
探索を行っていないので、それほどGPU性能は必要なさそうです。

(続く)

*1:DeepMind Research on Ladder — StarCraft II — Blizzard News

*2:AlphaStar: Mastering the real-time strategy game StarCraft II | DeepMind

2019-11-30

AlphaStarの論文を読むその１１（インフラ）

AlphaStar 強化学習

インフラ

リーグを訓練するために、多数のStarCraft II対戦を並行して実行し、それらのゲームのデータに基づいてエージェントのパラメータを更新する。
これを管理するために、さまざまなタイプの分散ワーカーで非常にスケーラブルな訓練セットアップを開発した。

ハードウェア

リーグのすべてのトレーニングエージェントに対して、16,000のStarCraft IIの並列対戦と16のアクタータスク（それぞれ8つのTPUコア*1を備えたTPU v3デバイスを使用）を実行して、推論を実行する。
ゲームインスタンスはプリエンプティブCPU（それぞれ28の物理コアを備えた150のプロセッサとほぼ同等）上で非同期に進行するが、エージェントステップの要求はTPUを効率的に使用するために動的にバッチにまとめられる。
バッチ推論にTPUを使用すると、以前の研究*2 *3よりも大幅に効率が向上する。

訓練パイプライン

アクターは、ネットワークを介して中央の128コアTPUラーナーワーカーに観測、アクション、および報酬のシーケンスを送信し、トレーニングエージェントのパラメーターを更新する。
受信したデータはメモリにバッファリングされ、2回再生される。
ラーナーワーカーは、大きなバッチで同期更新を実行する。
各TPUコアは、4つのシーケンスのミニバッチを処理し、合計バッチサイズは512である。
ラーナーは、毎秒約50,000エージェントステップを処理する。
アクターは、ラーナーからのパラメーターのコピーを10秒ごとに更新する。

コーディネーター

このアクターとラーナーのセットアップの12の個別のコピーをインスタンス化する：各StarCraft種族に対して、1つのメインエージェント、1つのメインエクスプロイト、2つのリーグエクスプロイトエージェント
ある中央コーディネーターは、利得行列(payoff matrix)の推定値を維持し、要求に応じて新しい対戦をサンプリングし、メインおよびリーグのエクスプロイトをリセットする。
追加の評価ワーカー（CPUで実行）を使用して、利得(payoff)の見積もりを補完する。
訓練セットアップの概要については、拡張データの図6を参照。

拡張データ図6|トレーニングインフラストラクチャ|リーグ全体のトレーニング設定

f:id:TadaoYamaoka:20191125083339p:plain

感想

アクターは並列実行を行い、軌跡をラーナーに送信して、ラーナーは同期でパラメータの更新を行うという仕組みになっています。
A2Cの並列処理に近い構成だと思います。

アクターの推論は、1つのサーバ内の並列実行している対戦のステップをまとめてバッチで処理を行っています。
私が作成しているdlshogiの自己対局でも似たような処理を行っています。

リプレイバッファを使用していますが、再生回数は2回と少なめです。
50万ステップ分ごとにパラメータの更新を行っており、AlphaZeroに比べるとパラメータの更新頻度は高いようです。

(続く)

*1:[1704.04760] In-Datacenter Performance Analysis of a Tensor Processing Unit

*2:[1802.01561] IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures

*3:[1807.01281] Human-level performance in first-person multiplayer games with population-based deep reinforcement learning

2019-11-30

AlphaStarの論文を読むその１０（リーグ構成）

AlphaStar 強化学習

リーグ構成(Populating the League)

訓練中、新しいプレイヤーを作成するためにスナップショットが作成されたときの訓練対象の対戦相手の分布と、教師ありパラメーターにリセットされる確率のみが異なる3つのエージェントタイプを使用した。

メインエージェント

メインエージェントは、35％SP、50％PFSPの割合でリーグの過去のすべてのプレイヤーに対して訓練され、さらに15％のPFSPマッチは、エージェントがもはやメインエクスプロイトを打ち負かすことができなくなったメインプレイヤー(forgotten players)と対戦する。
forgotten playersや強力なエクスプロイターが存在しない場合、代わりに15％がセルフプレイに使用される。
$2 \cdot 10^9$ ステップごとに、エージェントのコピーが新しいプレイヤーとしてリーグに追加される。
メインエージェントはリセットされない。

リーグエクスプロイター

リーグエクスプロイターはPFSPを使用して訓練され、凍結されたコピーは、ゲームの70％以上で、または $2 \cdot 10^9$ ステップのタイムアウト後に、リーグ内のすべてのプレイヤーを倒したときにリーグに追加される。
この時点で、エージェントが教師ありパラメーターにリセットされる確率は25％である。
直観的には、リーグエクスプロイトがリーグ内のグローバルな盲点を識別しているということである（リーグ内のプレイヤーは誰も負けることはできないが、それ自体は必ずしも堅牢ではない）。

メインエクスプロイター

メインエクスプロイターはメインエージェントと対戦する。
半分の時間で、現在の勝率が20％未満の場合、エクスプロイターは、メインエージェントによって作成されたプレイヤーに対して $𝑓_{\text {var }}$ の重み付けでPFSPを使用する。
これは、学習を促進するカリキュラムを形成する。
それ以外の場合、十分な学習シグナルがあり、現在のメインエージェントと対戦する。
このエージェントは、ゲームの70％以上で3つのメインエージェントが全員敗北したとき、または $4 \cdot 10^9$ ステップのタイムアウト後にリーグに追加される。
その後、教師ありパラメーターにリセットされる。
メインエクスプロイターはメインエージェントの弱点を特定し、その結果、それらをより強固にする。

詳細については、補足資料の擬似コードを参照。

感想

3種類のエージェントが存在し、それぞれに役割が設定されています。

メインエージェントはあらゆる弱点に対処できるエージェントで、エクスプロイターは弱点を突くことに特化したエージェントです。
エクスプロイターには2種類あり、リーグ全体の弱点を見つけるリーグエクスプロイターと、メインエージェントの弱点を見つけるメインエクスプロイターです。

それぞれ条件に達するとスナップショットが作成されて、リーグに追加されていきます。
エクスプロイターは、その際パラメータが初期化される場合があります。
そうすることで、特定の戦略を見つけたエージェントがその戦略を忘れずに残り続け、また新たな戦略を見つけられるエージェントが継続して生まれることになるので、メインエージェントがより堅牢になるという仕組みのようです。

リーグのエージェントが増え続けることになりますが、優先順位付きFictitious Self-Playを使用しているので、無駄な対戦相手が選ばれないようになっています。

(続く)