Qhapaq Lab

Proof-Number Search

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

概要

PNS では各ノードに、

  • proof number
  • disproof number

を持たせる。

概念的には、

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

を数えている。

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

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

実装例

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

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

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

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 は、長い詰みや複雑な分岐のある詰将棋で特に有効である。 アルファベータ法 のように全体を深さ優先で舐めるより、 「証明に近い部分木」へ集中できるからである。

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

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

将棋AIでの位置づけ

通常の対局用将棋AIでは、 アルファベータ法と 静止探索を中心とする探索が主流である。

一方で、

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

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

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

注意点

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

関連項目

参考にしたホームページ