Qhapaq Lab 
  # Proof-Number Search

Proof-Number Search（PNS）は、
AND/OR 木の根が「証明できるか」「反証できるか」を最小コストで調べる best-first search である。
将棋では特に詰将棋や詰み探索の文脈で重要であり、
通常の [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/) とは役割がかなり異なる。

## 概要

PNS では各ノードに、

- proof number
- disproof number

を持たせる。

概念的には、

- その局面が勝ちだと証明するのにどれだけ手間がかかるか
- 負けではないと示すのにどれだけ手間がかかるか

を数えている。

OR ノードでは「どれか 1 つ証明できればよい」ので最小を取り、
AND ノードでは「全部証明しなければならない」ので和を取る。

この値が最も有望な frontier node を選んで展開していくのが、
PNS の基本である。

## 実装例

教育用に単純化すると次のようになる。

```cpp
while (!root.proven() && !root.disproven()) {
    Node* mostProving = selectMostProvingNode(root);
    expand(mostProving);
    evaluateTerminalChildren(mostProving);
    updateAncestors(mostProving);
}
```

更新規則は概ね次のようになる。

```cpp
if (node.isOrNode()) {
    node.proof = min(child.proof);
    node.disproof = sum(child.disproof);
} else {
    node.proof = sum(child.proof);
    node.disproof = min(child.disproof);
}
```

## 詰将棋との関係

PNS は、長い詰みや複雑な分岐のある詰将棋で特に有効である。
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/) のように全体を深さ優先で舐めるより、
「証明に近い部分木」へ集中できるからである。

Chessprogramming Wiki でも、
将棋や詰将棋での応用が明示的に言及されている。

## Conspiracy Number Search との関係

[Conspiracy Number Search](/shogi/shogiwiki/search/conspiracy-number-search/) は、
根の値を覆す難しさを扱う best-first search である。
PNS はその流れの近縁にありつつ、
より「証明問題」に特化した形と見ると分かりやすい。

## 将棋AIでの位置づけ

通常の対局用将棋AIでは、
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)と
[静止探索](/shogi/shogiwiki/search/quiescence-search/)を中心とする探索が主流である。

一方で、

- 詰み探索
- 詰将棋ソルバ
- 終局証明

では PNS 系が非常に重要になる。

そのため「通常探索の代わり」ではなく、
「目的の違う専用探索」と理解するのが適切である。

## 注意点

- 木全体を保持しやすく、メモリ消費が大きくなりやすい
- 終端判定や合法手生成の正確性が特に重要になる
- 一般対局の全局面へそのまま適用するのは重い

## 関連項目

- [Conspiracy Number Search](/shogi/shogiwiki/search/conspiracy-number-search/)
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [探索木](/shogi/shogiwiki/search/search-tree/)

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

- [Chessprogramming Wiki: Proof Number Search](https://www.chessprogramming.org/Proof-Number_Search)
- [Chessprogramming Wiki: Victor Allis](https://www.chessprogramming.org/Victor_Allis)
- [en.wikipedia.org: Proof Number Search](https://en.wikipedia.org/wiki/Proof-number_search)
- [citeseerx.ist.psu.edu: Document](https://citeseerx.ist.psu.edu/document?doi=db6ce86eea0106dc6ae75349a2cacb212b91884e&repid=rep1&type=pdf)