2019-11-01

AlphaStarの論文を読むその２

AlphaStar

昨日の続きです。

人間のデータの重要性

StarCraftの主な課題の1つは、新しい戦略を発見すること
一度、地上ユニットの局所戦略を学んだ後、航空ユニットを単純に使用するとパフォーマンスが低下する
航空ユニットがその局所戦略を効果的に利用する、数千ステップを超える一連の命令を実行する可能性は非常に低い
この問題に対処するため、人間のデータを利用する
各エージェントは教師ありで学習したパラメータで初期化される
強化学習中にも、エージェントを人間の統計に条件付ける
エージェントは統計に従う報酬を受け取るか、もしくは、条件なしで独自の戦略を自由に選択して訓練する
また、エージェントは行動の確率が教師方策と異なる場合、ペナルティを受け取る
この人間の探索の導入により、訓練中、多様なプレイが引き続き調査される
図3Eに人間のデータの重要性を示す

f:id:TadaoYamaoka:20191101085707p:plain

感想

単体では効果のない行動を他の行動と関連させた場合に効果を発揮し、それにステップ数を要する場合、強化学習で学習させることが困難であることが示されています。
将棋に例えると大駒を捨ててでも相手の囲いを崩すといった、局所的には駒損でも数手先で有利になるといったケースでしょうか。
AlphaZeroがうまくいっているのは、囲碁や将棋では行動空間が比較的少ないためMCTSのような探索と組み合わせることで先読みが可能になるので、強化学習のみで学習できたのだと思います。
StarCraftのように行動空間が広すぎるため探索が使えない状況では、強化学習でステップ数のかかる戦略を発見するのは困難ということだと思います。

リーグトレーニング

マルチエージェント強化学習のアルゴリズムであるリーグトレーニングを導入する
不完全情報ゲームの場合、戦略にサイクルの関係が生まれる
AlphaGoと同様の自己対局では、急速に学習するが、サイクルに嵌ることがある
不完全情報ゲームではFictitious self-play(FSP)という自己対局アルゴリズムで、以前のすべての方策の一様な混合に対する最良の応答を計算することでサイクルを回避できる
2人ゼロサムゲームではナッシュ均衡に収束する
このアプローチを拡張して不均一な方策の混合に対する最良の応答を計算する
リーグには、多様なエージェントと現在と過去のイテレーションの方策が含まれる
各イテレーションで、そのエージェントに固有の方策が対戦相手としてサンプリングされる
エージェントのパラメータはアクタークリティックによってゲームの結果から更新される

感想

不完全情報の理論は詳しくないので、FSPというのがどういうものか分かっていません。
不完全情報ゲームでは、ナッシュ均衡が最善の方策となるので、リーグを構成することでそれを発見しようという試みでしょうか。
ポーカーAIのPluribusでは、リグレット(後悔)を最小にする学習をすることで、ナッシュ均衡に収束させていました。
AlphaStarでは報酬はAlphaZeroと同じようにゲームの結果ですが、リーグ戦とすることでナッシュ均衡になるようにしているようです。

リーグ構成

リーグは3つの異なるタイプのエージェントで構成される
主に対戦相手を選択するアルゴリズムが異なる

メインエージェント

メインエージェントは、各対戦相手の勝率に比例して確率的に選択する(優先順位付きfictitious self-play(PFSP)メカニズム)
これにより、最も問題のある相手を克服する機会がエージェントに与えられる
固定確率でメインエージェントが対戦相手に選ばれる
これにより、自己対局による迅速な学習が回復する

メインエクスプロイトエージェント(main exploiter agent)
※適当な訳が思いつかなかったが、exploitは悪用可能といった意味。つまり、相手の弱点を突くエージェント。

最新のメインエージェントのみと対戦する
目的はメインエージェントの潜在的な弱点を識別すること
メインエージェントが弱点に対処するように促す

リーグエクスプロイトエージェント

メインエージェントと同様のPFSPメカニズムを使用するが、対象はメインエージェントではない
目的はリーグ全体の組織的な弱点を見つけること

