将棋AIの進捗 その22(探索と評価の直列化)

前回、ねね将棋が世界コンピュータ将棋選手権で高い探索速度を出していたので、バリューの計算中に末端ノードから新しく探索を行う方法で簡易な実装をして実験を行った。
しかし、末端ノードから新しく探索を始めると、新しく始めた探索のバリューの計算されるまで、元の探索のバックアップが行われないため、正しくゲーム木が成長しない状態となっていた。

そこで、ねね将棋と同じように経路を保存して、バッチで評価した後にバックアップを行う実装に変更して検証をやり直した。
ねね将棋では、シングルスレッドで探索を行い、GPUの計算をマルチプロセスで行う実装になっているが、GPUの計算中も探索を行いたいため、以下のような方式にした。

探索とGPU計算は同一のスレッドで直列に実行し、GPU計算の完了のためにスレッドの同期を不要にした。探索はバッチサイズ分実行し、GPU計算はバッチ処理を行う。
この探索スレッドを2つ並列で実行し、GPUの計算は競合するため排他制御を行う。
そうすることで、一方のスレッドでGPUの計算中にも探索を行うことができる。

GPUが複数枚ある場合は、GPUごとに2つの探索スレッドを割り当てる。

探索速度比較

GPU2枚のPCで探索速度の比較を行った。

	スレッド数	探索速度(シミュレーション/秒)
変更前	168×2	12457
変更後	2×2(バッチサイズ192)	14158

※初期局面で10万回シミュレーション

探索速度が向上することが確かめられた。

探索の深さ

前回の記事で、探索速度を上げるとモンテカルロ木探索の特性としてゲーム木が幅方向に広がるため、強さに結びつかないという考察を行った。

幅方向に広がるのを抑えるため、バッチサイズ分探索を繰り返す際、同じ経路を探索した場合は、その探索は破棄して、バッチサイズを減らす実装にした。
そうすることで、バリューの計算を待つ処理を疑似的に再現できる。

今回の実装方法で、探索の深さを確認した。

	探索の深さ
変更前	36
変更後	35

今回の実装では、探索の深さはバリューを待つ実装と同等になった。

強さの確認

GPSfishと対局して、強さの確認を行った。

1手3秒50回対局で勝率は72%となり、変更前とほぼ同じ勝率となった。

2スレッドの効果

GPUあたり2スレッドで探索を行うことの効果を確認した。

スレッド数	探索速度(シミュレーション/秒)
1	13154
2	14158
3	14057

スレッド数を2にすると1の場合よりも探索速度が向上している。3にしてもGPU計算が競合するため意味がない。

Linuxでの速度

以前の実装はスレッドの同期を行うため、Linuxで性能がでなかった。
今回の実装はGPUの計算を待つ処理を直列で実装しているため、スレッドの同期が不要となっている。
そのため、Linuxでも探索速度が上がることが期待できる。
そこで、探索速度をLinuxで測定を行った。

	スレッド数	探索速度(シミュレーション/秒)
変更前	168×2	2258
変更後	2×2(バッチサイズ192)	11388

探索速度が5倍に向上した。
しかし、Windowsの8割程度なので、まだ改善の余地はありそうである。

スケーラビリティ

GPUの枚数をさらに増やした場合に、探索速度が向上するかAWSの4GPUのインスタンス(p3.8xlarge)で確認を行った。

GPU枚数	探索速度(シミュレーション/秒)	探索の深さ	探索時間(秒)
1	9416	30	9.512
2	18529	35	4.533
3	27475	35	2.632
4	35701	33	2

※バッチサイズ192
※初期局面で10万回シミュレーション

探索速度がほぼ線形に伸びている。
10万回シミュレーションで測定しているため、探索の深さは深くなっていないが、同じ時間の探索ではより多くのシミュレーションが行えるため、深さも深くできる可能性がある。

そこでGPU枚数4枚でシミュレーション回数を40万回にして測定を行った。

シミュレーション回数	探索速度(シミュレーション/秒)	探索の深さ	探索時間(秒)
10万	35701	33	2
40万	36298	37	9.077

探索時間は、GPU1枚のときと同じだが、探索の深さはより深く探索できている。
探索速度の向上が、強さに結びつくことが予想できる。

まとめ

探索とGPU計算の直列化によって、探索速度を改善できることが確認できた。
自己対局による強化学習の実行速度も改善できそうなので、変更を行う予定である。
実装方法を教えていただいた、ねね将棋の日高さんに感謝いたします。

将棋AIの進捗 その21(探索の深さ)

