2019-11-21

MuZeroの論文を読む（概要、導入、先行研究）

MuZero 強化学習

MuZeroの論文を読んでいきます。
基本的にだらだら訳していくだけです。
途中で感想を書いていきます。

概要

プランニング能力を備えたエージェントを構築することは、人工知能の追求における主な課題の1つである。
ツリーベースのプランニング方法は、完全なシミュレーターが利用できるチェスや囲碁などの挑戦的なドメインで大成功を収めている。
ただし、実際の問題では、環境を支配するダイナミクスはしばしば複雑で未知である。
この研究では、ツリーベースの探索と学習モデルを組み合わせることにより、基礎となるダイナミクスの知識がなくても、挑戦的で視覚的に複雑な領域で超人的なパフォーマンスを実現するMuZeroアルゴリズムを紹介する。
MuZeroは、反復的に適用されたときに、プランニングに最も直接関係する量（報酬、行動選択方策、および価値関数）を予測するモデルを学習する。
モデルベースのプランニングアプローチが過去に苦労してきた57種類のAtariゲーム(AI技術をテストするための標準的なビデオゲーム環境)で評価したとき、新しいアルゴリズムは最先端を達成した。
ゲームルールの知識がなくても、囲碁、チェス、将棋で評価した場合、MuZeroは、ゲームルールが提供されたAlphaZeroアルゴリズムの超人的なパフォーマンスと一致した。

導入

先読み探索に基づくプランニングアルゴリズムは、人工知能で顕著な成功を収めている。
人間の世界チャンピオンは、チェッカー、チェス、囲碁、ポーカーなどの古典的なゲームで敗北しており、プランニングアルゴリズムは、物流から化学合成までのアプリケーションで現実世界に影響を与えた。
ただし、これらのプランニングアルゴリズムはすべて、ゲームのルールや正確なシミュレーターなどの環境のダイナミクスに関する知識に依存しており、ロボット、産業用制御、インテリジェントアシスタントなどの実世界のドメインへ直接適用する妨げになっている。

モデルベースとモデルフリー

モデルベースの強化学習（RL）は、まず環境のダイナミクスのモデルを学習し、次に学習したモデルに関してプランニングすることにより、この問題に対処することを目的としている。
通常、これらのモデルは、真の環境状態の再構築、または一連の完全な観測に焦点を合わせている。
ただし、Atari 2600ゲームなどの視覚的な領域では、従来の研究は最先端からはほど遠いままである。
代わりに、最も成功した方法はモデルフリーRLに基づいている。
つまり、環境との相互作用から最適な方策や価値関数を直接推定する。
ただし、モデルフリーアルゴリズムは、チェスや囲碁などの正確で洗練された先読みを必要とする分野では、最先端とはかけ離れている。

MuZero

この論文では、視覚的に複雑なドメインセットであるAtari 2600で最先端のパフォーマンスを達成しながら、チェス、将棋、囲碁などの精密なプランニングタスクで超人的なパフォーマンスを維持する、モデルベースRLへの新しいアプローチであるMuZeroを紹介する。
MuZeroは、AlphaZeroの強力な探索および探索ベースの方策反復アルゴリズムに基づいているが、学習モデルを訓練手順に組み込む。
MuZeroは、AlphaZeroを、シングルエージェントドメインや中間タイムステップで報酬がないドメインなど、より広範な環境に拡張する。

アルゴリズムの概要

アルゴリズムの主なアイデア（図1に要約）は、プランニングに直接関連する将来の側面を予測することである。
モデルは入力として観測（例：囲碁の盤面やAtariの画面）を受け取り、それを隠れ状態に変換する。
隠れ状態は、前の隠れ状態と仮想の次の行動を受け取る再帰プロセスによって繰り返し更新される。
これらのすべてのステップで、モデルは方策（プレイする手など）、価値関数（予測される勝者など）、および即時報酬（手をプレイすることで獲得したポイントなど）を予測する。
モデルは、これら3つの重要な量を正確に推定することを唯一の目標として、エンドツーエンドで訓練され、探索によって生成される方策と価値の推定値と観測される報酬を一致させるようにする。
元の観測を再構築するために必要なすべての情報を取得するための隠れ状態に対する直接的な制約や要件はなく、モデルが維持および予測しなければならない情報量を大幅に削減する。
また、隠れ状態が環境の未知の真の状態に一致する要件もない。また、状態のセマンティクスに対するその他の制約もない。
代わりに、隠れ状態は、現在および将来の価値と方策の予測に関連するあらゆる方法で状態を表すことができる。
直感的には、エージェントは、最も正確なプランニングにつながるルールまたはダイナミクスを内部で生み出すことができる。

f:id:TadaoYamaoka:20191121214604p:plain

先行研究

強化学習は、モデルベースとモデルフリーの2つの主要なカテゴリに分類できる。
モデルベースのRLは、中間ステップとして、環境のモデルを構築する。
古典的に、このモデルは、次の状態を予測する状態遷移モデルと、その遷移中に予想される報酬を予測する報酬モデルという2つのコンポーネントで構成されるマルコフ決定プロセス（MDP）で表される。
モデルは通常、選択された行動、またはオプションなどの時間的に抽象的な動作を条件とする。
モデルが構築されると、価値反復やモンテカルロ木検索（MCTS）などのMDPプランニングアルゴリズムを適用して、MDPの最適な価値または最適な方策を計算するのは簡単である。
大規模または部分的に観測された環境では、アルゴリズムは最初にモデルが予測する状態表現を構築する必要がある。
表現学習、モデル学習、およびプランニングのこの3者間の分離は、エージェントが効果的なプランニングのための表現またはモデルを最適化できないため、潜在的に問題があり、その結果、たとえばプランニング中にモデリング誤差が悪化する可能性がある。

モデルベースRL

モデルベースRLのための一般的なアプローチは、ピクセルレベルで観測ストリームを直接モデリングすることに焦点を当てている。
深い確率的なモデルは、複合誤差の問題を緩和する可能性があるという仮説が立てられている。
ただし、ピクセルレベルの粒度でのプランニングは、大規模な問題では計算上扱いにくい。
他の方法では、ピクセルレベルで観測ストリームを再構築する*1 *2、または将来の潜在状態を予測するのに十分な潜在状態空間モデルを構築する*3 *4。
これにより、より効率的なプランニングが容易になるが、モデル容量の大部分は無関係な可能性のある詳細に集中する。
これらの従来の方法はいずれも、Atariなどの視覚的に複雑なドメインで効果的なプランニングを容易にするモデルを構築していない。結果は、データ効率の面でも、適切に調整されたモデルフリーの方法の方が優れている*5。

