TadaoYamaokaの開発日記

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

詰み探索のループ対策

やねうら王から移植した詰み探索では、以下の後手3手詰めの局面を不詰みと判定してしまう。
position sfen +B+R5n1/5gk2/p1pps1gp1/4ppnsK/6pP1/1PPSP3L/PR1P1PP2/6S2/L2G1G3 w B2N2LP2p 1
f:id:TadaoYamaoka:20180521223401p:plain

原因を調べたところ、探索にループが発生し、深さが4で始めと同じ局面になり、pnとdnが誤ってカウントされてしまうことで、後手の2五銀のループが検出できずに最大深さまでループして探索が打ち切られてその結果が置換表に登録されてしまっていた。
やねうら王の詰み探索では、無限ループの対策としてThreshold Controlling Algorithm (TCA)が実装されているが、置換表がループ後に現れた局面を同一と判定してしまっているため誤動作していた。
対策として、探索の深さが異なる局面は別の局面として置換表に登録することにした。
深さが同じでも別の経路から同じ局面に至る場合があるが、それはまた別の対策が必要になる。

対策を入れた後に、前回と同様の15手詰めの局面で速度を比較した。

対策前 176ms
対策後 380ms

2.15倍遅くなってしまったが、対策前はたまたま正しく動いていたものと思われる。

詰み探索で優越関係の利用

やねうら王から移植した詰み探索の速度を上げるために優越関係の実装を行った。

局面Aが局面Bを優越するとは、AとBの盤上の駒の配置が同一で持駒のみが異なっており、Bの持駒がAの持駒の部分集合になっている場合を示す。
参考:
詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について

言い換えると、盤面が同じで持駒が多い局面のことを指す。
詰み探索では、ある局面と盤面が同じで持駒がより少ない局面で詰みが証明できるならば、その局面も詰みであることを利用すると、探索ノード数を減らすことができる。

置換表

優越関係を利用するには、盤面が同じ局面を効率的に置換表から検索できる必要があるため、通常の探索では置換表のキーは、盤面と持駒を合わせたハッシュ値になるが、優越関係を利用する場合、置換表のキーは、盤面のみのハッシュ値とする。
局面を区別するため、持駒も置換表のエントリに保持しておく。

持駒の表現

持駒は、各駒の枚数に必要なビット数を割り当て、32bitに詰め込む。
AperyではHand型で実装されているので、そのまま利用した。
Aperyには優越関係を調べるためのisEqualOrSuperiorメソッドも用意されている。

置換表のエントリ数

ハッシュキーを盤面のみとするため、持駒のみが異なる複数局面のハッシューが同一となる。
そのため、同一のハッシュキーに対して十分なエントリ数を用意しておく必要がある。
256エントリあれば、ほとんどの場合でエントリが不足することはない。
エントリが不足したらどれかのエントリを上書きすることになる。
(情報量が少ないエントリを上書きするのがよいが実装していない。)

優越関係の利用

詰み探索中に置換表を検索する際に、優越関係を満たす局面に詰み(証明数が0)があれば、そのエントリを返すようにする。
ここで、ORノードとANDノードで優越関係が逆になるので注意する。
ORノードでは、持駒の少ない局面を調べるが、ANDノードでは、相手側の持駒になるので相手の持駒が多くても詰むか調べる必要がある。

速度比較

以下の15手詰めの局面で速度を比較した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

優越関係利用なし 1625ms
優越関係利用あり 176ms

9.23倍高速になった。

まとめ

優越関係の実装は、ハッシュキーの仕組みを変更するだけで実装することができ実装は難しくないが、効果が大きい。
優越関係を利用することで無駄合いの判定などの特別な処理を行うことなく、無駄合いの局面の探索を省略できる。

なお、優越関係を満たす局面の不詰みも利用することが可能だが、かえって遅くなる場合があったので利用しないことにした。

優越関係の利用は、詰みの局面のみではなく、優越関係を満たす局面のpnの値も利用できる。
そちらについても実装する予定である。

優越関係を実装したソースコードはこちら。
github.com

やねうら王の詰み探索をAperyに移植

Aperyの初期局面集には、詰みの局面を数%含んでいるので、これを除きたい。
詰みの局面で自己対局を行い教師局面を生成すると終盤局面に偏りが生じると考えるためである。
なお、初期局面集に詰みの局面を含めることがマイナスか判断するには実験が必要だが、確かめてはいない。

