TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

【dlshogi】Multi PV対応版の実行ファイル公開

dlshogiのMulti PV対応版の実行ファイルを公開します。
Release Multi PV対応版 · TadaoYamaoka/DeepLearningShogi · GitHub

実行ファイルのみの公開ですので、世界将棋AI 電竜戦バージョン(「GCT電竜」同梱)に上書きしてください。

また、探索部の改良により、電竜戦バージョンよりも、NPSが約9%向上して、メモリ使用量も約7%削減されています。

NPS

floodgateからサンプリングした99局面を5秒探索時のNPS(NVIDIA V100×8使用)

電竜戦バージョン 20210109版 比率
平均 216960 235636 108.61%
中央値 218729 245209 112.11%
最大 267915 265209 98.99%
最小 131937 150549 114.11%
メモリ使用量

50000000ノード探索時のメモリ使用量
※10000000ノード以上探索すると浮動小数の桁落ちで精度が低下するため、UCT_NodeLimitはデフォルトのまま使用することを推奨

メモリ使用量(KB) 比率
電竜戦バージョン 86,928,724 100%
20210109版 81,162,384 93.36%
ShogiGUIの検討画面

※ShogiGUIで使用する際は、エンジン登録時にタイムアウトするため、事前に将棋所に登録してキャッシュファイルを作成する必要があります(数分かかります)。
MCTSの性質上、候補手は評価値の順にならない場合があります。候補手は、訪問回数順(期待値が高く、かつ誤差が小さい)に並びます。
f:id:TadaoYamaoka:20210109150801p:plain

将棋AIの進捗 その53(MultiPVの実装)

