TadaoYamaokaの開発日記

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

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

前回の日記で、ブートストラップについて少し書いたが、1000万局面では効果がわからなかったので、局面を増やして再度検証した。

ブートストラップ

前回も書いたが、本来の報酬(勝敗)とは別の推定量(探索結果の評価値)を用いてパラメータを更新する手法をブートストラップという。
elmo_for_learnで生成したデータには、局面の探索結果の評価値が含まれているので、バリューネットワークの値をその評価値に近づけるように学習することで、学習の効率を上げることができると思われる。
経験的にブートストラップ手法は、非ブートストラップ手法より性能が良いことが知られている。

ブートストラップ項を加えた損失関数

elmoと同様に、ブートストラップ項の損失には、2確率変数の交差エントロピーを使用する。

バリューネットワークの値をp、探索結果の評価値をシグモイド関数で勝率に変換した値をqとした場合、交差エントロピーは以下の式で表される。
\displaystyle
\begin{eqnarray*}
H(p, q) &=& - \sum_t p(t) \log q(t) \\
 &=& -p \log q - (1 - p) \log(1-q)
\end{eqnarray*}

交差エントロピー偏微分は、
\displaystyle
\frac{\partial H(p, q)}{\partial w} = q - p
となるが、Chainerで実装する場合、backwardの処理をGPUで計算できるように、cudaの処理を記述する必要がある。
技量不足でその部分を実装できなかったため、交差エントロピーを以下のように計算して、微分は計算グラフの処理に任せることにした。

def cross_entropy(p, q):
    return F.mean(-p * F.log(q) - (1 - p) * F.log(1 - q))

このブートストラップ項に係数\lambdaを掛けて、元の損失関数に加える。
損失関数は以下の通りになる。

loss1 = F.mean(F.softmax_cross_entropy(y1, t1, reduce='no') * z)
loss2 = F.sigmoid_cross_entropy(y2, t2)
loss3 = cross_entropy(F.sigmoid(y2), value)
loss = loss1 + loss2 + args.val_lambda * loss3

loss1は指し手予測(policy network)の損失、loss2は勝率予測(value policy)の損失、loss3がブートストラップ項である。

測定結果

ブートストラップなしで2億局面学習したモデルから、ブートストラップなし/ありで、8000万局面を学習して精度を比較した。

train loss1 train loss2 train loss3 test acc.(policy) test acc.(value)
ブートストラップ項なし 0.8883 0.4638 0.4439 0.7651
ブートストラップ項あり 0.8853 0.4741 0.4427 0.4444 0.7658

train loss2(value networkの損失)は、ブートストラップ項のなしの方が減少しているが、test accuracyはブートストラップ項ありの方がわずかに良い。
train loss3はブートストラップ項ありの場合のみ測定しているが、初期から減少を続けており、value networkの予測が評価値に近づいている。

GPSfishとの対局

ブートストラップ項ありで学習したモデルで、GPSfishと対局させた。
f:id:TadaoYamaoka:20170628075612p:plain
GPSfishに勝つことができた。
評価値はGPSfishとほぼ同じ傾向だが、GPSfishより早く評価値が付いている。

ブートストラップ項なしで学習したモデルでは以前と同様に、評価値がGPSfishより遅れて不利を判断しており、勝つことができなかった。
ブートストラップ項を追加することで、バリューネットワークの学習効率が上がることが確かめられた。

これで、ディープラーニングのみでも(GPSfishよりも)強いソフトが作れることが確認できた。
この方法で、さらに学習を進める予定。

将棋でディープラーニングする その38(学習継続中)

前回の日記で、利きを入力特徴に加えることで精度が上がることを確認したので、利きを追加したモデルで、初期値から学習をやり直した。

学習データには、elmo_for_learnで深さ8で生成した、1億5千万局面を使用した。

以前に生成したときは、引き分けの局面も出力していたが、引き分けの報酬を0(または1)として学習すると、精度に悪影響があるため、今回は引き分けは出力しないようにした。

iteration単位

