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