TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

Leela Chess Zeroウォッチ

少し古いが、Leela Chess Zeroの進化をまとめたよい記事があったので、読んでいる。
Leela Chess — Test40, Test50, and beyond | by Veedrac | Medium
GitHubのissuesから拾うのもしんどいのでまとめがあるとありがたい。

Leela Chess Zeroは新しい手法をいくつも試しているので参考になる。

Test40

Test40は、それ以前のすべての実験の統合している。

Test35ゲームでシード

  • Test40の訓練開始にTest35ゲームを使用した。

SENet

AlphaZero論文とのマッチング

ゲーム終了時の温度低下
  • AlphaZeroは、最初の15手でのみ温度を使用する。 Test40は、温度を1.2から0.45に下げるだけ。
cpuct式の変更
  • cpuct定数をAlphaZeroの式に変更
ファーストプレイの緊急度(FPU)

確率的重み平均化

  • Test30は、ネットワーク訓練にSWA(Stochastic Weight Averaging)を導入した。
  • これは、グローバルミニマムを見つけるのに役立つ手法である。
  • これにより、オーバーフィットが減少し、強さと訓練速度が向上する。

終盤テーブルベース

  • 終盤のテーブルベースは、終盤の位置に完璧な正解を与える。
  • テーブルベースは非常に大きいため、すべての貢献者にダウンロードを依頼することは実用的ではないため、セルフプレイで使用することができない。
  • Test30でサーバで再スコアリングするアプローチを導入。
  • Test40は、テーブルベースサイズを5から6に増やした。

Test50以降

Test50に含める可能性が高いと思われるアイデアをリストする。

ランダムプレイのシード

  • AlphaZeroは、知識がゼロの偽のネットワークでゲームをランダムにプレイすることから始まる。
  • ランダムにプレイすることで、ネットワークを使用するよりも初期の学習速度がわずかに向上する。

実装:https://github.com/LeelaChessZero/lc0/pull/725

畳み込み方策ヘッド

  • 方策ヘッドを単純なベクトルから、8x8の位置を示すレイヤーにする。
  • 最終的な結果は明らかに良ないが、学習時間が短くなるため訓練時間が短縮される。
  • 私が知る限りではマイナス面がないので、Test50に使用されることを期待する。

ディスカッション:https://github.com/LeelaChessZero/lc0/issues/637
実装:https://github.com/LeelaChessZero/lc0/pull/712
※T60で採用された模様

Contempt and trade penalties

  • 他のエンジンを破るための探索の変更

※チェスの特有の話でよく理解できなかった。
実装:https://github.com/LeelaChessZero/lc0/pull/703
実装(旧):#702, #577, #536, #466, #550, #436

価値ヘッドで引き分けを推定

  • 価値ヘッドの出力を、Win/Draw/Lose(WDL)に分ける。
  • これによる利点:
    • 引き分けを認識できる
    • 自己対局でドローオファーを提供することで情報のないゲームを早く終わらせることができる
    • 探索時の引き分けの価値を変更することで、弱い相手との引き分けを避けることができる

実装:https://github.com/LeelaChessZero/lc0/pull/635
実装(訓練でオファーを提供):https://github.com/LeelaChessZero/lc0/pull/724

訓練におけるkldgainしきい値

  • 現在、自己対局では1手につき800回の正確なプレイアウトを実行している。
  • 定数にすることが良いかは議論がある。水平線の先の戦略が見つけられない。
  • kldgainしきい値は探索と活用のバランスをとる。
  • 探索のある時点からある時点のKLダイバージェンスからプレイアウトがどの程度有効か測る。
  • 値が大きい場合、ネットワークが現在の状況に混乱しているのでさらに探索が必要。
  • 800固定の代わりに、KLDが100を下回るまで探索する。
  • テストでは、+120 eloになった。
  • プレイアウトあたり平均766ノードしかない。
  • 複雑な局面では最大で5300ノードまで続く。

提案:https://github.com/LeelaChessZero/lc0/issues/684
実装:https://github.com/LeelaChessZero/lc0/pull/721

確実な伝播(Certainty Propagation)

  • チェックメイトによる勝ち、負けとドローをツリーに伝播する。
  • +20 eloと対局の高速化の効果と、mate-in-Nの表示ができる

