2020-01-12

将棋AIの進捗その36(UCBの価値の初期値)

AlphaZeroのMCTSのUCBには、
$\displaystyle Q(s, a) + C(s)P(s,a)\frac{\sqrt{N(s)}}{1+N(s,a)}$
という式が使用されており、このUCBで行動価値の信頼区間の上限を見積もっている。

$Q(s, a)$ は、行動 $a$ の行動価値を、探索を行った結果得られた価値の平均で推定する。
ここで、 $N(s, a)=0$ のとき $Q(s, a)$ は未定義であるため、何らかの値で推定する必要がある。
AlphaZeroでは0で初期化、つまり、未探索のノードの価値を0(負け)としている。

dlshogiでは、これを0.5(引き分け)で初期化している。
以前に、これをAlphaZeroに合わせて0で初期化してみたところ、勝率が極端に落ちたので、0.5のままとしている。

dlshogiで、負けで初期化すると勝率が極端に落ちる原因はよくわかっていない。
方策を分布ではなく指し手で学習しているという、学習方法の違いによるものかもしれない。

Leela Chess Zeroの初期値

Leela Chess Zeroでは、元々 $N(s, a)=0$ のときの $Q(s, a)$ に、親ノードの価値が使用されていた。

以下のissueで、これをAlphaZeroと同様に0で初期化することについて議論されている。
Initialize Q = 0 instead of parent Q for self-play to match AGZ paper · Issue #344 · LeelaChessZero/lc0 · GitHub

学習時の自己対局では、負けで初期化することで、負けの局面は広く探索して、勝ちの局面では現在の方策が実際に良いか補強して検証するという目的があると考察されている。

以下のPRでは、ルートの初期値は、勝ちで初期化した方が、チェスではAlphaZeroにより近くなると主張されている。
理由は、35手くらいまではすべて探索されるからと説明されている。
Add AtRoot versions of FpuStrategy and FpuValue (and convert FpuReduction to FpuValue). by Mardak · Pull Request #750 · LeelaChessZero/lc0 · GitHub

現在のLeela Chess Zeroの設定を確認すると、ルートノードでは、勝ちで初期化し、中間ノードでは負けで初期化している。
対局時の設定も、同じになっている。

親ノードの価値で初期化を試す

dlshogiで負けで初期化するとうまく機能しないが、Leela Chess Zeroが以前に行っていた、親ノードの価値で $N(s, a)=0$ のときの $Q(s, a)$ を初期化する方法を試してみた。

技巧2と1手3秒で100対局した結果は、以下のようになった。

条件	結果	勝率
0.5(引き分け)で初期化	59勝38敗3分	60%
親ノードの価値で初期化	65勝28敗7分	69%

※Core i7 4コア、GPU 2080Tiを使用
※自己対局で学習した最新のモデルを使用

親ノードで初期化することで、勝率が9%(R+68.6)上昇した。