ミニバッチサイズ32で、1000iterationごとのtrain loss、test accuracyは以下の通りとなった。
policy networkとvalue networkをマルチタスク学習しているので、test accuracyはそれぞれ求めている。
f:id:TadaoYamaoka:20170626145033p:plain
train lossが急に上がっている箇所は、棋譜を1000万局面単位で生成してその単位でソートしているため、局面に偏りが出ているためである。

epoch単位

1000万局面を1epochとした場合、epoch単位では以下の通りとなった。
f:id:TadaoYamaoka:20170626145326p:plain

train lossは、まだ減少しているが、ほとんど進まなくなっている。
test accuracy(policy)もまだ増えているが、ほとんど進まなくなっている。
test accuracy(value)は、10epochあたりから0.75から変化していない。

GPSfishと対局

GPSfishと対局すると、GPSfishが劣勢と判断している局面でも優勢と判断しており、かなり遅れてマイナスとなっている。
f:id:TadaoYamaoka:20170626145917p:plain
バリューネットワークが勝敗がはっきりするまで局面を正しく学習できていないようである。

バリューネットワークは、局面の勝率を学習するため、似た局面での勝ち、負けのデータが十分な量必要になる。
1億5千万局面では不十分と思われる。

バッチサイズ変更

勝率は確率的な事象であるため、バッチサイズが小さいと学習できない可能性があるため、バッチサイズを変えて学習してみた。
16epoch目をミニバッチサイズを変えて学習した場合の、train lossとtest accuracyは以下の通りとなった。

ミニバッチサイズ train loss1 train loss2 train loss test acc.(policy) test acc.(value)
b=32 0.9122 0.4522 1.3644 0.4301 0.7569
b=64 0.9102 0.4592 1.3694 0.4362 0.7604
b=128 0.8997 0.4672 1.3669 0.4377 0.7626
b=256 0.8997 0.4683 1.3680 0.4386 0.7620
b=512 0.8998 0.4684 1.3683 0.4380 0.7620
b=1024 0.9049 0.4719 1.3769 0.4371 0.7609

loss1は指し手(policy network)の損失、loss2は勝率予測(value network)の損失を示す。

b=32がtrain lossが一番低くなっているが、test accuracyは一番悪くなった。
b=256がtest accuracy(policy)が最も高い。test accuracy(value)は、b=128が最も高いが、b=256,512もほぼ同じである。
よって、b=256を採用することにする。
学習時間もb=32では1000万局面で1:56:08だったが、b=256にすることで1:15:18と短くなる。

ブートストラップ

elmo_for_learnで生成したデータには、局面の探索結果の評価値が含まれている。
バリューネットワークの値をその評価値に近づけるように学習することで、学習の効率を上げることができないか試した。

このように別の推定量を用いてパラメータを更新する手法をブートストラップと呼び、elmoでも用いられている
また、数手先の探索の評価値を用いるため、TD学習とも呼ばれる。
理論的には理由が明らかにされていないが、経験的にブートストラップ手法は、非ブートストラップ手法より性能が良いことが知られている。

train loss1 train loss2 train loss3 test acc.(policy) test acc.(value)
ブートストラップなし(b=128) 0.9031 0.4620 0.5077 0.4377 0.7628
ブートストラップあり(b=128) 0.9007 0.4744 0.4466 0.4370 0.7621

train loss3はブートストラップ項の損失で、バリューネットワークの値と探索結果の評価値をシグモイド関数で勝率に変換した値との交差エントロピーを示す。
ブートストラップ項の損失には係数\lambda=0.5を掛けている。

train loss3は下がっているので、評価値に近づいているが、test accuracy(value)はほとんど変わっていない。
この測定だけでは、効果があるか不明である。
一旦採用しないで学習を進めることにする。

WindowsでChainerをGPUを使って動かす(v2.0対応)

Windowsで安定して使用できるv1.24を使用していましたが、Chainer v2.0でパフォーマンスが向上するということなので、アップデートしました。

v1.24用のコードに一部修正が発生しましたが、軽微な修正で対応できました。

アップデート手順

v1.24をアンインストールして、インストールし直す。

pip uninstall chainer
pip install chainer --no-cache-dir

