TadaoYamaokaの開発日記

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

将棋AI実験ノート:自己対局の評価値の補正

Discordで、評価値と勝率を変換する際の以下のシグモイド関数の係数aは、dlshogiはelmo_for_learnの自己対局から求めた756.0864962951762という値を使用しているが、floodgateの棋譜などを学習する場合はもっと低い値になるので補正すべきというやり取りがあった。

\displaystyle
\frac{1}{1 + \exp(-score / a)}

floodgateの棋譜から調査

R3800以上の棋譜

実際にどれくらいの値なのか2019年~2020年のR3800以上のfloodgateの棋譜から調べてみたところ、
a = 236.94908509
という結果であった。

R2000以上の棋譜

R2000以上とすると、
a = 398.66185164
という結果であった。

調査に使用したスクリプトcsa_score_value_fit.py · GitHub

Discordでのやり取りの通り、係数aは小さい値になった。
また、レーティングが高いほど、係数aが小さくなる傾向がありそうである。

自己対局の評価値と勝率の関係

dlshogiの自己対局で生成した教師データに対しても、評価値と勝率の係数を調べてみた。
自己対局では評価値はルートノードの訪問回数が最も多い子ノードの平均価値(勝率)を、評価値に変換して記録している。
その際の係数には、a=756.0864962951762を使用しているため、その値に近い値になると考えていた。

しかし、実際に調べてみると、
a = 488.09106542
という結果であった。

調査に使用したスクリプトhcpe_score_value_fit.py · GitHub

これは、自己対局時の探索で求めた勝率と、実際の対局結果を統計処理した勝率にずれがあることを示している。
係数が小さい方にずれているということは、実際の勝率が探索で求めた勝率よりも高いことを示している。
なぜ係数が小さい方にずれるのかは分からないが、探索で求めた評価値をそのまま学習に使うよりも、実際の勝敗から求めた係数で補正した方がよい可能性がある。

評価値を補正して学習

評価値を勝敗から求めた係数で補正したデータを使用し、dlshogiのモデルを学習して、補正なしの場合とありの場合で、精度を比較した。
テストデータには、2017年~2018年6月のfloodgateのR3500以上の棋譜からサンプリングした856,923局面(重複なし)を使用した。
初期値とデータのシャッフルにより結果が変わるため4回測定して平均を求めている。

精度は、方策、価値(勝率)、Q値(評価値)のテスト損失で比較する。
(正解率は、テストデータのクラスの分布が不均衡だと比較しにくいため、精度の比較には損失の方がよい)

変換に使用したスクリプトfix_hcpe_eval.py · GitHub

floodgateの棋譜

2019年~2020年のR3800以上のfloodgateの棋譜(6235207局面)の評価値を補正して、初期値から学習した結果は以下の通り。

方策 価値(勝率) Q値(評価値)
補正なし 1.70100901 0.656220725 0.688526105
補正あり 1.713669813 0.65317638 0.691249333

補正ありの場合が、価値の損失が小さくなっている。
(その変わり、方策の損失が大きくなっているが、これは、初期値から学習した段階では、方策と価値がトレードオフの関係で学習されるためと考えられる。)

補正を行うことで、価値の精度が上がることを示している。

Q値(評価値)が、補正を行った方が高くなっているのは、テストデータの評価値は補正を行っていないためと考えられる。
テストデータに評価値を補正したデータを使用すると、

方策 価値(勝率) Q値(評価値)
補正なし 1.648518813 0.65597565 0.659327383
補正あり 1.659034425 0.65457407 0.65837852

補正ありの方が、Q値(評価値)の損失も小さくなった。

自己対局の棋譜

自己対局で生成した教師データ(4千万局面)の評価値を補正して、学習済みモデルに追加学習を行った結果は以下の通り。

方策 価値(勝率) Q値(評価値)
補正なし 0.816202783 0.49896154 0.644653933
補正あり 0.812867498 0.493460893 0.658458863

補正ありの場合が、価値の損失が小さくなっている。
また、方策の損失も小さくなっている。
Q値(評価値)の損失は大きくなっているが、テストデータの評価値の補正を行っていないためである。

テストデータに評価値を補正したデータを使用すると以下の通りになった。

方策 価値(勝率) Q値(評価値)
補正なし 0.80054098 0.498679225 0.512195093
補正あり 0.79759852 0.493009955 0.508437538

Q値(評価値)の損失についても小さくなっている。

まとめ

floodgateの評価値と勝率の変換に使用するシグモイド関数の係数は、コンピュータ将棋界隈で知られている600よりも小さい値であることがわかった。
また、自己対局時の探索で求めたPVの平均価値(勝率)と、実際の対局結果の統計から求めた勝率にはずれがあることが確認できた。

