Google Compute Cloudでの探索実験

　8GPUインスタンスを使って探索速度を検証した。

　まず20CPU、8GPU(Tesla V100)のインスタンスを使って探索速度を検証した。

　早い段階で頭打ちになっている。8GPU使うときのGPU利用率を見てもあまり高くなっていない（1GPUなら50%くらいは行く）。

　1GPUでも探索中は20CPUを満遍なく使っている。

　なんだかんだCPUがボトルネックになっていそうではあるので増やしてみた。（別に探索中に立てるスレッド数を増やすわけではないので意味はないと思ったが検証のため）。

　20CPU→40CPUにしたときはそこそこ上がったのでお！と思ったが、60CPUにしたらまた下がったので、なにかマシンの影響だったのかもしれない。CPUの情報を見ておけばよかったか。

　最後に、探索中バックアップするときのmutexロックを外してみたところ、8GPUでNPSが46371まで上がった（約1.5倍程度）。やはり排他制御でかなり詰まっているようだ。

考察

　そもそも現状の並列化を振り返ると、次のような想定をしている。

　こうやってGPUをフルに使うのが理想なのだが、現状はGPUの方が空いている時間が多く、おそらく次のようになっている。

　CPUを増やす方法として、このキューを3つにするというのは実装しているのだが、3つのキューを順繰りに計算していくことになると最善読み筋を伸ばすのに時間がかかるのでかえって弱くなってしまいそうな気がしている。

　フラットに図を眺めてみれば、単純にキューを埋める部分を複数スレッド化すれば良いのではないかと思えた。むしろなんで今までそれを思いつかなかったのか。実装してみます。

思考時間とレートの関係(2)

　上の調査に便乗してMiacisでも調べ直した。以前（8ヶ月前）の調査は

　結論としては今回も変わらず、「思考時間2倍でレート+100ちょい」という感じ。

　以下対戦相手はYO/Kristallweizen（Thread4・0.2秒）。

Miacis 1手1秒

対局数	勝数	引き分け数	敗数	勝率	相対Eloレート
1000	461	0	539	46.1%	-27.2

　（本筋とは関係ないが前回に比べて、探索中のバッチサイズを32から64にすることで持ち時間1秒でもレート低下が抑えられた。）

Miacis 1手2秒

対局数	勝数	引き分け数	敗数	勝率	相対Eloレート
500	315	0	185	63.0%	92.5

　レート上昇分は119.7

MuZero

　以前もちらっと触れたが、MuZeroの論文中で学習したシミュレータと真のシミュレータでの比較グラフが掲載されている。（囲碁についての結果なので将棋でも単純比較はできないかもしれないが）

Figure 3 A 囲碁に関してのグラフ

　オレンジ線の方が真のシミュレータでの結果なのでそっちを見ることとして、これの1秒〜2秒の変化ではR+100くらいだろうか。大雑把に1秒でR:4800、50秒でR:5400と読み取れば持ち時間50倍でレート+600なので、2倍分で考えると。まぁこれくらいしか上がらないものなのかなという印象。

対局結果メモ

　ここ数日で回していた対局結果をメモしておく。対局結果は全てMiacis側から見たもの。マシンはCPUの周波数約3.6GHz、GPUは2080ti。YO/Kristallweizenは4スレッド、定跡オフ。

ベースライン

　Miacis側 0.5秒、YO/Kristallweizen側 0.1秒。

対局数	勝数	引き分け数	敗数	勝率	相対Eloレート
1000	453	0	547	45.3%	-32.8

持ち時間二倍

　Miacis側 1秒、YO/Kristallweizen側 0.2秒。

対局数	勝数	引き分け数	敗数	勝率	相対Eloレート
1000	416	0	584	41.6%	-58.9

　0.5秒/0.1秒での対局に比べてレートが30ほど落ちた。今までの調査でも多少わかっていたことだが、Miacisは持ち時間を増やしたときの性能の伸び方があまり良くない。

定跡について

　Miacis側 0.5秒、YO/Kristallweizen側 0.1秒で対局。

定跡オン