GPUを使用する場合は、cupyを追加でインストールする。

pip install cupy

MNISTサンプルの実行

git clone https://github.com/pfnet/chainer.git
cd chainer
python examples\mnist\train_mnist.py -g 0

成功すれば、以下のように表示される。

H:\src\chainer>python examples\mnist\train_mnist.py -g 0
GPU: 0
# unit: 1000
# Minibatch-size: 100
# epoch: 20

epoch       main/loss   validation/main/loss  main/accuracy  validation/main/accuracy  elapsed_time
1           0.192455    0.0952584             0.942016       0.9691                    41.9665
2           0.0766379   0.0824858             0.975816       0.9736                    44.3679
3           0.0475103   0.0777052             0.984365       0.9759                    46.7663
4           0.0350414   0.0709947             0.988666       0.9795                    49.1532
5           0.0306068   0.0739683             0.990015       0.9812                    51.5701
6           0.0223621   0.082753              0.992615       0.9787                    53.9638
7           0.0204088   0.07966               0.993482       0.9805                    56.4207
8           0.0193365   0.074065              0.993732       0.9814                    58.8356
9           0.0145758   0.0646451             0.995515       0.985                     61.2115
10          0.015124    0.087687              0.995498       0.981                     63.6042
11          0.0152862   0.0875953             0.995016       0.9826                    65.9779
12          0.0150241   0.0847389             0.995349       0.983                     68.3442
13          0.00898874  0.0903441             0.997049       0.9807                    70.6993
14          0.0138175   0.124715              0.995916       0.9764                    73.0819
15          0.00765957  0.0941705             0.997549       0.9818                    75.4683
16          0.0109906   0.116298              0.996966       0.9781                    77.8691
17          0.0103545   0.0987549             0.996749       0.9824                    80.2834
18          0.0108863   0.127021              0.997149       0.9787                    82.7075
19          0.0088669   0.120687              0.997332       0.9792                    85.0907
20          0.00868301  0.108154              0.997749       0.9821                    87.4538

v1用のコード修正

自分が記述したコードで、対応が必要な個所は以下の通りでした。

trainとtestオプション削除

BatchNormalizationのtestオプションと、dropoutのtrainオプションを削除し、モデル実行時に

with chainer.using_config('train', False):

を使用する。

volatileオプション削除

Variableのvolatileオプションを削除し、モデル実行時に

with chainer.no_backprop_mode():

を使用する。

use_cleargrads削除
optimizer.use_cleargrads()

を削除する。

v1からv2への変更の詳細は、公式のドキュメントを参照。

パフォーマンス測定

v2.0にすることでパフォーマンスが向上するか確認した。

検証している将棋のWide Resnetのモデルの学習時間で比較した。

time(mm:ss)
v1.24 0:21:01
v2.0 0:19:53


学習時間が5.39%向上した。
また、Windowsで問題なく実行できた。

将棋でディープラーニングする その37(利き数を入力特徴に追加)

モデルの精度を上げるために、入力特徴を追加して精度が上がるか検証しました。


AlphaGoでは盤面の情報に加えて呼吸点などの情報を入力特徴に加えることで、精度が向上している。
盤面の情報(4個の特徴)のみでは、test accuracyが47.6%だが、48個の特徴とすることで、55.4%となっている。

一方、私が作成した将棋用のWide Resnetのモデルでは、盤面+王手のみを入力特徴とした場合、1億3千万局面でtest accuracyが43.4%まで学習できたが、それ以上は精度が上がらなくなっている。

そこで、入力特徴を追加して精度が上がるか検証する。

追加する入力特徴は、ShogiNet(GAN将棋)のアピール文章を参考にした。

入力特徴を一つずつ追加して、精度を測定し効果があった場合、その特徴を採用して次の特徴を検証した。

elmo_for_learnで深さ8で生成した20万局面で初期値から学習を行い、テストデータ2万局面で比較を行う。
勝敗データを報酬の重みとして、バリューネットワークも同時に学習を行う。

成りゾーン

成りゾーンを追加した場合、以下のようになった。