詰みの局面を除くために初期局面集の各局面に対して詰み探索が必要になる。
以前にdf-pnを実装したことがあるので、それを使って試そうと思ったが、証明ノードが多い不詰みの局面でうまく動かなかったためバグ取りをするより、やねうら王の詰み探索を移植することにした。

やねうら王の詰み探索をAperyに移植

やねうら王のmate-engineソースコードをほぼそのまま流用して、Aperyに移植を行った。
ElmoTeacherDecoder/dfpn.cpp at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub

基本的にPositionクラスのメソッド名を変えるだけで対応できたが、やねうら王にあってAperyにない機能については、それらも移植した。
王手の生成については、以前に移植したことがあるのでそれを利用した。
また、Positionから1手指した後のハッシュキーを取得するメソッドがなかったので、AperyのPositionクラスに追加した。
ElmoTeacherDecoder/position.cpp at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub

移植した詰み探索を使って、以前に試した15手詰めの局面の詰み探索を行い探索速度を調査した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

結果、1625msと以前に自作したdf-pnと同じくらいの速度だった。
それほど早くないが、バグなく安定して使えるのでこれを使用することにする。

探索速度

20手以上の長手数の詰みや、証明ノード数が多い不詰みの局面だと非常に探索に時間がかかるので、探索の深さと探索局面数に制限を設けて時間がかかる局面は不詰みとして扱うことにした。
探索の深さ=20
探索局面上限=1048576

これで、シングルプロセスで平均33局面/秒の速度で探索できるようになった。

分割処理

詰み探索の置換表はStockfish風になっているが参照、更新する際に特別な考慮をしないとlock lessでは使用できなそうである。
Stockfishがグローバルな置換表をマルチスレッドで使用できる仕組みがどうなっているかはあまり理解できていない。
詰み探索の置換表はマルチスレッドでは使えなそうである。
そこで、初期局面集を分割してマルチプロセスで処理するようにした。

10コアのPCで初期局面集を10分割して、各プロセスで約500万局面ずつ探索して、1.75日くらいで完了する見込みである。
副産物で大量の詰み局面集ができあがるので、何かの用途があるかもしれない。

なお、自玉が王手の場合は、ANDノードから探索を行い詰みの場合はそれも除くようにした。

モンテカルロ木探索での利用

dlshogiではモンテカルロ木探索の末端ノードで7手の詰み探索を行っているが、7手であればAND/OR木を全て探索しても早いので、df-pnは使っていない。
df-pnを使えばもう少し探索手数を増やせるので、置き換えることも検討したい。
置換表がマルチスレッドに対応していないので、スレッドごとに置換表を分けることになると思う(もしくはロックを実装する)。
以前は探索スレッド数が多いこともあったdf-pnはあきらめていたが、探索と評価の直列化をしたことでスレッドごとに置換表を割り当てても問題なさそうである。
スレッドごとに置換表を分ける場合、サイズはあまり大きくできないので、探索ノード数を制限することになりそうである。

やねうら王教師局面からAperyの初期局面集を作成

やねうらおさんが公開してくれていたdepth10で作った110億局面の教師から、Apery用の初期局面集を作成するツールを作成しました。

教師局面に記録されている評価値の絶対値を閾値にして、Aperyの初期局面集形式(hcp)を出力します。

コマンド例)

psv_to_hcp.exe shuffled_sfen1.bin shuffled_sfen1.hcp 500

先日記事にしたAperyでやねうら王のPackedSfenValueを読み込むコードの応用です。

需要があるかわかりませんが、初期局面集のバリエーションを増やしたい場合にご利用ください。
github.com

改造したPositionクラスの本体はこちら
ElmoTeacherDecoder/hcp_decoder at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub

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

前回、対局プログラムを探索と評価の直列化することによって高速化を行ったが、自己対局プログラムについても探索と評価の直列化を行った。

以前は、探索を複数スレッドで行って、ニューラルネットワークを計算をキューにためて専用のスレッドでバッチ処理を行っていたが、スレッドの同期がボトルネックになっていた。
2枚のGPUのPCで、GPUごとに180スレッドと140スレッドという大量のスレッドで探索を行い、ニューラルネットワークの計算完了を探索スレッドでビジーウェイトで待機していた。
ニューラルネットワークの計算が完了すると同時に、大量スレッドが一斉に動き始めるため、CPUを奪い合う状況が発生しており、性能低下を起こしていた。
Windowsではそれなりの速度で動いていたが、LinuxではWindowsの3割程度の性能になっていた。