実装:https://github.com/LeelaChessZero/lc0/pull/700
実装(古い、より多くの機能):https://github.com/LeelaChessZero/lc0/pull/487
※v0.23.0で採用された模様

価値の悲観化

  • 訪問が少ないノードの価値を低下させる。
  • デフォルトで0.6回の負けがあるとして計算する。
  • 効果はわずか+20 elo

実装:https://github.com/LeelaChessZero/lc0/pull/707
※まだ採用されていない模様

Q学習

  • 価値の目標にゲーム最終結果の代わりに、モンテカルロ木探索によって生成されたQ値を使う。
  • ネットワークが体系的に間違っている場合、実際の結果がわからないため混乱を解決できない可能性がある。
  • 興味深い解決策は、qとzを平均して、両方を組み合わせることである。
  • これにより方策がより学習可能になり、ランダム性が低下する。

実装(部分):https://github.com/LeelaChessZero/lc0/pull/722
※T60で採用された模様

単純なリグレットベース探索(root cpuct, SR+CR MCTS, VOI, or other)

  • MCTSが悪いという議論
  • 単純にルートのcpuctを増加させることで+100 elo改善する。
  • ルートノードで累積的な後悔ではなく単純な後悔を最適化することにより、UCTよりも優れた機能を発揮できるはず。

※論文読まないと何のことか理解できない。
論文:MCTS Based on Simple Regret, VOI-aware MCTS

ゲームの分割

  • ゲーム開始時に温度でランダムな探索を使う代わりに、ゲームの開始局面をランダム化して、温度ゼロで開始位置からプレイするとどうなるか。
  • 多くの中盤と終盤局面を学習できる。
  • これについてはまだ多くの議論がある。

実装:https://github.com/LeelaChessZero/lc0/pull/720
ディスカッション:https://github.com/LeelaChessZero/lc0/issues/342https://github.com/LeelaChessZero/lc0/issues/237
※まだ採用されていない模様

感想

結構知らないテクニックもあり参考になります。
すでにdlshogiで試している内容もいくつかありました。
終盤テーブル(将棋では詰み探索)、確実な伝播、Q学習(いわゆるelmo式)、開始局面集とか。
dlshogiは効果測定まで十分できていませんが、Leela Chess Zeroは、issuesで十分に議論を行ってから採用しているので、その過程が参考になります。

Leela Chess Zeroのブログに最新の情報もあるので、そちらも確認したいと思っています。

将棋AIの進捗 その34(終盤力の強化)

前回の日記からしばらくぶりですが、その間SENetの学習を続けていました。

自己対局中の詰み探索の深さ

ディープラーニングMCTS系は終盤に弱点があるので、dlshogiでは自己対局中にルート局面でdf-pnによる詰み探索を行い、詰みが見つかった場合は、ゲームを打ち切り勝ち負けを正確な報酬として与えて学習している。
詰みの手順を学習しなくなるが、終盤の局面の価値評価が正確になる。
対局時は、ルート局面で並列で詰み探索を行っているので、詰みの手順は覚えなくても良いと割り切っている。

しかし、対局時のMCTSのシミュレーション中のノードでは、詰みの手順覚えていないため、中間ノードで詰みの絡む局面での方策の誤差が大きくなっている心配がある。
そこで、詰みの絡む局面での方策の精度を上げるために、新しい試みとして自己対局中の詰み探索の深さを、ランダムで浅くするということを行っていた。

しかし、これは失敗で、方策と価値の精度の両方とも、以前よりも低くなってしまった。
詰みが見つかった場合と、自分で詰みの局面を探索した場合の学習データが混じったいことで、悪影響があったのかもしれない。

ということで、数か月分のSENetの学習をやりなしている。
現状、SENetなしの場合を超えていないので、SENetはボツにする可能性が高い。

終盤力強化の別のアプローチ

以前から終盤力強化の別のアプローチとして、マルチエージェント学習が使えないかと思案していた。
しかし、複数エージェントを学習する分、マシンパワーが必要になるため躊躇していた。

USIエンジンをエクスプロイターとする

効果的に終盤の弱点を突くエージェントと対局を行えば、なにも学習するエージェントを複数作らなくてもよい。
そこで、αβ探索系のソフトを一定数リーグに加えることを試すことにした。
αβ探索系のソフトは終盤が強いという特徴があるので、終盤の弱点を防ぐことが期待できる。
また、別のエージェントを学習しなくてよいので、マシンパワーも節約できる。