モデルベースのRLの新しいアプローチ

モデルベースのRLへのまったく異なるアプローチが最近開発され、価値関数の予測にエンドツーエンドで焦点を当てている*6。
これらの方法の主なアイデアは、抽象MDPでのプランニングが実際の環境でのプランニングと同等になるように、抽象MDPモデルを構築することである。
この等価性は、価値の等価性を確保することで実現される。つまり、同じ実際の状態から開始して、抽象MDPを介した軌跡の累積報酬が実際の環境での軌跡の累積報酬と一致するということである。

predictron

predictron*7は、（行動なしで）価値を予測するための価値等価モデルを最初に導入した。
基礎となるモデルはまだMDPの形式をとっているが、その遷移モデルが環境内の実際の状態に一致する必要はない。
代わりに、MDPモデルはディープニューラルネットワークの隠れ層と見なされる。
拡張されたMDPは、報酬の予想累積合計が実際の環境に関する予想値と一致するように（たとえば、TD学習によって）訓練される。

価値等価モデルの拡張

価値等価モデルは、その後、（行動付き）価値の最適化に拡張された。
TreeQN*8は、抽象MDPモデルを学習し、そのモデル（ツリー構造のニューラルネットワークで表される）での木探索が最適価値関数に近似するようにする。
価値反復ネットワークはローカルMDPモデルを学習し、そのモデル（畳み込みニューラルネットワークで表される）での価値反復が最適価値関数を近似するようにする。
価値予測ネットワーク*9は、おそらくMuZeroに最も近い先行研究であり、実際の行動に基づいたMDPモデルを学習する。
つまり、拡張されたMDPは、単純な先読み探索によって生成された実際の行動シーケンスを条件とする報酬の累積合計が実際の環境と一致するように訓練される。
MuZeroとは異なり、方策の予測はなく、探索では価値の予測のみが使用される。

感想

AphaZeroでは、強化学習で行動を選択する際に、MCTSで環境（遷移確率）をモデル化していました。これはモデルベースと呼ばれる手法です。
Atariゲームのような視覚的に複雑な領域や、現実世界のような複雑なドメインでは、環境がモデリングできないためモデルフリーの手法が用いられています。
AlphaStarでも、行動空間が広すぎるため先読みができないため、モデルフリーの手法がとられていました。
しかし、囲碁や将棋のように正確な先読みが必要な領域ではモデルフリーの手法では、パフォーマンスがでないことが述べられています。

Atariのような視覚的に複雑な領域でもモデルベースのアプローチを適用できるようにしたというのが、この論文の主旨のようです。
アルゴリズムの詳細は、この後読んでいきます。
(続く)

*1:[1502.02251] From Pixels to Torques: Policy Learning with Deep Dynamical Models

*2:[1506.07365] Embed to Control: A Locally Linear Latent Dynamics Model for Control from Raw Images

*3:[1809.01999] Recurrent World Models Facilitate Policy Evolution

*4:[1906.02736] DeepMDP: Learning Continuous Latent Space Models for Representation Learning

*5:[1906.05243] When to use parametric models in reinforcement learning?

*6:[1612.08810] The Predictron: End-To-End Learning and Planning

*7:[1612.08810] The Predictron: End-To-End Learning and Planning

*8:[1710.11417] TreeQN and ATreeC: Differentiable Tree-Structured Models for Deep Reinforcement Learning

*9:[1707.03497] Value Prediction Network

2019-11-21

AlphaStarの論文を読むその７（アーキテクチャその３）

AlphaStar

アーキテクチャ詳細の続きです。
ベースラインと損失に関する部分です。

勝敗ベースライン(Winloss Baseline)

入力：prev_state, scalar_features, opponent_observations, cumulative_score, action_type, lstm_output
出力：
- winloss_baseline : 「action_type」引数に使用されるベースライン値
ベースラインは、最初にベースラインで使用されるさまざまな観測値を収集して前処理する。使用される観測は、（そのまま使用される「lstm output」を除いて）スカラーエンコーダーと同じ方法で処理される「lstm_output」、「agent_statistics」、「unit_counts_bow」、「upgrades」、「beginning_build_order」、および「scalar_features」の「cumulative_statistics」（アップグレードとスペルの効果を除く）である。値の1Dテンソルとしての「cumulative_score」は、「agent_statistics」のように処理される。ベースラインは「opponent_observations」からこれらと同じ観測を抽出する。これらの特徴量はすべて連結されて、「action_type_input」を生成し、サイズ256のリニアを通過し、256の隠れユニットとレイヤー正規化を伴う16のResBlocksを通過し、ReLUを通過し、1つの隠れユニットを含む全結合層を通過する。このベースライン値は( (2.0 / PI) * atan((PI / 2.0) * baseline) )によって変換され、ベースライン値「winloss_baseline」として使用される。

Winloss Split VTrace Actor-Critic, TDLambda, UpGo Loss

入力：action_type_logits, delay_logits, queued_logits, units_logits, target_unit_logits, target_location_logits, winloss_baseline
Winloss報酬はゲームの終了時にのみ付与され、エージェントがゲームに勝った場合は+1、それ以外の場合は-1である。
action_type引数、遅延、および他のすべての引数は、個別の（「分割」）VTrace Actor-Critic損失を使用して個別に更新される。これらの更新の重みは1.0と見なす。 action_type、delay、およびその他の引数も同様に、UPGOを使用して、VTrace Actor-Critic損失と同じように、相対的な重み1.0で個別に更新される。ベースラインは、TD(λ)を使用して更新され、相対的な重みは10.0、またlambda 0.8である。

ビルド順序ベースライン(Build Order Baseline)

Winloss Baselineと同様だが、「cumulative_statistics」にはアップグレードとスペルの効果が含まれる。

Build Order Split VTrace Actor-Critic, TDLambda Loss