このようなマルチスレッドの問題は、コンピュータサイエンスではThundering herd problem(大群の問題)と呼ばれている。「Optimized C++」にも記述されていた。

この問題を避けるため、一つのスレッドで探索をバッチサイズ分繰り返した後、評価(ニューラルネットワークの計算)を同一のスレッドでバッチ処理するように変更を行った。ニューラルネットワークの計算中にも探索を行えるように、2つのスレッドで探索を行うようにした。

自己対局プログラムでは、バッチサイズ分の対局を並行で進行し、各対局のシミュレーションを1回実行し、各対局の評価要求を1つずつキューにためてバッチで処理するようにした。

局面生成速度比較

変更前後で局面の生成速度は、以下のようになった。
GPUの2枚(Titan V+1080Ti)のPCで測定した。スレッド数、バッチサイズは生成速度が最大になるように調整している。

スレッド数 生成速度(node/sec)
変更前 180+140 11.26+8.53=19.79
変更後 2+2(バッチサイズ:192+176) 14.17+11.35=25.52

生成速度が変更前から1.29倍になった。

Linuxでの生成速度

変更前はLinuxで性能がでなかったが、変更後の速度を測定した。

スレッド数 生成速度(node/sec)
変更後 2+2(バッチサイズ:208+176) 12.10+9.55=21.65

Windowsの85%程だが変更前より高速になった。


自己対局による教師局面の生成速度が上がったことで、変更前は500万局面の生成と学習に3日かかっていたが、2日半程度に短縮できそうである。
Linuxでの生成速度も上がったので、価格が安いAWS(もしくはGCP)のLinuxGPUインスタンスの利用も検討したい。

使用ライブラリをAperyに変更

dlshogiは今までAperyから派生したelmo_for_learnのソースを使用していましたが、最新のAperyで修正されたバグの修正を取り込むため使用ライブラリをAperyに変更しました。
入玉宣言に修正が入っていたので、そこだけ取り込むつもりでしたが、ついでにすべてのソースを最新にしました。

また、今までLEARNを有効にしてビルドしていたので、枝狩りが少ない状態になっており長手数の詰みが見つけられない局面があったため、対局用ではLEARNをオフにしてビルドすることにしました。

Aperyでやねうら王のPackedSfenValueを読み込む

世界コンピュータ将棋選手権のアピール文章にも書いたが、マルチGPUで動かす場合、GPUごとに異なるモデルをロードすることで、モデルごとに誤る確率が独立とすると複数モデルが同時に誤る確率は、単一のモデルを使用する場合より低くなるため精度の向上が期待できる。
世界コンピュータ将棋選手権では、教師ありで学習した3つのモデルを使用したが、どれもelmoで生成したデータを使用しており、学習局面数の差しかなくあまり効果がなかったかもしれない。
elmoとは違う系統の教師局面で学習したモデルを使えば、モデルごとの独立性が高まる。

3駒関係の評価関数でも、Aperyとやねうら王の評価関数で重み付き平均をとるということが行われており、効果を上げている。

そこで、やねうら王で生成した教師局面からもモデルの学習を行えるようにしたい。
計算リソースが足りないため、自己対局による強化学習はゼロからではなく事前学習したモデルから開始する予定だが、その際にも2つの系統のモデルうまく使えないかと考えている。

dlshogiはベースにAperyから派生したelmo_for_learnを使用しているので、やねうら王で生成した教師局面の読み込みには対応していない。
そこで、一部ソースを追加してやねうら王で生成した教師局面を読み込めるようにした。

実装とテスト方法について、メモを残しておく。

elmoの教師局面

elmoで使用されている教師局面は、HuffmanCodedPosAndEval(hcpe)という形式で保存されている。
hcpeは、局面をハフマン符号で圧縮したHuffmanCodedPos(hcp)と評価値、指し手、勝敗から構成されている。
hcpは、手番と王の座標、盤面の各座標の駒と持ち駒から構成されている。
各座標の駒と持ち駒は、ハフマン符号で圧縮されて1~8bitで表現されている。

やねうら王の教師局面

やねうら王の教師局面は、PackedSfenValueという形式で保存されている。
PackedSfenValueは、局面をハフマン符号で圧縮したPackedSfenと評価値、指し手、手数、勝敗から構成されている。
PackedSfenは、hcpと同じ情報から構成されているが、ハフマン符号がelmo(Apery)とは異なる。

つまり、ハフマン符号を変更すれば、ほぼ同じコードでPackedSfenValueを読み込むことができる。

elmo(Apery)のハフマン符号