どちらのデータも学習に使用する場合、評価値を実際の対局結果から求めた係数で補正することで、価値の精度が向上することが確かめられた。

dlshogiの学習スクリプトにも評価値を自動で補正するオプションを処理を追加する予定である。

dlshogi with GCT(WCSC31バージョン)のWindows版ビルド済みファイル公開

dlshogi with GCT(WCSC31バージョン)のWindows版ビルド済みファイルを公開します。

ダウンロード

Release 第31回世界コンピュータ将棋選手権バージョン · TadaoYamaoka/DeepLearningShogi · GitHub

NVIDIA GPUに対応したTensorRT版と、NVIDIA GPU非搭載のWindows PCでも動作するOnnxRuntime版を含みます。

OnnxRuntime版について

Windows 10 version 1903以降のPCであれば実行可能です。
ただし、探索速度は、TensorRT版にくらべて落ちます。
最高のパフォーマンスを出すには、TensorRT版をTensorCore搭載のNVIDIAGPU(NVIDIA GeForce 2080Tiなど)で動かすことを推奨します。

同梱しているモデルファイル
model-0000225kai.onnx 比較的オールラウンダー(デフォルト)
model-0000226kai.onnx たややん互換局面特化

※大会では予行2日目最終戦以外は、model-0000226kai.onnxを使用

検討での使用

ShogiGUIの検討機能で使うには、一部対応できていない機能があります。
「深さ」の指定はできません。
時間無制限でも、UCT_NodeLimitで設定したノード数に達すると探索を終了します。

検討では、設定でDNN_Batch_Sizeを256など大きめにした方がNPSが上がります。

第31回世界コンピュータ将棋選手権 結果報告

「dlshogi with GCT」として、第31回世界コンピュータ将棋選手権に参加しました。
本日は予選2日目で、dlshogiはシードのため2日目からの参加でした。
上位8チームが決勝進出になります。

結果は、30チーム中14位と決勝進出ならず残念な結果でした。

昨年の電竜戦で、dlshogiを使用したGCTが優勝したため、ディープラーニング勢の躍進が期待されていましたが、
決勝進出は、NNUE系が7チームという結果になりました。

唯一PALがディープラーニングで、決勝に進出しています。
(決勝に進出したRyfamateはdlshogiとやねうら王(NNUE)の合議のようです。)

dlshogiが振るわなかった理由について

電竜戦やfloodgateに比べると持ち時間が長いことが関係している

dlshogi(GCT)は、floodgate(10分10秒加算)では大会で使用したGPUより世代が古いV100×8(gct_model-0000225kai_v100x8)で、レーティング4430と水匠4(Suisho4_TR3990X)とほぼ互角になっています。
ローカルの持ち時間3分1秒加算の対局(たややん互換局面使用)でも、3GPUのdlshogiが40スレッドの水匠3改に対して、60%くらいの勝率になっていました。
GCTが優勝した電竜戦は、10分2秒加算でした。

今回の世界コンピュータ将棋選手権は、15分5秒加算のルールで、長い持ち時間になっています。

dlshogiは、Resnet10ブロック192フィルタという軽めのモデル(AlphaZeroは20ブロック256フィルタ)を使用して、指し手のみを学習しているため、長い持ち時間を活かしきれない条件だったと推測しています。

探索ノード数の上限をfloatの桁落ちの制約で3千万局面に設定しているため、上限に達することが多くありました。

また、指し手のみを学習している(AlphaZeroは方策の分布を学習する)ため、探索中の各局面で調べる手がかなり絞られており、探索の深さが60以上(多いときは90以上)になっていました。
持ち時間が長い分を、深さより幅方向に時間を使えた方が読み漏れが防げた可能性があります。

そのため、より大きなモデルの方が有効だったか、温度パラメータを調整する余地があったかもしれません。

戦型に弱点がある

振り飛車が得意なHoneyWaffleに負けたことから、相手が上手い振り飛車だと弱点がありそうです。
強化学習の初期局面には、中盤中心の5億と、たややん互換局面集を多く学習して、たややん互換局面集で勝率測定をしていたため、たややん互換以外の戦型に弱点があったかもしれません。

入玉宣言を最短で目指さい

最後のNovice戦では、ほぼ勝ちで入玉宣言を目指せる局面から、無駄な駒得で手数が伸びて引き分けになってしまいました。
入玉宣言できる局面で、狙いに行くにはどうするかは課題があります。

まとめ

