TadaoYamaokaの開発日記

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

将棋でディープラーニングする その32(転移学習)

以前の日記で、バリューネットワークを学習した際、SL policy networkからバリューネットワークに転移学習が可能であることに言及した。

転移学習するには、12層まではネットワーク構造が同じであるため、SL policy networkからバリューネットワークにパラメータをそのままコピーすればよい。

モデルのコピー方法

Chainerでモデルを部分的にコピーするには、以下のようにする。

policy_model = PolicyNetwork()
value_model = ValueNetwork()

serializers.load_npz(args.policy_model, policy_model)

value_dict = {}
for path, param in value_model.namedparams():
    value_dict[path] = param

for path, param in policy_model.namedparams():
    value_dict[path].data = param.data

serializers.save_npz(args.value_model, value_model)

一旦モデルのインスタンスを作って、それぞれのモデルのnamedparams()でパラメータのパスとパラメータを取得して同じパスのパラメータの値をコピーすればよい。

転移学習の効果測定

1億局面から学習済みのSL policyのモデルをバリューネットワークにコピーして、elmo_for_learnで生成した100万局面でバリューネットワークを学習したところ以下のようになった。
f:id:TadaoYamaoka:20170607222435p:plain
※凡例のinitialが初期値から学習した場合
※transferが転移学習した場合

1エポック後のテストデータ1万局面のtest accuracyは以下の通りとなった。

初期値 0.6400353908538818
転移学習 0.7109866142272949

転移学習した方がtrain lossが35%小さくなり、test accuracyは11%大きくなっている。

以上の結果から、SL policy networkからバリューネットワークへの転移学習は効果があることが確かめられた。

なお、バリューネットワークの出力はAlphaGoではtanhだが、sigmoidに変更している。
理由は、後ほどSL policyとvalue networkのマルチタスク学習を試したいため、lossを交差エントロピーに揃えたいためである。
上記のtest accuracyは、binary_accuracyで求めている。

モデルのコピーには以下のコードを使用した。
https://github.com/TadaoYamaoka/DeepLearningShogi/blob/master/dlshogi/transfer_policy_to_value.pygithub.com

ChainerをC++から使う

ディープラーニングを使った将棋プログラムを試しているが、将棋プログラムは速度が必要なため、開発言語はC++が適している。
しかし、使用しているディープラーニングフレームワークのChainerはPythonにしか対応していない。

CaffeやCNTK、TensorFlowなどC++で実行可能なフレームワークもあるが、個人的にはChainerが使いやすいので、できればC++からChainerを使用したい。

以前に、ChainerのモデルをC++で読み込んでcuDNNで実行することを試したが、今回はBatchNormalizationやDropoutも使用しているので、スクラッチで作成するには少々無理がある。

ということで、C++からPythonランタイムを呼び出して、PythonでChainerを使うことを考える。
Pythonの呼び出しにはオーバーヘッドがあるので、その影響も考慮する。

実装方法

C++からPythonの呼び出しは、Boost.Pythonを使うことで比較的簡単に実装できる。
(Boost.Pythonのセットアップ方法は以前の日記参照)

#include <boost/python.hpp>

namespace py = boost::python;

py::object module_ns = py::import("module").attr("__dict__");
py::object module_func = module_ns["func"];

module_func();

のようにして、Pythonに定義した関数を実行できる。

Chainerを使用する場合、データの入出力にNumpyを使用する。
NumpyもBoost.Numpyを使うとC++側から簡単に利用できる。

float features[BATCHSIZE][FEATURENUM][H][W];

np::ndarray ndfeatures = np::from_data(
	features,
	np::dtype::get_builtin<float>(),
	py::make_tuple(BATCHSIZE, FEATURENUM, H, W),
	py::make_tuple(sizeof(float)*FEATURENUM*H*W, sizeof(float)*H*W, sizeof(float)*W, sizeof(float)),
	py::object());

auto result_object = predict(features);
np::ndarray result = py::extract<np::ndarray>(result_object);