elmo(Apery)では、ハフマン符号は、position.cppで以下のように定義されている。

const HuffmanCode HuffmanCodedPos::boardCodeTable[PieceNone] = {
    {Binary<         0>::value, 1}, // Empty
    {Binary<         1>::value, 4}, // BPawn
    {Binary<        11>::value, 6}, // BLance
    {Binary<       111>::value, 6}, // BKnight
    {Binary<      1011>::value, 6}, // BSilver
    {Binary<     11111>::value, 8}, // BBishop
    {Binary<    111111>::value, 8}, // BRook
    {Binary<      1111>::value, 6}, // BGold
    {Binary<         0>::value, 0}, // BKing 玉の位置は別途、位置を符号化する。使用しないので numOfBit を 0 にしておく。
    {Binary<      1001>::value, 4}, // BProPawn
    {Binary<    100011>::value, 6}, // BProLance
    {Binary<    100111>::value, 6}, // BProKnight
    {Binary<    101011>::value, 6}, // BProSilver
    {Binary<  10011111>::value, 8}, // BHorse
    {Binary<  10111111>::value, 8}, // BDragona
    {Binary<         0>::value, 0}, // 使用しないので numOfBit を 0 にしておく。
    {Binary<         0>::value, 0}, // 使用しないので numOfBit を 0 にしておく。
    {Binary<       101>::value, 4}, // WPawn
    {Binary<     10011>::value, 6}, // WLance
    {Binary<     10111>::value, 6}, // WKnight
    {Binary<     11011>::value, 6}, // WSilver
    {Binary<   1011111>::value, 8}, // WBishop
    {Binary<   1111111>::value, 8}, // WRook
    {Binary<    101111>::value, 6}, // WGold
    {Binary<         0>::value, 0}, // WKing 玉の位置は別途、位置を符号化する。
    {Binary<      1101>::value, 4}, // WProPawn
    {Binary<    110011>::value, 6}, // WProLance
    {Binary<    110111>::value, 6}, // WProKnight
    {Binary<    111011>::value, 6}, // WProSilver
    {Binary<  11011111>::value, 8}, // WHorse
    {Binary<  11111111>::value, 8}, // WDragon
};

// 盤上の bit 数 - 1 で表現出来るようにする。持ち駒があると、盤上には Empty の 1 bit が増えるので、
// これで局面の bit 数が固定化される。
const HuffmanCode HuffmanCodedPos::handCodeTable[HandPieceNum][ColorNum] = {
    {{Binary<        0>::value, 3}, {Binary<      100>::value, 3}}, // HPawn
    {{Binary<        1>::value, 5}, {Binary<    10001>::value, 5}}, // HLance
    {{Binary<       11>::value, 5}, {Binary<    10011>::value, 5}}, // HKnight
    {{Binary<      101>::value, 5}, {Binary<    10101>::value, 5}}, // HSilver
    {{Binary<      111>::value, 5}, {Binary<    10111>::value, 5}}, // HGold
    {{Binary<    11111>::value, 7}, {Binary<  1011111>::value, 7}}, // HBishop
    {{Binary<   111111>::value, 7}, {Binary<  1111111>::value, 7}}, // HRook
};

やねうら王のハフマン符号

やねうら王ではハフマン符号は、extra/sfen_packer.cppにコメントで記載されている。コメントに合わせて、Aperyのposition.cppに以下の通りハフマン符号を定義する。

const HuffmanCode PackedSfen::boardCodeTable[PieceNone] = {
	{ Binary<         0>::value, 1 }, // Empty
	{ Binary<         1>::value, 4 }, // BPawn
	{ Binary<        11>::value, 6 }, // BLance
	{ Binary<      1011>::value, 6 }, // BKnight
	{ Binary<       111>::value, 6 }, // BSilver
	{ Binary<     11111>::value, 8 }, // BBishop
	{ Binary<    111111>::value, 8 }, // BRook
	{ Binary<      1111>::value, 6 }, // BGold
	{ Binary<         0>::value, 0 }, // BKing 玉の位置は別途、位置を符号化する。使用しないので numOfBit を 0 にしておく。
	{ Binary<       101>::value, 4 }, // BProPawn
	{ Binary<     10011>::value, 6 }, // BProLance
	{ Binary<     11011>::value, 6 }, // BProKnight
	{ Binary<     10111>::value, 6 }, // BProSilver
	{ Binary<   1011111>::value, 8 }, // BHorse
	{ Binary<   1111111>::value, 8 }, // BDragona
	{ Binary<         0>::value, 0 }, // 使用しないので numOfBit を 0 にしておく。
	{ Binary<         0>::value, 0 }, // 使用しないので numOfBit を 0 にしておく。
	{ Binary<      1001>::value, 4 }, // WPawn
	{ Binary<    100011>::value, 6 }, // WLance
	{ Binary<    101011>::value, 6 }, // WKnight
	{ Binary<    100111>::value, 6 }, // WSilver
	{ Binary<  10011111>::value, 8 }, // WBishop
	{ Binary<  10111111>::value, 8 }, // WRook
	{ Binary<    101111>::value, 6 }, // WGold
	{ Binary<         0>::value, 0 }, // WKing 玉の位置は別途、位置を符号化する。
	{ Binary<      1101>::value, 4 }, // WProPawn
	{ Binary<    110011>::value, 6 }, // WProLance
	{ Binary<    111011>::value, 6 }, // WProKnight
	{ Binary<    110111>::value, 6 }, // WProSilver
	{ Binary<  11011111>::value, 8 }, // WHorse
	{ Binary<  11111111>::value, 8 }, // WDragon
};