なお、AlphaStarの論文では、このような弱点を突く役割のエージェントをエクスプロイター(搾取者)と呼んでいた。
AlphaStarではエクスプロイターも学習するので、膨大なマシンパワーが必要となっている。

任意のソフトをエクスプロイターとして使えるように、USIエンジンを呼び出す形で実装した。
USIエンジンとの対局で学習局面を生成 · TadaoYamaoka/DeepLearningShogi@10d862a · GitHub

強さの計測にも使える

この方法のもう一つのメリットとして、自己対局中にUSIエンジンに対する勝率も計測できるという点がある。
今まではマシンパワー不足のために、他のソフトと対局しての強さの測定は、不定期に行っていた。
この方法だと、常時強さの監視が可能になる。

デメリット

デメリットとしては、USIエンジンを複数並列で実行するため、CPUパワーが必要になる点がある。
現在10コアのCPUと3GPUのPCで学習を行っており、現状でもCPUがボトルネックになっている。
ということで、コア数を増やすため3970xをポチってしまった。

Aperyを使用したテスト

テストのために、USIエンジンとしてAperyを使用して、1スレッド1手500msでリーグに混ぜて学習させてみた。
局面の生成速度は、1GPU、64並列で、

エクスプロイターなし 26.39 nodes/sec
エクスプロイター(8つ)あり 21.92 nodes/sec

となった。
4コアのPCでの測定なので、CPUネックで速度が落ちていそうである。

勝率は、少ししかテストしていないが、3勝6敗であった。
初期局面集をつかっているので、偏っている可能性はある。

1手1秒とすると、0勝9敗となった。
自己対局中は800シミュレーションしか行っていないので、1手1秒は強すぎるようだ。
思考時間は500msくらいがよさそうである。

まとめ

まだほとんどテストしていないため、この方法で終盤に強くなるかは確認できていない。
新しいCPUが届いたら、本格的に学習をさせてみるつもりである。

対局中にディープラーニングとαβを組み合わせて、終盤を強化する方向性もある思うが、将棋AIを作り始めた動機がディープラーニングで強い将棋ソフトが作れるかだったので、対局時はαβは使わないという方向でアイディアを試していきたいと思っている。

MuZeroの論文を読む その9(訓練)

付録G 訓練

  • 訓練中に、MuZeroネットワークはK個の仮想ステップに対して展開され、MCTSアクターによって生成された軌跡からサンプリングされたシーケンスに合わせられる。
  • シーケンスは、リプレイバッファ内の任意のゲームから状態をサンプリングし、その状態からKステップ分展開することで選択される。
  • Atariでは、サンプルは優先度P(i) = \frac{p_i^\alpha}{\sum_k{p_k^\alpha}}の優先度付き経験再生*1に従って再生される。ここで、p_i = |\nu_i - z_i|、𝑣は探索価値、𝑧は観測されたnステップ収益である。
  • 優先サンプリングによって導入されたサンプリングバイアスを修正するために、重要度サンプリング比w_i = (\frac{1}{N} \cdot \frac{1}{P(i)})^\betaを使用して損失をスケーリングする。
  • すべての実験で、\alpha = \beta = 1に設定する。
  • ボードゲームの場合、状態は均一にサンプリングされる。
観測値、損失
  • シーケンスに沿った各観測値には、対応するMCTSポリシー\pi_t、推定値\nu_t、環境報酬u_tもある。
  • 展開された各ステップkで、ネットワークはそのステップの価値、方策、および報酬目標に損失があり、合計するとMuZeroネットワークの合計損失となる(式1を参照)。

\displaystyle
\begin{align}
l_t(\theta) &= \sum_{k=0}^K l^r (u_{t+k}, r_t^k) + l^v(z_{t+k}, v^k_t) + l^p(\pi_{t+k}, \mathbf{p}^k_t) + c ||\theta||^2
\label{muzero_eqn}
\end{align}
\tag{1}

  • 中間報酬のないボードゲームでは、報酬予測の損失を省略していることに注意する。
  • ボードゲームの場合、ゲームの最後まで直接ブートストラップする。それは、最終結果を予測するのと等しい。 Atariの場合、n=10ステップ先までブートストラップする。