のようにして4次元Tensorを作成して、Pythonの関数の引数に渡し、結果をndarrayで受け取れる。

計測

上記の実装方法で、Chainerで実装した将棋の指し手を予測する方策ネットワークを呼び出すプログラムを作成し、処理時間を計測してみた。

predict call 1000 times
8480[msec]
8.48[msec per each call]
117.925[nps]

昨日Pythonで計測したときは、140npsだったので、スループット(nps)が落ちている。
C++からPython呼び出しのオーバーヘッドが発生している。

オーバーヘッド計測

オーバーヘッドを計測するため中身のない処理をC++から呼び出した場合の、処理時間を計測した。

dummy call 100000 times
7[msec]
7e-05[msec per each call]

無視できる程度の時間しかかかっていない。
引数、戻り値が一切ない処理の場合は、ほとんどオーバーヘッドはないようだ。

次に、引数と戻り値を方策ネットワークと同じにして、処理をなくしたもので計測してみた。

dummy2 call 1000 times
15[msec]
0.015[msec per each call]

今度は、1000回の呼び出しで15msec、1回あたり0.015msecかかっている。
言語間の変数のバインディングにオーバーヘッドがあるようだ。

ただし、方策ネットワークの実行時間が1回あたり8.48msecなので、それほど気にする必要はなさそうだ。


処理時間の計測には、以下のコードを使用した。
github.com

将棋でディープラーニングする その31(DNNのスループット)

方策ネットワークを対局中に用いた場合のスループットを計測した。

PUCTアルゴリズムで並列で探索をする場合、複数スレッドからGPUを使用するため、複数スレッドから使用する場合を考慮する。

まず、それぞれのスレッドからDNNを実行した場合について計測した。

測定条件

測定条件は以下の通り。

  • 12層、フィルターサイズ3×3、フィルター192枚、入力85枚、出力8181クラスのDNN(Wide ResNet)
  • バッチサイズ 1
  • 1000回ループして処理した時間を計測
  • 3回測定して平均をとる

測定結果

測定結果は以下の通りとなった。
f:id:TadaoYamaoka:20170605111559p:plain

複数スレッドから実行するとスレッドが増えるほどスループットが落ちている。
GPUは同時には利用されず、どこかで排他制御されていると思われる。
複数スレッドからの要求をキューにためておいて、1スレッドから利用した方がよいと言える。

バッチサイズを増やした場合

次に、1スレッドから利用して、バッチサイズを増やした場合について計測した。
f:id:TadaoYamaoka:20170605111855p:plain

バッチサイズが増えるほど線形にスループットが伸びている。
これは、GPU内で並列化が行われ、バッチサイズによらず実行時間が同じになるためと思われる。

NPSについての考察

バッチサイズを4にしても、NPSは560程度であり、将棋プログラムのNPSに比べて圧倒的に少ない。
i7 6700K(4コア4GHzのCPU)でやねうら王2017 Early(SSE42)を動かすと、NPSは3,564,673出ている。

Ponanza Chainerが行っていたように、DNNの実行と並列で従来プログラムで探索を行う方が効果的かもしれない。

PUCTアルゴリズムと従来のプログラムを組み合わせるには、以下のような方式が考えられる。

  • 方策ネットワークの出力がでるまでは、評価関数の値を事前確率として使用する
  • バリューネットワークの出力が出るまでは、評価値の値を使用する
  • 方策ネットワークの出力がでたら、評価関数の値と平均をとる
  • バリューネットワークの出力がでたら、評価値の値と平均をとる

実装が大変そうなのと、期待外れ度を知るのも意味があるので、まずDNNのみを用いてPUCTの実装を試したい。


スループットの計測には以下のコードを使用した。
https://github.com/TadaoYamaoka/DeepLearningShogi/blob/master/utils/throughput.pygithub.com

Ray+Rnのソースを調べる

将棋プログラムでPUCTアルゴリズムを試すため、囲碁プログラムのRayを元にCNTKを使って、ディープラーニングに対応させたRnのソースを調べています。
RnはPUCTアルゴリズムを実装しているので、参考になります。

