Qhapaq Lab 
  # Conspiracy Number Search

Conspiracy Number Search（CNS）は、
ルートの評価をひっくり返すために「何枚の葉の値が変わる必要があるか」を手掛かりに探索を進める best-first search である。
[ミニマックス法](/shogi/shogiwiki/search/minimax/)に基づく探索ではあるが、
通常の深さ優先 [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/) とはかなり異なる性格を持つ。

## 概要

Conspiracy Number の考え方は、
あるノードの値を別の値へ変えるには
「葉の評価が最低いくつ変わる必要があるか」
を数えることにある。

この数が大きければ、
現在の評価は比較的安定しているとみなせる。

CNS はその情報を使って、

- ルートの値を変えそうな葉
- その候補へつながる細い部分木

を優先して広げる。

そのため木は、
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/) のように幅広く深さを揃えて広がるのではなく、
「値をひっくり返しそうな筋」を狙って不規則に伸びやすい。

## 基本的な流れ

概念的には次のようになる。

1. ルートの可能値と conspiracy number を見積もる
2. ルートの値を変えるうえで有望な leaf を選ぶ
3. その leaf を展開して評価する
4. conspiracy number を根まで更新する
5. 十分な確信が得られるまで繰り返す

これは「どれだけ深く読めたか」よりも、
「現在の最善手がどれだけ頑健か」を重視する探索といえる。

## 実装イメージ

教育用の擬似コードは次のようになる。

```cpp
while (!confidenceReached(root)) {
    Node* leaf = selectMostDangerousLeaf(root);
    expand(leaf);
    evaluateChildren(leaf);
    backupConspiracyNumbers(leaf);
}

return root->bestMove;
```

実際には、

- possible values の管理
- conspiracy number の更新
- どの leaf を「危険」とみなすか

の設計が中心になる。

## Proof-Number Search との関係

[Proof-Number Search](/shogi/shogiwiki/search/proof-number-search/) は、
AND/OR 木で真偽を証明する問題に特化した手法であり、
Conspiracy Number Search の流れをより終局証明向けに整理したものと見なされることがある。

将棋では特に詰将棋や終局証明の文脈で
PNS 系の方が話題になりやすい。
そのため一般対局エンジンでは CNS 自体より、
そこから発展した考え方を知っておく意味が大きい。

## 将棋AIでの位置づけ

通常の実戦将棋AIでは、
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/) とその派生が主流であり、
CNS が中心になることは少ない。

ただし、

- best-first search の発想を知る
- 値の安定性や「読み筋の頑健さ」を考える
- [Proof-Number Search](/shogi/shogiwiki/search/proof-number-search/) 系とのつながりを理解する

うえでは有用である。

## 注意点

- 木全体をメモリに保持しやすく、実装が重くなりやすい
- 評価値が細かいほど管理コストが増える
- 一般的な実戦エンジンでは [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/) より扱いにくい

## 関連項目

- [ミニマックス法](/shogi/shogiwiki/search/minimax/)
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [Proof-Number Search](/shogi/shogiwiki/search/proof-number-search/)
- [探索木](/shogi/shogiwiki/search/search-tree/)

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

- [Chessprogramming Wiki: Conspiracy Number Search](https://www.chessprogramming.org/Conspiracy_Number_Search)
- [Chessprogramming Wiki: Conspiracy Numbers](https://www.chessprogramming.org/Conspiracy_Numbers)
- [Chessprogramming Wiki: Proof Number Search](https://www.chessprogramming.org/Proof-Number_Search)
- [research.tilburguniversity.edu: Conspiracy Number Search 2](https://research.tilburguniversity.edu/en/publications/conspiracy-number-search-2)
- [www.scitepress.org: 57530.Pdf](https://www.scitepress.org/papers/2016/57530/57530.pdf)