最後の2週間は、かなり強化学習をがんばったのですが、結果が及ばす残念でした。
ディープラーニングはまだ伸びしろがあると考えているので、次の大会では結果が残せるように開発は続けたいと思っています。

決勝に行けなかったので需要があるかはわかりませんが、dlshogiのビルド済みバイナリとGCTのモデルは後日公開する予定です。
強化学習で生成したデータも公開を検討していますが、Googleドライブの無料枠に収まらない(圧縮しても50GBくらい必要)のでディスクをどうしようかと思っています。

将棋AIの実験ノート:重複局面の平均を学習

dlshogiの自己対局で生成したデータを学習すると、方策損失がNaNになるというissueをもらった。
自己対局棋譜を用いるとPolicyのlossがNaNになる · Issue #44 · TadaoYamaoka/DeepLearningShogi · GitHub

原因

実際にデータをもらって、調査したところ、強化学習で生成したデータに重複局面が多いとうまく学習できない(方策損失がNaNになる)ということがわかった。

私が行っているdlshogiの強化学習では、約5億局面の初期局面集を使用しているため、重複がほぼないため問題が起きていなかった。
しかし、floodgateの棋譜から作成した26手まで初期局面集を使用して生成したデータの場合、デフォルト設定(--random 4)では33%が重複局面になっていた。
重複を削除して、データをユニークにするとうまく学習できるようになった。

局面の偏りについての考察

機械学習の一般論として、データの偏りが大きすぎる場合は、汎化性能を上げるためにアンダーサンプリングなどの手法がとられる。
同様に、局面の偏りが大きすぎると学習に悪影響があると考えられる。

ただし、将棋の学習では、序盤の頻度が高い局面は、それに応じてサンプル数が多い方が良い可能性はある。
しかし、自己対局で生成した局面は、対局時の出現頻度と生成された局面の頻度が一致する理想的な状態にはならない。

AlphaZero方式の強化学習では、30手までは、ルートの子ノードの訪問数に応じたボルツマン分布で手を選択し、30手目以降はグリーディーに選択する。
30手までの出現頻度が実際の対局時の頻度に近くなる保証はなく、また、30手目までが同一の場合、それ以降の手順も重複する可能性が高い(30手目以降もディリクレ分布によるノイズが加えられるが、同じになる確率の方が高い)。

dlshogiの場合は、初期局面集を使用してデフォルト4手だけルートの子ノードの訪問数に応じたボルツマン分布で手を選択しているため、初期局面集が少ないとAlphaZero方式よりも重複しやすい。

偏りをなくす方法

自己対局の初期局面集を増やす

dlshogiの強化学習のように、5億局面くらい初期局面集を用意すれば、ほぼ重複が起きない。

ランダムを増やす

オプションを変更して、ボルツマン分布で手を選択する手数を増やすことで、偏りを減らすことができる(例:--random 8)。
しかし、それ以降グリーディーで選択する手で重複が起きる問題は解消されない。

ユニークにする

単純に偏りをなくすには、ユニークにすればよい。
hcpeフォーマットの場合、

hcpes = np.fromfile(file1, dtype=HuffmanCodedPosAndEval)
np.unique(hcpes, axis=0).tofile(file2)

のようにすれば、ユニークにできる。

しかし、単純にユニークにすると、局面が同一で、勝敗が異なる場合の勝敗の分布を無視してしまう。

アンダーサンプリングする

局面の出現頻度に応じてサンプリングされる確率を下げることで、偏りをなくすことができる。
しかし、アンダーサンプリングすると全データが使用されなくなる。

重複局面を平均化する

重複局面の方策の分布と勝敗および評価値を平均化して、1サンプルとして学習する。
実装が容易で、偏りをなくして、勝敗の分布が学習に反映されるようになる。

重複局面を平均化する方法の実験

ここでは、実装が容易な重複局面を平均化する方法を試してみた。

floodgateの26手目までから作成した初期局面集を使用して、--random 8で、500万局面を生成した。
8.4%が重複局面であった。

初期値から学習した場合と、学習済みモデルに追加学習した場合の2パターンで、テスト精度を比較した。
テストデータには2017年~2018年6月のfloodgateのR3500以上の棋譜からサンプリングした856,923局面(重複なし)を使用した。
初期値やデータのシャッフルによって、結果がぶれるため10回測定の平均で比較した。

初期値から学習した場合
  • テスト損失
平均化 方策損失 価値損失 Q値損失
なし 1.042137719 0.621680436 0.680630963
あり 1.048347286 0.616545519 0.680523165
  • テスト一致率