メインエクスプロイトエージェントとリーグエクスプロイトエージェントは、定期的に再初期化される
それにより多様性を促進し、必ずしも堅牢性の必要のない特殊な戦略を発見できる可能性がある

リーグの構成比
f:id:TadaoYamaoka:20191101223625p:plain

感想

それぞれ異なる弱点を発見する目的で異なるタイプのエージェントでリーグが構成されています。
囲碁AIのGLOBIS-AQZでもマルチエージェント学習が行われているようですが、AlphaStarのようにエージェントを目的別を分けて構成するやり方は、囲碁や将棋の学習でも応用ができそうです。
例えば終盤に特化したエージェントを作るとか。
定期的に初期化して、特殊な戦略を見つけるというやり方も効果があるかもしれません。

訓練したエージェント

StarCraftには3つの種族がある
3つのメインエージェント(各種族に1つ)、3つのメインエクスプロイトエージェント(各種族に1つ)、6つのリーグエクスプロイトエージェント(各種族に2つ)を使用してリーグを訓練した
各エージェントは32の第3世代TPUを使用して44日間訓練した
900の異なるエージェントが作成された

今日はこの辺で。
続きはまた明日。

2019-11-01

AlphaStarの論文を読む

AlphaStar

Natureで発表されたAlphaStarの論文を読んでいきます。
無料で読めるPDFは、DeepMindのブログからダウンロードできます。

PythonとTensorFlowによる疑似コードも公開されており、Supplementary Dataからダウンロードできます。

Methodも含めると結構なボリュームがあるので、少しずつ記事にしていこうと思います。
理解できていない部分もあるので、勉強もかねて調べながら書いていきます。
ところどころ感想を挟んでいきます。
たぶん、まとまりのない内容になると思います。

概要

多くの実際のアプリケーションでは、複雑な環境でのエージェントが必要
StarCraftは、複雑さとマルチエージェントの課題という点で実世界との関連性があり、人工知能の重要な研究課題となる
以前の研究では、ゲームを単純化したり、手作りのサブシステムにしたりしてAIに有利であったにもかかわらず、人間のトッププレイヤーにかなわなかった
この論文では、汎用的な学習方法でStarCraftの課題に対処する
人間とエージェントの両方のデータを使用するマルチエージェント強化学習アルゴリズム
ディープニューラルネットワークを使用する
結果は、人間のプレイヤーに対するオンラインゲームで評価した
グランドマスターレベルに達し、人間プレイヤーの99.8％以上勝利した

StarCraftⅡについて

リアルタイムの戦略(RTS)ゲーム
数百のユニットの個別に制御して、高度な経済的意思決定のバランスをとる必要がある
非推移的ゲーム（じゃんけんの関係）
反撃の戦略が多様
素朴な自己対局では新しい戦略を発見できない
自己対局での戦略は人間のプレイヤーにはおそらく効果的でない
行動の組み合わせが必要な行動空間（数百のアクションタイプとそれに応じた選択。各ステップで約1026通りの選択肢）
長期計画が必要（数十万のタイムステップ、約10分間）
不完全な情報（カメラ外の一部の敵ユニットは除外される。人間と同様にカメラビューの移動が必要）
人間の反応速度と公平性を保つため制約を課す（1分あたりの行動(APM)に制限。条件はプロプレイヤーが承認）

感想

強化学習のみでは、効果的な戦略をほとんど学習できなかったことは、以前の論文に書かれています。
カメラビューの移動は、以前のブログでプロプレイヤーに勝利したときに、不公平と指摘されていた点です。
今回の条件はプロプレイヤーのお墨付きのようです。
論文の執筆者にも、Team Liquidのメンバーが載っていました。

学習アルゴリズム

模倣学習、強化学習、マルチエージェント学習を使用
詳細はMethod（※後日記事にする予定）
AlphaStarの主要の要素は、方策 $\pi_\theta$
ニューラルネットワークで表現される
ゲーム開始からの観測を入力として受け取り、行動を出力する
人間のデータからサンプリングした戦略を要約する統計にも基づく

