2020-08-29

Likelihood of superiorityについて

昨日の記事でcshogiに、2つのプログラム間の連続結果からLOS(Likelihood of superiority)の算出を実装したことを書いたが、その計算式は、チェスで使用されている式をそのまま適用した。

LOSについて

測定された勝率がどれくらい確からしいかを表したのがLOSである。
100%で確実に強いと言える。

これは、仮説検定（ $H_0$ :P(勝ち)=P(負け)、 $H_1$ :P(勝ち)>P(負け)）の片側検定のp値と等価である。
つまり、
LOS = 1 - p値
である。

チェスで使用されている近似式

Match Statistics - Chessprogramming wiki
の説明では、チェスで使用されている近似式は、勝ち、引き分け、負けの3項分布における、勝ちの確率が、以下の正規分布で近似できることを前提にしている。
$\displaystyle {\bf N} (N/2, N(1-draw\_ratio)) \\ = {\bf N}(N/2, wins + losses)$

そうすると、勝ちと負けの差は、2つの正規分布の差になるので、それも正規分布になる。
正規分布の差の公式を当てはめると、
$\displaystyle {\bf N}(0, 2(wins + losses))$
となる。

LOSは、これの積分で求められるので、誤差関数を使うと、
$\displaystyle LOS = \frac{1}{2} \left( 1 + erf( \frac{wins - losses}{\sqrt{2wins + 2losses}}) \right)$
で計算できる。

この式については、以下のフォーラムに議論の過程が残っている。
Likelihood of superiority - TalkChess.com
Calculating the LOS (likelihood of superiority) from results - TalkChess.com

将棋に当てはめて良いか

3項分布の近似が
$\displaystyle {\bf N}(N/2, wins + losses)$
となる部分の根拠を探したが、見つけられなかった。

将棋では、引き分けがチェスに比べて少ないため、むしろ2項分布で近似した方がよい気がしている。

2項分布を正規分布で近似する場合は、
$\displaystyle {\bf N}(N/2, N \cdot \frac{1}{2} \cdot \frac{1}{2})$
となる。

N=100、引き分けが0の場合で、2つの正規分布の形を比較すると、
チェスの近似式

plt.plot(x, norm.pdf(x, 50, np.sqrt(100)))

2項分布

plt.plot(x, binom.pmf(x, 100, 0.5))

だいぶグラフの形が異なる。

まとめ

チェスで使用されているLOSについて、式がどのように導出されているかを調べた。
しかし、近似式の根拠をはっきり書いている記述が見つけられなかった。

チェスに比べて引き分けが少ない将棋に、近似式をそのまま当てはめると誤差が大きいような気がしている。
統計にそこまで詳しいわけでないので、統計に強い方のアドバイスがもらいたいと思っている。

2020-08-28

cshogiにElo rating測定機能を追加

cshogi コンピュータ将棋

Cythonを使った高速なPythonの将棋ライブラリcshogiに、Elo rating測定機能を追加した。

誤差とLOS

連続対局を行い、Elo ratingと誤差(95%信頼区間)をレポートする。
何%の確率で強いと言えるかを表すLOS(Likelihood of superiority)も表示する。
LOSが95%を超えない場合は、追加で対局が必要であるという判断ができる。

以下のような形式で、結果がレポートされる。

100 of 100 games finished.
Apery_WCSC28 vs Gikou 2 (v2.0.2): 62-38-0 (62.0%)
Black vs White: 60-40-0 (60.0%)
Apery_WCSC28 playing Black: 36-14-0 (72.0%)
Apery_WCSC28 playing White: 26-24-0 (52.0%)
Gikou 2 (v2.0.2) playing Black: 24-26-0 (48.0%)
Gikou 2 (v2.0.2) playing White: 14-36-0 (28.0%)
Elo difference: 85.0 +/- 71.2, LOS: 99.2 %, DrawRatio: 0.0 %

※cutechessを参考にしている。

複数プログラムでの測定