平均化 方策一致率 価値一致率
なし 0.364850523 0.639321282
あり 0.362664658 0.644984585
平均化 方策エントロピー 価値エントロピー
なし 2.281808841 0.606063402
あり 2.294291323 0.605066263
学習済みモデルに追加学習した場合
  • テスト損失
平均化 方策損失 価値損失 Q値損失
なし 0.761351238 0.511269072 0.645805857
あり 0.760675438 0.510021321 0.646256217
  • テスト一致率
平均化 方策一致率 価値一致率
なし 0.478925051 0.730855406
あり 0.479427199 0.732262122
平均化 方策エントロピー 価値エントロピー
なし 1.593853935 0.555852106
あり 1.603584761 0.556084998

考察

初期値から学習した場合は、方策は平均化なしが良く、価値は平均化ありが良いという結果になった。
方策が下がったのは平均化によりサンプル数が減ったことが起因している可能性がある。
学習済みモデルに追加学習した場合は、方策、価値どちらも、平均化した方が良い結果になった。

まとめ

自己対局で生成した局面に重複局面が多いとうまく学習できない事象の対策として、重複局面を平均化する方法を試した。
実験の結果、学習済みモデルに追加学習する場合は、重複局面を平均化した方が、良さそうという結果が得られた。

序盤の出現頻度が高い局面のサンプル数を増やした方がよいという考えもあるが、自己対局で生成した局面が理想的な出現頻度になっているかは考慮が必要だと考える。

ソース

feature/hcpe3_averageブランチに平均化する処理を実装したソースをプッシュした。
GitHub - TadaoYamaoka/DeepLearningShogi at feature/hcpe3_average
※平均化に対応したのは、方策の分布を学習する場合(train_hcpe3.py)のみである。

cshogiにリーグ戦モードを追加

プログラムの修正やモデルを学習した後の強さの計測に変更前後の自己対戦のみだと、系統が違うソフトに対して強くなっていないことがあるため、基準となるソフトを加えたリーグ戦で確認を行っている。

連続対局には、cshogiを使用して、PGNファイルを出力して、Ordoでeloレーティングを計算している。
今までcshogiは2つのソフトの連続対局しか対応していなかったため、マシンやプロセスを分けて実行していた。
スペックが同じでもマシンや使用するGPUが変わると、誤差の原因になるため、3つのソフトを指定してリーグ戦で対局できるようにした。
リーグ戦を並列で実行すれば、同じハードを均等に使うので、誤差が出にくい。
また、各ソフトの対局数が同じになるので、途中経過を確認しやすい。


cshogiの使い方についてあまりドキュメントを書いていないので、使い方を書いておく。

cshogiのインストール

pip install cshogi

アップデートの場合は、

pip install cshogi -U

連続対局の実行方法

コマンド例
python -u -m cshogi.cli /work/DeepLearningShogi/usi/bin/usi /work/DeepLearningShogi/usi/bin/usi /work/YaneuraOu/bin/YaneuraOu-by-gcc --name1 model1 --name2 model2 --options1 Draw_Ply:320,OwnBook:false,PV_Interval:0,DNN_Model:/work/model/model1.onnx,UCT_Threads:2 --options2 Draw_Ply:320,OwnBook:false,PV_Interval:0,DNN_Model:/work/model/model2.onnx,UCT_Threads:2 --options3 USI_Hash:2048,Threads:2,PvInterval:9999,NetworkDelay:0,NetworkDelay2:0,ResignValue:10000,MaxMovesToDraw:320 --opening /work/taya36.sfen --draw 320 --time 180000 --inc 1000 1000 1500 --games 128 --pgn model1_vs_model2_time180inc1-01.pgn > log_model1_vs_model2_time180inc1-01.txt &

エンジンは、位置引数に2つもしくは3つ指定できる。
2つの場合は1対1で先後入れ替えて連続対局を行い、3つの場合はリーグ戦になる。
リーグ戦は、先後入れ替えて1局ずつを3ソフト全組み合わせに対し行うことを繰り返す。

同一ソフトで、パラメータのみ変える場合は名前が被るため「--name1 」などで名前を上書きする。「1」の部分が引数の1番目のエンジンであることを示している。
USIオプションは、「--options1」などで指定する。

「--opening」で開始局面集を指定する。
デフォルトでランダムでサンプリングするが、「--opening-seed 0」のようにシードを固定できる。
「--opening-moves」で開始局面集の何手目から開始するか指定できる。

「--draw」で引き分けとする手数を指定できる。

「--time」と「--inc」で、持ち時間と1手加算時間をミリ秒単位で指定する。
エンジンごとに値を分ける場合は、エンジンの数だけ複数指定する。

