Young Brothers Wait Concept（YBWC）は、並列 alpha-beta 探索で 「最初の有望手を先に読み、その結果が分かるまで後続の兄弟ノードの並列化を待つ」 という考え方である。
alpha-beta 探索では、最初に読んだ手が beta cut を起こすことが多い。 もしそうなら、残りの兄弟ノードを並列に読んでも無駄になる。
そこで YBWC では、
という方針を取る。
この「無駄な並列探索を減らすため、若い兄弟は待つ」という発想が名前の由来である。
YBWC は、
という利点がある。
特に、 手の並べ替えが良い場合は、 最初の手で cut する確率が高いため効果が出やすい。
int parallelSearch(Node node) {
Move first = firstOrderedMove(node);
int alpha = search(first);
if (alpha >= node.beta) {
return alpha;
}
parallel_for_each(remainingMoves(node), [&](Move move) {
search(move);
});
return collectBestScore();
}これは概念を示す簡略化例であり、実際には
が重要になる。
Lazy SMPは、ゆるく独立探索を走らせる方式である。 それに対して YBWC は、
をより厳密に制御する。
そのため、YBWC の方が理論的には整理されているが、実装は複雑になりやすい。
将棋AIでもマルチスレッド探索は重要だが、 近年は実装容易性からLazy SMP寄りが多い。 それでも YBWC は、並列 alpha-beta を理解する基礎概念として重要である。