TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

将棋AIの進捗 その39(リーグ戦)

年末にCPUを3970Xに変えてから、USIエンジンをリーグに加えた強化学習を行っている。
USIエンジンを各探索スレッドにつき2つ、GPUにつき探索スレッドを3つ、3GPUで探索を行っているので、合計18プロセス起動している。
メモリの制約が厳しくこれ以上は起動できなかった。

リーグの構成は、1/8はUSIエンジンと対局して、残りは自己対局を行っている。
1手500msだと局面生成速度は、リーグなしと比べて7割くらいになる。
USIエンジンには、elmo(WCSC28)を使用した。

タスクマネージャの様子
f:id:TadaoYamaoka:20200119000643p:plain
GPU使用率にCUDAの使用率は反映されていない。

リーグ戦の効果測定

リーグ戦を開始してから、途中でdropoutを削除する変更と、未探索ノードの初期値の変更を行ったため、リーグ戦のみの効果は測定できていないが、リーグ戦導入後の損失、floodgateの棋譜に対する正解率、USIエンジンに対する勝率は以下のようになった。

訓練損失

f:id:TadaoYamaoka:20200119001457p:plain

テスト損失

f:id:TadaoYamaoka:20200119001510p:plain

テスト正解率

f:id:TadaoYamaoka:20200119001533p:plain

USIエンジンに対する勝率

f:id:TadaoYamaoka:20200119001948p:plain

考察

リーグ戦を開始したモデルは、既に200サイクル学習したモデルで、テスト損失はほぼ横ばいになっていた。
リーグ戦で学習するとテスト損失は上昇傾向がある。
210epochで急に上昇しているのは、dropoutを削除したためである。
それ以外の区間ではやや上昇している。

方策の正解率は、0.3%程上昇している。
価値の正解率は、ほぼ横ばいである。

テスト損失が上がって、正解率が上がるという結果からは良くなっているのか悪くなっているのか判断がつかない。

USIエンジンとの勝率は、218epochで未探索ノードの初期化方法を変えたことで大幅に上昇した。
それ以外の区間でも少しずつ上昇している。

技巧2との対局

技巧2と1手3秒で100対局した結果は以下の通りである。

結果 勝率 信頼区間
76勝20敗4分 79% 70.0%-86.09%

未探索ノードの初期化方法を修正した同じ対局プログラムして、213epoch時点のモデルを使用すると、

結果 勝率 信頼区間
67勝27敗6分 71% 61.4~79.4%

だったので、強くなっていそうである。

Apery(WCSC28)との対局

技巧2に8割近く勝てるようになったので、Apery(WCSC28)とも対局させてみた。

結果 勝率 信頼区間
55勝41敗4分 57% 47.3%-66.72%

※CPUはCore i7 4コア、GPUは2080Ti 1枚

Apery(4コア(8スレッド))と互角の強さになっていた。
f:id:TadaoYamaoka:20200119091724p:plain

まとめ

USIエンジンをリーグに加えて強化学習を行った効果かは追加で検証しないとわからないが、他の変更の効果も合わせて、Apery(WCSC28)と互角レベルの強さにすることができた。
MCTSは終盤が弱いという課題も克服できつつあると思う。

2019/1/19 追記

やねうら王のEvalShareオプションをtrueにすると、メモリ使用量を減らせることに気付いた。
設定すると、コミット済みが119GBだったが、84GBまで減った。
メモリに余裕ができたので、USIのプロセスを探索スレッドあたり3に増やした。
局面生成速度は、数%速くなった。

将棋AIの進捗 その38(SWA)

dlshogiの学習にSWA(Stochastic Weight Averaging)を実装して、測定した。

SWA

SWA(Stochastic Weight Averaging)は、一定間隔での重みを平均化することで、ニューラルネットワークのテスト精度を改善するテクニックである。
一般的なアンサンブルの手法では予測の結果を平均化するが、SWAでは重みを平均化することで実現する。

SWAの実装

SWAの実装は、PyTorchの実装を参考にした。
この実装では、学習開始時点からの平均を計算するようになっているが、強化学習に適用する場合は、古いステップの重みは忘れていった方が良い。
そこで、平均の代わりに、指数移動平均を使用するように変更した。
DeepLearningShogi/swa.py at master · TadaoYamaoka/DeepLearningShogi · GitHub

Leela Chess Zeroや、KataGoでも、指数移動平均を使用している。

重みを平均化する間隔はKataGoの設定を参考にして250バッチ(バッチサイズ1024)間隔、区間は適当に10とした。

効果測定

dlshogiの強化学習で生成した12サイクル分(1サイクル250万局面、1回の学習で過去10サイクル分を使用)のデータを学習して、188サイクル学習したモデルから追加で学習して効果を測定した。
SWAとdropoutは、どちらもアンサンブルの効果を狙ったもので、目的が重複しているためdropoutなしの場合も比較した。
テストデータには、floodgateの棋譜を使用した。

グラフ凡例
SWA ドロップアウト
master なし あり
nodropout なし あり
swa あり なし
swadropout あり あり
方策のテスト損失