勾配のスケーリング
  • 異なる展開手順でほぼ同様の勾配の大きさを維持するために、2つの別々の場所で勾配をスケーリングする。
    • 各ヘッドの損失を\frac{1}{K}でスケーリングする。ここで、Kは展開ステップの数である。 これにより、展開するステップ数に関係なく、勾配の合計が同じ大きさになることが保証される。
    • また、ダイナミクス関数の開始時の勾配を\frac{1}{2}にスケーリングする。 これにより、ダイナミクス関数に適用される勾配の合計が一定に保たれる。
論文での設定
  • この論文で報告されている実験では、常にK=5ステップで展開する。
  • 詳細な図については、図1を参照。

f:id:TadaoYamaoka:20191121214604p:plain

隠れ状態のスケーリング
  • 学習プロセスを改善し、アクティベーションを制限するために、隠れ状態を行動入力と同じ範囲([0, 1])にスケーリングする:s_{scaled} = \frac{s - \min(s)}{\max(s) - \min(s)}
ハードウェア
  • すべての実験は、第3世代のGoogle Cloud TPUを使用して実行された。
  • ボードゲームごとに、訓練用に16個のTPUを使用し、自己対局用に1000個のTPUを使用した。
  • Atariの各ゲームでは、訓練に8 TPUを、セルフプレイに32 TPUを使用した。
  • Atariでセルフプレイに使用されるTPUの割合がはるかに少ないのは、1回の動きのシミュレーション回数が少なく(800ではなく50)、表現関数に比べてダイナミクス関数のサイズが小さいためである。
感想

付録Gでは訓練の詳細について述べられています。

Atariではリプレイバッファからサンプリングする際に優先度付き経験再生が使用されていますが、ボードゲームでは使用していない理由について気になります。
優先度付き経験再生を使用すると逆効果なのか、効果が小さかったのかもしれません。
私が作っている将棋AIでもそのうち実験したいと思っています。

損失には3種類あり、AlphaZeroにはなかった報酬目標の損失が加わっています。しかし、中間報酬ボードゲームでは使用されず、Atariのみで使用されています。
価値の損失は、ボードゲームではブートストラップされず(モンテカルロ法)、Atariでは10ステップ先でブートストラップしています。
ボードゲームでもelmo式のように、モンテカルロ法と按分してブートストラップすることも有効だと思っていますが、そのうち検証してみたいと思っています。

使用しているハードウェアは、AlphaZeroでは学習用に第2世代TPU64、自己対局に第1世代3000でしたが、どちらも第3世代になっています。

次回は評価についてです。次で最後です。
(続く)

WindowsでPyTorchをC++(Visual C++)で動かす【更新】

以前にWindowsでLibTorchをC++から使う方法について記事を書いたが、内容が古くなったので書き直す。

基本的な手順は以前と同じだが、リリースビルドとデバッグビルドの使い分けができるようになっている。

最新のLibTorch 1.3は、Release用のバイナリと、Debug用のバイナリが別々に配布されている。
以前は、Release用のバイナリのみだったため、Debugビルドで動かすことができなかった。

LibTorchのインストール

https://pytorch.orgのQUICK START LOCALLYから、Stable/Windows/LibTorch/C++/10.1(CUDAのバージョンが10.1の場合)を選んでlibtorch-win-shared-with-deps-1.3.1.zipをダウンロードする。
適当な場所に解凍する。
以下、C:\に解凍したとして説明する(zipのルートフォルダがlibtorchなので、C:\libtorchが作成される)。

デバッグ用モジュール

デバッグビルドを行う場合は、「Download here (Debug version):」のリンクからlibtorch-win-shared-with-deps-debug-1.3.1.zipをダウンロードする。

リリース用モジュールとは別の場所に展開する。
以下、C:\libtorch\debugに、zipのlibtorch配下のフォルダを展開したとして説明する。

cmakeインストール

cmakeをVisual Studioのインストール時のオプションでインストールする。

最も単純なサンプルをビルドして実行

Installing C++ Distributions of PyTorch — PyTorch master documentation
の説明の通り、適当な場所に

  • CMakeLists.txt
  • example-app.cpp

を作成して、上記のページの内容の通り内容を記述する。

ビルド

スタートメニューから「x64 Native Tools Command Prompt for VS 2019」※を起動する。
Visual Studio 2019の場合。Visual Studio 2017でも可。
サンプルコードを配置したディレクトリに移動して、以下のコマンドを実行する。