train loss test accuracy(policy) test accuracy(value)
成りゾーンなし 1.7554 0.2984 0.7947
成りゾーンあり 1.7620 0.2954 0.7980

効果が見られなかったので、不採用とする。
成りゾーンの位置の情報はすでに表現できていたと思われる。

各マスの利き数

利き数とは、座標ごとにいくつの利きがあるかを表す。
8方向と桂馬を含めて最大10となるが、上限値を設ける。
上限値を1,2,3,4とした場合で比較した。

利き数上限 train loss test accuracy(policy) test accuracy(value)
利き数なし 1.7554 0.2984 0.7947
1 1.7307 0.3024 0.7936
2 1.7022 0.3128 0.8160
3 1.6939 0.3143 0.8158
4 1.6833 0.3147 0.8005

利き数上限2にすると、test accuracy(policy)が1.44%、test accuracy(value)が2.13%上がった。
利き数上限3にすると、test accuracy(policy)はさらに上がり1.59%となり、test accuracy(value)はほぼ同じである。
利き数上限4にすると、test accuracy(policy)はさらに上がっているが、test accuracy(value)は下がっている。

利き数は守備が弱い箇所、強い箇所を測る指標になるので、囲碁における呼吸点のような意味を持つ。
policy、valueともに精度が上昇しており、効果的な特徴のようだ。
利き数上限3を採用することにする。

駒の利き

駒の種類ごとに、どのマスに利いているかを表す。

train loss test accuracy(policy) test accuracy(value)
駒の利きなし 1.6939 0.3143 0.8158
駒の利きあり 1.6628 0.3222 0.7950

policyの精度は上がったが、valueは下がった。
policyはモンテカルロ木探索で補完できるので、valueを重視し不採用とする。

王手情報

aperyのCheckInfoのdcBBとpinnedを使用する。
それぞれ、間の駒を動かした場合に王手になる駒と、動かすと王手にされる駒を表す。

train loss test accuracy(policy) test accuracy(value)
王手情報なし 1.6939 0.3143 0.8158
王手情報あり 1.6869 0.3199 0.8029

policyはほぼ変わらず、valueが下がった。
不採用とする。

歩のある筋

train loss test accuracy(policy) test accuracy(value)
歩のある筋なし 1.6939 0.3143 0.8158
歩のある筋あり 1.6977 0.3143 0.8071

policyはほぼ変わらず、valueが下がった。
不採用とする。


明らかに効果があったのは、利きの数のみであった。
利き数(上限3)を採用することで、policyが1.59%、valueが2.11%向上した。

修正したモデルを使用して、一から学習し直す予定。

追記

初期値と学習データの並びによって、value networkはぶれることがあるようなので、駒の利きと王手情報は採用してもよいかもしれない。
学習データを増やして追試を行う予定。

同じ条件で再度、駒の利きを追加して学習した。

train loss test accuracy(policy) test accuracy(value)
駒の利きなし 1.6939 0.3143 0.8158
駒の利きあり 1.6576 0.3246 0.8095

policyの精度は1.03%上がって、valueはほぼ同じになった。
valueは毎回1~2%ぶれるので、採用することにする。

王手情報も駒の利きを採用した状態で再度学習した。

train loss test accuracy(policy) test accuracy(value)
王手情報なし 1.6576 0.3246 0.8095
王手情報あり 1.6533 0.3256 0.8224

policyはほとんど変わっていない。
valueは増えているが誤差と思われる。
不採用とする。

駒の利きがない場合とある場合で、1000万局面を学習し、テストデータ10万局面で評価した結果、以下の通りとなった。

train loss test accuracy(policy) test accuracy(value)
駒の利きなし 1.4483 0.3655 0.8210
駒の利きあり 1.4370 0.3723 0.8210

駒の利きはpolicyの精度に効果があることが確かめられた。

将棋でディープラーニングする その36(PUCTアルゴリズムの実装)

Ray+Rnのソースを元に、policy networkとvalue networkを使った、モンテカルロ木探索を実装しました。

実装方法

以前の日記で書いたPUCTアルゴリズム*1を実装した。

