Proof-Number Search (PNS)
Proof-Number Search (PNS) is a best-first AND-OR game tree search algorithm designed to determine the exact outcome of a game state—win, loss, or draw—under minimax rules. Unlike traditional alpha-beta pruning algorithms that traverse trees in a depth-first manner evaluating scalar heuristics, PNS treats tree expansion as a boolean logic satisfiability problem. It assigns two integer values to every node: a proof number (pn), representing the minimum number of unvisited leaf nodes that must be proven true to establish the node's truth value, and a disproof number (dn), representing the minimum number of leaf nodes that must be proven false to establish its falsity. By iteratively selecting and expanding the most vulnerable leaf node—the one with the minimum proof or disproof number depending on whether the node is an OR or AND node—PNS concentrates computational power on the narrowest logical path to a definitive terminal outcome, making it exceptionally powerful for endgame analysis and tactical puzzle solving.
HOW-TO IMPLEMENT & CONFIGURE
- A modern systems programming language supporting recursion, pointer/reference management, and dynamic memory allocation (e.g., C++, Rust, Go, or Python 3.10+).
- An immutable or state-reversible game state representation implementing a standard game interface (successor generation, terminal state evaluation, canonical hashing/transposition table keys).
- An explicit graph-based memory structure or transposition table to prevent exponential explosion from state transposition loops in cyclic game graphs.
Step 1
Define the core Node structure that holds the game state representation, its current proof number (pn), disproof number (dn), evaluation flags, and pointers to its generated children. Establish a transposition table to map game state hashes to pre-allocated heap nodes.
import sys
from typing import Dict, List, Optional, Tuple
class Node:
def __init__(self, state, is_or_node: bool):
self.state = state
self.is_or_node = is_or_node # True if player's turn (OR), False if opponent's turn (AND)
self.pn = 1
self.dn = 1
self.expanded = False
self.children: List['Node'] = []
self.evaluated_terminal = False
self.terminal_value = None # True (Win), False (Loss), None (Ongoing)Step 2
Implement the recursive select, expand, and update phases of Proof-Number Search. The select phase descends the tree choosing the child with the minimum proof number (for OR nodes) or minimum disproof number (for AND nodes). The expand phase generates children, and the update phase bubbles proof and disproof numbers back to the root.
class ProofNumberSearch:
INF = sys.maxsize
def __init__(self, initial_state):
self.root = Node(initial_state, is_or_node=True)
self._initialize_leaf(self.root)
def _initialize_leaf(self, node: Node):
if node.state.is_terminal():
node.evaluated_terminal = True
node.terminal_value = node.state.get_result()
if node.terminal_value is True:
node.pn = 0
node.dn = self.INF
elif node.terminal_value is False:
node.pn = self.INF
node.dn = 0
else:
node.pn = 1
node.dn = 1
else:
node.pn = 1
node.dn = 1
def select_most_proving_node(self, node: Node) -> Node:
if not node.expanded or not node.children:
return node
# Select child with minimum pn for OR node, or minimum dn for AND node
best_child = None
if node.is_or_node:
min_val = self.INF
for child in node.children:
if child.pn < min_val:
min_val = child.pn
best_child = child
else:
min_val = self.INF
for child in node.children:
if child.dn < min_val:
min_val = child.dn
best_child = child
return self.select_most_proving_node(best_child)
def expand(self, node: Node):
if node.expanded or node.evaluated_terminal:
return
successors = node.state.generate_successors()
for next_state in successors:
child = Node(next_state, is_or_node=not node.is_or_node)
self._initialize_leaf(child)
node.children.append(child)
node.expanded = True
self.update_values(node)
def update_values(self, node: Node):
while node is not None:
old_pn, old_dn = node.pn, node.dn
if node.evaluated_terminal:
node = node.parent if hasattr(node, 'parent') else None
continue
if node.is_or_node:
# OR node: pn = sum(child.pn), dn = min(child.dn)
sum_pn = 0
min_dn = self.INF
for child in node.children:
sum_pn += child.pn
if child.dn < min_dn:
min_dn = child.dn
node.pn = min(sum_pn, self.INF)
node.dn = min_dn
else:
# AND node: pn = min(child.pn), dn = sum(child.dn)
min_pn = self.INF
sum_dn = 0
for child in node.children:
if child.pn < min_pn:
min_pn = child.pn
sum_dn += child.dn
node.pn = min_pn
node.dn = min(sum_dn, self.INF)
if node.pn == old_pn and node.dn == old_dn:
break # No change propagated
node = getattr(node, 'parent', None)Step 3
Write rigorous test suites validating tree invariant properties. Ensure that after each expansion cycle, root.pn == 0 (proved win), root.dn == 0 (proved loss), or memory limits are safely respected. Benchmark node expansion throughput.
def test_pns_convergence():
# Mock state object for validation
class DummyState:
def __init__(self, val):
self.val = val
def is_terminal(self):
return self.val in [0, 1]
def get_result(self):
return True if self.val == 1 else False
def generate_successors(self):
return [DummyState(1)] if self.val == 2 else []
initial = DummyState(2)
pns = ProofNumberSearch(initial)
mpn = pns.select_most_proving_node(pns.root)
pns.expand(mpn)
assert pns.root.pn == 0 or pns.root.dn == 0
Step 4
Mitigate integer overflow during summation of proof/disproof numbers by bounding values with a safe threshold constant (INF). Implement transposition table caching via Zobrist hashing to merge identical game graph nodes and prevent infinite memory consumption.
# Implement saturated addition to prevent integer overflow
def safe_add(a: int, b: int, inf: int) -> int:
if a >= inf or b >= inf:
return inf
return min(inf, a + b)Mathematical Foundations of Proof and Disproof Numbers
Let G be a game tree graph where nodes represent game states. PNS avoids evaluating scalar heuristics by defining two exact boolean proof metrics. For any node n, proof number pn(n) is the minimum number of leaf nodes that must be evaluated as TRUE (win for the maximizing player) under any resolution of unexpanded branches to make n TRUE. Conversely, disproof number dn(n) is the minimum number of leaf nodes that must be evaluated as FALSE to make n FALSE. For terminal nodes, if n is a win, pn(n) = 0 and dn(n) = infinity. If n is a loss, pn(n) = infinity and dn(n) = 0. For non-terminal OR nodes (where the maximizing player moves), the metrics aggregate as: pn(n) = sum(pn(c)) for all children c, and dn(n) = min(dn(c)) for all children c. For non-terminal AND nodes (where the minimizing player moves), the aggregation inverts: pn(n) = min(pn(c)) for all children c, and dn(n) = sum(dn(c)) for all children c. These recurrence relations guarantee that the algorithm targets the absolute narrowest vulnerability in the adversarial tree.
Memory Management & Transposition Tables
Because board games feature transpositions (distinct move sequences leading to identical board configurations), standard tree algorithms will waste exponential memory unrolling Directed Acyclic Graphs (DAGs) into trees. Production deployments of Proof-Number Search must couple the algorithm with a Transposition Table (TT) indexed by a robust Zobrist hash of the game state. When selecting or expanding a node, the engine checks if the state already exists in the TT. If present, pointers are shared, transforming the search space from a strict tree into a general graph. Special care must be taken during the value update phase to handle circular dependencies correctly without inducing infinite recursive loops.
📚 STANDARDS & ACADEMIC RFC CITATIONS
- Allis, L. V., van der Herik, H. J., & Huntjens, I. P. (1994). Proof-number search. Artificial Intelligence, 66(1), 91-124.
- Breuker, D. M., Uiterwijk, J. W., & van der Herik, H. J. (2001). Solving problems accurately by proof-number search. Artificial Intelligence, 129(1-2), 193-219.
- Kishimoto, A., & Schaeffer, J. (2005). Transposition table optimizations for proof-number search. Proceedings of the National Conference on Artificial Intelligence (AAAI).