ビルド順序の報酬は、真（人間のリプレイ）のビルド順序とエージェントのビルド順序の間の負のレーベンシュタイン距離です。ただし、ユニットのタイプが同じ場合は $1_{(a != b)}$ の代わりに $lev_{a, b}(i - 1, j - 1) + 1_{(a != b)}$ となる。コストは、真のビルドされたエンティティとエージェントのエンティティ間の距離の2乗であり、[0,0.8]以内に再スケーリングされる。2つ以上のゲートウェイが離れている場合、最大0.8になる。（何か新しいものを建築したため）エージェントのビルド順序が変更されるたびに、報酬が与えられる。ビルドされていないユニット（自動砲塔や幼虫など）、労働者ユニット、補給施設のビルド順序はスキップされる。
人間の探査（ビルドユニット、アップグレード、および効果）のリプレイはゲームの開始時に選択され、エージェントが見るゲームと同じホーム種族およびアウェイ種族を伴う同じマップになる。
更新はWinlossと同様に計算されるが、UPGOを使用せず、ビルド順序ベースラインを使用して適用され、相対重み付けは方策に4.0、ベースラインに1.0が適用される。

ビルドユニットベースライン(Built Units Baseline)

勝敗ベースラインと同様

Built Units Split VTrace Actor-Critic, TDLambda Loss

ビルドされたユニットの報酬は、人間のリプレイでビルドされたエンティティとエージェントがビルドしたエンティティ間のハミング距離である。 8分後、報酬に0.5が乗算される。 16分後、報酬にさらに0.5が乗算される。 24分後以降は報酬がない。
更新はWinlossと同様に計算されるが、UPGOがない場合、ビルドユニットベースラインを使用して適用され、相対重み付けは方策に6.0、ベースラインに1.0が適用される。

アップグレードベースライン(Upgrades Baseline)

勝敗ベースラインと同様だが、「cumulative_statistics」にはアップグレードのみが含まれる点が異なる。

Upgrades Split VTrace Actor-Critic, TDLambda Loss

ビルドされたユニットの報酬は、人間のリプレイのアップグレードとエージェントが調査したアップグレードとのハミング距離である。 8分後、報酬に0.5が乗算される。 16分後、報酬にさらに0.5が乗算される。 24分後以降は報酬がない。
更新は、UPGOを使用せず、アップグレードベースラインを使用して適用されることを除いて、Winlossと同様に計算され、相対重み付けは方策に6.0、ベースラインに1.0が適用される。

エフェクトベースライン(Effects Baseline)

勝敗ベースラインと同様だが、「cumulative_statistics」にはエフェクトのみが含まれる。

Effects Split VTrace Actor-Critic, TDLambda Loss

ビルドされたユニットの報酬は、人間のリプレイのエフェクトとエージェントが作成したエフェクト間のハミング距離である。 8分後、報酬に0.5が乗算される。 16分後、報酬にさらに0.5が乗算される。 24分後以降は報酬がない。
更新はWinlossと同様に計算されるが、UPGOを使用せず、エフェクトベースラインを使用して適用され、相対重み付けは方策に6.0、ベースラインに1.0が適用される。

エントロピー損失(Entropy Loss)

すべてのアクション引数に重み1e-4のエントロピー損失があり、特定のアクションタイプに対してどの引数が可能かによってマスクされている。

蒸留損失(Distillation Loss)

同じ観測が与えられたファインチューニングされた教師あり方策の出力ロジットと一致させるため、すべてのアクション引数に2e-3の重みで蒸留損失がある。
軌跡が「cumulative_statistics」に条件付けられていた場合、ゲームの最初の4分間のアクションタイプロジットに重量1e-1の追加の蒸留損失がある。

感想

探索に人間のリプレイを活用するために、報酬と方策の損失の2か所に人間のリプレイの統計が使用されています。
報酬は、ゲームの序盤により高く与えられています。
RTSゲームには序盤の定跡のようなものがあって、例えばAge of Empiresでは村人はまずガゼルを見つけて狩って、食料が貯まったら村人を生産してといった効率的な手順が確立されています。初心者はまずそれを覚えて練習するということをします。
序盤のビルド順序に人間のリプレイからの報酬を与えているのは、それと同じことをしていると思われます。
その手順自体を強化学習自身で発見できないものかと思いますが、まだできないのが現状のようです。

アーキテクチャ詳細は以上です。
(続く)

2019-11-17

AlphaStarの論文を読むその６（アーキテクチャその２）

AlphaStar

アーキテクチャ詳細の続きです。

コア(Core)

入力：prev_state, embedded_entity, embedded_spatial, embedded_scalar
出力：
- next_state : 次のステップのLSTM状態
- lstm_output : LSTMの出力
コアは、「embedded_entity」、「embedded_spatial」、および「embedded_scalar」を単一の1Dテンソルに連結し、そのテンソルを「prev_state」と一緒に、サイズ384の3つの隠れ層を持つLSTMに送る。投影(projection)は使用されない。ゲートにレイヤー正規化を適用する。 LSTMの出力が、このモジュールの出力となる。

アクションタイプヘッド(Action Type Head)

入力：lstm_output, scalar_context
出力：
- action_type_logits : 各アクションを実行する確率に対応するロジット
- action_type : action_type_logitsからサンプリングされたaction_type
- autoregressive_embedding : 「lstm_output」と以前にサンプリングされたすべての引数からの情報を結合する埋め込み。引数がサンプリングされる順序は、ネットワーク図（拡張データ図3）を参照

f:id:TadaoYamaoka:20191106084710p:plain

アクションタイプヘッドは、「lstm_output」をサイズ256の1Dテンソルに埋め込み、それぞれサイズ256のレイヤー正規化で16個のResBlocksに渡し、ReLUを適用する。出力は、「scalar_context」によってゲーティングされる「GLU」を介して、可能なアクションタイプごとに1つのロジットを持つテンソルに変換される。「action_type」は、温度0.8の多項ロジットからサンプリングされます。ここで、教師あり学習中は、「action_type」が人間のアクションタイプの正解データとなり、温度は1.0である（他のすべての引数についても同様）。
次に、最初にReLUとサイズ256の全結合層を「action_type」のワンホットに適用し、「scalar_context」によってゲーティングされた「GLU」を介してサイズ1024の1Dテンソルに投影することにより、「autoregressive_embedding」が生成される。その投影は、「lstm_output」の別の投影に追加され、「scalar_context」によってゲーティングされたサイズ1024の1Dテンソルに「autoregressive_embedding」が生成される。

遅延ヘッド(Delay Head)