以前に考察したように、将棋ではプレイアウトで終局までプレイしても精度が低いため、終局までのシミュレーションは行わず、末端ノードでバリューネットワークの値を報酬として使用した。

バリューネットワークの計算結果を待つ必要があるため、スレッドをCPUのコア数以上に実行して、並列に実行を行い、複数スレッドのpolicy networkとvalue networkの計算を同時に行うようにした。
また、policy networkとvalue networkの計算結果は、ハッシュテーブルに登録し、同じ局面で再利用するようにした。

実行結果

将棋所を使い、Lesserkaiと対局をさせた。
f:id:TadaoYamaoka:20170619000941p:plain

以前のpolicyのみのバージョンでは、中盤で評価値が反転する悪手を指すことがあったが、モンテカルロ木探索を行うことで、悪手を指すことがなくなった。
Lesserkai相手には、実行した限り、100%勝つようになった。

16スレッド、2000プレイアウトで、1手1秒程度かかる。
ハッシュにヒットしない局面では、NPSは1000程度しかでていない。

評価値は、選択した手のバリューネットワークによる報酬の平均rを、以下の式で対数スケールに変換して表示している。
\displaystyle
 -log(\frac{1}{r} - 1) \times 754.3
定数754.3は、elmoの教師データの勝率から算出した。(以前の日記参照)

GPSfishとの対局

ShogiGUIに付属するGPSfishとも対局させた。
f:id:TadaoYamaoka:20170619001753p:plain

終盤で崩れることが多く、何回か行ったが1度も勝つことができない。

評価値の傾向は、だいたい同じになっているので、バリューネットワークの精度はそれなりになっているようだ。

考察

GPSfish相手に、勝てない理由として以下のように考えている。

  • ログを見ると同じ手ばかり調べている
  • プレイアウト数が足りない
  • モデルの精度不足

強くするには、それぞれについて対策を行っていく必要がある。

同じ手を調べることが多い点については、終局までのシミュレーションを行っていないため、ランダム要素がなく探索するルートが固定されてしまっている。
各ノードで、候補手のUCBが最大の値を選択しているが、UCBの値を使って確率的に手を選択した方が、調べる局面の幅を広げることができる。

プレイアウト数が少ない点については、さらに高速化が必要になってくるが、コア数以上のスレッドで実行しているので、これ以上スレッドを増やしても逆効果になる。
コア数の多いCPUに交換すれば増やせるが、アルゴリズムでの工夫がないかもう少し検討したい。

モデルの精度不足については、現在のモデルはこれ以上学習しても精度が上がらなくなっているので、効果的な入力特徴を追加したり、層数を増やしたり、試行錯誤する必要がありそうだ。
結構根気がいる作業なので、ぼちぼち試していきたい。


まだ、強さはいまいちだが、従来の探索を使わずに、ディープラーニングのみを使って将棋を指すプログラムのベースができた。
時間制御とか細かいところの実装ができていないので、もう少しブラッシュアップしたい。
作り始めたときは少し検証してみるくらいのつもりだったが、ここまでできたので、できれば改良して大会にも出ようかと考えている。

PUCTアルゴリズムの実装を公開しまた。Ray+Rnのソースを流用しています。
github.com

追記

35億局面学習することで、GPSfishにもそこそこ勝つようになり、floodgateでレーティング2710になりました。
将棋AIの進捗 その3 - TadaoYamaokaの開発日記

将棋でディープラーニングする その35(マルチタスク学習(補足))

試している将棋でのディープラーニングについて、PUCTの実装をRay+Rnソースコードを参考に行っていますが、囲碁部分のコードを将棋に置き換えるのがわりと面倒で、完成にはもうしばらくかかりそうです。

その間に、追加でモデル学習の実験を行いました。
今回は、あまりたいした内容ではないです。

検証内容

先日、policy networkとvalue networkを同時に学習するマルチタスク学習を試したが、policy networkとvalue networkで12層までを共有する構成としていたが、policy networkは最終層まで共有されているので、value networkの学習で出力に悪影響がでていないか気になっていた。

そこで、共有する層を減らして、マルチタスク学習を行った場合の精度について追加で検証を行った。