mkdir build
cd build
cmake -DCMAKE_PREFIX_PATH=C:\libtorch ..

buildディレクトリに「example-app.sln」が作成されるので、Visual Studioで開いて、スタートアッププロジェクトを「example-app」に設定し、ソリューションの構成を「Release」に設定しビルドする。

ビルド成功し実行すれば、以下のように表示される。

 0.3171  0.7950  0.6067
 0.1094  0.7421  0.8496
[ Variable[CPUType]{2,3} ]

なお、ソリューションの構成を「Release」以外でビルドした場合、

エラー	LNK1104	ファイル 'torch-NOTFOUND.obj' を開くことができません。

というエラーが出力される。対処方法は後述する。

コマンドラインからビルドする場合

コマンドラインからビルドする場合、以下のコマンドでビルドする。

cmake --build . --config Release

デバッグビルド

上記の方法では、Debugでビルドすることができないため、自作のC++のプログラムをデバッグする際に困る。
cmakeのオプションを

cmake -DCMAKE_PREFIX_PATH=C:\libtorch\debug ..

として、別のプロジェクトを作成することで、Debugでビルドできるようになる。

しかし、Release用とプロジェクトが分かれてしまうので、不便である。
そこで、cmakeで生成された「example-app.vcxproj」を直接編集する。

<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">

から、対応する閉じタグの

</ItemDefinitionGroup>

までの間の、「C:\libtorch」を「C:\libtorch\debug」に置換する。

また、「torch-NOTFOUND」を「C:\libtorch\debug\lib\torch.lib」に置換する。

これで、Debug構成でもビルドできるようになる。

なお、CMakeLists.txtを編集して、cmakeを再構成した場合は、上書きされてしまうので注意が必要である。

その他のソリューション構成の場合

cmakeが生成するVisual Studioのプロジェクトには、「Release」と「Debug」以外に、「MinSizeRel」と「RelWithDebInfo」が含まれる。
これらの構成でビルドしたい場合は、上記と同様のビルドエラーが発生するため、対応するItemDefinitionGroupタグ内の「torch-NOTFOUND」を「C:\libtorch\lib\torch.lib」に置換すると良い。

デバッグビルドでのCUDAが使用できない問題

現在のバージョンでは、デバッグビルドでのCUDAが使用でいないという問題が発生している。
LibTorch crashes in debug mode: DispatchStub: missing CUDA kernel · Issue #22681 · pytorch/pytorch · GitHub

バグフィックスが行われているようなので、次のバージョンで修正されると思われる。

MuZeroの論文を読む その8(ネットワーク)

付録E ネットワーク入力

表現関数

ボードゲーム
  • 囲碁、チェス、将棋の表現関数への入力として使用されるボード状態の履歴は、AlphaZeroと同様に表される。
  • 囲碁および将棋では、AlphaZeroのように最後の8つのボード状態をエンコードする。
  • チェスでは、引き分けの正確な予測を可能にするために、過去100のボード状態に履歴を増やした。
Atrari
  • Atariの場合、表現関数の入力には、解像度96x96の最後の32個のRGBフレームと、それらの各フレームにつながった最後の32個の行動が含まれる。
  • ボードゲームとは異なり、Atariの行動は必ずしも観測に目に見える影響を与えないため、行動の履歴をエンコードする。
  • RGBフレームは、色ごとに1つの面としてエンコードされ、それぞれ赤、緑、青の範囲[0,1]に再スケーリングされる。
  • RGB入力のその他の正規化、ホワイトニング、またはその他の前処理は行わない。
  • 行動履歴は、𝑎 / 18にスケーリングされた単純なバイアス面としてエンコードされる(Atariには合計18アクションがある)。

ダイナミクス関数

  • ダイナミクス関数への入力は、表現関数またはダイナミクス関数の以前の適用によって生成された隠れ状態であり、遷移の行動の表現と連結される。
  • 行動は、隠れ状態と同じ解像度の面で空間的にエンコードされる。
  • Atariでは、この解像度は6x6である(ネットワークアーキテクチャの節のダウンサンプリングの説明を参照)。
  • ボードゲームでは、これはボードサイズと同じである(囲碁では19x19、チェスでは8x8、将棋では9x9)。