入力：autoregressive_embedding
出力：
- delay_logits : 各遅延の確率に対応するロジット
- delay : サンプリングされた遅延
- autoregressive_embedding : 「lstm_output」と以前にサンプリングされたすべての引数からの情報を結合する埋め込み。引数がサンプリングされる順序は、ネットワーク図（拡張データ図3）を参照
「autoregressive_embedding」は、サイズ128（ゲームステップで要求される遅延ごとに1つ）を持つ「delay_logits」に埋め込まれる前に、ReLUで2層（それぞれサイズ256）の線形ネットワークを使用してデコードされる。「delay」は多項ロジットを使用して「delay_logits」からサンプリングされるが、他のすべての引数とは異なり、サンプリングの前に「delay_logits」に温度は適用されない。「action_type」と同様に、「delay」はReLUを含む2層（それぞれサイズ256）の線形ネットワークを介してサイズ1024の1Dテンソルに投影され、「autoregressive_embedding」に追加される。

キューヘッド(Queued Head)

入力：autoregressive_embedding, action_type, embedded_entity
出力：
- queued_logits : キューイングする確率とキューイングしない確率に対応するロジット
- autoregressive_embedding : 「lstm_output」と以前にサンプリングされたすべての引数からの情報を結合する埋め込み。引数がサンプリングされる順序は、ネットワーク図（拡張データ図3）を参照
キューヘッドは遅延ヘッドと似ているが、サンプリング前に0.8の温度がロジットに適用され、「queued_logits」のサイズは2（キューイングとキューイングなし）である。選択された「action_type」に対してキューイングが不可能な場合、投影された「queued」は「autoregressive_embedding」に追加されない。

ユニット選択ヘッド(Selected Units Head)

入力：autoregressive_embedding, action_type, entity_embeddings
出力：
- units_logits : 各ユニットを選択する確率に対応するロジット。可能な64ユニットの選択ごとに繰り返される。
- units : このアクションのために選択されたユニット。
- autoregressive_embedding : 「lstm_output」と以前にサンプリングされたすべての引数からの情報を結合する埋め込み。引数がサンプリングされる順序は、ネットワーク図（拡張データ図3）を参照
該当する場合、ユニット選択ヘッドはまず、「action_type」を受け入れることができるエンティティタイプを決定し、最大でユニットタイプの数に等しいそのタイプのワンホットを作成し、サイズ256の全結合層とReLUに渡す。これは、このヘッドでは「func_embed」と呼ばれる。
また、ユニットを選択できるマスクを計算し、存在するすべてのエンティティ（敵ユニットを含む）を選択できるように初期化する。
次に、32チャンネルとカーネルサイズ1の1D畳み込みを介して「entity_embeddings」を供給することにより、各エンティティに対応するキーを計算し、ユニットの選択終了に対応する新しい変数を作成する。
次に、最大64ユニットを選択するために繰り返され、ネットワークは「autoregressive_embedding」をサイズ256の全結合層に渡し、「func_embed」を追加し、ReLUとサイズ32の全結合層に組み合わせを渡す。結果は、クエリを取得するために、サイズが32で初期状態がゼロのLSTMに送られる。エンティティキーはクエリで乗算され、マスクと温度0.8を使用してサンプリングされ、選択するエンティティが決定される。そのエンティティは、将来の反復で選択できないようにマスクされる。選択されたエンティティのワンホットの位置にキーが乗算され、エンティティ全体の平均が減らされ、サイズ1024の全結合層を通過し、後続の反復のために「autoregressive_embedding」に追加される。最後の「autoregressive_embedding」が返される。「action_type」にユニットの選択が含まれない場合、このヘッドは無視される。

ターゲットユニットヘッド(Target Unit Head)

入力：autoregressive_embedding, action_type, entity_embeddings
出力：
- target_unit_logits : ユニットをターゲットとする確率に対応するロジット
- target_unit : サンプリングされたターゲットユニット
「func_embed」は、ユニット選択ヘッドと同じように計算され、同じ方法でクエリに使用される（サイズ256の全結合層を介して渡される「 autoregressive_embedding」の出力に追加される）。次に、クエリはReLUとサイズ32の全結合層を介して渡され、クエリはユニット選択ヘッドと同じ方法で作成されたキーに適用され、「target_unit_logits」を取得する。「target_unit」は、温度0.8の多項ロジットを使用して「target_unit_logits」からサンプリングされます。ここで、これは2つの終端引数の1つであるため（もう一つはロケーションヘッド。ターゲットユニットとターゲットロケーションはどちらもアクションがないため）、「autoregressive_embedding」を返さないことに注意する。

ロケーションヘッド(Location Head)

入力：autoregressive_embedding, action_type, map_skip
出力：
- target_location_logits : 各場所をターゲットとする確率に対応するロジット
- target_location : サンプリングされたターゲットの場所
「autoregressive_embedding」は、4つのチャネルで「map_skip」（マップ情報が1D埋め込みに変更される直前）の最後のスキップと同じ高さ/幅になるように変更され、2つはチャネル次元に沿って連結され、ReLUを介して渡され、128チャネルとカーネルサイズ1の2D畳み込みを通過してから、別のReLUを通過する。次に、3Dテンソル（高さ、幅、チャネル）は、「autoregressive_embedding」でゲートされ、「map_skip」の要素を使用して、128チャネル、カーネルサイズ3、FiLMの一連のゲート付きResBlocksを通過します。順番は最後のResBlockスキップが最初になる。その後、カーネルサイズ4およびチャンネルサイズ128、64、16、1の一連の転置2D畳み込みのそれぞれによって2倍にアップサンプリングされる（128 x 128入力から256 x 256ターゲットロケーション選択にアップサンプリングされる）。これらの最終的なロジットは、実際のターゲット位置を取得するために、温度0.8でフラット化およびサンプリング（建築アクションのためのカメラの外側など、「action_type」を使用して無効な場所をマスク）する。

感想

初期の論文では、アクションの引数はそれぞれ別に出力してchain ruleを適用していましたが、今回はアクションタイプの引数は、ネットワークで表現されています。
選択したアクションタイプが埋め込みにされて、次の引数選択の入力となり、その出力も埋め込みに追加されて、次の引数に渡されています。
アクションの引数のネットワーク構成には、MLP、ポインターネットワーク、アテンション、Deconv ResNetが引数に応じて使われています。
StarCraftくらいに操作が複雑になると、それに応じた複雑な方策の表現が必要になっています。

アーキテクチャ詳細の方策に関する部分は以上です。残りはバリューネットワークに関する部分です。