const HuffmanCode PackedSfen::handCodeTable[HandPieceNum][ColorNum] = {
	{ { Binary<        0>::value, 3 },{ Binary<      100>::value, 3 } }, // HPawn
	{ { Binary<        1>::value, 5 },{ Binary<    10001>::value, 5 } }, // HLance
	{ { Binary<      101>::value, 5 },{ Binary<    10101>::value, 5 } }, // HKnight
	{ { Binary<       11>::value, 5 },{ Binary<    10011>::value, 5 } }, // HSilver
	{ { Binary<      111>::value, 5 },{ Binary<    10111>::value, 5 } }, // HGold
	{ { Binary<     1111>::value, 7 },{ Binary<  1001111>::value, 7 } }, // HBishop
	{ { Binary<    11111>::value, 7 },{ Binary<  1011111>::value, 7 } }, // HRook
};

AperyのPositionクラスに、PackedSfenから局面を読み込めるメソッドを追加する。

bool set(const PackedSfen& sfen, Thread* th);

setメソッドは、HuffmanCodedPosから局面を読み込むメソッドをほぼ流用して実装した。
これで、PackedSfenValueの読み込みが可能になる。

指し手は、形式が異なるため以下のようにしてApery形式に変換を行う。

		// 指し手 bit0..6 = 移動先のSquare、bit7..13 = 移動元のSquare(駒打ちのときは駒種)、bit14..駒打ちか、bit15..成りか
		u16 bestMove16 = psv->move & 0x7f; // 移動先
		if ((psv->move & 0x4000) == 0) {
			// 移動
			bestMove16 |= psv->move & 0x3f80;
		}
		else {
			// 駒打ち
			bestMove16 |= (((psv->move >> 7) & 0x7f) + SquareNum - 1) << 7;
		}
		// 成り
		if ((psv->move & 0x8000) != 0)
			bestMove16 |= 0x4000;

		const Move move = Move(bestMove16);

テスト用の教師局面を作成

やねうら王を使ってテスト用の教師局面を作成した。
やねうら王のビルドは、Visual Studio 2017が必要だが、2015しかインストールしていないので、MSYS2のg++でビルドした。
やねうら王のMakefileで、「COMPILER = g++」を有効にして、MSYS2 MinGW 64-bitで、makeを実行する。
makeのターゲットはavx2とする。

make -j8 avx2

やねうら王では、ユーザ定義の処理をsource\engine\user-engine\user-search.cppに定義できるようになっているので、ここにテスト用データを生成する処理を記述する。

void user_test(Position& pos_, istringstream& is)
{
    std::cout << pos_.sfen() << std::endl;

    Learner::PackedSfenValue psv;
    psv.gamePly = 1;
    pos_.sfen_pack(psv.sfen);
    psv.move = move_from_usi("2g2f");
    psv.score = 10;
    psv.game_result = s8(1);

    std::fstream fs;
    fs.open("test.psv", ios::out | ios::binary);
    fs.write((char*)&psv, sizeof(Learner::PackedSfenValue));
    fs.close();
}

コマンドラインで、YaneuraOu-by-gcc.exeを実行して、

isready
position startpos
user

と入力すると初期局面のテストデータをtest.psvというファイルに出力できる。

positionコマンドの局面を変更することで異なる局面を生成できる。
評価値、指し手、手数、勝敗は、ソースに直書きしているので、必要に応じて修正する。