以下、Windowsでビルドして、ソースをステップ実行するまでの手順です。

ビルド環境

  • Windows Home 64bit
  • Visual Stuido 2015 Community

CNTKダウンロード

以下のサイトからCNTK2.0をダウンロードする。
Releases · microsoft/CNTK · GitHub
Windows→CNTK for Windows v.2.0 GPU
のリンクからダウンロードする。

ダウンロードした「CNTK-2-0-Windows-64bit-GPU.zip」を任意のフォルダに解凍する。

環境変数PATHに
(CNTKを解凍したフォルダ)\cntk
を追加する。

Rnのソースをgit clone

Rnのソースをgit cloneする。

git clone -b nn https://github.com/zakki/Ray

プロジェクトのパス修正

Ray\win\ray\ray.vcxprojをテキストエディタで開く。
「C:\programs\CNTK-2-0-beta12-0-Windows-64bit-GPU」をCNTKを解凍したフォルダに置換する。

「EvalDll.lib」を「Cntk.Eval-2.0.lib」に置換する。

ビルド

Ray\win\ray.slnをVisual Studio 2015で開く。

デバッグビルドだとCNTKが動かなかったため、Releaseビルドにする。
Releaseビルドでは最適化されているため、ステップ実行が行いにくい。
そこで、プロジェクトの構成をコピーして、Release_NoOptを作成し、プロジェクトの設定で、C/C++→最適化を無効(/Od)に設定する。

プロジェクトの構成をRelease_NoOpt/x64にする。

ソリューションをビルドする。

Ray\win\x64\Release_NoOpt\ray.exeを
Rya\直下にコピーする。

GoGuiで実行

GoGuiをダウンロードしてインストールする。
GoGuiを実行し、ray.exeをプログラムに登録する。

プログラムを起動する。

プロセスにアタッチしてデバッグ

Visual Studioで、デバッグ→プロセスにアタッチを選択し、ray.exeにアタッチする。

ソースを調べたい箇所にブレークポイントを設定する。

UCTで探索を行っている箇所は、UctSearch.cppのParallelUctSearchあたりとなる。

CNTKで方策ネットワークを実行しているのは、UctSearch.cppのEvalPolicyあたりとなる。

PUCTのUCB値を計算しているのは、UctSearch.cppのSelectMaxUcbChildあたりとなる。

対局を開始する。
ブレークポイントで止まるので、ステップ実行してソースを調べる。

それぞれ別スレッドで動いているので、デバッグ→表示→並列スタックで、各スレッドのスタックトレースを見るとよい。
f:id:TadaoYamaoka:20170604155838p:plain

将棋でディープラーニングする その30(探索アルゴリズム)

まだ方策ネットワークもバリューネットワークも精度が低いが、精度を上げるのは一旦保留して、対局時の方法について検討する。

以前に考察したように、将棋は読みが重要なゲームであるため、探索を用いず方策ネットワークのみで指しても強くならないと思われる。

AlphaGoでは、モンテカルロ木探索をベースにして、方策ネットワークとバリューネットワークをうまく組み合わせている。

UCTアルゴリズム

代表的なモンテカルロ木探索のアルゴリズムであるUCTアルゴリズムでは、以下のように探索を行う。
毎回ルートノードからUCBが大きいノード(後手では小さいノード)を選択しながらツリーを下っていく。
末端ノードに到達したら、そこからrollout policyに従い終局までプレイする(これをプレイアウトと言う)。
プレイアウトの結果を、末端ノードからツリーを逆に上りながら、ノードの報酬として記録する(これをバックアップと言う)。
末端ノードは一定回数を訪問したら、合法手でノードを展開する。
最終的にルートの子ノードで最も訪問した手を選択する。
f:id:TadaoYamaoka:20170603234401p:plain:w200

UCBは、以下の式で計算される。
\displaystyle
\overline{x_j} + \sqrt{\frac{2\log n}{n_j}}
\overline{x_j}は期待報酬、nは親が同じノードの訪問数の合計、n_jはノードの訪問数