感想

人間データからの統計を併用する点が、以前との大きな違いです。
人間が発見できる戦略を強化学習アルゴリズムでは発見できないというのが現状で、最先端の強化学習アルゴリズムでもまだ人間には及ばないようです。
OpenAIのかくれんぼでも似たような課題に取り組んでいました。

アーキテクチャ

アーキテクチャは、汎用ニューラルネットワークコンポーネントで構成
プレイヤーと敵ユニットの観察には、自己注意メカニズムを使用
空間情報と非空間情報を統合するために、スキャッター接続を使用
部分的な観測可能性に対処するため、観測の時系列にLSTMを使用
構造化された行動空間のために、自己回帰ポリシーとポインターネットワークを使用

感想

自己注意メカニズムは、トランスフォーマーのことです。
自然言語処理のBERTなどで使われています。
AlphaStarでは、ユニットの埋め込み表現を作るために使われています。
前回のプロプレイヤーと対戦したバージョンでもトランスフォーマーは使われていました。
その前の論文では、1×1の畳み込みによりユニットの埋め込み表現を作っていました。

教師あり学習

エージェントのパラメータは最初は教師ありで訓練する
人間のリプレイの公開データセットからサンプリング
方策を人間の行動を予測するように訓練
これにより人間のプレイを反映した多様な戦略が生まれる

強化学習

その後、異なるエージェントに対して勝率を最大化するように設計された強化学習アルゴリズムで訓練
対戦相手の選択は、後述のマルチエージェントの手順により決定
強化学習アルゴリズムは、アクタークリティックと同様の方策勾配アルゴリズム
非同期に収集したリプレイバッファを使用して経験再生を行う（オフポリシー学習）
つまり、以前の方策によって生成された経験から現在の方策を更新する
大規模な行動空間では、以前の方策と現在の方策が一致する可能性が低い
不一致でも効果的に学習できる手法を使用する： TD(λ)、重要度サンプリング(V-trace)および自己模倣アルゴリズム(UPGO)
分散を減らすため価値関数には敵の視点からの情報も使用
図3I、Kに相対的な重要性を示す

f:id:TadaoYamaoka:20191101000629p:plain

感想

通常、方策勾配法は、オンポリシーで学習されます。
オフポリシーで学習すると、分散と安定性を制御することが非常に困難であることが、ACERの論文に書かれていました。
ACERは、方策勾配法をオフポリシーで学習するSOTAな手法です。
AlphaZeroは、方策勾配法でもリプレイバッファを使用してオフポリシーで学習されていました。
おそらく、囲碁では以前の方策を使っても現在の方策とずれることが少ないことから成功しているのだと思います。

V-traceとUPGOについては、わかっていないので後で勉強して記事にするつもりです。

(続く)

2019-10-28

cshogiをOpenAI Gymインターフェースに対応させてみた

cshogi コンピュータ将棋

強化学習の勉強をしていてアルゴリズムを実装して試してみたいが、CartPoleとか学習させても面白くないのでせっかくなので将棋で試せるようにしてみたくなった。

ということで、cshogiをOpenAI Gymインターフェースに対応させてみた。

Gymインターフェース

公式の説明の通りいくつかのインターフェースを実装するだけなので、特に難しいことはなかった。
https://github.com/openai/gym/blob/master/docs/creating-environments.md
別にこのインターフェースを使わなくてもよいのだが、標準的なインターフェースに従っている方が、一般的な強化学習の枠組みに沿うので理論との整合性がとりやすくなると思う。

DQNサンプル

試しにPytorchのチュートリアルのDQNを将棋に適用してみた。

ソース：
cshogi_gym/dqn.py at master · TadaoYamaoka/cshogi_gym · GitHub

Google Colabでの実行結果：
https://colab.research.google.com/drive/1d7bo0vbhnzxiESBYTjwRhbQYB2ohH984

