Conspiracy Number Search（CNS）は、 ルートの評価をひっくり返すために「何枚の葉の値が変わる必要があるか」を手掛かりに探索を進める best-first search である。 ミニマックス法に基づく探索ではあるが、 通常の深さ優先 アルファベータ法 とはかなり異なる性格を持つ。
Conspiracy Number の考え方は、 あるノードの値を別の値へ変えるには 「葉の評価が最低いくつ変わる必要があるか」 を数えることにある。
この数が大きければ、 現在の評価は比較的安定しているとみなせる。
CNS はその情報を使って、
を優先して広げる。
そのため木は、 アルファベータ法 のように幅広く深さを揃えて広がるのではなく、 「値をひっくり返しそうな筋」を狙って不規則に伸びやすい。
概念的には次のようになる。
これは「どれだけ深く読めたか」よりも、 「現在の最善手がどれだけ頑健か」を重視する探索といえる。
教育用の擬似コードは次のようになる。
while (!confidenceReached(root)) {
Node* leaf = selectMostDangerousLeaf(root);
expand(leaf);
evaluateChildren(leaf);
backupConspiracyNumbers(leaf);
}
return root->bestMove;実際には、
の設計が中心になる。
Proof-Number Search は、 AND/OR 木で真偽を証明する問題に特化した手法であり、 Conspiracy Number Search の流れをより終局証明向けに整理したものと見なされることがある。
将棋では特に詰将棋や終局証明の文脈で PNS 系の方が話題になりやすい。 そのため一般対局エンジンでは CNS 自体より、 そこから発展した考え方を知っておく意味が大きい。
通常の実戦将棋AIでは、 アルファベータ法 とその派生が主流であり、 CNS が中心になることは少ない。
ただし、
うえでは有用である。