Source of 並列探索 parallel-search

  # 並列探索

並列探索は、複数のスレッドやコアを使って探索を高速化する技術群である。
現代の将棋AIやチェスエンジンでは、マルチコア CPU を活かすために重要な分野である。

## 概要

探索木は基本的に逐次的な構造を持つため、完全にきれいな並列化は難しい。
それでも実際には、

- ルートで手を分ける
- 部分木を分担する
- [置換表](/shogi/shogiwiki/search/transposition-table/)を共有する

などの方法で性能向上を狙う。

Chessprogramming Wiki でも、

- [Young Brothers Wait Concept](/shogi/shogiwiki/search/young-brothers-wait-concept/)
- [Lazy SMP](/shogi/shogiwiki/search/lazy-smp/)

が代表的な方式として挙げられている。

## なぜ難しいのか

逐次探索では、

- 先に読んだ枝の結果が
- 後続の枝刈り条件に影響する

ため、単純に仕事を分けるだけではうまくいかない。

また、共有メモリでは

- [置換表](/shogi/shogiwiki/search/transposition-table/)の競合
- PV 情報の整合性
- スレッド間同期コスト

も問題になる。

## 代表的な方式

### Young Brothers Wait Concept

最初の有望手を先に読み、その結果を使って後続の仕事を並列化する考え方。
理論的には洗練されているが、実装はやや複雑になる。

### Lazy SMP

複数スレッドが似た探索をほぼ独立に進め、
共有[置換表](/shogi/shogiwiki/search/transposition-table/)を通じてゆるく協調する方式。
実装が比較的簡単で、実用エンジンで広く使われている。

## 実装イメージ

ルートで簡単に分担するイメージは次のようになる。

    void parallelRootSearch(const Position& root, std::vector<Move> moves) {
        parallel_for_each(moves, [&](Move move) {
            Position next = doMove(root, move);
            int score = -search(next, depth - 1, -INF, INF);
            storeRootResult(move, score);
        });
    }

実際には、単純なルート分割だけでは負荷の偏りが大きいため、
共有テーブルやスレッド管理を併用する。

## 将棋AIでの位置づけ

将棋AIは 1 手あたりの探索量が大きいので、マルチスレッド化の恩恵が大きい。
一方で、

- 大きな[NNUE](/shogi/shogiwiki/search/nnue/)評価器
- 大きな[置換表](/shogi/shogiwiki/search/transposition-table/)

を共有するため、メモリ帯域や NUMA の影響も受けやすい。

## 注意点

- NPS が増えても、時間当たりの実力向上は線形には伸びない
- 同期が多いとスケーリングが悪くなる
- 評価器やハッシュのサイズが大きいとメモリ帯域がボトルネックになりやすい

## 関連項目

- [Lazy SMP](/shogi/shogiwiki/search/lazy-smp/)
- [Young Brothers Wait Concept](/shogi/shogiwiki/search/young-brothers-wait-concept/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [NNUE](/shogi/shogiwiki/search/nnue/)

## 参考にしたホームページ

- [Chessprogramming Wiki: Parallel Search](https://www.chessprogramming.org/Parallel_Search)
- [Chessprogramming Wiki: Young Brothers WAIT Concept](https://www.chessprogramming.org/Young_Brothers_Wait_Concept)
- [Chessprogramming Wiki: LAZY SMP](https://www.chessprogramming.org/Lazy_SMP)
並列探索 parallel-search parallel-search