強さの測定は、同系統のプログラム同士だと勝率の差が付きやすくあまり信用ができない傾向がある。
そのため、系統が違う複数のプログラムを混ぜて測定を行う必要がある。

複数プログラムの対局結果から、Elo ratingを算出するのは単純ではなく、Bayesian Eloのようなベイズ推定で事後確率から事前確率を推測するアルゴリズムが必要になる。

Ordo

Leela Chess Zeroのテストでは、Ordoというツールが使用されている。
Ordoでは以下のような形式で、複数プログラムのレーティング差がレポートできる。

   # PLAYER                 :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W     D    L  D(%)
   1 sf                     :     0.0   ----  2073.5    4000    52      98  800  2547  653    64
   2 lc0_policytempdecay    :    -9.6    9.0   973.0    2000    49      85  338  1270  392    64
   3 lc0                    :   -16.6    9.5   953.5    2000    48     ---  315  1277  408    64

Ordoは、チェスのデファクトスタンダードであるPGNフォーマットを入力とする。
PGNには、プログラム名と結果を含む7個の必須の項目だけ記述されていればよく、将棋の対局結果も問題なく記述できる。

PGN出力機能

そこでcshogiにも、連続対局の結果をPGNで出力する機能を追加した。
出力したPGNをOrdoに入力すると、以下のような結果が表示できる。

PS C:\> ordo-win64.exe -Q -D -a 0 -A "Gikou 2 (v2.0.2)" -W -n8 -s1000 -U "0,1,2,3,4,5,6,7,8,9,10" -p games.pgn
0   10   20   30   40   50   60   70   80   90   100 (%)
|----|----|----|----|----|----|----|----|----|----|
***************************************************

   # PLAYER              :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 Apery_WCSC28        :    89.8   75.7    62.0     100    62      99   62    0   38     0
   2 Gikou 2 (v2.0.2)    :     0.0   ----    38.0     100    38     ---   38    0   62     0

White advantage = 75.74 +/- 39.21
Draw rate (equal opponents) = 0.00 % +/- 0.00

オプション「-W」を付けると、先手有利を補正した上のレーティングになる。
推定された先手のレーティングは、「White advantage」に表示される。
※チェスのツールのためWhiteが先手なので注意

上記は2プログラムの例だが、複数プログラムの対局の組み合わせで連続対局を行い、結果のPGNを連結して、Ordoに入力すれば、複数プログラムのレーティングが計算できる。

使い方

インストール方法

ソースからインストールする場合

pip install git+https://github.com/TadaoYamaoka/cshogi

ビルド済みwheelパッケージからインストールする場合

OS、Pythonのバージョン別にファイルが分かれているため、Releaseから対応するファイルのURLを指定する。
Windows、Python3.7の場合：

pip install https://github.com/TadaoYamaoka/cshogi/releases/download/v0.0.5/cshogi-0.0.5-cp37-cp37m-win_amd64.whl

コマンド例

> python -m cshogi.cli C:\apery_wcsc28\bin\apery_wcsc28_bmi2.exe C:\gikou2_win\gikou.exe --options1 Byoyomi_Margin:0 --options2 ByoyomiMargin:0 --byoyomi 100  --games 100 --opening records2016_10818.sfen --pgn games.pgn

2020-08-23

将棋AIの実験ノート：Mask-AttentionでAIの着目点を可視化する

dlshogi コンピュータ将棋

深層強化学習でAIが着目している箇所を可視化するという以下の論文の手法（Mask-Attention）を、将棋AIでも試してみたい。
http://mprg.jp/data/MPRG/F_group/F20200610_itaya.pdf

Mask-Attention

方策ヘッドに、位置情報をAttentionとして乗算する。
f:id:TadaoYamaoka:20200823000006p:plain

Attentionは、人間によるヒントは不要で、自動で学習される。
推論時に、Attentionの重みを取り出すことで、AIが着目している箇所を可視化できる。