2019-11-15

高速なPythonのリバーシ(オセロ)ライブラリ

リバーシ C++ SIMD Python

将棋で強化学習のアルゴリズムをいろいろ試そうとしたが、DQNが全く学習しないので、もう少し簡単なゲームを先に試そうと思う。
ということで、リバーシ(オセロ)で試すことにした。

Pythonで使えるリバーシのライブラリがないか探したが良さそうなのが見つからなかったので、自分で作ることにした。
石をひっくり返す処理をPythonのfor文で実装すると遅くなることが予測できるので、cshogiと同じようにC++で実装して、Pythonから呼び出す形式にした。

ビットボードの実装

C++でビットボードを使って高速に実装する方法について調べたところ、SIMD(AVX2とBMI)を使った実装が公開されていたので流用させてもらうことにした。
実装の詳細は、以下のページで解説されている。
オセロの着手可能位置生成【ビット演算テクニック Advent Calendar 2016 23日目】 - prime's diary
オセロの終盤ソルバーを100倍以上高速化した話

Visual C++とGCC対応

上記のコードはインテルコンパイラ向けに作られていたので、Visual C++とGCCで動作するように移植を行った。

GCCは、_bittest64などのx64のCPU命令の組み込み関数が用意されていないので、ビット演算で実装する必要があった。
SIMD命令も一部用意されていないものがあったので、以下のようにマクロ定義で対応した。

#define _mm_setr_epi64x(v0, v1) _mm_set_epi64x((v1), (v0))
#define _mm256_set_m128i(v0, v1)  _mm256_insertf128_si256(_mm256_castsi128_si256(v1), (v0), 1)
#define _mm256_setr_m128i(v0, v1) _mm256_set_m128i((v1), (v0))

Pythonのインターフェース

cshogiの元にしたpython-shogiに近い形で実装した。
将棋では手を戻す操作を可能にしているが、オセロの場合は盤面は128bitで表現できるため、盤面のコピーで対応した方が早いため、手を戻す操作は実装していない。

以下は、ランダムに手を選んで終局までプレイする例である。

from creversi import *
import random
board = Board()
while not board.is_game_over():
    print(board)
    print('black' if board.turn else 'white')
    moves = list(board.legal_moves)
    if len(moves) == 0:
        board.move_pass()
        print('pass')
    else:
        move = random.choice(moves)
        print(move_to_str(move))
        board.move(move)

盤面はprint()で以下のように表示できる。

 |abcdefgh
-+--------
1|........
2|........
3|........
4|...ox...
5|...xo...
6|........
7|........
8|........

cshogiと同じようにSVGで表示する機能もそのうち実装したい。

creversi

ライブラリ名は「creversi」とした。
ソースはGitHubで公開した。
github.com

このライブラリを使って、DQNなどのアルゴリズムを試してみるつもり。
強化学習に必要な機能は随時追加する予定。

2019-11-14

AlphaStarの論文を読むその５（アーキテクチャ）

しばらく空きましたが、続きです。
アーキテクチャは長いので途中までです。

アーキテクチャ

AlphaStarの方策は関数 $\pi_{\theta}\left(a_{t} | s_{t}, z\right)$ で、以前のすべての観測とアクション $S_{t}=O_{1: t}, a_{1: t-1}$ および𝑧（戦略統計を表す）を現在のステップの行動 $a_t$ の確率分布にマッピングする

拡張データ表1 | エージェント入力空間

カテゴリ	フィールド	説明
エンティティ：最大512	ユニット型	例：ドローンまたはフォースフィールド
	オーナー	エージェント、敵、中立
	状態	現在の健康状態、シールド、エネルギー
	画面タイプ	例：戦場の霧（不確定要素）の中にある敵の建物のスナップショット
	ポジション	エンティティの位置
	労働者数	リソース収集基地建築用
	クールダウン	攻撃のクールダウン
	属性	目に見えない、動力付き、幻覚、アクティブ、貨物内、および/または画面内
	ユニット属性	例：生物または装甲
	貨物の状態	現在および最大の貨物スペース
	建物の状態	建築の進行状況、建築キュー、およびアドオンの種類
	リソースの状態	残りのリソースの内容
	命令の状況	命令キューと命令の進捗
	バフステータス	バフとバフ持続時間
マップ：128x128グリッド	高さ	地図の場所の高さ
	可視性	地図の場所が現在表示されているかどうか
	クリープ	特定の場所にクリープがあるかどうか
	エンティティの所有者	エンティティを所有しているプレーヤー
	アラート	ユニットが攻撃を受けているかどうか
	進行可能	どのエリアをナビゲートできるか
	建築可能	建築できるエリア
プレイヤーデータ	人種	エージェントと対戦相手が要求した種族、エージェントの実際の種族
	アップグレード	エージェントのアップグレードと対戦相手のアップグレード（人間に知られている場合）
	エージェント統計	エージェントの現在のリソース、供給、軍隊の供給、労働者の供給、最大供給、アイドル労働者の数、ワープゲートの数、および幼虫の数
ゲームの統計	カメラ時間	現在のカメラ位置。カメラは32x20のゲームユニットサイズの長方形です。現在のゲーム時間

拡張データ表2 | エージェント行動空間

フィールド	説明
アクションタイプ	実行するアクション。アクションの例としては、ユニットの移動、建物からのユニットの訓練、カメラの移動、無操作などがあります。完全なリストについては、PySC2を参照
選択したユニット	アクションを実行するエンティティ
ターゲット	アクションのターゲットとなる256x256に離散化されたマップ内のエンティティまたは場所
待機中	このアクションをキューに入れるか、すぐに実行するか
繰り返す	このアクションを複数回発行するかどうか
ディレイ	次の観測を受信するまで待機するゲームのタイムステップ数

$\pi_\theta$ は、次の構造を持つディープニューラルネットワークとして実装される

ニューラルネットワークの構造

観測 $o_t$ はベクトル表現にエンコードされ、結合され、ステップ間でメモリを維持するディープLSTMによって処理される
行動の引数 $a_t$ は、LSTMと観測エンコーダの出力を条件として、自己回帰的にサンプリングされる
可能な報酬ごとに価値関数がある（後述の強化学習を参照）

アーキテクチャのコンポーネントは、教師あり学習でのパフォーマンスから選択および調整された
ディープラーニングアーキテクチャの最近の多くの進歩が含まれている
エージェントアーキテクチャの高レベルの概要を拡張データの図3に示す