囲碁の行動のエンコード
  • 囲碁では、通常の行動(盤上に石を打つ)は、すべて0の面としてエンコードされ、1つの1が着手された石の位置にある。
  • パスは、すべて0の面としてエンコードされる。
チェスの行動のエンコード
  • チェスでは、行動をエンコードするために8つの面が使用される。
  • 最初のワンホットプレーンは、駒の移動元の位置をエンコードする。
  • 次の2つの面は、駒が移動された位置をエンコードする:ボード上にある場合、ターゲット位置をエンコードするワンホットプレーン、およびターゲットが(ボード上で)有効かどうかを示す2番目のバイナリプレーン。
  • これは、簡単にするために方策の行動空間がすべての有効な行動(すべてが合法ではない)のスーパーセットを列挙するために必要である。 また、方策予測とダイナミクス関数入力をエンコードするために同じ行動空間を使用する。
  • 残りの5つのバイナリプレーンは、プロモーションのタイプ(クイーン、ナイト、ビショップ、ルーク、なし)を示すために使用される。
将棋の行動のエンコード
  • 将棋のエンコードも同様で、合計11面である。
  • 最初の8つの面を使用して、駒の移動元を示しす。盤の位置(最初のワンホットプレーン)または7種類の持ち駒(残りの7つのバイナリプレーン)のいずれかである。
  • 次の2つの面は、チェスのようにターゲットをエンコードするために使用される。
  • 残りのバイナリプレーンは、移動が成りであったかどうかを示す。
Atariの行動のエンコード
  • Atariでは、行動は面に適切に割り当てられたワンホットベクトルとしてエンコードされる。

付録F ネットワークアーキテクチャ

予測関数
  • 予測関数\mathbf{p}^k, v^k = f_\theta(s^k)は、AlphaZeroと同じアーキテクチャを使用する。
    • 1つまたは2つの畳み込み層で、解像度を維持しながら面の数を減らし、出力のサイズの全結合層が続く。
Atariでの価値と報酬の予測
  • Atariでの価値と報酬の予測では、すべての実験において\epsilon = 0.001の可逆変換h(x) = sign(x)(\sqrt{|x| + 1} - 1 + \epsilon x)を使用してターゲットをスケーリングする。
  • 次に、同等のカテゴリ表現を取得するために、スカラー報酬および価値ターゲットに変換\phiを適用する。
  • サイズ601の個別サポート(関数の台)セットを使用し、-300〜300の整数ごとに1つのサポートを使用する。
  • この変換では、各スカラーは2つの隣接するサポートの線形結合として表されるため、元の値はx = x_{low} * p_{low} + x_{high} * p_{high}によって復元できる。
  • 例として、3.7のターゲットは、3のサポートでは0.3の重み、4のサポートでは0.7の重みとして表される。
  • ネットワークの価値と報酬の出力も、サイズ601のsoftmax出力を使用してモデル化される。
  • 推論中、実際の価値と報酬は、それぞれのsoftmax分布の下で最初に期待値を計算し、その後スケーリング変換を逆変換することによって取得される。
  • 価値と報酬のスケーリングと変換はネットワーク側で透過的に行われ、アルゴリズムの残りの部分には見えない。
表現関数とダイナミクス関数
Atariの観測
  • 観測の空間分解能が大きいAtariの場合、表現関数は、空間分解能を下げるためにストライド2の畳み込みのシーケンスから始める。
  • 具体的には、解像度96x96および128の面(それぞれ3つのカラーチャネルの32の履歴フレーム、面にブロードキャストされる対応する32の行動と連結)の入力観測から始めて、次のようにダウンサンプリングする。
    • ストライド2および128の出力面で1回の畳み込み、出力解像度48x48
    • 128面の2つの残差ブロック
    • ストライド2および256の出力面を使用した1つの畳み込み、出力解像度24x24
    • 256面の3つの残差ブロック
    • ストライド2、出力解像度12x12の平均プーリング
    • 256面の3つの残差ブロック
    • ストライド2、出力解像度6x6での平均プーリング
  • ダイナミクス関数(常に6x6のダウンサンプリング解像度で動作する)の場合、行動は最初に画像としてエンコードされ、次に平面次元に従って前のステップの隠れ状態を使ってスタックされる。
感想