　standard_book.dbを利用。手数を無視して局面の同一性を判定し、一局面に複数の手が登録されている場合、ランダムに選択する。

対局数	勝数	引き分け数	敗数	勝率	相対Eloレート
250	85	0	165	34.0%	-115.2

　やや対局数が少ないが、レートが80程度落ちてしまった。

定跡オン（初手、二手目飛車先固定）

　定跡オンでの対局を眺めていると、standard_book.dbは振り飛車が多めに見えた。Miacisは振り飛車側を持つのが苦手と思われるので初手と二手目だけについては飛車先を伸ばす手に固定して居飛車に固定するようにした。

対局数	勝数	引き分け数	敗数	勝率	相対Eloレート
250	98	0	152	39.2%	-76.2

　少しだけレートは伸びたが、250局の範囲では誤差内くらいか。

定跡オン（真やねうら王 定跡）

　居飛車固定でも弱かったことからstandard_book.db自体がやや良くない定跡である可能性を考えて、真やねうら王定跡を使うようにした。念の為初手、二手目は飛車先固定にした。

対局数	勝数	引き分け数	敗数	勝率	相対Eloレート
250	123	0	127	49.2%	-5.6

　定跡オフでのベースラインに比べてもややレートが伸びている。持ち時間の消費も抑えられる分もあるのでfloodgate等では有効そう。

教師あり学習による事前学習

　再現性をある程度担保したいので、一度強化学習で学習したパラメータを初期値として再び強化学習をやるようなことはあまりしたくない。かといって毎回ランダムパラメータから学習しているのも効率が悪いと思えたので、自分の中で折り合いのつく点として、教師あり学習である程度事前学習を行ってから強化学習をすることを試してみた。

結果

教師あり学習

　まず教師あり学習を0.1Mステップ(学習時間は4時間弱ほど)回した時点では、Policy損失が1.656799、Value損失が0.701600となった。これは今までの強化学習

での最終的な損失と比べると

手法	Policy損失	Value損失
教師あり学習	1.656799	0.701600
強化学習	2.020327	0.702119

となり、強化学習より小さい値となっているが、これをそのまま対局させても強くない(おおむねレート-300程度である)ことがわかっている。floodgateのデータを「2016年~2018年は学習データ、2015年は検証データ」と分けているとはいえ、データに相関が高いので汎化性能が高くないままに損失の数値は低くできてしまうということだろうか。

　この教師あり学習で得られたパラメータを初期値として強化学習を行った。

強化学習:損失

左:Policy損失　右:Value損失

　事前学習によってPolicy損失、Value損失ともに僅かながら改善されているが、そこまで極端な差が出るというわけでもなかった。よく見ると一番最初の検証時点(0.1Mステップ)での損失は教師あり学習での最終的な損失より大きい値となっている。教師あり学習で得た初期値があまり有効ではなく、学習をやり直している雰囲気を感じる。

強化学習:各ステップでの性能測定(Miacis側0.5秒)

　0.5Mを超えたあたりからはほとんど差がなくなっている。事前学習にはあまり意味がなさそうだ。

おまけ

　floodgateには振飛車の棋譜をちらほらあるようで、そこから教師あり学習を行ったため強化学習の初期には飛車を振る序盤がそこそこ現れていた。

　しか序盤が対抗形風味だとしてもその後囲いあう展開にはならず、さっさと大駒を交換して乱戦模様になっていることが多い。教師あり学習で「振飛車っぽい指し方」を学習できているわけではなく、序盤数手の段階で飛車を左に置く行動の割合が少し多いだけというように感じられた。また、結局学習が進むと居飛車のみになっていた。

　棋譜の保存は学習データ生成中の100局につき1局の頻度であり、さらにそこから数十局を雑に目視で確認しただけなのではっきりした検証ではない。雑談程度に。

探索速度と棋力の関係

　以前AlphaZeroの探索速度を検討した回でMiacisの探索速度も調べた。

　この記事でも述べた通り、今の仕組みではNPSが上がれば棋力が上がるとは限らない。というわけでやねうら王/Kristallweizen(2スレッド、0.1秒)と対局してレートを測定した。