f:id:TadaoYamaoka:20191106084710p:plain

AlphaStarには1億3900万個の重みがある
推論中に必要な重みは5500万個のみ
アブレーション図3Fは、スキャッタ接続、トランスフォーマー、およびポインタネットワークの影響を比較している

f:id:TadaoYamaoka:20191111085542p:plain

感想

方策の自己回帰的な表現について詳細が記述されていませんが、前の論文に記述がありました。
このブログでも、以前に記事にしました。

アーキテクチャ詳細

※アーキテクチャ詳細は、Supplementary Dataのdetailed-architecture.txtに記載されています。

入力

prev_state : 以前のLSTM状態
entity_list : ゲーム内のエンティティのリスト（上記拡張データ表1参照）
map : ゲームマップを記述する7つのレイヤー（上記拡張データ表1参照）
scalar_features : プレイヤーのデータとゲームの統計情報、およびビルドオーダー
opponent_observations : 相手の観測値（「entity_list」、「map」、「scalar_features」と構造が似ている）。ベースラインにのみ使用され、プレイ中の推論には使用されない
cumulative_score : ゲームによって追跡されるさまざまなスコアメトリック。ベースラインにのみ使用され、プレイ中の推論には使用されない。これらは、プレイ中に人間には見えない。スコア、アイドル生産時間、作業時間、ユニットと構造物の合計値、ユニットと構造物の合計破壊値、収集された鉱物とヴェスピンの合計、鉱物とヴェスピンのコレクションの割合、使用済みの合計が含まれますミネラルとヴェスピン

エンティティエンコーダ

入力：entity_list
出力：
- embedded_entity : 埋め込みエンティティの1Dテンソル
- entity_embeddings : 各エンティティの埋め込み（すべてのエンティティに1つの埋め込みを持つ「embedded_entity」とは対照的）
entity_listの各エンティティのフィールドは最初に前処理されて連結され、各エンティティに単一の1Dテンソルが存在するようになる。フィールドは以下のように前処理される。
- unit_type：最大256のワンホット（不明なユニットタイプを含む）
- unit_attributes：13個のユニット属性ごとに1つのブール値
- alliance：最大5つのワンホット（未知の同盟を含む）
- ※他、current_health,current_shields,current_energy,cargo_space_used,cargo_space_maximum,build_progress,current_health_ratio,current_shield_ratio,current_energy_ratio,display_type,x_position,y_position,is_cloaked,is_powered,is_hallucination,is_active,is_on_screen,is_in_cargo,current_minerals,current_vespene,mined_minerals,mined_vespene,assigned_harvesters,ideal_harvesters,weapon_cooldown,order_queue_length,order_1,order_2,order_3,order_4,buffs,addon_type,order_progress_1,order_progress_2,weapon_upgrades,armor_upgrades,shield_upgrades,was_selected,was_targetedは省略
これらの前処理済みエンティティは最大512個あり、512個より後のエンティティは無視される。エンティティを参照しない512エントリのいずれにも、-1e9のバイアスを使用する。
前処理されたエンティティとバイアスは、2層の自己注意の3つの層を持つトランスフォーマーに入力される。各レイヤーで、各自己注意ヘッドはサイズ128のキー、クエリ、およびバリューを使用し、カーネルサイズ1のConv1Dを介して集約値を渡し、チャネル数を2倍（256）にする。ヘッドの結果は合計され、隠れサイズ1024および出力サイズ256の2層MLPを通過する。
トランスフォーマーの出力は、ReLU、256チャネルとカーネルサイズ1の1D畳み込み、および別のReLUを介して渡され、「entity_embeddings」が生成される。ユニット全体のトランスフォーマー出力の平均（欠落しているエントリによってマスクされる）は、サイズ256の全結合層とReLUを介して供給され、「embedded_entity」が生成される。

空間エンコーダ（Spatial Encoder）

入力：map、entity_embeddings
出力：
- embedded_spatial : 埋め込みマップの1Dテンソル
- map_skip : 中間計算(intermediate computations)の出力のテンソル
2つの追加のマップレイヤーが、上記拡張データ表1で説明されているレイヤーに追加される。 1つ目は、2つの可能な値を持つカメラレイヤー：場所が仮想カメラの内側か外側か。 2つ目は散在する(scattered )エンティティ。「entity_embeddings」は、サイズ32の1Dコンボリューションとそれに続くReLUを介して埋め込まれ、特定の場所のサイズ32のベクトルがそこに配置されたユニットに対応するようにマップレイヤーに分散される。プレーンは次のように前処理される。
- camera: 位置がカメラ内にあるかどうかの最大2つのワンホット
- scattered_entities: エンティティの埋め込みからの32個のfloat値
- height_map: マップの高さ/255.0のfloat値
- ※他、visibility,creep,entity_owners,alerts,pathable,buildableは省略
前処理後、プレーンは連結され、カーネルサイズ1の2D畳み込みによって32チャネルに投影され、ReLUを通過してから、チャネルサイズ64、128、128の3つの2D畳み込みとReLUを介して128x128から16x16にダウンサンプリングされる。これらの3つのダウンサンプリング畳み込みのカーネルサイズは4、ストライドは2。128チャネルとカーネルサイズ3の4つのResBlocksがダウンサンプルされたマップに適用され、スキップ接続が「map_skip」に接続される。 ResBlockの出力は、全結合層とReLUによってサイズ256の1Dテンソルに埋め込まれ、「embedded_spatial」になる。

感想

エンティティエンコーダで個々のユニット埋め込み表現を作って、空間エンコーダーの対応するユニットの位置に入力されています。
エンティティエンコーダにユニットを入力する順番をどうするのか疑問に思いましたが、エンティティエンコーダーへの入力順に関係なく、空間エンコーダーではユニット対応する位置に入力するので順番は関係なくなります。
また、エンティティエンコーダのembedded_entityは、すべてのユニットを統合した埋め込み表現となっていますが、トランスフォーマーは自己注意のクエリ、キー、バリューの機構によって入力順に依存しないで出力を得ることができるので、どのような順でユニットを入力しても良いことになります。

スカラエンコーダ