dlshogiでは、MCTSの末端ノードでバリューを計算し、その値をバックアップしているが、GPUでバリューの計算が終わるまで待機している。
バリューの計算が終わる前に次の探索を始めると、ノードにバーチャルロスのみが反映された状態で、勝敗の推定値が反映されておらず、その状態で探索すると精度が落ちるためである。
そのため、GPUを増やしても探索速度（シミュレーション/秒）が上げられない点が課題となっている。

第28回世界コンピュータ将棋選手権で、ねね将棋が、CPUを1スレッドにして、バリューの計算中もシミュレーションを繰り返すことで、高い探索速度を達成していた。
select766.hatenablog.com
キューに追加する際に、経路も保存する実装になっており、実装は複雑になっている。

dlshogiはスタックの巻き戻しの際にバックアップしているので、同じような実装を試すには大幅な変更になるので、バリューの計算中に末端ノードから新しく探索を行うことで、経路の保存はスタックに残すことで実装してみた。
デフォルトのスタックサイズではオーバーフローするため、リンカオプションでスタックサイズを十分に大きくした。
同じノードに到達した際にポリシーの計算を待つ処理はそのままとした。
※2018/5/9 追記
この実装方法には問題があり、下記の検証はあまり意味のない結果でしたので、後日記事を書き直します。

UctSearch.cpp

		// valueの計算中は、別の探索を行う
		while (uct_node[child_index].evaled == 0) {
			// 探索回数を1回増やす
			atomic_fetch_add(&po_info.count, 1);
			// 盤面のコピー
			unique_ptr<Position> pos(new Position(*pos_root));
			// 1回プレイアウトする
			UctSearch(pos.get(), current_root, 0);
			// 探索を打ち切るか確認
			bool interruption = InterruptionCheck();
			// ハッシュに余裕があるか確認
			bool enough_size = uct_hash->CheckRemainingHashSize();
			if (!pondering && GetSpendTime(begin_time) > time_limit) break;
			if (!(po_info.count < po_info.halt && !interruption && enough_size)) break;
		}

測定結果

GPU2枚のPCで探索速度を比較した結果、以下の通りとなった。

探索速度比較

※初期局面を1秒間探索
※スレッド数は探索速度が最大になるように調整

	スレッド数	探索速度(シミュレーション/秒)
バリューを待つ実装	144×2	10121
バリューを待たない実装	8×2	15239

バリューを待たない実装の方が、探索速度が向上することが確かめられた。

探索速度が上がったことで、強くなっているか確認するために、GPSfishと対局させてみた。
結果、0勝10敗と、明らかに弱くなってしまった。

考察

バリューの計算中に探索を行うと、探索が幅方向に広がるため、それが原因で探索の精度が落ちていると考えた。
そのことを確認するために、探索の深さを調べた。
探索終了後に、ゲーム木を訪問回数が最大のノードをたどったときの探索の深さは以下のようになっていた。

	探索の深さ
バリューを待つ実装	24
バリューを待たない実装	10

仮説の通り、バリューの計算を待たない場合、探索の深さが浅くなっていた。
次に、探索の幅が広がらないように、PUCTの定数を大きくして、再度測定してみた。

PUCTの定数	探索の深さ	探索速度(シミュレーション/秒)
1.0	10	15239
2.0	17	12760
3.0	19	11087
4.0	21	10068
5.0	23	8847

PUCTの定数を増やすと深さが大きくなることが確かめられた。しかし、反比例して探索速度が落ちている。
バリューを待つ実装の方が、同じ探索の深さでは探索速度が高くなっている。

単純に探索速度を上げるだけでは、強さには結びつかないため、幅と深さと速度のバランスをとることが必要そうだ。
ねね将棋がブログで解説を書かれる予定ということなので、この辺の分析もしてもらえると嬉しい。

dlshogiは、バランスは悪くないようにも思えるが、現在の実装ではLinuxで性能がでない課題があるので、どうするか継続検討したい。

第28回世界コンピュータ将棋選手権 出場結果

第28回世界コンピュータ将棋選手権に参加してきました。

dlshogiは、一次予選に7位で通過しましたが、二次予選では1勝8敗で24チーム中最下位という結果でした。

dlshogiは、今回注目されていたCrazy Shogiと同じくモンテカルロ木探索とディープラーニングを組み合わせたソフトです。
今回ディープラーニングを使用したチームは複数チームありましたが、一次予選通過できたのはdlshogiだけでした。
dlshogiの学習方法、探索の実装がある程度通用することが示せてよかったと思います。