この式は、(期待値)+(バイアス項)という構成になっており、期待報酬が高いところを選択するが、訪問数が少ないノードを優遇するという意味を持つ。

PUCTアルゴリズム

AlphaGoでは、UCTアルゴリズムの代わりに方策ネットワークとバリューネットワークを使ったPUCTアルゴリズム*1を採用している。
PUCTアルゴリズムでのノード選択の基準は、以下の式で計算される。
\displaystyle
\begin{equation}
Q(s_t,a)+u(s_t,a)
\end{equation}

Q(s_t,a)はバリューネットワークの出力とプレイアウトの結果の平均で、期待報酬を表す。
u(s,a)は、以下の式で表される。
\displaystyle
u(s,a) = c_{puct} p(s,a) \frac{\sqrt{\sum_b N_r(s,b)}}{1 + N_r(s,a)}
c_{puct}は定数、p(s,a)は方策ネットワークの出力を事前確率として使用する。
N_r(s,a)はノードaの訪問数を表す。
\sum_b N_r(s,b)は親が同じノードの訪問数になる。

PUCTの値の役割は、UCBと同じだが、期待報酬にバリューネットワークの出力を使い、バイアス項に方策ネットワークの出力を使うことで、候補手選択の精度を高めている。

将棋への応用

将棋では囲碁のようにプレイアウトで終局までプレイしてもあまり精度が上がらないことが知られている。
将棋のように狭い読みが必要なゲームでは、プレイアウトで求めた期待報酬が実際の報酬と乖離することが多いためと考えられる。

そのため、PUCTアルゴリズムを将棋に適用する場合は、プレイアウトを使わずに、バリューネットワークの出力のみを期待報酬として用いた方が有効と考えられる。
ノードは1回訪問したら展開し、選択したノードのバリューネットワークの出力を上位のノードにバックアップする。

AlphaGoでは、方策ネットワークとバリューネットワークの計算中に、並列でプレイアウトを行うことで、効率を上げている。
プレイアウトを行わない場合は、各ノードで方策ネットワークとバリューネットワークの計算を待つ必要がある。

モンテカルロ木探索は、ルートノードから並列化を行うことで効果がある知られているため、GPUの処理限界まで並列化を行い効率を上げることが有効と思われる。

並列化を行っても、従来の評価関数ベースの探索に比べたら探索ノードはかなり少なくなると思われる。
そのため、方策ネットワークとバリューネットワークのモデルの精度が高くないと強いプログラムはできない。

モデルの精度向上は別課題として、次回からPUCTアルゴリズムの実装を試したい。

将棋でディープラーニングする その29(強化学習【修正版】)

以前にRL policy networkを学習する際の報酬に応じた勾配の実装方法について記述したが、計算方法に誤りがあった。

softmax_cross_entroyを修正して、backwardの際の勾配に重みを掛けていたが、lossを計算する際に重みが掛けられていないため、間違ったlossを使用していた。

Twitterでアドバイスを頂いたので、その方法で実装し直した。

softmax_cross_entroyは出力がスカラー値になっているが、オプションにreduce='no'を指定すると、平均される前のバッチの状態でlossが取得できる。

そのlossに対して重みを掛けた後に、平均をとることで、正しいlossが計算できる。

Chainerでは以下のように実装する。

loss = F.mean(F.softmax_cross_entropy(y, t, reduce='no') * z)
loss.backward()

※zはバッチごとの報酬

この実装で計算される損失は、出力と報酬により以下の関係になる。

出力 報酬 損失
正解 正の小さい値
正解 負の小さい値
誤り 正の大きい値
誤り 負の大きい値

※出力正解は選択された行動の遷移確率が高い場合で、誤りは遷移確率が低い場合
上記表の〇のデータが増えるように学習される。
つまり、損失の期待値を最小化する。

RL policy networkの学習