入力：scalar_features、entity_list
出力：
- embedded_scalar : 埋め込みスカラ特徴量の1Dテンソル
- scalar_context : 後でゲーティングのコンテキストとして使用する特定のスカラ特徴量の1Dテンソル
スカラエンコーダは、各「scalar_features」を1Dテンソルに埋め込み、それらを連結して「embedded_scalar」を生成する。これらの埋め込み特徴量の一部は、連結されて「scalar_context」を生成する。特徴量は次のように埋め込まれる。
- agent_statistics : log(agent_statistics+1)を入力し、サイズ64の全結合層とReLUを通過することにより埋め込まれる
- race : 両方の種族は、最大5のワンホットに埋め込まれ、サイズ32の全結合層とReLUを介して埋め込まれる。訓練中、相手の要求された種族は、ランダム種族との対戦をシミュレートするために、対戦の10％では隠される。この埋め込みは「scalar_context」にも追加される。敵の種族がランダムであるか、隠されているためにわからない場合、ユニットの1つを観察した後、観測に真の種族を追加する。
- ※他、upgrades,enemy_upgrades,timeは省略
空間エンコーダのように、いくつかの追加特徴量を追加し、他の「scalar_features」と同様に埋め込み、連結する。これらの特徴量は次のとおり。
- unit_counts_bow : 「entity_list」のbag-of-words。ユニットカウントベクトルは、平方根によって埋め込まれ、全結合層を通過し、ReLUを通過する。
- mmr : 教師あり学習中、模倣しようとしているプレーヤーのMMR(Match Making Rating)。それ以外では、6200に固定される。MMRは、最大6のmin(mmr / 1000, 6)のワンホットにマッピングされ、サイズ64の全結合層とReLUを通過する。
- cumulative_statistics：累積統計（ユニット、建物、効果、アップグレードを含む）は、人間のゲームの統計に存在するかどうかのブールベクトルに前処理される。ベクトルは、ユニット/建物、効果、およびアップグレードの3つのサブベクトルに分割され、各サブベクトルはサイズ32の全結合層とReLUを通過し、連結される。この埋め込みは「scalar_context」にも追加される。
- ※他、begin_build_order,last_delay,last_action_type,last_repeat_queuedは省略
上記のように、すべての特徴量は「embedded_scalar」用に連結され、注記されている特徴量は「scalar_context」用に連結される。

(続く)

2019-11-03

AlphaStarの論文を読むその４

AlphaStar

続きです。

前回までで論文の本文を紹介しました。
今回からMethodsを読んでいきます。本文と内容の重複もあります。
ほぼだらだらと訳しただけです。

ゲームとインターフェイス

ゲーム環境

StarCraftは、SF世界で行われるリアルタイム戦略ゲーム
1998年にBlizzard EntertainmentがStarCraftをリリースして以来、数千万ドルの賞金のある強力な競技コミュニティが存在
StarCraft IIの最も一般的な競技設定は1対1で、各プレイヤーは3つの利用可能な種族、Terran、Protoss、およびZergから1つを選択
プレイヤーは小さな基地と少数の労働者ユニットから始め、リソースを集めて追加のユニットや建物を建設し、敵を偵察し、新しい技術を研究する
プレイヤーはすべての建物を失うと敗北する

AIと人間の公平性

リアルタイムゲームの人間とコンピューターの対戦の公平性の概念は広く受け入れられていない
対戦条件、インターフェース、カメラビュー、アクションレート制限、遅延は、プロのStarCraft IIプレイヤーとBlizzardと協議して開発された
AlphaStarのプレイ条件は、プロプレイヤーが承認したもの（プロ選手の声明を参照）

(抄訳)
AlphaStarには優れた正確な制御機能がありますが、超人間的な感覚はありません。人間が理論的に達成できないレベルではありません。
人間よりもいくつかの面で優れており、他の面でも悪化していますが、もちろんAlphaStarと人間のプレイヤーの間には避けられない違いがあります。
StarCraftの「本物の」ゲームをプレイしており、非現実的な機能を備えているためにバランスが完全に失われないように、非常に公平に感じます。カメラの表示が制限されているため、マルチタスクを実行するときに常にすべてを同時に捕捉できるとは限らないため、その側面も非常に公平で人間らしく感じられます。

エージェントの各ステップで、方策は観測 $o_t$ を受け取り、ゲームインターフェイスを介して行動 $a_t$ を行う
エージェントステップごとに数ゲームタイムステップ（それぞれ45ミリ秒）が存在する場合がある

カメラビュー

人間は、マップの一部だけを表示する画面を通じてStarCraftをプレイする。マップ全体の高レベルのビューも表示する。
エージェントは、同様のカメラのようなインターフェイスを介してゲームと対話する
これにより、自然に注意の経済性が課される
そのため、エージェントは完全に表示して対話する領域を選択する
エージェントは、行動としてカメラを移動できる

カメラの外側の敵ユニットには特定の情報が隠されており、エージェントは特定の行動（建物の建築など）についてのみカメラ内をターゲットできる
AlphaStarは、カメラの外側で人間よりも正確に位置をターゲットにできるが、ターゲットの位置（256x256グリッド）はカメラの内側と外側で同じように扱われるため、AlphaStarの位置の精度は低い
エージェントはユニットのセットを任意の場所で選択することができるが、人間のコントロールグループの使用程柔軟性がない
実際には、エージェントはこれらの追加機能を活用していないようである
アブレーション図3Hは、このカメラビューを使用するとパフォーマンスが低下することを示している

APMの制限

人間には、実行できる1分あたりのアクション数（APM）が物理的に制限がある
エージェントには、APMの制限を強制する監視レイヤーがある
これにより、行動の優先順位付けが必要になる経済性が導入される
エージェントは、5秒のウィンドウごとに重複しないアクションの実行に最大22の制限がある
行動とゲームで測定されるAPM間の変換は簡単ではなく、エージェントの行動は人間の行動と比較するのは困難
コンピューターはステップごとに異なるアクションを正確に実行できる

f:id:TadaoYamaoka:20191103220842p:plain:w250

遅延

人間には、新しい情報に反応する速さが制限がある
AlphaStarには2つの遅延源がある
第一に、（訓練ではない）リアルタイム評価では、AlphaStarには、フレームが観測されてから、レイテンシ、観測処理、および推論のために行動が実行されるまでに約110ミリ秒の遅延がある
第二に、エージェントは次を観測するタイミングを事前に決定するため（平均370ミリ秒、場合によっては数秒）、予期しない状況に遅れて反応する場合がある

f:id:TadaoYamaoka:20191103220814p:plain:w250

感想

