[Theory of Computer Game 11]

PNS (Proof-Number Search)

Chinese 遊戲AI

written by LiaoWC on 2022-02-18

PNS (Proof-Number Search) 是一種適合最接近終盤使用或是要證明一個盤面是否為必勝/必敗。它會優先選擇有較少節點要解的分支來做。先了解一下名詞，再來看範例。

名詞

proof number：要證明一個狀態至少還有幾個狀態要解。0 表示 true；∞ 表示 false。在 OR 層取下一層 proof number 的 min，在 AND 層取下一層 proof number 的 sum。
disproof number：要反證一個獎至少還有幾個狀態要解。0 表示 false；∞ 表示 true。在 OR 層取下一層 disproof number 的 sum，在 AND 層取下一層 disproof number 的 min。

（true 表這個狀態會贏；false 表這個狀態會輸）

AND-OR tree：抽象化 Minimax 樹，原本取 max 的用 OR 表示（方形），取 min 的用 AND 表示（圓形）。範例會用這種形式呈現。
most proving node：AND-OR tree 每次會選擇 most proving node 來展開。OR 層選 proof number 最小的，AND 層選 disproof number 最小的。遇到一樣我們就選左邊的。

範例

我們來看範例。每個節點旁的數字為（proof number, disproof number），每輪找 most proving node 來展開，並向上更新回去。如果 most proving node 是 terminal state，看是勝還是負，如果是勝的話，proof/disproof number 為 0/∞；如果是負的話，proof/disproof number 為 ∞/0。

從根節點開始：