秒読みの場合は「--byoyomi」で秒読み時間をミリ秒単位で指定する。
こちらも複数指定することでエンジンごとに値を分けることができる。

「--resign」で投了の閾値を設定できる。例)--resign 3000
「--mate_win」を指定すると、手番側の詰みを見つけた時点で終了する(手番側の詰みの探索を信用する)。

「--games」で対局数を指定する。

「--pgn」でPNGの出力パスを指定する。

「--csa」を指定すると、指定したフォルダにCSAファイルを出力する。
「--multi_csa」を指定すると複数対局を1ファイルに出力する。

「--keep_process」を指定すると、1局ごとにエンジンのプロセスを終了しない(リーグ戦の場合は、先後入れ替えのタイミングのみ)。

「--debug」を指定すると、USIコマンドとその応答をすべて標準出力に出力する。

対局の結果は、標準出力に出力される。
ファイルに出力したい場合は、リダイレクトする。
リダイレクトすると、バッファリングされるため、pythonのオプションに「-u」を付けると良い。

eloレーティングの計算

PGNファイルをOrdoに渡すことでeloレーティングが計算できる。

Ordoの実行例
ordo-win64.exe -Q -D -a 0 -W -n8 -s1000 -U "0,1,2,3,4,5,6,7,8,9,10" -p model1_vs_model2_time180inc1-01.pgn

複数プロセスで並列実行した場合は、複数PGNファイルを入力できる。

ordo-win64.exe -Q -D -a 0 -W -n8 -s1000 -U "0,1,2,3,4,5,6,7,8,9,10" -p model1_vs_model2_time180inc1-01.pgn -- model1_vs_model2_time180inc1-02.pgn model1_vs_model2_time180inc1-03.pgn

以下のように表示される。

0   10   20   30   40   50   60   70   80   90   100 (%)
|----|----|----|----|----|----|----|----|----|----|
***************************************************

   # PLAYER                        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 model_gct_010_opt             :    31.3   31.7   116.0     205    57      77  110   12   83     6
   2 model-0000195                 :    10.5   32.0   107.0     205    52      97  100   14   91     7
   3 YaneuraOu NNUE 6.00 64AVX2    :   -41.8   31.3    84.0     204    41     ---   80    8  116     4

White advantage = 11.75 +/- 19.12
Draw rate (equal opponents) = 5.61 % +/- 1.32

レーティングの誤差と、どれくらいの確かさで強いかを表すCFS(%)も表示されるため、有意差があるか確認できる。

将棋AIの実験ノート:方策の分布を学習すると探索パラメータの調整が必要になる

以前に方策の分布を学習することで、Actor-Criticで学習するよりも精度が上がることを確かめた。
dlshogiの強化学習でも、方策の分布を学習するように移行した。

しかし、テストデータに対する精度は上がるが、実際に対局すると弱くなっているという問題が発生した。

精度の比較

すでに精度が飽和しているモデルに対して、1億局面を生成し方策の分布を学習すると以下のように精度が大幅に向上した。

テストデータに、floodgateのレート3500以上の対局の棋譜からサンプリングした856,923局面を使用して評価した結果は以下の通り。
※このテストデータは、GCTのノートブックで公開しているテストデータとは別である。

テスト損失
方策の損失 価値の損失 Q値の損失 損失合計
学習前 0.83306111 0.51837930 0.63040887 1.38874626
学習後 0.76382181 0.50587031 0.63739542 1.31348998
テスト正解率
方策の正解率 価値の正解率
学習前 0.47950766 0.73489700
学習後 0.48287093 0.73816614
テストエントロピー
方策のエントロピー 価値のエントロピー
学習前 1.11967892 0.58347101
学習後 1.40010058 0.56201832

方策、価値の正解率も向上している。特に方策は大幅に向上した。
方策のエントロピーが上がっており、予測の確率分布が広がっていることが分かる。

強さの比較

持ち時間3分1手1秒加算

   # PLAYER           :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 model-0000195    :    13.8   15.8   233.0     432    54      96  215   36  181     8
   2 model_gct_010    :   -13.8   15.8   199.0     432    46     ---  181   36  215     8

※model_gct_010が方策の分布を学習したモデル

精度が上がったのに反して、弱くなっている。

考察

方策のエントロピーが上がっていることから、探索の幅が広がっていると考えられる。

初期局面を100万ノード探索した際の、PVの深さは

学習前 42
学習後 32

となっていた。

分布の広がりは、以下のようになっていた。

方策の確率分布

f:id:TadaoYamaoka:20210405213614p:plain

ルートの子ノードの訪問回数