可視化だけではなく、精度も向上すると報告されている。
f:id:TadaoYamaoka:20200823000626p:plain

将棋への応用

dlshogiのニューラルネットワークも、論文と同様に価値ヘッドと方策ヘッドで構成されており、Mask-Attentionの機構を導入するは簡単である。

なお、Leela Chess Zeroでは、SENetが導入されており、チェスではAttentionによる精度向上が確かめれている。
SENetは、チャンネルに対して乗算を行うため、どのチャンネルに注目しているかをAttentionで補助している。
（dlshogiでもSENetを試したが、結果が得られるほど実験できていない。）
Mask-Attentionは、方策ヘッドのみで、位置に対してAttentionを導入しているという違いがあるが、将棋でも精度も向上が期待できそうである。

今後の予定

ということで、簡単に実装できそうなので、（やる気がでれば）まずは教師ありで学習してみて、可視化と精度の比較をしてみたい。
実現できれば、ディープラーニングの将棋AIならではの使い方ができて面白いのではないかと思う。

2020-08-18

dlshogiにおける思考時間と強さの関係更新

dlshogi コンピュータ将棋

先日記事にしたdlshogiにおける思考時間と強さの関係について、思考時間8秒、16秒の結果と、水匠2のスレッド数を8にした場合の結果が測定できたので記事にする。

測定条件は前回と同じである。

dlshogi vs 水匠2(1000万ノード固定)の測定結果

思考時間(秒)	勝ち	引き分け	勝率	R
1	87	9	36.6%	-95.44
2	132	7	54.2%	29.25
3	158	3	63.8%	98.44
4	165	2	66.4%	118.33
8	175	6	71.2%	157.24
16	197	6	80.0%	240.82

f:id:TadaoYamaoka:20200818223151p:plain

水匠2(8スレッド) vs 水匠2(1000万ノード固定)の測定結果

思考時間(秒)	勝ち	引き分け	勝率	R
1	54	19	0.254	-187.16
2	88	33	0.418	-57.50
3	119	33	0.542	29.25
4	184	24	0.784	223.94
8	203	15	0.842	290.66
16	218	20	0.912	406.20

f:id:TadaoYamaoka:20200818223503p:plain

思考時間に対するレーティングの伸び比較

f:id:TadaoYamaoka:20200818223921p:plain

dlshogiの方が思考時間が短い場合に強く、水匠2の方が思考時間を延ばした場合のレーティングの伸びが良い。
AlphaZeroの論文の通りであれば、dlshogiの方が思考時間に対してレーティングの伸びが良いはずだが、異なる傾向になった。

ただし、水匠2は同一ソフトなので勝ちやすいということもあるかもしれないので、別の機会にdlshogiのノード固定に対する測定も追試したい。

2020-08-16

将棋AIの実験ノート：活性化関数Swishを試す続き

dlshogi コンピュータ将棋

先日試したSwishについて、推論速度がどれくら低下するのかと、精度が上がった代わりに速度が低下した場合に強さにどう影響するのかが気になったので調べてみた。

精度

先日は、8サイクル分学習した時点の結果を記したが、今回は16サイクル分学習したモデルを使用した。
16サイクル分学習した時点の精度は以下の通り。

条件	訓練損失平均	テスト損失	policy一致率	value一致率
Swishなし	0.84661563	1.61019968	0.44103022	0.69944063
Swishあり	0.86657027	1.58214659	0.44275271	0.71354634

Swishの方がvalueの学習が安定する傾向がありそうだ。

推論速度

floodgateの棋譜からサンプリングした100局面に対して、5秒思考した際のNPSを計測した。
測定プログラム：
https://github.com/TadaoYamaoka/DeepLearningShogi/blob/master/utils/benchmark.py

V100 1枚で、Onnx出力してTensorRTを使用。

	Swishなし	Swishあり
平均	34926.01	30477.17
中央値	37064	32797
最小値	17572	17036
最大値	41434	34941

NPSは、平均で87.3%に低下している。

