TadaoYamaokaの日記

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

将棋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で性能がでない課題があるので、どうするか継続検討したい。