f:id:TadaoYamaoka:20210405213617p:plain

初期局面だと少しわかりにくかったが、学習前は特定の手に集中しているのに対して、方策が全体に少し広がっているのが確認できる。

弱くなる原因

Actor-Criticは、方策が決定論的に偏りやすい傾向があるため、現在の探索パラメータの温度パラメータは1.74と高めに設定されている。
optunaで最適化を行った結果、それが最適になっている。

方策の分布を学習すると、方策の確率分布が広がるため温度パラメータは比較的低めに設定されるべきである。

なお、Leela Chess Zeroの温度パラメータは、1.4に設定されている。
https://training.lczero.org/training_runs

探索パラメータの再調整

方策の分布を学習後のモデルを使用して、探索パラメータを再調整を行った。
なお、optunaで少し探索を行っただけのため、まだ調整は不十分な状態である。

初期局面のPVの深さは、41になった。

学習前と学習後のモデルで対局した結果は、以下の通りとなった。
持ち時間3分1手1秒加算

   # PLAYER               :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 model-0000195        :     0.7   10.5   514.0    1024    50      55  470   88  466     9
   2 model_gct_010_opt    :    -0.7   10.5   510.0    1024    50     ---  466   88  470     9

ほぼ互角になっている。

水匠3改を加えてリーグ戦を行った結果は以下の通り(測定途中)。

   # PLAYER                        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 model_gct_010_opt             :    30.6   59.1    35.5      63    56      65   33    5   25     8
   2 model-0000195                 :    11.1   56.8    33.5      64    52      86   32    3   29     5
   3 YaneuraOu NNUE 6.00 64AVX2    :   -41.7   57.5    26.0      63    41     ---   24    4   35     6

こちらの結果では、強くなっていそうである。

まとめ

方策の分布を学習することで、テストデータに対する精度があがるが、探索パラメータがそのままだと弱くなることがわかった。
原因は、Actor-Criticで学習したモデルと、方策の分布を学習したモデルで、最適な探索パラメータが変わるためである。
探索パラメータを再調整すると、強さも精度を反映した結果になる。

将棋AIの実験ノート:AVX対応

コンピュータチェスのCeresでは、PUCTによるノード選択の処理をAVXを使って高速化している。
これは、Ceres独自の「parallelized descent algorithm」(並列降下アルゴリズム)と合わせて使用することで、効果を発揮するもののようだ。

Ceresで実際にどれくらいNPSがでるか確認したところ、15ブロック、192フィルタのモデルを使用して、RTX30901枚で、初期局面のNPSは、142,685であった。

go nodes 1000000
Loaded network weights: 750181: 15x192 WDL MLH  from H:\src\Ceres\lc0\weights_run3_750181.pb.gz
info depth 1 seldepth 2 time 1016 nodes 1 score cp -0 tbhits 0 nps 1 pv g2g3  string M= 157
(略)
info depth 10 seldepth 22 time 7005 nodes 999471 score cp 8 tbhits 0 nps 142685 pv c2c4 e7e6 g2g3 d7d5 f1g2 d5d4 g1f3 c7c5 e2e3 b8c6 e3d4 c5d4 e1g1 g8f6 f1e1 f8d6 a2a3 a7a5 d2d3 e8g8 b1d2  string M= 157
bestmove c2c4

一方、dlshogiは、10ブロック、192フィルタのモデルで、初期局面のNPSは48,245である。
チェスと将棋の盤面サイズ、終端ノードでの詰み探索のありなどの条件の違いはあるが、Ceresはdlshogiより大きいモデルで約2.96倍のNPSが出ている。

dlshogiの探索部もまだまだ高速化の余地があることが分かる。

Ceresの並列アルゴリズムをdlshogiにも導入したいと考えているが、とりあえず、並列アルゴリズムは現在のままで、ノード選択処理のAVX化を行ってみた。

Ceresは並列アルゴリズムと組み合わせてAVX化しているが、単にノードを選択する際に、複数の子ノードのUCBを計算して、UCBが最大のノードを選ぶ処理をAVX化した。

AVX化前の処理

	for (int i = 0; i < child_num; i++) {
		const WinType win = uct_child[i].win;
		const int move_count = uct_child[i].move_count;

		if (move_count == 0) {
			// 未探索のノードの価値に、親ノードの価値を使用する
			q = parent_q;
			u = init_u;
		}
		else {
			q = (float)(win / move_count);
			u = sqrt_sum / (1 + move_count);
		}

		const float rate = uct_child[i].nnrate;
		const float ucb_value = q + c * u * rate;
		if (ucb_value > max_value) {
			max_value = ucb_value;
			max_child = i;
		}
	}