強さの測定

互角局面集を使用して、先後を交互に入れ替え、250戦行った結果で測る。
引き分けも考慮するため、勝率は、勝ちを1ポイント、引き分けを0.5ポイントとして、ポイントの合計/250で計算する。
1GPU、秒読み1秒で、250対局行った結果は以下の通り。

Swishあり vs Swishなし

勝ち	引き分け	勝率	Eloレーティング
157	14	65.6%	112.14

R+112.14という結果になった。NPSは低下しているが、精度の向上の効果がそれを上回っているようだ。

ReLUを途中からSwishに変更できるか

Swishにすることで、同一データの学習で強くなることが確認できたが、現在学習済みのモデルのReLUをSwishに変更できるか検証してみた。

条件	訓練損失平均	テスト損失	policy一致率	value一致率
Swishなし	0.69250407	1.6051037	0.46532138	0.72403891
Swishあり	0.92641119	1.51048969	0.44681778	0.71891699

条件	訓練損失平均	テスト損失	policy一致率	value一致率
Swishなし	0.69250407	1.6051037	0.46532138	0.72403891
Swishあり	0.76547083	1.52928974	0.46177364	0.72609071

まとめ

活性化関数をReLUからSwishに変更するとNPSが低下するが、精度向上の効果の方が大きいことがわかった。
既存のモデルの活性化関数をReLUからSwishに変更すると精度が大幅に低下するが、十分にファインチューニングを行えばSwishに変更できる。

過去10サイクル分くらいで学習を行って、policy、valueの両方で精度が上回って、また強さも上回ることができれば、dlshogiの活性化関数をSwishに変更したいと思う。

2020-08-14

将棋AIの実験ノート：活性化関数Swishを試す

dlshogi コンピュータ将棋

画像認識で高い精度を達成しているEfficientNetで使われている活性化関数Swishが将棋AIでも効果があるか試してみた。

EfficientNetでは、残差ブロックにMBConvというアーキテクチャが使用されており、その中の活性化関数にSwishが使用されている。
MBConvについても別途検証を行ったが、今回はSwishの効果について記す。

Swishについて

Swishは以下の式で定義される活性化関数である。
$\displaystyle x \cdot \sigma(\beta x)$
ここで、 $\sigma(z)$ はシグモイド関数 $\sigma(z)=(1+exp(-z))^{-1}$ である。

グラフの形は以下のようになる。
f:id:TadaoYamaoka:20200814131227p:plain

どのような場合でもReLUに代わるものではないが、多くのタスクでReLUよりも精度が向上することが報告されている。

PyTorchのSwish実装

GitHubで公開されているPyTorchのEfficientNetの実装からSwishのコードを流用した。

この実装では、微分の計算が効率化されている。

ただし、Onnxに出力する際はエラーになるようなので、オリジナル実装に切り替える必要がある。

dlshogiのネットワークへの適用

dlshogiのpolicy_value_network.pyのreluをswishに置き換えたソースがこちら。
DeepLearningShogi/policy_value_network_swish.py at feature/experimental_network · TadaoYamaoka/DeepLearningShogi · GitHub

比較実験

測定条件

dlshogiの強化学習で生成した教師局面を使用して、教師あり学習を行い、floodgateからサンプリングした856,923局面に対する損失と一致率で評価する。
強化学習で生成した局面は、1サイクルあたり約270万局面生成しており、それを過去10サイクル分を1回のデータセットとして学習する。
8サイクル分のデータを学習した時点で比較した。

学習率：0.001(最初の1サイクルのみ0.01)
バッチサイズ：1024
最適化：Momentum SGD(係数0.9)
学習則：dlshogiと同じ。

学習には、ampを使用した。

測定結果

条件	訓練損失平均	テスト損失	policy一致率	value一致率
Swishなし	0.85036430	1.62555117	0.43175799	0.70151462
Swishあり	0.86290113	1.60377155	0.43336603	0.71022165