バッチサイズ16

　このバッチサイズではスレッド数を増やしてもNPSは伸びず、棋力もほとんど変わらない。

バッチサイズ32

　バッチサイズを32にするとスレッド数を増やすほどNPSは伸びるようになる。しかしだからといって棋力が伸びるわけではない。

バッチサイズ64

　バッチサイズ64ではもっとNPSが大きくなるのだが、やっぱり棋力は伸びない。

バッチサイズ128

　バッチサイズ128では最大15KまでNPSが大きくなるのだが、やっぱり棋力は伸びない。

スレッド数2

　今までの結果では基本的にどれもスレッド数2で最大のレートになっている。スレッド数2でのEloレートを1枚のグラフにまとめると次のようになる。

　このグラフでもやっぱりNPSとEloレートは関係がなさそう。

結論

　現状のMiacis(ch128, ブロック10)で棋力が最大になるのはバッチサイズが32、スレッド数2のときであり、おおよそ7.5K NPSである。NPS自体はもっと高めることができるが、今の仕組みではNPSとEloレートはあまり関係がなさそうだった。

　ネットワークが小さいのにAlphaZeroよりも探索速度が出てないことになる。TPUが速いだけという以上の差がありそうに感じられる。AlphaZeroが棋力を最適化した結果として10K NPSになったとすれば探索の仕組みがちょっと違うのかもしれない。

AtCoder Beginner Contest 156

結果

順位   228th / 5737
パフォーマンス   2034
レーティング  1753 → 1784(+31)

　E問題までの5完。F問題も解きたかったけど、終了後10分くらい粘ってもダメだったのでそんなに行けそうでもなかった。

A - Beginner

　最初提示されているのが表示レーティングかと思って入力例1の結果が全然違ってびっくりした。

　提出

B - Digits

　えー、難しくない？ でも割っていくだけで良かったのか。余計な実装をしてしまった。

　提出

C - Rally

　うぉー座標に関して全探索。どうでもいいけど最近配列の入力を

    vector<int64_t> X(N);
    for (int64_t& x : X) {
        cin >> x;
    }

と受け取るのがマイブーム。

　提出

D - Bouquet

　最初は脳死で事前計算するCombinationを持ってきて、いやでもダメじゃんとなって普通に計算する方のCombinationを計算。なんかいまいち綺麗に書ききれなかったな。

　提出

E - Roaming

　わりと早い段階で「最終的に空になる部屋が個」の場合の数を計算すれば解けそうという観点が出てきた。それで考えていくと、空になる部屋を選ぶnCiと、人が部屋のうちのどこかに属する{n - 1}_C_iが見えるので勝ち。後ろのやつを考えるとき僕もooo|||oooみたいな丸と仕切りの図を書いてしまうね。

　の場合コーナーケースだとか？ 全室埋まりが作れないというところかな？ 全然気づかないでやっていた。

　無駄なMODpowを削除しないまま提出してしまったのが悔やまれる。コードゴルフをやるつもりはないけどできるだけ無駄な記述はない状態で出したい。

　提出

F - Modularness

　クエリ問題になっている意味が何かあるのかなとちょっと疑ったけど、普通に各クエリをで解くことができそうと判断してそれに向かう。

　クエリがとして、足されるがで周期が回るので、の倍数でどこかループすることがわかる。そのループ周期はみたいな感じで書けるので、とで最小公倍数をどうのこうのすると周期がわかるんですね〜。

　あとは条件に合うものを数える方法を考える。初めにをで割った余りに加工しておくんだけど、のときはではなくにしておけば、失敗するときはなんかで割った商が増える感じになるのでそれを上手く計算すればできる。

　しかし入力例2とかで1ズレたり合ったりするので終わり。を1小さくするべきなのかそうじゃないのかがわからなかった。

　コンテスト終わってから気づいたけどこれループ周期とかを考える必要はないんですね。オーバーフローしないかとか心配になったんだけど、の各要素が最大で、全体が個で、それを個足しうるからで大丈夫なんだ。32行で綺麗に書けたので自分としてはこれで満足。でもfinalはC++の予約語？ にあるから変数名にするのはやめようねとAtCoderのコード表示を見ていて思った。