AVX化後の処理

const __m256i m256i_zero{};
const __m256i m256i_one = _mm256_set1_epi32(1);
const __m256 m256_one = _mm256_set1_ps(1);
const __m256i m256i_eight = _mm256_set1_epi32(8);

	__m256 m256_c = _mm256_broadcast_ss(&c);
	__m256 m256_parent_q = _mm256_broadcast_ss(&parent_q);
	__m256 m256_init_u = _mm256_broadcast_ss(&init_u);
	__m256 m256_sqrt_sum = _mm256_broadcast_ss(&sqrt_sum);

	__m256 vmaxvalue = _mm256_set1_ps(-FLT_MAX);
	__m256i vnowposition = _mm256_set_epi32(7, 6, 5, 4, 3, 2, 1, 0);
	__m256i vmaxposition = vnowposition;
	for (size_t i = 0; i < child_num; i += 8) {
		if (i + 8 > child_num) {
			// 残り8未満
			__m256i mask_rest;
			switch (child_num - i) {
			case 1:
				mask_rest = _mm256_set_epi32(0, 0, 0, 0, 0, 0, 0, -1);
				break;
			case 2:
				mask_rest = _mm256_set_epi32(0, 0, 0, 0, 0, 0, -1, -1);
				break;
			case 3:
				mask_rest = _mm256_set_epi32(0, 0, 0, 0, 0, -1, -1, -1);
				break;
			case 4:
				mask_rest = _mm256_set_epi32(0, 0, 0, 0, -1, -1, -1, -1);
				break;
			case 5:
				mask_rest = _mm256_set_epi32(0, 0, 0, -1, -1, -1, -1, -1);
				break;
			case 6:
				mask_rest = _mm256_set_epi32(0, 0, -1, -1, -1, -1, -1, -1);
				break;
			case 7:
				mask_rest = _mm256_set_epi32(0, -1, -1, -1, -1, -1, -1, -1);
				break;
			default:
				// unreachable
				mask_rest = _mm256_set1_epi32(0);
				break;
			}
			__m256i m256i_move_count = _mm256_maskload_epi32(move_count + i, mask_rest);
			__m256i mask = _mm256_cmpgt_epi32(m256i_move_count, m256i_zero);

			//	q = (float)(win / move_count);
			__m256 m256_win = _mm256_maskload_ps(win + i, mask_rest);
			__m256 m256_move_count = _mm256_cvtepi32_ps(m256i_move_count);
			__m256 m256_q_tmp = _mm256_div_ps(m256_win, m256_move_count);
			__m256 m256_q = _mm256_blendv_ps(m256_parent_q, m256_q_tmp, _mm256_castsi256_ps(mask));

			//	u = sqrt_sum / (1 + move_count);
			__m256 m256_move_count_plus1 = _mm256_add_ps(m256_move_count, m256_one);
			__m256 m256_u_tmp = _mm256_div_ps(m256_sqrt_sum, m256_move_count_plus1);
			__m256 m256_u = _mm256_blendv_ps(m256_init_u, m256_u_tmp, _mm256_castsi256_ps(mask));
			__m256 m256_rate = _mm256_maskload_ps(nnrate + i, mask_rest);

			//const float ucb_value = q + c * u * rate;
			__m256 m256_ucb_value = _mm256_mul_ps(m256_c, m256_u);
			m256_ucb_value = _mm256_mul_ps(m256_ucb_value, m256_rate);
			m256_ucb_value = _mm256_add_ps(m256_q, m256_ucb_value);

			// mask
			m256_ucb_value = _mm256_and_ps(m256_ucb_value, _mm256_castsi256_ps(mask_rest));

			// find max
			__m256 vcmp = _mm256_cmp_ps(m256_ucb_value, vmaxvalue, _CMP_GT_OS);
			vmaxvalue = _mm256_max_ps(m256_ucb_value, vmaxvalue);
			vmaxposition = _mm256_blendv_epi8(vmaxposition, vnowposition, _mm256_castps_si256(vcmp));
			vnowposition = _mm256_add_epi32(vnowposition, m256i_eight);

			break;
		}

		//if (move_count == 0) {
		__m256i m256i_move_count = _mm256_load_si256((__m256i*)(move_count + i));
		__m256i mask = _mm256_cmpgt_epi32(m256i_move_count, m256i_zero);

		//	// 未探索のノードの価値に、親ノードの価値を使用する
		//	q = parent_q;
		//	u = init_u;
		//  --> 下記のelseの計算結果と合わせて_mm256_blendv_psで設定する
		//}
		//else {
		//	q = (float)(win / move_count);
		__m256 m256_win = _mm256_load_ps(win + i);
		__m256 m256_move_count = _mm256_cvtepi32_ps(m256i_move_count);
		__m256 m256_q_tmp = _mm256_div_ps(m256_win, m256_move_count);
		__m256 m256_q = _mm256_blendv_ps(m256_parent_q, m256_q_tmp, _mm256_castsi256_ps(mask));

		//	u = sqrt_sum / (1 + move_count);
		__m256 m256_move_count_plus1 = _mm256_add_ps(m256_move_count, m256_one);
		__m256 m256_u_tmp = _mm256_div_ps(m256_sqrt_sum, m256_move_count_plus1);
		__m256 m256_u = _mm256_blendv_ps(m256_init_u, m256_u_tmp, _mm256_castsi256_ps(mask));
		//}

		//const float rate = uct_child[i].nnrate;
		__m256 m256_rate = _mm256_load_ps(nnrate + i);

		//const float ucb_value = q + c * u * rate;
		__m256 m256_ucb_value = _mm256_mul_ps(m256_c, m256_u);
		m256_ucb_value = _mm256_mul_ps(m256_ucb_value, m256_rate);
		m256_ucb_value = _mm256_add_ps(m256_q, m256_ucb_value);

		// find max
		__m256 vcmp = _mm256_cmp_ps(m256_ucb_value, vmaxvalue, _CMP_GT_OS);
		vmaxvalue = _mm256_max_ps(m256_ucb_value, vmaxvalue);
		vmaxposition = _mm256_blendv_epi8(vmaxposition, vnowposition, _mm256_castps_si256(vcmp));
		vnowposition = _mm256_add_epi32(vnowposition, m256i_eight);
	}
	// find max
	const int* maxposition = (int*)&vmaxposition;
	__m256 vallmax = _mm256_max_ps(vmaxvalue, _mm256_shuffle_ps(vmaxvalue, vmaxvalue, 0xb1));
	vallmax = _mm256_max_ps(vallmax, _mm256_shuffle_ps(vallmax, vallmax, 0x4e));
	vallmax = _mm256_max_ps(vallmax, _mm256_permute2f128_ps(vallmax, vallmax, 0x01));
	__m256 vcmp = _mm256_cmp_ps(vallmax, vmaxvalue, _CMP_EQ_US);
	int mask = _mm256_movemask_ps(vcmp);
	max_child = maxposition[__builtin_ctz(mask)];