大会では、参加者の方と情報交換できて、新たに試したいこともでてきました。
YSSの山下さんとPonanza Chainerの大渡さんに技術的な話を聞くことができて参加した甲斐があった思います。
ねね将棋とbroadenもモンテカルロ木探索とディープラーニングを試されており、有益な情報交換をすることができました。

来年は、Crazy Shogiも優勝を目指してくるということなので、こちらも負けないように頑張るつもりです。

dlshogi（wcsc28版）のビルド済みファイル公開

dlshogiの第28回世界コンピュータ将棋選手権バージョンのビルド済みファイルを公開しました。

第5回将棋電王トーナメントバージョンは、Chainerの環境構築が必要でしたが、USIエンジンの実行のみであれば不要になっています。
CUDA、cuDNNはライセンス上の問題が起きないように同梱していませんので、別途インストールが必要です。下記のページの説明を参照してください。

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

USIエンジンをAWSのWindowsインスタンスで実行する

以前にAWSのWindowsサーバで、GPUを増やしても探索速度を上げられなかったということを書きましたが、後からバグがあって1個のGPUしか使っていなかったがわかりました。
バグを修正したバージョンで、p3.8xlargeで4GPUを使うと自宅のGPU2枚のPCより少し探索速度を上げることができました。
p3.16xlargeだと、なぜか探索速度が落ちてしまいました。
ということで世界コンピュータ選手権はp3.8xlargeを使うことにします。

探索速度の比較

ハードスペック	スレッド数	シミュレーション/秒
Corei9 10コア+GPU2枚(TitanV+1080Ti)	255+255	10779
Xeon 32コア+GPU4枚(Tesla V100)	168+168+144+96	12224

スペックは2倍以上ですが、探索速度の向上は13%です。
スレッド数は探索速度が最大になるように調整した結果です。

AWSでUSIエンジンを実行する方法

dlshogiはLinuxでも実行できるようにしていますが、探索速度はWindowsの方が高いので、AWSのOSはWindowsにする予定です。

USIエンジンをAWSで実行するには、SSHでリモートで実行して標準入出力でやり取りすれば可能です。
将棋所は、実行ファイルに引数を渡すことができませんが、バッチファイルにSSHコマンド記述して、バッチファイルを登録すれば問題ありません。

WindowsのAMIは、デフォルトではSSHで接続できないため、自分でSSHサーバを構築する必要があります。
WidnowsでのSSHサーバの構築方法は、別の記事にしました。
AWSのWindows AMIにsshで接続する - TadaoYamaokaの開発日記

上記の記事を参考に、AWSのWindowsサーバにSSHサーバを構築して、公開鍵で認証する設定を行います。
将棋所を実行するクライアントからsshコマンドで接続できることが確認できたら、以下のようなバッチファイルを作成します。

@echo off
C:\OpenSSH-Win64\ssh xxxx@xxxx.us-west-2.compute.amazonaws.com C:\Users\xxxx\Documents\dlshogi\usi

※ユーザ名とホスト名とUSIエンジンのパスは書き換えてください。

これを将棋所に登録します。
将棋所のエンジン選択は、デフォルトで拡張子が「.exe」のファイルしか表示されませんが、ファイル名に「*」を入力してEnterキーを押せば、バッチファイルも表示されるので、登録できます。

これで、ローカルで動くUSIエンジンと同様にエンジン設定と実行が可能です。
当然ですが、エンジン設定に設定するファイルパスはサーバ上でのパスです。

以上です。

アンサンブル対応

使えるGPU枚数が増えたので、GPUごとに異なるモデルをロードできるようにしました。
アンサンブルにより精度が向上することを狙っていますが、まだ十分に検証できていません。
試しに自己対局した強化学習のモデルを1GPUに割り当ててみましたが、弱くなりました。
今回は自己対局した強化学習のモデルは使用しないで、教師ありで学習した3種類のモデルを使用する予定です。

AWSのWindows AMIにsshで接続する

AWSのWindows AMIで作成したインスタンスにsshで接続する方法についてです。

使用したAMIは、「Windows_Server-2016-English-Deep-Learning-2018.03.24 (ami-4f168837)」です。

WindowsでSSHサーバを構築する方法はいくつかありますが、マイクロソフトがオープンソースで公開している「Win32 port of OpenSSH」を使用しました。
GitHub - PowerShell/Win32-OpenSSH: Win32 port of OpenSSH