将棋での考慮点

学習間隔

チュートリアルでは1ステップごとに学習が行われるが、将棋では終局まで報酬がないため1エピソード完了時に学習するようにした。

バッチサイズ

学習はリプレイバッファからサンプリングして行うが、1バッチに終端の報酬が1つは含まれないと学習が進まないため、バッチサイズは最大手数と合わせて512とした。

行動空間

元のチュートリアルのCartPoleは、行動空間が2次元だが、将棋の場合は最大593で、状態により可変となる。
可変では扱いにくいため、dlshogiと同じように無駄な手も含めて移動先座標＋移動方向で固定次元で出力するようにして、gatherで合法手のみに絞るようにした。

ミニマックスを考慮したQ学習

Q学習の学習則は以下の式だが、1ステップ後（s'）は、相手の局面のため $\max _{a} Q\left(s^{\prime}, a\right)$ の符号を反対にする必要がある。
$\displaystyle \delta=Q(s, a)-\left(r+\gamma \max _{a} Q\left(s^{\prime}, a\right)\right)$

詰み探索

詰みの手順も学習させてもよいが終局まで長引くため短い手数の詰み探索を行うようにした。
そのため、cshogiにAND/ORのよる高速な詰み探索を実装した。

棋譜の出力

lossだけ見ても面白くないので、自己対局結果が見られるようにKIFフォーマットで棋譜を出力するようにした。
そのため、cshogiに棋譜出力機能を実装した。

学習結果

とりあえず1000局学習させてみたが、1000局ではほとんど有効な手は学習しておらず、学習が進むとほとんど千日手になる。
Q学習は終端の報酬が徐々に開始状態の方向に波及していくが、将棋のように終端まで報酬がなく状態空間が広いと、序盤の学習には相当な時間がかかりそうに思うが、ディープなモデルでは局所的に有効な手を学んでいければそうでもないかもしれない。
DQNは、R2D2とか最新の価値ベースの手法に比べると相当効率の悪いアルゴリズムなので、DQNをベースラインとして他の手法も試してみたい。

2019-10-22

cshogiのバグ修正とdlshogi-zeroの更新

cshogiにいくつかバグがあったので修正した。

move16がデグレード

やねうら王の教師局面に対応した際に、move16がデグレードしていた。
単純な編集ミスだったので修正した。

千日手が判定できないバグ

board.is_draw()

は、引数に遡る手数を受け取るが、デフォルト引数の場合開始局面まで調べる。
デフォルト引数の場合、intの正の最大値にしていたが、2^31-1とするところを2^31にしていたので負数になっており千日手が判定できなくなっていた。

連続王手の千日手が判定できないバグ

USIエンジン同士の対局で連続王手の千日手が判定できていなかった。

連続王手の千日手には、2パターンあって一つは、連続王手した局面が4回繰り返した局面の場合で、指した後の局面の手番で判定するので定数REPETITION_WINになる。

もう一パターンは、特殊なパターンで、連続王手から逃れた局面が4回繰り返した局面になる場合である。かずさんのブログに具体例がある。
こちらは、定数REPETITION_LOSEになる。

REPETITION_WINは、対応しているつもりだったがバグがあって判定できていなかった。
REPETITION_LOSEは、そもそも対応していなかった。
両方正しく判定できるように修正した。

dlshogi-zeroの更新

cshogiの更新に合わせてdlshogi-zeroが動かなくなっていたので、最新版で動くように更新した。
dlshogi-zeroは、技術書典で頒布したディープラーニングを使った将棋AIの作り方3のために作成したプログラムだが、たまに電子版を買ってくださる方いるので対応した。

2019-10-13

エントロピー正則化項の微分

エントロピー正則化数学 DeepLearning

以前に方策が決定論的にならないようにするために、損失にエントロピー正則化項を加えることを書いたが、誤差逆伝播する際の微分の式が誤っていたので訂正する。

方策がソフトマックス関数の場合のエントロピーの微分