f:id:TadaoYamaoka:20200814143424p:plain
f:id:TadaoYamaoka:20200814143705p:plain

テストデータに対する、損失、policyの一致率、valueの一致率すべてでSwishを使用した方が良い結果になった。

まとめ

dlshogiのResnetを使用したモデルの学習にSwishを使用すると精度が改善されることが確認できた。

今回は初期値からの学習を行ったが、現在学習済みのモデルに対して、活性化関数を変更した場合にどうなるかについても確認したい。
途中から変更しても効果があるなら、現在継続している学習に変更を取り入れる予定である。

Swishは深いモデルでうまく機能する傾向があるそうだが、もしかしたらNNUEの学習でも効果があるのかもしれないので（私は試さないので）興味のある方は試してみてほしい。

続き
将棋AIの実験ノート：活性化関数Swishを試す続き - TadaoYamaokaの開発日記

2020-08-12

dlshogiのautomatic mixed precision対応

dlshogi

48先生から頂いたautomatic mixed precision対応のプルリクに対応しました。
Pytorch 1.6 の Automatic Mixed Precision対応 by bleu48 · Pull Request #18 · TadaoYamaoka/DeepLearningShogi · GitHub

automatic mixed precisionは、PyTorch 1.6で追加されたTensorCoreを使用して学習を高速化する機能です。
詳細は↓こちらを参照。
Introducing native PyTorch automatic mixed precision for faster training on NVIDIA GPUs | PyTorch

学習時間

dlshogiの学習で測定した結果は以下の通り。

条件：

27,051,941局面の学習
バッチサイズ 1024
SWA使用

条件	学習時間	SWAのbn_update	合計
ampなし	2:33:57	0:43:58	3:17:55
ampあり	1:15:53	0:31:52	1:47:45

学習時間とSWAのbn_updateの合計で、54%に短縮されている。

精度

テストデータにはfloodgateの棋譜からサンプリングした856,923局面を使用

条件	訓練損失平均	テスト損失	policy一致率	value一致率
ampなし	1.1555423	1.6557858	0.40078359	0.69063551
ampあり	1.15769344	1.65721888	0.40040172	0.68830110

精度が大幅に落ちるということは起きていない。
わずかに下がっているが、初期値の違いでも起きる差なのでampの影響は小さいと思われる。

補足

ampは、FP16への変換を自動で行い、精度が落ちないように計算中の値を自動でスケーリングする。
勾配がInfやNanになる場合は、そのstepはスキップされ、更新が連続で成功した場合に、自動でスケーリングパラメータを調整している。

dlshogiの初期モデルの学習は、初期値によってはモデルの出力がnanになることが良く起きていたが、上記の仕組みによりそれが発生しなくなった。
今の自己対局の仕組みでは起きていないが、以前は学習が進むと突然nanになるようなこともあったので、それも自動で防げるという効果もありそうだ。

まとめ

automatic mixed precisionを使用することで、精度を落とさずに学習を(上記の測定条件の場合)約1.8倍に高速化できる。

48先生、ありがとうございました。

LOSについて

チェスで使用されている近似式

将棋に当てはめて良いか

まとめ

誤差とLOS

複数プログラムでの測定

Ordo

PGN出力機能

使い方

インストール方法

ソースからインストールする場合

ビルド済みwheelパッケージからインストールする場合

コマンド例

Mask-Attention

将棋への応用

今後の予定

dlshogi vs 水匠2(1000万ノード固定)の測定結果

水匠2(8スレッド) vs 水匠2(1000万ノード固定)の測定結果

思考時間に対するレーティングの伸び比較

精度

推論速度

強さの測定

Swishあり vs Swishなし

ReLUを途中からSwishに変更できるか

最新の1サイクル分だけ、ReLUをSwishに変更して学習した場合

まとめ

Swishについて

PyTorchのSwish実装

dlshogiのネットワークへの適用

比較実験

測定条件

測定結果

まとめ

学習時間

精度

補足

まとめ