個人的には技術的な内容の方に興味がありますが、対戦条件や、反応速度でのAIのアドバンテージに対する公平性について、AIが人間を超えたかという点では関心が深い部分だと思います。

AlphaStarの論文を読むその３

AlphaStar

続きです。

本文の残りの部分です。

実験による評価

対戦条件

公式オンラインマッチメイキングシステムBattle.netの制限なし条件で評価した
3つのメインエージェントTerran、Protoss、Zergを評価
各エージェントは、訓練中に3つの異なるスナップショットで評価

教師ありトレーニングのみ（AlphaStar Supervised）
27日間のリーグトレーニング（AlphaStar Mid）
44日間のリーグトレーニング（AlphaStar Final）

AlphaStar SupervisedとAlphaStar Midは、Battle.netのランクなしレーティングで、各種族でそれぞれ30ゲームと60ゲームを行い評価
AlphaStar Finalは、AlphaStar Midのレーティングから、各種族でさらに30ゲームを行い評価
Battle.netのマッチメイキングで、マップと対戦相手を選択
対戦はブラインド条件で実施：AlphaStarには対戦相手が明かされない。匿名アカウントでプレイ。
これらの条件は、定常状態でのAlphaStarの強さを推定するために選択されたが、悪用可能な弱点がないことを直接測るものではない

評価結果

AlphaStar Finalは、Protossで6,275マッチメイキングレーティング（MMR）、Terran で6,048、Zergで5,835のレーティングを達成
ランク付けされた人間プレイヤーの99.8％を超える
3つの種族すべてでグランドマスターレベルに達した
AlphaStar Supervisedは平均レーティング3,699に達し、人間のプレイヤーの84％を超え、教師あり学習の効果を示している

f:id:TadaoYamaoka:20191102124633p:plain

感想

人間の対戦条件にした点が、前回との違いです。前回は特定のマップと種族に制限していました。
重大な弱点がないかを測るものではないと言及していますが、これについてredditで議論されていました。
成果自体は素晴らしいという肯定的意見もありますが、人間の99.8％に勝ってもトッププレイヤーに勝ったわけではないとか、真偽は分かりませんががすでにAlphaStarに有効な戦略を見つけているよみたいな否定的な書き込みもありました。

アブレーション（構成要素を抜いて効果を測定すること）と追加評価

さらに分析するため内部アブレーションを実施（図３）

f:id:TadaoYamaoka:20191102125248p:plain:w250

教師あり学習したエージェントに対する強さを測定（図４）

f:id:TadaoYamaoka:20191102125639p:plain:w250

メインエージェントのパフォーマンスは、3つの種族すべてで着実に向上した
メインエクスプロイトエージェントのパフォーマンスは、時間の経過とともに低下
メインエージェントはホールドアウトした検証エージェントに対してパフォーマンスが向上
これはメインエージェントが堅牢になったことを示している
各時点でのリーグのすべてのプレイヤーのナッシュ均衡は、以前のイテレーションに対して小さな勝率を得る
学習アルゴリズムが循環または回帰しないことを示唆している

f:id:TadaoYamaoka:20191102131424p:plain:w150

リーグの訓練を通してユニットの構成が変更され、多様な戦略的進歩が示された

f:id:TadaoYamaoka:20191102131522p:plain:w250

感想

図３Fのスキャッター接続の効果が高いが、スキャッター接続が空間情報と非空間情報を接続するという説明はあるが、具体的などうしているかが論文中に書かれていないので、具体的に知りたいところです。
ゲーム理論に詳しくないので図４Cのナッシュ均衡のグラフの読み方がよくわからなかった。

結論

AlphaStarは、StarCraft IIでグランドマスターレベルを達成した最初のエージェント
ゲームを簡素化することなく、広範なプロeスポーツで人間のプレーヤーの最高のリーグに到達した最初のエージェント
StarCraftと同様に、パーソナルアシスタント、自動運転車、ロボット工学などの実世界のドメインでは、不完全に観測された情報が与えられた場合リアルタイムの決定が必要
StarCraftと同様に、多くのアプリケーションには、サイクルまたは悪用可能な弱点を含む複雑な戦略があり、エージェントを現実世界に展開すると予期しない戦略または複雑なエッジケースに遭遇する場合がある
StarCraft IIでのAlphaStarの成功は、汎用の機械学習アルゴリズムが実際の複雑な問題に大きな影響を与える可能性があることを示唆している

本文は以上です。
次回からMethodsを読んでいきます。
(続く)

概要

導入

モデルベースとモデルフリー

MuZero

アルゴリズムの概要

先行研究

モデルベースRL

モデルベースのRLの新しいアプローチ

predictron

価値等価モデルの拡張

感想

勝敗ベースライン(Winloss Baseline)

Winloss Split VTrace Actor-Critic, TDLambda, UpGo Loss

ビルド順序ベースライン(Build Order Baseline)

Build Order Split VTrace Actor-Critic, TDLambda Loss

ビルドユニットベースライン(Built Units Baseline)

Built Units Split VTrace Actor-Critic, TDLambda Loss

アップグレードベースライン(Upgrades Baseline)

Upgrades Split VTrace Actor-Critic, TDLambda Loss

エフェクトベースライン(Effects Baseline)

Effects Split VTrace Actor-Critic, TDLambda Loss

エントロピー損失(Entropy Loss)

蒸留損失(Distillation Loss)

感想

コア(Core)

アクションタイプヘッド(Action Type Head)

遅延ヘッド(Delay Head)

キューヘッド(Queued Head)

ユニット選択ヘッド(Selected Units Head)

ターゲットユニットヘッド(Target Unit Head)

ロケーションヘッド(Location Head)

感想

ビットボードの実装

Visual C++とGCC対応

Pythonのインターフェース

creversi

拡張データ表1 | エージェント入力空間

拡張データ表2 | エージェント行動空間

ニューラルネットワークの構造

感想

アーキテクチャ詳細

入力

エンティティエンコーダ

空間エンコーダ（Spatial Encoder）

感想

スカラエンコーダ

ゲームとインターフェイス

ゲーム環境

AIと人間の公平性

カメラビュー

APMの制限

遅延

感想

関連研究

リアルタイム戦略（RTS）ゲーム

感想

模倣学習

リーグ

感想

実験による評価

対戦条件

評価結果

感想

アブレーション（構成要素を抜いて効果を測定すること）と追加評価

感想

結論