f:id:TadaoYamaoka:20200118134510p:plain

価値のテスト損失

f:id:TadaoYamaoka:20200118134555p:plain

Q値(評価値)のテスト損失

f:id:TadaoYamaoka:20200118134624p:plain

テスト損失の合計

f:id:TadaoYamaoka:20200118135607p:plain

方策の正解率

f:id:TadaoYamaoka:20200118134640p:plain

価値の正解率

f:id:TadaoYamaoka:20200118134658p:plain

考察

方策のテスト損失を見ると、ドロップアウトありなしで、損失の値に開きがあるがこれは、学習時にドロップアウトにより素子が無効化されている影響である。
ドロップアウトの有無の条件が同じもの同士では、SWAを使った方が値が安定しており、最終的にわずかに損失が小さくなっている。

価値のテスト損失も同じ傾向である。
Q値のテスト損失は、ドロップアウトなしの場合SWAなしが最終的な損失が小さくなっているが、損失の合計ではSWAありの方が良い。


方策の正解率は、ドロップアウトなしの方が良く、ドロップアウトの有無が同じ条件では、SWAありの方が良い。
価値の正解率は、ドロップアウトなしの方が良く、ドロップアウトなしの場合SWAなしの方が最終的にわずかに高くなっているが各サイクルで逆転が起きている。


全体的に、SWAがある方が学習が安定して、テスト精度はわずかに高くなることが分かった。
また、ドロップアウトがない方が、テスト正解率が高くなる。

学習時間

SWAを使用した場合の学習時間を比較した。
各サイクルの学習時間平均は以下の通りとなった。

master 2:18
nodropout 2:19
swa 3:02
swadropout 3:03

SWAを使用すると学習時間が、1.3倍になる。
SWAは、学習終了時に重みを平均化したモデルでBatchNormalizationの統計を計算しなおす必要があるため、訓練データを使って順伝播を計算し直す必要がある。
そのため、学習時間が長くなっている。

まとめ

SWAを使用することで、floodgateの棋譜に対するテスト精度が少しだけ上がることが確認できた。
学習時間が長くなるが、学習中も強化学習で局面を生成しているので、それほど問題にはならないのでSWAを採用することにする。

将棋AIの進捗 その37(FPU reduction)

昨日MCTSで未訪問のノードの価値を、動的に親ノードの価値で初期化する方法を試した。
その結果、技巧2(4コア)に対する勝率が、60%から69%(R+68.6)になった。

昨日の結果の考察

今までは0.5(引き分け)で初期化していたため、劣勢の局面で未探索のノードがすべて1回は探索されることになるので、終盤の合法手の多い局面では探索が広すぎる条件になっていた。
十分な数の探索が行われれば問題ないが、探索の深いノードでは十分な数の探索が行われないので、すべてのノードが探索対象となると、ひどい手がバックアップされることになる。
そう考えると、0.5(引き分け)で初期化するのは明らかに良くないと思われる。

0.5(引き分け)にしていたのは、AlphaGoの論文にQ(s,a)=0で初期化するという記述があり、AlphaGoは価値ネットワークの出力を-1(負け)、1(勝ち)としていたためである。
その後、AlphaZeroの中の人の投稿で、探索時は0を負けとしていることが明らかになった。
この時点で、0で初期化することを試したが、dlshogiではかえって弱くなったので、0.5のままとしたという経緯がある。

FPU reduction

Leela ZeroのPRで、FPUを訪問済みのノードの方策の確率に応じて低減することが提案され、有意に差があることが確認されている。
modify fpu reduction depending on visited policy by Eddh · Pull Request #827 · leela-zero/leela-zero · GitHub
※FPU(First Play Urgency)は、未訪問のノードを探索する緊急度を表す用語で、未訪問のノードの初期値のこと

これをdlshogiでも試してみた。

下記式の低減係数C_{FPU}は、ルートで0、中間ノードで0.2とした。
\displaystyle
V(s) - C_{FPU} \sqrt{ \sum_{a'}{ I(N(a')>0) P(a') } }

技巧2との対局結果

技巧2(4コア)と1手3秒で100対局した結果は以下の通り。

条件 結果 勝率 信頼区間
FPU reductionなし 65勝28敗7分 69% 59.9~78.3%
FPU reductionあり 67勝27敗6分 71% 61.4~79.4%

100対局では、有意差は測定できなかった。
対局数を増やして確認してみたい。

FPU低減の係数はチューニングパラメータなので、チューニングでさらに良くなる可能性がある。
また、未訪問のノードの初期値を変えたことで、PUCTの係数も再チューニングを行う予定である。

自己対局のプログラムでも0.5は良くないので、変更する予定である。

将棋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') } }
これは、方策の確率が大きいノードが探索された数が多いほど、探索の緊急度を削減するという意味がある。
次は、この項も加えて検証してみたい。

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

年末に新しい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を試す予定である。

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

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

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

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

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

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

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

MuZeroの論文を読む その10(再分析、評価)

今回で、最後です。

付録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アルゴリズムでカバーできる範囲は広そうです。