PythonでAlphaZero Shogiを実装する その4

迫田さんのブログで、AlphaZeroは自己対局時にノードを再利用しているという根拠のリンクが貼られていて、確認したことろ確かにDeepMindの中の人がノードを再利用していると答えていました。
Accelerating Self-Play Learning in Goを読んだ - 水たまり

Alphazero news - Page 22 - TalkChess.com

[Q] Normally, an MCTS search would do "tree reuse" from move to move, carrying forward the subtree that was actually chosen. But during the training, there is noise added to the root. If one does tree reuse, the effect of the noise is lessened. Leela Chess Zero decided to disable tree reuse because of that. Leela Zero has kept it enabled.

[A] It is enabled at all times unless we are testing something specific that will be affected by it. We introduce diversity in two ways - dirichlet noise and visit count sampling.
Dirichlet noise is used to modify prior at the root node before each search (if it's enabled). So if a subtree is reused, when the next search starts it will be added to the node that is now the root node.
Visit count sampling isn't really affected.

AlphaZeroの論文ではノードの再利用については触れられていなかったため、dlshogiの自己対局を実装する時にどちらにするか悩みました。
dlshogiでは、相手の探索の結果が、自分の探索の結果に影響してしまうため、勝率にも影響がでそうなので、ノードの再利用は行わないようにしました。
しかし、AlphaZeroでは再利用を行っていたようです。

質問には再利用するとディリクレノイズの影響が少なからずあると書かれていますが、回答では、ノイズはルートノードのみに加わるので次の手番には持ち越されることはないとあります。
確かにその通りで、再利用の影響があるとすると木のバランスが先手、後手で非対称になることくらいです。
それも、影響がでるのは初めの数手で、後の方になると双方が再利用するノード数も同じくらいになるので、影響はなさそうです。
30手までは局面のバリエーションを増やすために訪問数に応じた分布で選択しているので、木のバランスも気にする必要はありません。

そう考えると再利用する方が、探索の精度が上がるため、正解な気がしてきました。

Leela Chess Zeroは再利用なしで、Leela Zeroは再利用しているようです。

dlshogi-zeroも、再利用するように修正しました。
ノードを再利用する · TadaoYamaoka/dlshogi-zero@2f1d2a6 · GitHub

dlshogiの方は、世界コンピュータ選手権が終わったら修正することにします。

【書籍】囲碁ディープラーニングプログラミング（翻訳）

マイナビ出版から「囲碁ディープラーニングプログラミング」という本が出版されます。
私は翻訳者として関わらせてもらいました。
PythonとKerasを使って、AlphaGo、AlphaGo Zeroの仕組みを一つずつ実装しながらディープラーニングを学べる入門書になっています。
囲碁プログラミングを題材にして、ディープラーニングの概念を初級から中級レベルの内容まで解説しています。

book.mynavi.jp

表紙のイラストは、天地明察の槇えびし先生です！

4/14(日)の技術書典6で、マイナビ出版「こ21」から先行販売されます。
どうぞよろしくお願いいたします。

書籍サポートサイト

『囲碁ディープラーニングプログラミング』サポートサイト | マイナビブックス

サポート情報（非公式）

出版社のサイトに記載される前の情報について記載します。

• p.103 図4.1

【誤】左側の図の四角の印の右隣の石は黒
【正】左側の図の四角の印の右隣の石は白

• p.103 図4.1 Bの説明

【誤】Bに打つと白の方が良いかもしれないが、黒は取られる心配がなくなる
【正】Bに打つと白にとってさらに良いかもしれないが、黒は悩む必要はない

• p.218 リスト7.17

【誤】X, y = generator.next()
【正】X, y = generator.__next__()

• p.60 リスト3.6

【箇所】
else:
if neighbor_string not in adjacent_opposite_color:
adjacent_opposite_color.append(neighbor_string)
【誤】else:ブロックのインデントが1つ深い

• 補足

サンプルのスクリプトを実行するには、codeディレクトリにあるsetup.pyを実行する必要があります。
codeディレクトリで、
pip install -e .
を実行してください。
GPUを使用する場合は、実行する前にcodeディレクトリにあるsetup.pyのtensorflowをtensorflow-gpuに書き換えてください。
これによりパッケージがインストールされます。アンインストールするには、
pip uninstall dlgo
を実行してください。

• TensorFlow、Keras、NumPyバージョンについて

masterブランチと章ごとのブランチでsetup.pyに記述されているバージョンが異なっています。
masterブランチのsetup.pyでは、

      install_requires=[
            'numpy<=1.14.5', 
            'tensorflow>=1.10.1', 
            'keras==2.2.2', 

となっていますが、章ごとのブランチではバージョンが指定されていないため、最新バージョンがインストールされます。
バージョン不整合が起きる場合はsetup.pyをmasterブランチと同じにするか、masterブランチのsetup.pyのバージョン番号指定を削除してください。
また、最新のTensorFlow（1.13.1）では、古いnumpyのバージョンでは動かないため、numpyのバージョンが必要です。
したがって、masterブランチのsetup.pyのnumpyのバージョン指定を削除し、numpyのバージョンアップ(pip install numpy -U)を行う必要があります。
バージョンを指定してインストールする場合は、
pip uninstall tensorflow
pip uninstall keras
pip install tensorflow==1.10.1
pip install keras==2.2.2
のようにアンインストールしてからバージョンを指定してインストールしてください。（TensorFlowでGPUを使用する場合は、tensorflow-gpuとしてください。）

将棋AIの進捗 その28(探索時のノイズの効果)

世界コンピュータ選手権まで残り1ヵ月もなくなったので、強化学習で強くするのはあまり望めないので探索部の調整を行っている。

以前のdlshogiでは、Policyの読み漏れによって、受けを間違えて数手先で詰まされる状況がよく起きていたため、Policyにノイズを加えて対策を行っていた。
ノイズをどれくらい加えるかは、GPSFishと対局の勝率から手動で調整を行い、効果が高かった1手目と3手目に加えていた。

手動で数回の実験で適当に決めていたこともあるので、今回ノイズの効果を測定し直すことにした。

測定条件

GPSFishに加えて技巧2とも対局を行って1手3秒、100回対局の勝率をノイズの条件を変えて測定した。

GPSFishとの対局は、CPUはCore i7-7700K(4コア)、GPUはGeForce 1080(1枚)。
技巧2との対局は、CPUはCore i7-6700K(4コア)、GPUはGeForce 1080Ti(1枚)。
やねうら王互角局面集を使用して先後入れ替えて対局。
ノイズは、0.3%の確率で1になる分布をPolicyとεの割合で按分する。
3手目のノイズは0.1%の確率でPolicyの確率を1.5倍にする。

測定結果

GPSFish

条件	勝率
1手目(ε=0.5)と3手目	70%
1手目のみ(ε=0.5)	70%
1手目のみ(ε=0.25)	74%
ノイズなし	78%

技巧2

条件	勝率
1手目(ε=0.5)と3手目	12%
1手目のみ(ε=0.5)	24%
1手目のみ(ε=0.25)	22%
ノイズなし	26%

考察

ノイズには少なからず効果があると考えていたが、ノイズがない場合がGPSFishに対しても技巧2に対しても一番勝率が良かった。
Policyの精度が低いうちは読み漏れによって、浅いトラップを見逃す可能性が高いが、Policyの精度が上がると探索の精度を落とすことになっていたようだ。
追試で、1手目(ε=0.5)と2手目にノイズを加えてみたが、GPSFishに対して勝率は67%と一番低い結果になった。

今までノイズありで、探索パラメータを調整していたため、大会までにノイズなしで調整し直すことにする。

Python環境をVisual Studio 2017に移行

Python3.5はVisual Studio 2015でビルドされているため、余計なトラブルを避けるためVisual Studio 2015を使い続けてきた。

最近、Visual Studio 2015が起動して数分後に30秒くらい固まる現象が起きて、再インストールしたりしたが直らないので、しばらく我慢して使っていた。
毎回固まるのはストレスがたまるので、思い切ってVisual Studio 2017に移行することにした。
先日Visual Studio 2019がでたところで、今更なのだが。

Pythonとの互換性

最新のAnacondaのPythonのバージョンは3.7で、3.7はVisual Studio 2017でビルドされているため、Visual Studio 2017にしてもPythonを使う上で問題はない。
Visual Studio 2017は細かくリビジョンが分かれている。
最新のVisual Studio 2017のデフォルトのツールセットは、15.9で、AnacondaのPythonは15.8でビルドされている。
リビジョンの違いは問題ないのか気になって調べたところ、Visual Studio 2015以降C/C++のランタイムはバイナリ互換が保たれている。
リビジョンの違いは影響なさそうだ。

なお、Visual Studio 2019にしない理由は、CUDA10が、まだVisual Studio 2019をサポートしていないためである。

Chainerのインストール

Visual Studio 2017に移行したので、ディープラーニングフレームワークの再インストールを行った。

Chainerをcupyからインストールしようとしたところ、

    building 'cupy.core._dtype' extension
    error: Microsoft Visual C++ 14.1 is required. Get it with "Microsoft Visual C++ Build Tools": https://visualstudio.microsoft.com/downloads/

というエラーがでてインストールできなかった。
14.1は、Visual Studio 2017のことなのでビルド環境は問題ないはずなので、Chainerのソースに何か問題があるようだ（別のCythonを使うパッケージはインストールできている）。

Chainerは、Windows向けにもビルド済みパッケージが配布されているので、そちらからインストールすることにした。

pip install cupy-cuda100
pip install chainer

で問題なくインストールできた。

TensorFlow

TensorFlowもビルド済みパッケージが配布されているので、Visual Studioのバージョンは関係なくインストールできる。

pip install tensorflow-gpu

Boost.Python

PythonからC++でビルドしたモジュールを使うためにBoost.Pythonを利用している。
Visual Studio 2015でビルドしたBoostが使えなくなったので、Visual Studio 2017でビルドし直した。
今まで使っていた1.59.1は、Visual Studio 2017ではビルドできなかった。C++の構文エラーが発生するようになっていた。
Boostのバージョンを最新の1.69.0にしたところ、今度は問題なくビルドできた。

Visual Studio 2015と2017でビルドしたコードの速度の比較

dlshogiをビルドし直してバージョンアップ前後の速度を比較してみた。

初期局面の探索速度

2015	7649.0 nps
2017	7646.6 nps

※3回測定した平均
違いはなかった（GPU律速なので当然だが）。

ということで、これまでより（固まらないという意味で）快適にコーディングできるようになりました。
ちなみに、Visual Studioはバージョン4から使っています。
Borland C++も持っていましたがIDEとしてはVisual Studioが使いやすかったですね。

PythonでAlphaZero Shogiを実装する その4

AlphaZeroでは、訓練と自己対局は並列で行われ、チェックポイントで自己対局で使用するネットワークが最新のネットワークに更新される。
チェックポイントは、ミニバッチサイズ4,096で、1,000ステップ間隔だが、チェックポイントの間に何ゲーム行われるかを論文から推測してみた。

チェックポイントあたりのゲーム数

• 70万ステップを12時間で完了
• チェックポイントは、ミニバッチサイズ4,096で、1,000ステップ間隔
• 自己対局は、5,000アクター（※疑似コードから）が並列で対局

以上が、AlphaZeroの論文に記載されている条件である。

これだけでは、推測できないので、自己対局で増える局面数と学習に使える新規の局面数の増加速度が同じで、学習に使う1ゲームあたり平均150手という仮定をおくと、1,000ステップを5,000並列で実行し、1ステップが4096手分なので、チェックポイントあたりのゲーム数は、
1000ステップ / 5000 * 4096手 / 150手 = 5.46 ゲーム
と算出できる。

なお、論文では、AlphaZero Shogiでは、70万ステップを12時間で完了しているため、1手あたりの時間は、
12時間/70万ステップ/4096*5000 = 0.075秒
と計算できる。
1回の対局が平均150手と仮定すると、1ゲームあたりは、11.3秒となる。

実装への反映

dlshogi-zeroは、訓練と自己対局を別々のプログラムで作成しているので、訓練と自己対局のバランスを、AlphaZero Shogiと同じにしようとすると、頻繁にプログラムを切り替えることになる。
プログラムの開始時のモデルのコンパイルなどを毎回行うと効率が悪いので、効率の良い仕組みを考えたい。

GPU1枚でも実行できるようにしようとすると、GPUは排他的に利用されるため、同時に実行はできないので、交互に実行することになる。
そうすると、1つのプログラムで、モデルを共有して訓練と自己対局を行うようにした方がよさそうだ。

1つのプログラムで訓練と自己対局を交互に行うとすると、以下のような流れになる。

1. チェックポイントを一定の局面数として、並列で実行しているエージェントのどれかのゲームが終了するたびに、チェックポイントに達しているかチェックする。
2. チェックポイントに達していたら、すべてのエージェントの実行を止めて、訓練を行う。
3. 訓練が完了したらモデルが更新される。
4. 最新のモデルを使って自己対局を再開する。

できれば、この実装に変更して、技術書典6の本に反映したい（間にあうだろうか・・・）。

追記（別の方法で検証）

自己対局で増える局面数と学習に使える新規の局面数の増加速度が同じと仮定したが、実際は自己対局で増える局面数の方が多いかもしれない。
ここからは誤差の大きい推測になるが、初代AlphaGoでは方策ネットワークの推論に3msかかっているため、ネットワークの規模の比率から1手あたりの時間を推測して、算出してみる。
初代AlphaGoの方策ネットワークは13層、192フィルタ、画像サイズ19×19で、
AlphaZero Shogiの方策ネットワークは83層（Resnet40ブロック+入力1+出力2）、256フィルタ、画像サイズ9×9で、
推論の計算量は、層数L、フィルタ数K、画像の幅Wとすると、計算量は、（あっているか自信なし）となるので、
計算量は、1.29倍となる。
したがって、1手800シミュレーションなので、1手あたり、6.11秒かかる。
1,000ステップあたりのゲーム数は、
12時間/70万ステップ*1000/6.11/150*5000=336.56ゲーム
となる。

自己対局で増える局面数と学習に使える新規の局面数の増加速度が同じという仮定は外れていそうだ。

こちらの推測を元にすると、別々のプログラムでもよいかもしれない。

2019/3/29追記

コメントで、AlphaZero論文のTable S3に訓練ゲーム数が記載されているとご指摘いただいたので、その値で計算し直してみました。
Table S3を完全に見落としていました。

Table S3には、

Mini-batches	700k
Traing Time	12h
Traning Games	24 million

と記載されています。

したがって、チェックポイントごとのゲーム数は、
24,000,000ゲーム*1000ステップ/70万ステップ=34285.71ゲーム
となります。
予測よりもずっと大きかったです。

あまりにも予測と差が大きいので、予測の方の何かの前提が間違っていそうです。
Table S3にThinking Timeが800sims～80msと記載されているので、1手80msのようです。

1つのアクターが並列化なしで800シミュレーションを80msで実行するのはおそらく不可能なので、一つ一つのアクターについてもなんらかの並列化を行っていそうです。

【告知】技術書典6で「ディープラーニングを使った将棋AIの作り方～強化学習編～」という本を頒布します

日記で何回かふれていますが、改めて、技術書典6で「ディープラーニングを使った将棋AIの作り方～強化学習編～」という本を頒布します。
techbookfest.org

シリーズ3冊目になります。今回は、AlphaZero Shogiの仕組みの解説と、AlphaZero Shogiを忠実にコピーしてPythonで実装したdlshogi-zeroの実装方法の解説です。

ソースが動くようになるまで苦労しましたが、本は2週間で書き上げました。分量は60ページ前後になります。500円の予定です。
印刷の締め切りぎりぎりまでねばって、ゼロからの学習の実験結果を載せる予定です。

2冊目のときは50部しか用意していなくて、午前中でなくなってしまったので、今回は多めに（200部？）刷る予定です（チェック数あんま多くないのでいっぱい余ったらどうしよう・・・）。
あと、電子版はないですかと聞かれたことがあるので、本に電子版のURLも付けるつもりです。
かんたん後払い決済に対応してないんですかと聞かれたこともあるので、今回は対応するつもりです。
既刊も少しだけ刷るつもりです。

ということで、どうぞよろしくお願いいたします。

↓本の目次です。

将棋AIの進捗 その28(弱点の克服)

前回、自己対局の報酬を詰み探索の結果に変更したことで、valueの精度向上したことを書いた。

詰み探索結果を報酬にしたのは、評価値が2000近くある局面から、詰みが見つかり一気に負ける局面があるためだが、そのような局面をより積極的に是正することにした。

方法

優勢と考えていた局面から負けた局面の評価を正しくするには、そのような局面を学習する機会を増やせばよいため、そのような局面を抽出して初期局面集に追加することにした。

今まで自己対局で生成した局面を3億局面以上残しているので、その中から評価値が高い状態から負けた局面を抽出した。
似た局面を減らすために、同一局面で抽出する間隔は10手以上空けた。

そのように抽出した局面を初期局面集に追加して、自己対局を継続した。
初期局面集はもともと3.7億くらい用意していたところに、100万局面くらいを追加した。
元の初期局面集が十分に大きいので、今回追加した局面に極端に偏った学習はされないという見込みである。
なお、初期局面集から1手ランダムに指した後の局面を自己対局の開始局面としている。

15サイクル自己対局を行った結果

1サイクルあたり250万局面生成して学習するというサイクルを15サイクル回した結果、floodgate R3500以上の棋譜との一致率は以下の通りとなった。

	policy loss	value loss	policy acc.	value acc.
120サイクル(初期局面集に追加前)	1.1045078	0.53318536	0.4404205	0.71591663
135サイクル(初期局面集に追加後)	1.1010139	0.5307383	0.44042057	0.7164469

一致率は、それほど変わっていないが、value lossが低下している。グラフで見ると、120サイクルまでは横ばいだったvalue lossが120サイクル以降下がっているのが確かめられる。

※80サイクル目以降、policyのlossが上がっているのは、詰み探索を報酬にした結果、詰みに関係する指し手とそれ以外の指し手の予測が難しくなったためと思われる。

このことから、勝率の予測がより正確になったと考えられる。

強さの測定

実際に強くなっているか確認するため、やねうら王 2017 Early KPPT 4.55 64SSE4.2と対局させてみた。
1手3秒で100回対局させた結果、勝率は29%となった。

※CPUは4コアのCorei7 6700K、GPUは1080Ti1枚、やねうら王互角局面集を使用

今までは数%程度だったので、勝率が上がっている。
苦手な局面を初期局面集に追加することは、偏りがでないように注意が必要だが、効果があったと言えそうだ。

余談

モンテカルロ木探索とディープラーニングを使う方法は、工夫しだいで個人レベルでも十分に強くできる見込みがあると思います。
将棋AIはαβ探索が主流ですが、選択的探索の方法が同じくらいの強さになると、コンピュータ将棋の大会も対立構造ができてより面白くなるのではないかと思います。

ということで、モンテカルロ木探索＋ディープラーニングを盛り上げるべく、技術書典6で本を出します。
techbookfest.org

以上、宣伝でした。