勾配計算を修正後、RL policy networkの学習をやり直した。
f:id:TadaoYamaoka:20170603160527p:plain
前回は途中で値が発散して学習できなくなったが、とりあえず1000イテレーション分学習ができた。
500イテレーション置きにパラメータを保存して、保存したパラメータと自己対戦するようにしている。
500イテレーションまではわずかに勝率が上がって、それ以降は勝率が落ちている。
学習が成功しているとは言い難い。
モデルの精度が低いと、対戦相手のミスで勝利することもあり、意味ある勝敗にならないことが原因と思われる。
あるいは、まだ学習方法に誤りがあるかもしれない。

elmo_for_learnの教師データで強化学習

自己対戦の結果の精度が低いと思われるので、elmo_for_learnで生成したデータの勝敗データを使用してRL policy networkの学習を行った。
f:id:TadaoYamaoka:20170603162602p:plain
学習率0.001、ミニバッチサイズ64で試したところ、はじめ順調にlossが低下していたが、途中で値が発散してしまった。

学習率変更

学習率を半分の0.0005にしてみたが、やはり発散する。
f:id:TadaoYamaoka:20170603202241p:plain


強化学習うまくいかないので、一旦保留することにします。

github.com

将棋でディープラーニングする その28(学習の高速化その2)

学習の高速化のため先日作成したPythonから使えるC++の将棋ライブラリ(cppshogi)に、RL policy networkも対応させました。

以前は将棋ライブラリとしてpython-shogiを使用していましたが、全てcppshogiに置き換えました。
これによって、学習がかなり高速化しています。

RL policy networkの学習

RL policy networkの学習の自己対戦が、以前は16ゲームをミニバッチとした1回のイテレーションに1分半かかっていましたが、4秒で終わるようになりました。
これでRL policy networkの学習をまともに行うことができるようになります。

また、今回は学習時にelmoの評価関数で各局面の評価値を求めて、その値をシグモイド関数で推定勝率に変換して、下記式のv(s_t^i)に使用しています。
\displaystyle
\Delta \rho = \frac{\alpha}{n} \sum_{i=1}^n \sum_{t=1}^{T^i} \frac{\partial \log p_\rho (a_t^i \mid s_t^i)}{\partial \rho} (z_t^i - v(s_t^i))
これにより、すでに評価値が高い局面で勝利した場合は報酬が少なくなり、評価値が低い局面から勝利した場合には報酬が多くなるように学習できるようになります。
つまり、勝敗に影響がある手をうまく学習できるようになります。

elmo_for_learnで1億局面を生成し、SL policy networkで学習させたモデルを使って、RL policy networkを学習させたところ、一応学習が進むことを確認しました。
f:id:TadaoYamaoka:20170602225632p:plain

しかし、途中から勝率が1.0になってしまい、必ず勝つ手順を覚えてしまっています。
まだ、モデルの精度がよくないため、大駒を序盤で捨ててしまい、評価値3000以上で勝ちとしているため、すぐに勝ちとなってしまいます。
モデルの精度がある程度高くないと、うまく学習できないようです。

使用したSL policy networkの精度

1億局面を学習したSL policy networkは、40%の一致率になっていますが、まだ序盤で大駒を捨てることが良くあります。
f:id:TadaoYamaoka:20170602225940p:plain
elmo_for_learnのデータは初期局面集から生成しているので、初手からの序盤の精度が落ちている可能性があります。

別のRL policy networkの学習方法

SL policy networkは局面を増やしても精度が上がらなくなっているので、別の方法を試そうと考えています。

elmo_for_learnで生成したデータは、勝敗データと評価値、指し手を含んでいるので、上記式のそれぞれz_t^iv(s_t^i)a_t^iとして使用可能です。
したがって、自己対戦を行わなくても、elmo_for_learnのデータで強化学習が可能です。
こちらの方法の方がうまく学習できる見込みがあります。
勝敗データを使うので、SL policy networkの精度を改善できると考えています。


次回は、elmo_for_learnのデータを使った強化学習を試す予定。

cppshogiに対応したコードをGitHubに公開しました。
python-shogiに依存したコードは削除しました。
github.com