パッと見には何をやっているか分からない(;'∀')
8未満を処理するためにswichで分けている部分が美しくない。

最大値のインデックスを探す処理は、はじめ思いつかなかったが、Discordで教えを乞うたところ、やねうらお氏から参考情報を教えていただき、それを元に実装したコードを、@wain_CGP氏に添削していただいた(最終的にはもらったコードほぼそのまま)。

測定

上記のAVX化した処理を探索部に組み込んで、どれくら速くなるか測定を行った。
V100 8枚で、floodgateからサンプリングした100局面(1局面は詰みなので除外)で測定した。
https://github.com/TadaoYamaoka/DeepLearningShogi/blob/master/utils/benchmark.py

測定結果
AVXなし AVXあり
平均 229621 239431 1.04
中央値 235244 242866 1.03
最大 264526 392199 1.48
最小 148579 152466 1.03

平均で、4%程NPSが上昇した。
最大では、1.48倍の局面がある。
探索する局面の子ノードの数によって効果が変わってくる。

コード

探索部に組み込んだ処理はこちら。
DeepLearningShogi/UctSearch.cpp at 63d17b043c4ca0a37d15ea4e417a63cdffb29cc6 · TadaoYamaoka/DeepLearningShogi · GitHub
詰みのAND-OR木探索も含んでいるので、さらに美しくなくなっている。

まとめ

Ceresにインスパイアされてノード選択処理のAVX化を行った。
結果、平均で4%程高速化することができた。

AVX化を行ってもCeresのNPSには遠く及んでいない。
Ceresは、AVX化よりも衝突を回避した並列アルゴリズムの方がNPSへの寄与が大きいと思われる。
そのうち、Ceresの並列アルゴリズムをdlshogiにも導入したいと考えている。

2021/4/4 追記

AVX化の前後で強さを確認を測定した。
持ち時間3分、1手1秒加算

   # PLAYER          :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 dlshogi_avx2    :     0.2    9.0   500.5    1000    50      52  370  261  369    26
   2 dlshogi         :    -0.2    9.0   499.5    1000    50     ---  369  261  370    26

AVX化しても強くなっていない。