AlphaZeroでは、8つの履歴局面を入力としていましたが、囲碁、将棋はAlphaZeroと同じで、チェスでは履歴局面の数が100に増やされています。
理由としては、引き分けを正確に予測するためと説明されています。

AlphaZeroでは、チェス、将棋では、繰り返し数が入力特徴量にありましたが、MuZeroではシミュレーション中の局面は、埋め込み表現に変換されるため正確に繰り返しを判断することができません。
そのため、必要な処置だったと推測できます。
将棋でも千日手があるので、履歴が8つでは足りないように思いますが、チェスの方がより引き分けにする戦略を多用するゲームのようなのでチェスだけ増やしたのではないかと思います。


チェス、将棋の移動先のエンコードで、移動元と移動先の組み合わせが合法かどうかを示すフラグが表現されています。
あまり詳細に書かれていないので推測ですが、MuZeroでは合法手の判断を行わないため、方策はすべての組み合わせを列挙するため、学習時に合法手を覚えさせるために必要だったと思われます。


ネットワーク構成は、ボードゲームではAlphaZeroと同じアーキテクチャとなっています。
Atariでは、ゲームによって価値と報酬の分布が異なるため、スケーリングしてカテゴリ化を行っています。
変換の説明にsupportという用語がでてきて、何かと思いましたが、数学の用語で日本語では「関数の台」というようです。
値をスカラではなくカテゴリ化してsoftmaxで出力するようにしています。
予測を容易にするために、値の解像度を落とすような操作をしていると理解できます。


次回は、訓練についてです。
(続く)

リバーシ(オセロ)で深層強化学習 その6(Dueling Network)

前回リバーシでDDQNを試したが、今回は同じくDQNの発展形であるDueling Networkを試す。

Dueling Network

[1511.06581] Dueling Network Architectures for Deep Reinforcement Learning

DQNでは行動価値を行動価値関数Qで推定するが、Dueling Networkでは、行動価値関数Qを状態価値関数Vとアドバンテージ関数Aに分解する。
DQNの以前の研究で、状態価値関数とアドバンテージ関数の2つに分解することで、Q学習とよりも速く収束することが示されている。

アドバンテージ関数は、以下の式で定義される。
\displaystyle
A^{\pi}(s,a) = Q^{\pi}(s,a) - V^{\pi}(s)
行動価値関数Qから状態価値関数Vを減算することで、各行動aの重要度の相対的な尺度を取得している。

この定義を使用すると、DDQNのターゲット
\displaystyle
y_i^{DDQN} =  r + \gamma Q(s',argmax_{a'} Q(s',a';\theta_i)   ;\theta^{-})
の行動価値関数Qを、2つのモジュールに分解できる。
\displaystyle
Q(s,a;\theta,\alpha,\beta) =  {V}(s;\theta,\beta) + {A}(s,a;\theta,\alpha)


ここで、VとAへの分解は、一意には定まらないことに注意する必要がある。
例えば、Vに定数を足して、Aからその値を引いてもQの値は同じになるということが起きる。
この性質のため、この式を直接使用するとパフォーマンスの低下を招く。


対処として、選択した行動で、Aが0になるように、次のように式を変形する。
\displaystyle
Q(s,a;\theta,\alpha,\beta) =  {V}(s;\theta,\beta)~+
\left({A}(s,a;\theta,\alpha) - \max_{a' \in |\mathcal{A}|}  {A}(s, a' ;\theta,\alpha) \right)


論文では、最大値の代わりに、平均を使用することで、学習の安定性を向上できると述べられている。
\displaystyle
Q(s,a;\theta,\alpha,\beta) =  {V}(s;\theta,\beta)~+
\left({A}(s,a;\theta,\alpha) - \frac{1}{|\mathcal{A}|} \sum_{a'} {A}(s, a' ;\theta,\alpha) \right)

実装方法

Dueling Networkは、DQNのネットワークの出力を、一旦VとAに分けた後、上記式の結果を出力することで実現する。
ネットワークの変更のみで実装でき、DQNの学習部分はそのまま適用できる。

論文では、学習部分はDDQNを使用しているので、DDQNを使用する。

実装

前回までのDQNのネットワークを以下のように変更した。
fcl2を、fcl2_advとfcl2_vに分けている。
forwardの最後で、fcl2_advとfcl2_vから出力のQを計算している。