　提出

学習に必要な演算量の比較メモ

　Miacisの学習はAlphaZeroの学習に比べて少ない計算量で行っていることは確かだが、実時間としては多くかかっている。総演算量(単位時間あたりの演算量×学習時間)をちゃんと検討しておくべきだと思ったのでメモを残しておく。基本的にCPUは無視してGPUあるいはTPUの演算量で比較することにする。

AlphaZero

　どちらでも記述は共通しており、学習に使った計算資源は

• 第1世代TPU5000基(生成に使用)
• 第2世代TPU16基(学習に使用)

となる。

　第1世代TPUの性能については2017年に論文が出ている。

　これのTable2が比較の表となっていて、92 TOPS(TeraOps/second)という性能になっている。第1世代TPUは8bit演算にしか対応しておらず、浮動小数点演算ではないのでFLOPSという単位ではないが、意味合い的には同じものだと思われる。

　第2世代TPUは普通の浮動小数点演算ができるらしく、その速度は180 TFLOPSとある。

　これらを合わせると、1秒間に行われる演算量は

となる。学習時間はTable S3から将棋で12時間とあるので、

がAlphaZeroの総演算量になる。だいたいと考えれば良さそう。

Miacis

　このときの学習が2080ti×2枚のマシンを185時間44分4秒動かしたものになる。

　2080ti(FP16)が108 TFLOPS

　（これの根拠はなんなんだろう。ちゃんと出典が示せるものがどこかにあれば嬉しいが）

なので、Miacisの計算量は

となる。おおむね程度と見なせる。

　比を取るとMiacisはAlphaZeroの0.0072倍くらいの演算量で学習をしていることになる。138倍ほど高速化できていればAlphaZeroと同じ性能が出ているはずだが、まぁ当然そこまでの高速化はできていないだろう。左右反転含めていろいろ工夫を入れているつもりではあるけど、それでも5倍速くなっていれば良いほうかなという感覚なので、もっと学習時間を多くするしかないのかもしれない。

対抗形における性能

　前回、左右反転によるデータ拡張を導入し、初期局面からの対局では勝率にあまり差がないことがわかった。しかし以前の結果では、対抗形の学習は不十分であるという場合が見られた。左右反転を学習データに含めると、飛車が左にあるような局面がデータに含まれるようになることから、対抗形での性能が改善されている可能性は残されている。今回はそれの検証を行った。

　前回同様、四間飛車の基本図として「人気抜群の四間飛車を知る。まずは美濃囲いを作ってみよう！【はじめての戦法入門-第2回】｜将棋コラム｜日本将棋連盟」の第2図(下図)から対局を行った。

　先手後手各125局ずつ行った結果が次となる。

局面	先手での勝率	後手での勝率	合計勝率
初期局面	72.8% (R:171.0)	74.4% (R:185.3)	73.6%
対抗形	34.4% (R:-112.1)	51.2% (R:8.3)	42.8%

　後手(居飛車)ではかろうじて50%を超えたが、それでも初期局面からの勝率よりはかなり下がっており、Eloレートで見ると180近く下がっている。先手(振飛車)になると、局面自体の不利さもあるのかもしれないが、Eloレート換算で300近く落ちている。相変わらず対抗形は全体的に苦手ということが言えそうだ。

　棋譜を調べると、居飛車の際、Miacisが穴熊に囲うことはなかった。全体的に急戦調の将棋が多く、きちんと囲うというよりは金銀が盛り上がるような展開が多かった。船囲い、elmo囲い、雁木囲いのようなものはときどき見られたが、よくわからない囲いになることが多数だった。

　学習中の棋譜を見てみても、ほとんどが相掛かり系統の将棋で中住まいがほとんどであり、飛車が左にあるというだけでは振飛車的な戦い方は学習できないのではないかと考えられる。以前の記事でも言及したように、やはり「囲い」を学習することができていない印象がある。

おまけ

　ちょうど対抗形だったので次の対局を解析してみた。

