並列探索は、複数のスレッドやコアを使って探索を高速化する技術群である。 現代の将棋AIやチェスエンジンでは、マルチコア CPU を活かすために重要な分野である。
探索木は基本的に逐次的な構造を持つため、完全にきれいな並列化は難しい。 それでも実際には、
などの方法で性能向上を狙う。
Chessprogramming Wiki でも、
が代表的な方式として挙げられている。
逐次探索では、
ため、単純に仕事を分けるだけではうまくいかない。
また、共有メモリでは
も問題になる。
最初の有望手を先に読み、その結果を使って後続の仕事を並列化する考え方。 理論的には洗練されているが、実装はやや複雑になる。
複数スレッドが似た探索をほぼ独立に進め、 共有置換表を通じてゆるく協調する方式。 実装が比較的簡単で、実用エンジンで広く使われている。
ルートで簡単に分担するイメージは次のようになる。
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は 1 手あたりの探索量が大きいので、マルチスレッド化の恩恵が大きい。 一方で、
を共有するため、メモリ帯域や NUMA の影響も受けやすい。