Leela Chess Zeroで、親ノードの価値で初期化する場合は、さらに低減(reduction)項が加えられている。
$\displaystyle V(s) - C_{FPU} \sqrt{ \sum_{a'}{ I(N(a')>0) P(a') } }$
これは、方策の確率が大きいノードが探索された数が多いほど、探索の緊急度を削減するという意味がある。
次は、この項も加えて検証してみたい。

2020-01-04

将棋AIの進捗その35(PyTorchに移行)

dlshogi PyTorch Chainer

年末に新しいCPUが届いたので、正月はPCを組んでいた。
同時にフルタワーケースを買ったのだが、GPU3枚だと熱対策をしないと安定動作しなかったので、ドリルで加工してファンを増設したりと正月から働いてしまったorz
安定動作するようになったので、前回記事にしたUSIエンジンをリーグに加えた強化学習を走らせている。
10サイクルほど学習したら結果を記事にする予定である。

SWA(Stochastic Weight Averaging)

Leela Chess Zeroの最新動向を調べていて、SWA(Stochastic Weight Averaging)という手法がdlshogiでも効果がありそうなので、試してみることにした。

SWAは、訓練中にネットワークの重みを一定間隔置きに平均化することで、局所最適ではなくグローバル最適に収束させる手法である。
SWAの実装は、ChainerではGitHubで実装例が公開されている。

PyTorchでは、オプティマイザの拡張機能として提供されており、PyTorchの方が簡単に実装できる。
Stochastic Weight Averaging in PyTorch | PyTorch

dlshogiの学習部にはChainerを使用していたが、Chainerは開発が終了したため、Chainerで実装するよりも、今後も考えてPyTorchに移行してから、SWAを試すことにした。

PyTorchに移行

ChainerからPyTorchへの移行は、APIが類似しており、ほぼAPIが1対1で対応しているため、比較的容易に移行できる。

以下では、単純な変換で対応できなかった点を記す。

モデルの保存形式

dlshogiでは対局プログラムはcuDNNのAPIを直接使用しており、Chainerで保存したモデルをC++で読み込んでいる。

PyTorchの標準的な方法では、モデルはPythonのPickle形式に、パラメータのstate_dictを格納して保存される。
C++のプログラム側でこれを読み込むのは苦労するので、モデルの保存形式は、Python側でChainerと互換性を持たせて保存することにした。

Chainerの保存形式は、Numpy標準のnpz形式なので、state_dictに格納されているtorch.TensorをNumpyに変換してからnp.savez()で保存するればよい。
また、畳み込み層や、全結合層のパラメータとバイアスの名前が違うために、互換性を持たすには変換が必要だった。

Chainer	PyTorch
W	weight
b	bias

また、BatchNormのパラメータの名前は、PyTorchでは、畳み込みと全結合と同じweightとbiasが使用されているため、保存時に層の種類を判定する必要がある。
処理を簡易にするため、層の名前にnormもしくはbnを含むかで区別するようにした。
BatchNormのパラメータの対応は以下のようになる。

Chainer	PyTorch
gamma	weight
beta	bias
avg_mean	running_mean
avg_var	running_var
N	num_batches_tracked

これで、C++側のプログラムの修正なしに、モデルが読み込めるようになった。

交差エントロピー誤差

Chainerでは、2値分類の交差エントロピー誤差の正解データには、0か1の整数を与える必要がある。
dlshogiでは、価値関数をブートストラップするために、自己対局中の探索結果の価値と、ゲーム結果の両方を損失として使用している。
前者の損失には、2確率変数の交差エントロピーを計算する必要があるため、自作の損失関数を使用していた。
PyTorchでは、BCEWithLogitsLossが正解データに確率変数を与えることができるため、自作の処理が不要になった。

後者の損失でも、引き分けを学習するため、同様に自作の損失関数を使用していたが、BCEWithLogitsLossを使用することができた。

正解率の計算

Chainerには、正解率の計算をするaccuracy関数とbinary_accuracy関数があるが、PyTorchでは用意されていない。
そのため、以下のような自作の関数を作成した。

def accuracy(y, t):
    return (torch.max(y, 1)[1] == t).sum().item() / len(t)

def binary_accuracy(y, t):
    pred = y >= 0
    truth = t >= 0.5
    return pred.eq(truth).sum().item() / len(t)

これは標準で用意されていてもよいと思うのが。

エポック数とイテレーション数のカウント

Chainerでは、オプティマイザが自動でイテレーション数のカウントして、エポック数をカウントアップするメソッドが用意されている。
PyTorchにはそれに相当する機能がないため、自分で変数をカウントアップし、オプティマイザの状態を保存する際に、それらも同時に保存する必要がある。

torch.save({
    'epoch': epoch,
    't': t,
    'optimizer_state_dict': optimizer.state_dict(),
    }, args.state)

これもPyTorchにも欲しい機能である。

まとめ

ChainerからPyTorchへの移行は比較的容易にできた。
今まで自作でがんばっていたがPyTorchで標準できるようになった箇所もあるが、逆にChainerにあった便利な機能がない箇所もあった。

ChainerからPyTorchへの移行できたので、次はSWAを試す予定である。

2019-12-31

Windowsのネイティブアプリで例外発生時にデバッガを起動する

Windows デバッグ

Windows XP以前では、プログラムが異常終了すると
f:id:TadaoYamaoka:20191231133757p:plain
このようなダイアログが表示されて、デバッガを起動できた。
※このダイアログはWindows10のもの

Windows10のデフォルトの設定では、ダイアログが表示されず、アプリがだまって終了する。
一般ユーザには不要なダイアログなので、デフォルトで表示しないようになったのは理解できる。

しかし、開発者にとっては再現性の低いバグをデバッグしたい場合に、再現時にデバッガでアタッチして原因を調べたい場合がある。
そのような場合、グループポリシーの設定を変更することで、異常終了時にダイアログを表示できるようになる。

ダイアログ表示を有効にする

グループポリシーエディター「gpedit.msc」を起動して、[コンピュータの構成]→[管理用テンプレート]→[Windows コンポーネント]→[Windows エラー報告]を選択して、「重大なエラーが発生したユーザーインターフェースを表示しないようにする」を無効に設定する。
f:id:TadaoYamaoka:20191231134410p:plain
※「gpedit.msc」はWindows Homeでは使用できないが、調べると別の方法で起動する方法がある。

以上で、プログラムが異常終了時にダイアログが表示されるので、[デバッガ]ボタンをクリックすることでデバッガ起動できるようになる。

2019-12-27

MuZeroの論文を読むその１０（再分析、評価）

MuZero 強化学習

今回で、最後です。

付録H 再分析

MuZeroのサンプル効率を改善するために、MuZero Reanalyzeという、わずかに異なるアルゴリズムを導入した。
MuZero Reanalyzeは過去のタイムステップを再検討し、最新のモデルパラメーターを使用して探索を再実行するため、元の探索よりも方策の品質が向上する可能性がある。
この新しい方策は、MuZero訓練中の更新の80％の方策目標として使用される。
さらに、最近のパラメータ $\theta^-$ に基づくターゲットネットワーク $\cdot, v^- = f_{\theta^-}(s^0)$ を使用して、価値関数のよる新鮮で安定したnステップブートストラップターゲット $z_t = u_{t+1} + \gamma u_{t+2} + ... + \gamma^{n-1} u_{t+n} + \gamma^n v^-_{t+n}$ を提供する。
さらに、他のいくつかのハイパーパラメータが調整された。主にサンプルの再利用を増やし、価値関数の過剰適合を回避するためである。
具体的には、状態ごとに0.1ではなく2.0サンプルが取り出された。価値目標は、方策および報酬目標の1.0の重みと比較して0.25まで重みが下げられた。また、nステップ収益は、n = 10ステップではなく、n = 5ステップに削減された。

f:id:TadaoYamaoka:20191225084442p:plain

付録I 評価

各プレイヤーのEloレーティングを測定することにより、ボードゲームでのMuZero（図2）の相対的な強さを評価した。

f:id:TadaoYamaoka:20191125231748p:plain

ロジスティック関数 $p(a \text{ defeats } b) = (1 + 10^{(c_{\mathrm{elo}} (e(b) - e(a)))})^{-1}$ によってプレーヤーaがプレーヤーbを破る確率を推定し、標準定数 $c_{\mathrm{elo}} = 1/400$ を使用してBayesEloプログラム*1によって計算されたベイジアンロジスティック回帰により評価 $e(\cdot)$ を推定する。

Eloの評価

Eloの評価は、訓練中のMuZeroの反復と、ベースラインプレーヤー（Stockfish、Elmo、またはAlphaZeroのいずれか）との間の1手あたり800シミュレーションのトーナメントの結果から計算された。
ベースラインプレーヤーは、1手あたり100ミリ秒の同等の探索時間を使用した。
ベースラインプレーヤーのEloレーティングは、公開されている値*2に固定されている。

Atariの評価

Atariでは、特に指定のない限り、1移動あたり50シミュレーションを使用して、標準の30分またはエピソードあたり108,000フレーム*3に制限された、ゲームあたり1000エピソード以上の平均報酬を計算した。
Atariシミュレーターの決定論的な性質の影響を緩和するために、30のnoopランダムスタートと人間のスタートの2つの異なる評価戦略を採用した。
前者の場合、各エピソードの開始時に、エージェントに制御を渡す前に、ランダムに0〜30回のnoopアクションがシミュレーターに適用される。
後者の場合、開始位置は人間のエキスパートプレイからサンプリングされ、エージェントにコントロールを渡す前にAtariシミュレーターを初期化する。

図S1：AtariでのMuZeroの5ゲームの再現性

f:id:TadaoYamaoka:20191226083106p:plain

合計報酬はy軸に表示され、百万単位の訓練ステップがx軸に表示されている。
暗い線は10回の個別の訓練実行のスコアの中央値を示し、明るい線は個別の訓練実行を示し、影付きの領域は25〜75パーセンタイルを示す。

表S1：30のランダムなno-opスタートの個々のゲームのAtariでのMuZeroの評価

f:id:TadaoYamaoka:20191226084731p:plain

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

表S2：人間の開始位置からの個々のゲームのAtariでのMuZeroの評価

f:id:TadaoYamaoka:20191226085155p:plain

各ゲームの最高の結果は太字で強調されている。
各エピソードは、最大30分のゲーム時間（108kフレーム）に制限されている。

図S4：個々のゲームのAtariでのMuZeroの学習曲線

f:id:TadaoYamaoka:20191226085644p:plain

合計報酬はy軸に表示され、何百万単位の訓練ステップがx軸に表示されている。
線は1000回の評価ゲームの平均スコアを示し、影付きの領域は標準偏差を示す。

感想

付録Hは、本文で少し触れられていた、リプレイバッファを小さくして、サンプル効率を高めたバージョンの詳細について述べられています。

付録Iは、評価結果の詳細について記載されています。
ボードゲームでは、ベースラインプログラム（チェスではStockfish、将棋はelmo、囲碁はAlphaZero）との1手800シミュレーションで、思考時間をそろえた条件で測定されています。ハードウェアの条件は不明です。

Atariの評価は、図S1を見ると毎回ばらつきがあり、ゲームによっては、再現性が低いものもあるようです。
表S1の各ゲームの評価を見ると、montezuma revengeのスコアは0で、まったく攻略できないゲームも見られます。
従来アルゴリズムで攻略できなかったゲームで攻略できるようになったというより、平均的にスコアがアップしています。
SOTAは、57ゲーム中37で、Ape-Xの5、R2D2の13に比べて、MuZeroアルゴリズムでカバーできる範囲は広そうです。

*1:Whole-History Rating: A Bayesian Rating System for Players of Time-Varying Strength | SpringerLink

*2:https://science.sciencemag.org/content/362/6419/1140

*3:[1507.04296] Massively Parallel Methods for Deep Reinforcement Learning

2019-12-26

Leela Chess Zeroウォッチ

LC0

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

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

Test40

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

Test35ゲームでシード

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

SENet

Test35は、新しいニューラルネットワークアーキテクチャであるSENetを導入した。

AlphaZero論文とのマッチング

Test30の間にAlphaZeroの論文がリリースされたため、Test40はそれからいくつかの修正を行った。
これについては、ブログ（https://blog.lczero.org/2018/12/alphazero-paper-and-lc0-v0191.html）で説明されている。

ゲーム終了時の温度低下

AlphaZeroは、最初の15手でのみ温度を使用する。 Test40は、温度を1.2から0.45に下げるだけ。

cpuct式の変更

cpuct定数をAlphaZeroの式に変更

ファーストプレイの緊急度（FPU）

UCB1は探索的すぎるため、未訪問のノードを負けとして扱う。
FPUの利点は、論文：Exploration exploitation in Go: UCT for Monte-Carlo Goで説明されている。

確率的重み平均化

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/342、https://github.com/LeelaChessZero/lc0/issues/237
※まだ採用されていない模様

感想

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

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

2019-12-25

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

将棋AI dlshogi

前回の日記からしばらくぶりですが、その間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を作り始めた動機がディープラーニングで強い将棋ソフトが作れるかだったので、対局時はαβは使わないという方向でアイディアを試していきたいと思っている。

2019-12-23

MuZeroの論文を読むその９（訓練）

MuZero 強化学習

付録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世代になっています。

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

*1:[1511.05952] Prioritized Experience Replay