エントロピーは以下の式で与えられる。
$\displaystyle H(p) = -\sum_j p_j \log p_j \tag{1}$

$p$ がソフトマックス関数の場合、ロジットを $z$ とすると、エントロピーの偏微分は、以下の通りシンプルな式になる。
$\displaystyle \frac{\partial H(p)}{\partial z_i} = p_i(-\log p_i - H(p)) \tag{2}$

この式は、以下の論文に記載されていた。
[1701.06548] Regularizing Neural Networks by Penalizing Confident Output Distributions

式の導出

以下、この式の導出について記載する。

上記の式は、Σと偏微分がうまく消えていてすっきりした形になっている。
論文には式の展開が記載されていないため、すぐにはどのように導出したのかわからなかった。
しかし、微分の連鎖則、積の微分公式、ソフトマックスの微分、エントロピーの定義と確率の合計が1になることを使うと導出できる（ネットを検索してもこの式について書かれている情報がなかったので自分で導出したが、思いつくのに1日くらいかかった）。

まず、微分の連鎖則を使うと偏微分の式は以下の通りに書ける。
$\displaystyle \begin{eqnarray} \frac{\partial H(p)}{\partial z_i} &=& \frac{\partial}{\partial z_i} (-\sum_j p_j \log p_j) \\ &=& -\sum_j ( \frac{\partial}{\partial p_j} (p_j \log p_j) \cdot \frac{\partial p_j}{\partial z_i} ) \tag{3} \end{eqnarray}$

$p_j \log p_j$ の微分は、積の微分公式を使うと、 $1 + \log p_j$ となるので、
$\displaystyle \frac{\partial H(p)}{\partial z_i} = -\sum_j ( (1 + \log p_j) \cdot \frac{\partial p_j}{\partial z_i} ) \tag{4}$
となる。