　上がMiacis、下がYaneuraOu/Kristallweizen(4Thread)で、どちらも1手5秒。

　※Miacisは評価値を-1000 ~ 1000の値で出す。歩を単位にした値ではなく勝率に基づいた値であり、+1000して20で割ると先手から見た予測勝率となる。要するに20点が勝率1%ポイント分。例) +100点→先手から見た予測勝率55%

　グラフの概形が似ているのでこの対局に関してはMiacisの評価もそこまでおかしいわけではなさそうだ。お互いに玉が不安定で5筋付近をフラフラする将棋だったのであまり苦手な展開ではなかったかもしれない。相穴熊の評価などがおかしくなりそうな気がするが、それについての評価はまた別の機会に。

AlphaZeroの探索はすごく速いか？

ふとAlphaZeroの論文読み直して、TPU4個とはいえ将棋で40K NPS出てるってやばくないか？ って思いましたね。手元だとチャンネル半分、ブロック半分で10K出てない気がするんですが。2080tiとTPUってそんなに差があるものなんですかね

— t (@tokumini_ss) 2020年2月18日

　あんまり調べず適当なことを言ってしまったのでちゃんと調べた。結論からすると、今のMiacisの実装よりは速そうだがそこまで非現実的な(おかしいと思えるほど)速いわけではなさそうだった。

背景

　AlphaZeroの論文の5ページ目あたりに検証対局時の探索速度の情報が載っている。

AlphaZero searches just 80 thousand positions per second in chess and 40 thousand in shogi, compared to 70 million for Stockfish and 35 million for Elmo.

であり、これは4基のTPUを用いた状況での速度とのことである。おおむねTPUの数とNPSが線形の関係にあるとすると、TPU1基では10K NPS出ると考えられる。これと比較して現在のMiacisの探索速度がどの程度であるか検証を行った。

前提

　現状、Miacisは残差ブロック中におけるチャンネル数が128(AlphaZeroは256)、残差ブロックの数が10個(AlphaZeroは20個)という比較的小さいネットワークを使用している。

　また探索においてはGPUが一度の計算で複数の局面を計算した方が並列計算ができて得であるため、バッチ処理を行っている。基本的にはねね将棋、dlshogiの手法

を真似したものであり、CPUでモンテカルロ木探索の選択ステップを回行い、GPUで評価したい局面をキューに溜めてから、一括で個の局面についてGPUで計算を行う。

　このCPUスレッドは複数用意することができる。「CPUでの評価要求を溜める時間 << GPUで計算する時間」である場合、CPUスレッドを1スレッドから2スレッドにすると効率的になるが、上の記事でも言及されているように2スレッドから3スレッドにしても効率的にはならない。

実験

　Miacisを用いて初期局面における探索速度を測定した。以下、使用したマシンはRTX 2080tiが1枚搭載されているものである。

学習済みパラメータ(10ブロック、128ch)

　まずは現在手元にある最も性能の高い学習済みパラメータで探索を行った場合にどの程度の探索速度が出るのかを確認した。

　バッチサイズを大きくすると10K NPSは超える結果となった。しかしバッチサイズ、スレッド数を増やすことによるNPSの増加が性能向上に繋がっているかどうかは自明ではない。これらを増やしたときには探索が幅広くなっているだけの可能性もあり、PV上の評価要求を投げた局面がなかなか計算されなければむしろ性能低下にも繋がりうる。このあたりは実際に対局させてみないとなんとも言い難いところであり、簡単な検証ではバッチサイズ32、スレッド数2が今のところ一番高い性能となっている。

　注意すべき点としては、バッチサイズ16までは2スレッド→3スレッドでNPSが伸びることはないが、それより大きいバッチサイズにするとスレッド数を増やした方がNPSが増えている。これはつまり「CPUでの評価要求を溜める時間 << GPUで計算する時間」が成り立っていないことを示している(実際にGPU使用率を見ていても40%程度でとどまっている)。どうせGPUが律速なのでCPU部分の高速化は気にしなくてもよいだろうと思っていたが、高速化で性能が伸びる余地があるのかもしれない。