ニューラルネットワークは11層までは、Wide ResNet構成としているので、11層まで共有した場合と、そこから1ブロック(2層)ずつ減らした場合の条件で測定した。

測定結果

1億局面をSL policy networkで学習したモデルをベースに、そこから3千万局面をRL policy networkとvalue networkのマルチタスク学習で学習した。
3千万局面学習した結果、以下の通りとなった。
f:id:TadaoYamaoka:20170615221633p:plain

1000iterationごとのグラフ
f:id:TadaoYamaoka:20170615223555p:plain

3千万局面を学習後の、accuracyにはそれほど差がないという結果になったが、train lossの減り方が12層まで共有したものが他より遅く、value networkのaccuracyが最も低い。
train lossは11層まで共有したものが最も低く、policyのaccuracyが最も高い。
value networkのaccuracyは9層まで共有したものが最も高いが、11層まで共有したものとの差は、0.0062でほとんど差はない。
7層まで共有したものはpolicy networkのaccuracyが最も低かった。

上記の結果から、12層目は共有しない方がよさそうで、11層目か9層目まで共有するのがよさそうだ。
12層は、1×1のフィルターに座標ごとのバイアスを加えた層で、policyの最終層で座標ごとにバイアスを加えている層になっているので、共有するとpolicyの出力に悪影響がでていると思われる。
11層までは共有することでマルチタスク学習の効果がでていると思われる。


以上の結果から、共有する層を11層までに修正した。
github.com

仮説検定でプログラムが有意に強くなったか検証する

プログラムで自己対局したときに、その対局数と勝敗の数から何%勝ちなら強くなったといえるのか。
そのような問題に統計的に答える方法として、仮説検定という方法がある。

仮説検定

仮説検定は、帰無仮設と対立仮説を設定し、帰無仮説が定めた有意水準の範囲内かにより、棄却されるか採択されるか判定する。

詳しい説明は、統計の教科書に譲るとして、対局結果から強いかの検定には以下の式で計算する。

帰無仮説 H_0P=P_0(=0.5)
対立仮説 H_1P > P_0
と設定すると、
\displaystyle
u_0 = \frac{r-P_0}{\sqrt{P_0(1-P_0)/n}}
u_0が棄却域Rにあれば、帰無仮説H_0は棄却され、対立仮説H_1が採択される。

ここで、rは勝率、nは対局数で、棄却域Rは、有意水準\alpha=0.05とするとR > 1.644854となる。

棄却域の臨界値は、R言語を使って、

qnorm(0.05, lower.tail=FALSE)

で計算できる。

対局数がn=100の場合、勝率rが有意であるためには、
\displaystyle
\frac{r-0.5}{\sqrt{0.5(1-0.5)/100}}>1.644854
から、
\displaystyle
r>0.5822427
であれば有意に強いと言える。

対局数が1000回だと、
\displaystyle
r>0.5260074
となる。

前回の日記で、自己対局の結果、100回対局して勝率が54%で強くなっていると判断したが、統計的には有意とは言えない。
逆に、勝率54%を有意と言うには、
\displaystyle
\frac{0.54-0.5}{\sqrt{0.5(1-0.5)/n}}>1.644854
から
\displaystyle
n > 422.7414
の対局が必要になる。

勝率と必要対局数

勝率と必要対局数の関係は、以下のグラフのようになる。
f:id:TadaoYamaoka:20170615075043p:plain
※横軸は勝率で、縦軸は必要対局数(10の対数)

グラフはR言語の以下のスクリプトでplotした。

need_n <- function(r) {
  qnorm(0.05, lower.tail=FALSE)^2 * 0.5 * (1-0.5) / (r - 0.5)^2
}
need_n_log10 <- function(r) {
  log10(need_n(r))
}
plot(need_n_log10, 0.5, 1)

Pythonでグラフを描くには、以下のように実行する。

import matplotlib.pyplot as plt
import numpy as np
import scipy.stats

x = np.linspace(0.5, 1, 100)
plt.plot(x, scipy.stats.norm.ppf(0.95)**2 * 0.5 * (1 - 0.5) / (x - 0.5) ** 2)
plt.yscale("log")