$\frac{\partial p_j}{\partial z_i}$ は、 $p$ がソフトマックス関数なので、ソフトマックス関数の微分から、
$\displaystyle \frac{\partial p_j}{\partial z_i} = \left\{ \begin{array}{ll} p_i(1-p_i) & (i = j) \\ -p_i p_j & (i \ne j) \end{array} \right. \tag{5}$
となる。

したがって、式(4)のΣの中は、
$\displaystyle \begin{eqnarray} (1 + \log p_j) \cdot \frac{\partial p_j}{\partial z_i} &=& \left\{ \begin{array}{ll} (1 + \log p_i) p_i(1-p_i) & (i = j) \\ (1 + \log p_j) ( -p_i p_j ) & (i \ne j) \end{array} \right. \\ &=& \left\{ \begin{array}{ll} p_i (1 - p_i + \log p_i - p_i \log p_i ) & (i = j) \\ p_i (-p_j - p_j \log p_j) & (i \ne j) \end{array} \right. \tag{6} \end{eqnarray}$
となる。

これを式(4)のΣに戻すと、 $i = j$ と $i \ne j$ をまとめられるため、
$\displaystyle \frac{\partial H(p)}{\partial z_i} = - p_i (1 -\sum_j p_j + \log p_i -\sum_j (p_j \log p_j)) \tag{7}$
となる。

ここで、確率の合計は1になるため $\sum_j p_j = 1$ となり、エントロピーの定義から、 $-\sum_j (p_j \log p_j) = H(p)$ となるため、
$\displaystyle \frac{\partial H(p)}{\partial z_i} = p_i (- \log p_i -H(p)) \tag{8}$
となり、式(2)が導出できた。

この式を使うと、エントロピー正則化項の誤差逆伝播が効率よく計算できる。
ただ、この式を使わなくても、ディープラーニングフレームワークの計算グラフを使えば、

loss = policy_loss + beta * F.mean(F.sum(F.softmax(z) * F.log_softmax(z), axis=1))

のように記述すれば、多少効率は落ちるがフレームワークがよろしくやってくれるので中身の式は気にする必要はない。

2019-10-05

matplotlibでグラフをインタラクティブに変更して見やすくする

python matplotlib

matplotlibで複数系列の時系列グラフなどを表示した場合、グラフの線が太く重なっている箇所の詳細が把握しにくい。
特にJupyter Notebookでブラウザで表示している場合は、コードで見栄えを調整する必要がある。

Jupyter QtConsoleで、「%matplotlib qt」とIPythonのマジックコマンドでグラフのバックエンドをQTに変更して、GUIでグラフを表示すると、インタラクティブに拡大縮小や、グラフの線の変更、系列の表示/非表示などが行える。

例

グラフ表示する時系列データのロード

pandas-datareaderで、yahooのNIKKEI225の株価データをロードする。

import pandas_datareader as pdr
price = pdr.DataReader("^N225", "yahoo", "1984/1/4", "2019/10/4")

Jupyter Notebookでグラフ表示

Jupyter Notebookで表示すると以下のようになる。

price.plot()

f:id:TadaoYamaoka:20191005221057p:plain

縦軸がVolumeに合わされているため、Open、Closeなどのデータが下の方に表示されている。
コードで非表示にする必要がある。

price[['High','Low','Open','Close','Adj Close']].plot()

f:id:TadaoYamaoka:20191005221425p:plain

縦軸のスケールが調整されて、株価の変動がわかるようになったが、Adj Closeの線しか見えない。
一部を拡大してみるにはまたコードを記述する必要がある。面倒である。

Qtでグラフ表示

次に、Jupyter QtConsoleで表示する。

%matplotlib qt
price.plot()

f:id:TadaoYamaoka:20191005221800p:plain

初期表示は、Jupyter Notebookと同じように表示される。
しかし、コードを書かなくてもGUI操作で見た目を変更できる。

操作については、以下のページにマニュアルがある。
Interactive navigation — Matplotlib 3.1.2 documentation

Volumeを非表示にして、
f:id:TadaoYamaoka:20191005222046p:plain
線の幅を調整して、
f:id:TadaoYamaoka:20191005222120p:plain
マウスで範囲指定して一部を拡大して、見たい箇所にドラッグすることができる。
f:id:TadaoYamaoka:20191005222650p:plain

2019/10/6 追記

Jupyter Notebookでも

%matplotlib notebook

とすることで、インタラクティブなグラフが描画される。
f:id:TadaoYamaoka:20191006234138p:plain

ただし、移動・拡大縮小はできるが、系列の表示/非表示などはできない。
また、Google Colabでは使用できない。

2019/10/19 追記

複数系列をグラフ表示する場合、線の太さを細くしたい場合がある。
系列が多いと後からGUIで設定するのはめんどくさい。
線の太さは、表示時に一括で設定できる。

price.plot.line(linewidth=0.5)

2019-09-29

将棋AIの実験ノート：chain ruleで方策を定義する（続き）

コンピュータ将棋

（前回の続き）

chain ruleで方策を定義したモデルと、現在のdlshogiの指し手を表現したモデルで、同じ局面を学習させて精度を比較した。

elmoで生成した、1000万局面を訓練に、100万局面をテストに使用した。

chain rule

f:id:TadaoYamaoka:20190929163420p:plain

現在のdlshogiの指し手表現

f:id:TadaoYamaoka:20190929163506p:plain

	test accuracy
chain rule	0.21363907
dlshogiの指し手表現	0.23695517

考察

現在のdlshogiの指し手表現の方がテスト局面に対する精度が高くなった。
chain ruleでは3つの確率を同じ重みにして、ハイパーパラメータも調整していないため、chain ruleでもそれらを調整することで精度が改善する可能性はあるが、将棋の指し手ではchain ruleを使用するよりもシンプルに移動先と移動方向を組み合わせた方がよさそうだ。

まとめ

将棋の方策をchain ruleで定義しても学習できる。
クラス数を抑えて一つの出力で方策を定義できる場合は、chain ruleを使わない方が精度が高くなる。

計測に使用したソースコード

GitHub - TadaoYamaoka/ShogiChainRulePolicy