ランダムパラメータ(10ブロック、128ch)

　AlphaZeroと同様の20ブロック、256chで検証を行いたいが、そのネットワークでの学習済みパラメータはないのでランダムパラメータでの探索速度を検証することになる。学習済みパラメータとランダムパラメータでは探索速度に差が出そうに思えたため、まず今のネットワークの大きさでランダム初期化したパラメータについても探索速度の検証を行った。

　直接的な比較ではないためわかりづらいかもしれないが、学習済みパラメータと比べて特にバッチサイズを大きくした際にNPSが2倍程度まで大きくなっている。これはランダムパラメータだと方策、価値がほぼ一様になるため選択ステップ選ばれる局面がバラけやすく、並列化が効率よく行われるためだと思われる。

ランダムパラメータ(20ブロック、256ch)

　AlphaZeroと同じネットワークサイズで測定を行った。

　バッチサイズを256あたりまで上げてもまだNPSが伸びる傾向があり、8K NPSあたりは目指せそうである。

　ネットワークをこれだけのサイズにすると「CPUでの評価要求を溜める時間 << GPUで計算する時間」が成り立ち、スレッド数を3以上にしても効果がないことがわかった。

全体の結果

　スレッド数2について上の3つの結果を一枚のグラフにまとめると

　バッチサイズを大きくすると学習済みパラメータであるかランダムパラメータであるかの差が大きくなるが、これはMiacisの実装上の問題かもしれない。

TPUとGPUの性能差も考慮して結論

　対局で使われたTPUが第1世代のものなのか第2世代のものなのかはわからないが、第2世代のものだろうと仮定して話を進める。第2世代TPUは一基で180 TFLOPSとのことである。

　（TPUのチップ一つが45 TFLOPSであり、これを4つまとめたものをTPU一基と見なすようだ。論文での「4TPUs」という言及はこのまとまったTPUを4つ使うのだと解釈した。）

　RTX 2080tiはFP16が108 TFLOPSらしい。

　つまりTPUは2080tiの5/3倍の速度が出ると考えられる。

　先の結果では2080tiでAlphaZeroサイズのネットワークを使うとバッチサイズ256, スレッド数2で7192 NPSであり、学習済みだと半分なる、TPUを使うとして5/3倍になることから換算するとだいたいほぼ6000 NPSとなる。

　AlphaZeroの4TPUで40K NPS(TPU一基あたり10K NPS)というのは、今のMiacisの実装よりも速そうだが、そこまで異様なほど速いというわけでもなさそうだ。

左右反転によるデータ拡張

要約

　左右反転によるデータ拡張を行うことで性能を落とさず学習速度を2倍にできた。

背景

　囲碁では左右反転や回転などを利用してデータ拡張することができ、本家AlphaZeroでも

の下の方にあるSupplementary Materialsに掲載されているFigure S1

において、同じ学習時間で比較したときにはこのようなデータ拡張が有効であると示されている。

　将棋では回転は利用できないので左右対称だけの2倍にしかならず、また飛車角の初期位置自体は左右非対称なので左右反転したデータが良いデータかはわからないが、ものは試しということで実装・実験を行った。

実験

　いつも通りのAlphaZero式強化学習を、左右反転によるデータ拡張あり/なしで比較した。データ拡張を入れる場合、対局を行ってリプレイバッファにデータを格納する際、盤面及び指し手の教師ラベルを左右反転させたものを同時に格納する(Valueの教師ラベルは同じものを使う)。

実験結果

• validation損失

左:Policy損失　右:Value損失

　Policy損失については左右反転によるデータ拡張を行った方が小さい値となった。Value損失はほぼ変わらなかった。

• 対局結果

　最後のステップでやや伸びているが、基本的に同程度の性能だった。

　データ拡張により生成速度はほぼ2倍になっており、現在Miacisでは生成速度に応じて自動的に学習時間を調整しているため学習時間が半分で済むようになった。上で示したグラフを、横軸に学習時間を取って描画し直すと次のようになる。

左:Policy損失　右:Value損失

　2080ti×2のマシンで学習全体は約186時間 ≒ 8日程度となった。