class DQN(nn.Module):

    def __init__(self):
        super(DQN, self).__init__()
        self.conv1 = nn.Conv2d(2, k, kernel_size=3, padding=1)
        self.bn1 = nn.BatchNorm2d(k)
        # 省略
        self.conv10 = nn.Conv2d(k, k, kernel_size=3, padding=1)
        self.bn10 = nn.BatchNorm2d(k)
        self.fcl1 = nn.Linear(k * 64, fcl_units)
        self.fcl2_adv = nn.Linear(fcl_units, 65)
        self.fcl2_v = nn.Linear(fcl_units, 1)

    def forward(self, x):
        x = F.relu(self.bn1(self.conv1(x)))
        # 省略
        x = F.relu(self.bn10(self.conv10(x)))
        x = F.relu(self.fcl1(x.view(-1, k * 64)))

        adv = self.fcl2_adv(x)
        val = self.fcl2_v(x).expand(-1, 65)

        out = val + adv - adv.mean(1, keepdim=True).expand(-1, 65)

        return out.tanh()

実行結果

1万イテレーション学習した結果は以下のようになった。

損失

f:id:TadaoYamaoka:20191218225242p:plain
2000イテレーションまでは安定していないが、それ以降は、DQNやDDQNよりも安定して損失が低下している。

強さ

ランダムと1000局対局した結果は以下の通り。

結果 勝率 信頼区間95%
DQN 833勝152敗15分 84.57% 86.7~82.2%
DDQN 847勝131敗22分 86.61% 88.6~84.3%
Dueling 935勝58敗7分 94.16% 95.5~92.5%

DQNとDuelingの勝率に有意差があるか検定するための統計量zは、-6.92となった。
z<−1.96であるため、DQNとDuelingの勝率は等しいという帰無仮説は棄却され、Duelingの方が有意に強いと言える。


DQNと直接対局した結果は、

先手 後手 結果 勝率(信頼区間95%)
Dueling DQN 498勝462敗40分 55.0~48.7%
DQN Dueling 412勝562敗26分 45.42~39.20%
計(DDQN-DQN) 1060勝874敗66 57.0~52.6%

直接対局でも、有意に強くなっている。

まとめ

Dueling Networkでリバーシの学習を行った。
DQNと比較して、同じイテレーション数で有意に強くなることが確認できた。
Dueling Networkは、リバーシに有効な手法と言えそうだ。

論文では、Prioritized Replayと組み合わせることでさらに効果があると述べられているので、次は、Prioritized Replayを試してみたい。

(続く)

2つのプログラムの勝率に違いがあるか検定する

昨日書いた記事で、DQNとDDQNのランダムに対する勝率の違いについて、統計的に違いがあると言えるのか検証してみた。

昨日の結果
結果 勝率
DQN 833勝152敗15分 84.57%
DDQN 847勝131敗22分 86.61%

※勝率は引き分けを無効として計算した。

仮説検定

以下のように帰無仮説と対立仮説を設定する。

帰無仮説 DQNとDDQNの勝率は等しい
対立仮説 DDQNの方が勝率が高い

統計量

2つの母比率の差を検定する際には、下記の統計量zを使用する。
この統計量は、標準正規分布N(0, 1)に従う。
\displaystyle
z=\frac{\widehat{p}_{1}-\widehat{p}_{2}}{\sqrt{\widehat{p}(1-\widehat{p})\left(\frac{1}{n_{1}}+\frac{1}{n_{2}}\right)}}

勝敗の結果を当てはめると、
\displaystyle
\widehat{p}_{1} = 0.8457 \\
\widehat{p}_{2} = 0.8661 \\
\widehat{p} = (833+847)/(1000-15+1000-22) = 0.8558 \\
n_1 = 985 \\
n_2 = 978
なので、統計量zは、
\displaystyle
z = -1.2845
となる。

棄却ルール

DDQNの方が勝率が高いことを示したいので、片側検定を用いる。
有意水準は、5%の半分=2.5%とする。

下側の棄却域は、Pythonを使って計算すると、

from scipy.stats import norm
norm.ppf(0.025)
Out: -1.9599639845400545

と算出できる。

z > -1.96であるため、zは、棄却域に入っていない。

結論

帰無仮説は、棄却できない。
よって、前回のランダムとの対局結果からは、DDQNは、DQNよりも勝率が高いとは言えない。