Qhapaqさんからのプルリクエストをもらっておきながら対応していなかったMultiPVに遅ればせながら対応しました。
MultiPVを使わない際の速度には一切影響しない形で実装したかったので、リファクタリングしてから取り込もうと思いつつ、探索部の改良を行っていたので遅くなってしまいました(・ω<

GitHubのソースからビルドが必要な状態なので、メモリ使用量を減らす改良なども行ったうえでバイナリもリリースするつもりです。

iOS版ボーカル音程モニター(Vocal Pitch Monitor)をバージョンアップ 1.3.0

正月は将棋AIの開発をちょっとお休みして、iPhoneアプリVocal Pitch Monitorのバージョンアップを行った。
Android版と機能差分が開いていたり、ノッチに対応していなかったりだったので、改修せねばと思いつつ、将棋AIの開発ばかりしていたので4年以上バージョンアップできていなかった。

今回のバージョンアップのメインはチューナー機能で、個人的にもAndroid版でアナログギターのチューナーとして使用しているので、Android版と比較して欲しい人が多そうなので対応することにした。まだAndroid版と機能差分があるので、徐々に対応したいと思う。
f:id:TadaoYamaoka:20210102174319p:plain:w200

更新内容
  • チューナー機能追加
  • ノッチに対応
  • 解析精度を向上
  • 低音方向の解析範囲をC1までに拡張
  • 録音時間を5分に延長
  • バグ修正


まだ審査中なので、新しいバージョンはダウンロードできないですが、1週間くらいでダウンロードできるようになると思います。

Vocal Pitch Monitor

Vocal Pitch Monitor

  • Tadao Yamaoka
  • Music
  • $1.99
apps.apple.com

余談

久しぶりだったので、Mac OSをバージョンアップして最新のXcodeを入れなおすところから始める必要があったり、プロビジョニングの更新に手間取ったり、新しい解像度のアイコンが必要だったり、アプリ申請に米国納税フォームの入力が必要になっていたりで、開発以外のところで丸一日くらい費やした。
iOS開発はこれがあるので、連休中じゃないとなかなかやる気が起きなかった。

将棋AIの進捗 その52(探索部の改良)

ここ数週間、探索部の細かい改良をしては測定していた。
小さなレーティング差を計測するには多くの対局数が必要になるので、一つの改良の確認に時間がかかるのがつらいところである。
1手1秒と1手3秒で結果が異なることもあるため、長時間思考で強くしたいため1手3秒での測定を基本にしている。
測定は、変更前後の自己対局と、水匠2 2スレッド1000万ノードとの対局(dlshogiは1GPU3スレッド)で確認している。
水匠2との対局は、対局数が少ないと誤差が大きくでるので、500対局以上でないと信用できない。

以下に、行った変更と測定結果をまとめておく。

1.ノード管理の変更

以前に、メモリ節約のために子ノードへのポインタと統計情報を、ノードに訪問するまで初期化しない対応を行ったが、弱くなったため不採用とした。
これを、子ノードへのポインタのみ親ノードで配列で管理し初期化のタイミングを遅らせて、統計情報の管理は今まで通りにするようにした。

以前に弱くなった理由は、子ノードのpolicyの値と、統計情報のメモリ配置が分散してしまったことだと考えたので、policyの値と統計情報はメモリ上で連続になるようにした。

また、ノード展開を排他制御するため、各ノードでmutexを保持していたが、これがノードごとに(VC++の場合)80バイト消費するので、固定サイズ65536だけmutexを確保して、各局面のハッシュの下位ビットをインデックスとして使用して利用するようにした。
これは、KataGoでもmutex_poolの仕組みとして採用されていたが、配列のインデックスをランダムに割り当ててノードにインデックスを保持する実装になっていた。
インデックスはノードに保持しなくても、探索中の局面のハッシュから導出した方がメモリの節約になる(←Discordでのやねうら氏からの指摘)。

測定結果
   # PLAYER             :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 dlshogi            :     1.5   11.9   383.0     760    50      60  340   86  334    11
   2 new_node_manage    :    -1.5   11.9   377.0     760    50     ---  334   86  340    11

   # PLAYER                        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 dlshogi                       :     5.2   22.6   275.5     542    51      65  267   17  258     3
   2 YaneuraOu NNUE 5.32 64AVX2    :    -0.6   13.9   535.5    1074    50      60  519   33  522     3
   3 new_node_manage               :    -4.6   22.6   263.0     532    49     ---  255   16  261     3

少し弱くなるようだが、5000万ノード(V100×8で約4分)探索した際のメモリ使用量は、86,880,520KBから79,180,824KB(91.1%)になった。
採用するか悩ましいが、勝率の型をfloatからdoubleにした場合にさらにメモリを消費することを考慮して、採用するつもりである。

2.勝率の型をfloatからdoubleに変更

勝率の型をfloatからdoubleにすることで、UCBの勝率項の誤差が小さくなる

測定結果
   # PLAYER        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 dlshogi       :     2.5   10.1   507.0    1000    51      68  484   46  470     5
   2 win_double    :    -2.5   10.1   493.0    1000    49     ---  470   46  484     5

   # PLAYER                        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)     W    D    L  D(%)
   1 YaneuraOu NNUE 5.32 64AVX2    :    15.9   10.0  1067.5    2000    53      91  1037   61  902     3
   2 dlshogi                       :     1.4   15.8   479.5    1000    48      89   464   31  505     3
   3 win_double                    :   -17.4   15.8   453.0    1000    45     ---   438   30  532     3

少し弱くなっている。
1手3秒だと、UCBの勝率項の誤差よりもnpsの低下の方が影響していそうである。
大会で長時間思考した場合は、誤差の影響の方ができるかもしれないので、1手3秒よりも長時間で確認する必要がある(確認予定)。

少なくとも定跡作成時は、doubleにした方がよいので、型をtypdedefで変更可能とする予定である。

3.UCBの定数をループの外で計算

今までループの中で平方根を含む定数を計算していたため、ループの外で計算するようにした。

測定結果
   # PLAYER       :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 ucb_const    :     7.1   29.9    64.5     124    52      68   59   11   54     9
   2 dlshogi      :    -7.1   29.9    59.5     124    48     ---   54   11   59     9

   # PLAYER                        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 YaneuraOu NNUE 5.32 64AVX2    :     6.6   33.9    90.5     176    51      59   87    7   82     4
   2 ucb_const                     :    -1.5   54.3    42.0      86    49      53   41    2   43     2
   3 dlshogi                       :    -5.1   55.5    43.5      90    48     ---   41    5   44     6

対局数が少ないので、この結果で強くなったとは言えないが、この変更で弱くなることはないので採用した(masterに反映済み)。

4.atomicのメモリオーダーを指定

atomic変数にメモリオーダーを指定しないと、デフォルトでmemory_order_seq_cst(複数スレッドで変更を同期する)になる。
2変数以上の変更順序を保証する必要がある場合は、memory_order_seq_cstにする必要があるが、1変数であれば一番緩い設定のmemory_order_relaxedにできる。
Leela Chess ZeroやKataGoなどでもmemory_order_relaxedにしている。

測定結果
   # PLAYER          :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 dlshogi         :     3.7   11.4   396.5     777    51      74  359   75  343    10
   2 memory_order    :    -3.7   11.4   380.5     777    49     ---  343   75  359    10

   # PLAYER                        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 YaneuraOu NNUE 5.32 64AVX2    :     3.0   13.6   558.0    1102    51      52  544   28  530     3
   2 memory_order                  :     2.4   22.1   278.5     558    50      64  271   15  272     3
   3 dlshogi                       :    -5.4   22.1   265.5     544    49     ---  259   13  272     2

自己対局ではなぜかむしろ弱くなっているが、誤差の範囲と言えそうだ。
x64のCPUであれば、atomicのload()は、memory_order_seq_cstでもmemory_order_relaxedでも同じ命令で、更新だけ異なるようである。
更新よりも参照回数が圧倒的に多いので影響がないと言えそうだ。
この変更は採用しなくても良さそうである。

5.詰み探索をtemplateで再帰処理する

今まで終端ノードでの詰み探索において、深さを引数に与えて、深さをデクリメントしながら再帰処理していた。
深さをC++のtemplate引数にすることで、再帰呼び出しコンパイル時に行うようにした。
深さ3は3手詰め専用ルーチンを実装しているので、深さ3をtemplateで特殊化することで、template引数で再帰処理できるようにした。

測定結果
   # PLAYER                 :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 mate_depth_template    :     9.4   29.8    69.5     132    53      73   64   11   57     8
   2 dlshogi                :    -9.4   29.8    62.5     132    47     ---   57   11   64     8

   # PLAYER                        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 mate_depth_template           :     5.1   54.3    47.0      92    51      58   46    2   44     2
   2 YaneuraOu NNUE 5.32 64AVX2    :    -2.5   32.5    92.0     186    49      50   90    4   92     2
   3 dlshogi                       :    -2.5   54.2    47.0      94    50     ---   46    2   46     2

まだ測定中で対局数が少ないので有意とは言えないが、強くなっていそうである。
dlshogiでは、終端ノードでの詰み探索が終盤の王手の多い局面でのボトルネックになっているので、この部分は可能な限り高速化したい。
測定を続けて少なくとも弱くなっていなければ採用する予定である。

6.1手詰めルーチンをやねうら王から移植

dlshogiは局面管理にAperyのソースコードを流用していて、1手詰めルーチンもAperyのコードをそのまま利用している。
Aperyの1手詰めルーチンは、近接王手のみチェックしているため、飛車や角の離し王手や、開き王手で詰みになる場合はチェックしていない。
一方、やねうら王の1手詰めルーチンでは、離し王手でも相手玉の24近傍ではチェックしており、開き王手も両王手になる場合はチェックしている(ただし、やねうら王ではレーティングが向上していないということでコメントアウトされた)。
この処理をdlshogiにも移植を行った。

測定結果
   # PLAYER      :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 mate1ply    :    10.4   19.1   171.5     325    53      86  161   21  143     6
   2 dlshogi     :   -10.4   19.1   153.5     325    47     ---  143   21  161     6

   # PLAYER                        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 dlshogi                       :    13.2   32.1   126.5     240    53      81  123    7  110     3
   2 YaneuraOu NNUE 5.32 64AVX2    :    -5.8   20.2   230.5     473    49      53  221   19  233     4
   3 mate1ply                      :    -7.3   32.9   116.0     233    50     ---  110   12  111     5

まだ測定中だが、自己対局では強くなって、水匠2相手では弱くなっていそうという傾向になっている。
水匠2との対局は誤差が大きくでるので、500局以上測定できてから判断した方が良さそうだ。

MCTSの探索では速度重視で、Aperyの1手詰めルーチンで、ルートノードでのdf-pnではやねうら王の1手詰めルーチンという使い分けが良いかもしれない。
あと、現状詰み探索では速度重視で不成を生成していないが、ルートノードでのdf-pnは時間に余裕があるので不成も生成した方が良さそうだと気付いた(試す予定)。

7.候補手が1手のみの場合すぐに展開する

ノードの候補手が1手のみの場合、そのノードを評価しないですぐに展開して1手深く探索するようにした。

測定結果
   # PLAYER     :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 onemove    :     6.3   10.2   517.5    1000    52      89  480   75  445     8
   2 dlshogi    :    -6.3   10.2   482.5    1000    48     ---  445   75  480     8

   # PLAYER                        :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 dlshogi                       :    10.1   17.0   429.0     826    52      88  418   22  386     3
   2 YaneuraOu NNUE 5.32 64AVX2    :    -3.6   11.1   820.0    1665    49      60  794   52  819     3
   3 onemove                       :    -6.5   17.0   416.0     839    50     ---  401   30  408     4

自己対局では強くなって、水匠2相手では弱くなるという判断に迷う結果になった。
不採用としておく。

8.投機的な探索

マルチスレッドで探索ノードの衝突が起きた場合に、Virtual lossを一時的に上げて再探索し、新しいノードに達したら仮展開し、事前評価しておくようにする(バックアップは行わない)。
これにより、ノードの衝突が多いとNPSが低下するのを防ぐことができる。

実装してみたのだが、floodagateからサンプリングした100局面でNPSを測定した結果では、NPSは向上しなかった(少し低下した)。
平均NPS:242671.18 → 240905.84

V100×8でGPUあたり3スレッドで探索すると、通常でも十分にVirtual lossが加算されているので、さらに加算して探索したノードをキャッシュしてもほとんどキャッシュヒットしていない状況だと思われる。
バッチサイズを上げてNPSを向上するのは一筋縄ではいかなそうである。
引き続き課題として取り組む予定である。

まとめ

探索部の改良で行ったことを忘れないうちにまとめた。
上記のうち、いくつかはレーティング向上につながりそうである。

本日開催の電竜戦TSECでは、いくつかは取り込んだ上で参加するつもりである。

将棋AIの進捗 その51(floatの桁落ち)

dlshogiの現在の実装では、長時間思考して探索ノード数が大きくなった場合に、ノードにバックアップされる価値の合計がfloat型になっているため、誤差が許容できないという指摘をやねうらお氏から頂いた。

floatに[0,1]の価値の値を足し合わせていく場合に、桁落ちは当然気を付けるべきだが、ディープラーニングを使用している場合、探索ノード数それほど多くならないので、指摘されるまで意識していなかった。
しかし、現状ではGPUを8枚使用するような状況になったので、長時間思考で問題になっていた。

floatの桁落ち

floatの仮数部は23ビットなので、有効桁数は10進数で7桁となる。
数千万ノードをバックアップする場合は、有効桁数には収まらなくなる。

以下のようなプログラムでシミュレーションすることで精度を確かめられる。

#include <iostream>
int main()
{
	const float value = 0.5f;
	const int N = 50000000;
	float win = 0;
	for (int i = 0; i < N; ++i) {
		win += value;
		if ((i + 1) % 1000000 == 0)
			std::cout << i + 1 << "\t" << std::fixed << win << "\t" << win / (i + 1) << std::endl;
	}
}

valueを0.5として、足し合わせていくと、1700万あたりで合計が増えなくなり、平均の計算の誤差が拡大していっている。
f:id:TadaoYamaoka:20201211234852p:plain

valueを0.8とすると、もっと早くから誤差が現れる。
f:id:TadaoYamaoka:20201211234909p:plain

持ち時間が長い大会の条件では、無視できない誤差となっている。

対策

doubleにする

floatをdoubleに変更することが、簡単な対策となる。
先ほどのプログラムのwinの型をdoubleに変えると、平均は誤差なく0.5となる。
f:id:TadaoYamaoka:20201211235239p:plain

ただし、floatからdoubleにすることで、メモリ使用量が増える。

平均を保持する

他の方法として、ノードに合計を保持するのではなく、平均を更新する方法もある。
n回バックアップされたノードの価値の平均をQ_n、n回目にバックアップされる価値をv_nとすると、n+1回目の平均は、
\displaystyle
Q_{n+1} = \frac{Q_n \cdot n + v_{n+1}}{n+1}
で、計算できるので、平均の更新量は、
\displaystyle
Q_{n+1} - Q_n = \frac{v_{n+1} - Q_n}{n+1}
で計算できる。

ただし、この方法で更新しようとすると、更新に変数を2つ使用するため、排他ロックが必要になる。
dlshogiは、可能な限りロックフリーになるようにatomicを使って実装しているため、この方式は採用したくない。
なお、Leela Chess Zeroはこの式を使用している。

また、この式を使用したとしても誤差がなくなるわけではない。
ノード数が増えると更新が無視されるようになるので誤差が広がらなくて済むだけである。

まとめ

長時間思考では誤差が無視できないことがわかったため、合計を保持する変数の型をdoubleに変更する対策を行うことにする。
現状でもメモリをかなり消費する実装になっているが、メモリ使用量がさらに増えることになる。
電竜戦で使用したAWSのA100インスタンスのメモリは1.1TBあるので、大会では問題にはならないだろう。

しかし、定跡作成で長時間思考する場合は、メモリの制約で探索ノード数を大きく増やせないという課題がある。
128GBで、5000万くらいが限度である。

将棋AIの進捗 その50(メモリ使用量削減)

dlshogiは、1ノードにつき平均2KBのメモリを消費する(局面の平均合法手を80とした場合)。
通常GPU 1枚で探索した場合、NVIDIA RTX 3090で最大4.5万NPS程度なので、5分探索したとすると、探索ノード数は1350万ノードで、約27GBのメモリを消費する。

複数枚GPUを使用して、定跡を作成する場合には、さらに多くのノードを探索することになる。
5000万ノードを探索すると、100GBのメモリが必要になる。
なお、使用メモリ量が搭載物理メモリ以上になると、スワップが発生するため、NPSが極端に落ちる。

dlshogiのノードのメモリ管理

各ノードには、候補手ごとに、

  • 候補手を表すMove型
  • ポリシーネットワークの確率
  • 訪問回数
  • バックアップされた価値の累計
  • 子ノードへのポインタ

などを記録している。

問題箇所

Discordでやねうらお氏から、子ノードへのポインタを候補手すべてについて保持せず、実際に訪問して必要になった時点で確保すれば削減できるとアドバイスをもらった。
Leela Chess Zeroでも、Edge_Iteratorという仕組みでリンクリストのような構造で、必要になった時点で追加する方式を採用している。
しかし、リンクリストの管理を行うために、ノードの排他制御が必要になっているため、dlshogiでは採用したくなかった。
そのため、候補手の分、管理領域を予め確保して、配列にインデックスでアクセスするという方式をとっている。

メモリ使用量削減

速度を重視して、この方式は変えたくないのだが、終端ノードで一度も子ノードに訪問していない場合は、子ノードの管理領域を確保しておく必要がないことに気付いた。
初回にいずれかの子ノードの訪問した時点で、管理領域を確保するようにすれば、メモリを節約できる。
つまり、ゲーム木の終端ノードの数だけ、子ノードの管理領域の分のメモリが削減される。

そのように管理領域を確保するタイミング変更して、どれくらいメモリを節約できるか測定した。

5000万ノード探索時のメモリ使用量

変更前後で、5000万ノードの探索を行い、ps auxでRSS(物理メモリの使用サイズ)を3秒おきに確認した。
f:id:TadaoYamaoka:20201208234751p:plain

変更前と比べて、86%に減らせることが分かった。

探索速度

探索速度が低下していないか、floodgateの棋譜からサンプリングした100局面を使用したベンチマークプログラムで確認した。

V100×8で測定した結果
平均NPS
変更前 227648
変更後 230801

NPSは低下していないことが確認できた。

まとめ

dlshogiのノードのメモリ確保タイミングを変更するとで、メモリ使用量を削減した。
これでも、まだメモリ使用量が多いので、Leela Chess Zeroのようなメモリ管理方式にするかは悩みどころである。
定跡作成時でも、5000万ノードも探索できれば十分な気もするので、ひとまずこれ以上の変更は行わないことにする。

探索ノード数が増えると、floatの桁落ちで精度が落ちるという問題も見つかっているので、そちらも別途改善予定。

2020/12/11 追記

上記の修正を行い、変更前後で勝率を比較すると、弱くなることが判明した。
メモリ使用量より強さを優先したいため、変更は取り込まないことにする。

   # PLAYER              :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 dlshogi             :    10.3   20.4   144.0     272    53      84  134   20  118     7
   2 memory_efficient    :   -10.3   20.4   128.0     272    47     ---  118   20  134     7

将棋AIの進捗 その49(並列化の課題)

dlshogiでは、複数GPUを使用して並列化した場合に、ノードの衝突が発生しやすくなりNPSが1/3近くになる場合がある。

例として、電竜戦でA100×8使用した時、以下の局面でNPSが初期局面に対して1/3近くなっていた。

局面 NPS
初期局面 342985
position startpos moves 7g7f 8c8d 2g2f 8d8e 8h7g 3c3d 7i8h 2b7g+ 8h7g 3a4b 2f2e 4b3c 6i7h 4a3b 3i3h 7a6b 3g3f 6c6d 5i6h 1c1d 3h3g 6b6c 6h7i 6c5d 3g4f 4c4d 3f3e 4d4e 3e3d 3c3d 4f3g 3b3c 2h3h 3d3e 4i4h 5a4a 2e2d 2c2d 3g3f 3e3f 3h3f P*3d P*2c S*3e 3f5f B*4d 153259

原因

MCTSで並列化を行う場合に、バーチャルロスという仕組みで、探索するノードをばらけさせることが行われている。
並列度が高くなると、バーチャルロスを使っても、同じ終端ノードに到達することが多くなる。

終端ノードを展開するには、ポリシーネットワークの計算を待つ必要があり、同じ終端ノードに到達した場合は、それ以上探索できないため探索(プレイアウト)を破棄している。

dlshogiでは、バッチサイズ分の探索を行ってから、GPUでバッチでまとめてポリシーネットワーク(とバリューネットワーク)の計算するということを行っているため、破棄した探索があると、バッチサイズが小さくなり、GPUが十分に活用できなくなる。

上記の2局面について、V100×8を使用して探索した場合の、バッチサイズの割合は以下の通りとなった。
f:id:TadaoYamaoka:20201206111221p:plain

初期局面(pos_0)では、ほとんどがバッチサイズ128(最大)で、ノードの衝突がほとんど起きていない。
一方、NPSが落ちる局面(pos_1)では、バッチサイズが100~128の間に分布している。
ログスケールで見ると、50以下にも分布していることが分かる。
f:id:TadaoYamaoka:20201206111743p:plain

小さいバッチサイズで計算しても、大きいバッチサイズで計算しても、同じだけ時間を消費するため、小さいバッチサイズによるNPSへの影響は大きい。

対策

GPUを有効に活用するには、バッチサイズを大きくする必要がある。

ノードが衝突した場合は、予測が外れても良いので、将来展開されるノードをあらかじめ計算しておくことで、GPUのバッチサイズを大きくすることができる。
しかし、予測の精度が低すぎると、無駄になるため、ある程度の予測精度が欲しい。

対策案
  1. 展開済みのゲーム木から次に展開されそうな兄弟ノードを仮展開する
  2. 衝突した終端ノードで、次に展開される可能性が高い手を予測して、仮展開する
  3. 一時的にバーチャルロスを上げて、通常の探索を行い終端ノードを仮展開する

いずれの案でも、ノードを仮展開した後に不正確なノードがバックアップされると精度に影響がでるため、バックアップは行わない。

案1は、Leela Chess Zeroで実装されている方法である。
lc0/search.cc at 99fecc9dbd701c78a057aff77734213006f94014 · LeelaChessZero/lc0 · GitHub

案2は、なんらかの方法で予測が必要になる。CPUのみで高速に計算できるポリシーネットワークのようなものが必要になる。

案3は、ちょうどこのブログを書いていた時に、Discordでやねうらお氏からdlshogiの探索部についてダメだし?されていた時に頂いた案である(感謝!)。


とりあえず、Leela Chess Zeroの実装を参考に、案1を試してみるつもりである。

案2は、そこそこの精度のポリシーネットワークはそれなりに計算が重くなりそうである。軽量なポリシーネットワークの学習には興味あるので別途試してみるかもしれない。

案3は、案1より良くなる可能性もあるので比較してみたい。

まとめ

現状のdlshogiの並列化の課題について整理した。
並列化が改善されれば、探索部のみでもdlshogiの棋力はまだ伸びる見込みである。

(やる気が起きて)実装ができたら、また記事にする予定である。