手順は、以下の記事を参考にしました。
ASCII.jp：マイクロソフト版OpenSSHをサーバーとして動作させる
※記事にはsshdのパスに誤りがあるので要注意です。パスの誤りに気づかず数時間無駄にしてしまいました・・・

OpenSSHのダウンロード

Releases · PowerShell/Win32-OpenSSH · GitHub
から、releaseの最新版のOpenSSH-Win64.zipをダウンロードして、「C:\」に解凍します。
※現時点で最新のv0.0.24.0を使用しました。
以下、「C:\OpenSSH-Win64」に解凍した前提とします。

sshdサーバーをサービスとしてインストール

PowerShellを管理者モードで起動し、

cd C:\OpenSSH-Win64
powershell -ExecutionPolicy Bypass -File install-sshd.ps1

sshd用にファイアウオール通過のルールを設定

New-NetFirewallRule -Protocol TCP -LocalPort 22 -Direction Inbound -Action Allow -DisplayName OpenSSH -Program C:\OpenSSH-Win64\sshd.exe

※参考にした記事では、「sshed.exe」になっていましたが誤りです。

ホストの認証キーを作る

.\ssh-keygen.exe -A

sshdサービスをPCの起動時に自動的に実行

Set-Service sshd -StartupType Automatic

sshd_configファイルを編集

notepad sshd_config

でsshd_configをメモ帳で開いて、

#PubkeyAuthentication yes

の行頭の「#」を削除して、保存します。

ユーザーのホームフォルダ以下に.sshフォルダを作って公開鍵ファイルを置く

接続するクライアントでキーペアを作成

接続するクライアント側にもOpenSSHをダウンロードして解凍し、PowerShellを管理者モードで起動して、以下のコマンドを実行します。

cd C:\OpenSSH-Win64
.\ssh-keygen -t rsa

ユーザフォルダ（C:\Users\xxxx\.ssh\）に、「id_rsa」と「id_rsa.pub」が作成されます。

サーバ側に公開鍵を置く

クライアントで作成した「id_rsa.pub」をサーバ側の「C:\Users\xxxx\.ssh\」にコピーします。
「.ssh」はエクスプローラでは作成できないので、コマンドプロンプトで「mkdir」で事前に作成します。

「id_rsa.pub」を「authorized_keys」にリネームします。
別のクライアントの公開鍵をする場合は、「authorized_keys」に「id_rsa.pub」の内容を追記します。

authorized_keysファイルのアクセス権で変更

C:\OpenSSH-Win64\FixHostFilePermissions.ps1 -Confirm:$false

sshdサービスを再起動

restart-service sshd

接続テスト

クライアントから接続できるかテストします。

cd C:\OpenSSH-Win64
ssh <サーバのユーザ名>@<サーバのIPアドレスまたはFQDN>

以上です。

将棋AIの進捗 その20(自己対局による強化学習)

自己対局による強化学習を続けています。
現在、1サイクルあたり500万局を自己対局で生成するサイクルを17サイクル実行したところです。
教師ありでelmoで深さ8で生成した4.9億局面を事前学習したモデルを初期モデルとしています。
初期モデルは、収束前のLesserkaiには勝つがGPSfishには1度も勝てない程度のモデルです。

数サイクル回した時点では、初期モデルに対して弱くなっていましたが、17サイクル回したところで、やっと初期モデルに対して1手3秒の50回の対局で有意水準5%で強くなったことが確かめられました。

しかし、GPSFishには1度も勝てていません。
1サイクルの実行にGPU3枚使って、3日かかっているので、レーティングを上げるのは気の長い作業になりそうです。

AlphaZeroの論文では、elmoのレーティングに達するのに110k stepsとなっています。

私のリソースでは、1 stepの実行に3日かかるので、1k stepsには333日、110k stepsには100年かかるため、AlphaZeroと同じレーティングの上昇傾向だと実現性がありません。
AlphaZeroと比較すると、

• 特徴量に利き数と王手を使っていること
• モデルサイズが小さいこと
• 初期局面集を使っていること
• 方策ネットワークの学習にREINFORCE Algorithmを使っていること
• 価値ネットワークの学習にブートストラップ法を使っていること

という違いがあるので、収束が速くなっていればよいのですが、まだわかりません。

もう少し自分で検証して、間違いなくレーティングが上昇することが確かめられたらleela zeroのようにコミュニティの力を借りることを検討したいと思っています。

世界コンピュータ選手権は、今のままでは弱すぎるので、教師ありで学習したモデルを主に使うことになりそうです。
マルチGPUの1枚を強化学習したモデルにしてアンサンブルにすることも考えています。