Proof-Number Search

The core mechanism of PNS is assigning two values to each node:

• Proof Number (pn): The minimum number of leaf nodes in the subtree that must be proven to be a win for the player to move.
• Disproof Number (dn): The minimum number of leaf nodes that must be disproven (shown to be a loss).

For a terminal winning node, pn=0 and dn=∞. For a terminal losing node, pn=∞ and dn=0. An AND node (where the player must find a winning move among all children) has its pn as the sum of its children's pns and its dn as the minimum of its children's dns. An OR node (where the opponent must find a refutation) uses the opposite logic. The algorithm always expands the node with the smallest proof or disproof number, depending on the current proving goal.

PNS is a best-first search algorithm that does not use depth or heuristic evaluation. Instead, it directly targets proving or disproving the root node's status. It models the game as an AND/OR tree:

• OR nodes represent positions where the player to move can choose a move (only one child needs to be proven a win).
• AND nodes represent positions where the opponent will respond (all children must be proven wins for the original player).

The search is guided solely by the proof and disproof numbers, making it exceptionally efficient for problems where the goal is a binary proof (win/loss) rather than finding a marginally better score. It is particularly effective for endgame databases and solving chess puzzles like checkmate-in-N.

Unlike Minimax with Alpha-Beta Pruning, which relies on a heuristic evaluation function to score non-terminal positions, PNS requires no such function. It operates purely on the logical structure of proof. This makes it immune to errors from inaccurate positional assessments, a significant advantage for proof-solving. However, it also means PNS cannot differentiate between a swift win and a slow one; it only seeks to prove the existence of a forced win. This characteristic makes it a deductive reasoning tool rather than an optimizing one, ideal for domains where certainty is paramount.

PNS is the foundational algorithm for complete game solvers. Its most famous application is in solving Connect Four, proving the first player can force a win with perfect play. It is also extensively used for:

• Constructing endgame tablebases for chess (e.g., King and Queen vs. King).
• Solving Shogi and Go endgame puzzles.
• Analyzing Awari and other combinatorial games.

The algorithm's efficiency stems from its ability to ignore vast sections of the tree that are irrelevant to the proof. It is often combined with transposition tables to recognize identical positions reached via different move orders, and with iterative deepening frameworks to manage memory.

PNS occupies a unique niche within the search landscape:

• Vs. Monte Carlo Tree Search (MCTS): MCTS uses stochastic rollouts for value estimation and balances the exploration-exploitation tradeoff (e.g., via UCT). PNS is deterministic and seeks proof, not statistical confidence.
• Vs. Alpha-Beta Search: Alpha-Beta is optimized for finding the best move using evaluations, often employing aggressive pruning. PNS is optimized for exhaustively proving a game-theoretic value, expanding nodes that appear most critical to the proof.
• Vs. Breadth/Depth-First Search: Uninformed searches explore the state space systematically. PNS is an informed, goal-directed search where the proof numbers act as a dynamic, internal heuristic guiding expansion toward the most proving node.

The basic PNS algorithm can suffer from memory explosion. Two critical variants address this:

• Proof-Number Search 2 (PN²): Employs a two-level search. The outer search uses PNS, but when a child node is selected for expansion, an inner depth-first search is initiated from that child to update its proof numbers more efficiently before returning to the outer loop.
• Depth-First Proof-Number Search (DF-PN): A more sophisticated variant that performs a depth-first traversal while maintaining proof number thresholds. It uses iterative deepening on the proof numbers themselves, allowing it to operate within strict memory limits. DF-PN is the modern standard for high-performance game-solving programs, as it dramatically reduces the memory footprint compared to naive best-first PNS.

Best-First Search is the overarching algorithmic paradigm for Proof-Number Search. It is a graph search algorithm that uses an evaluation function to determine which node is the most promising to explore next. Unlike depth-first or breadth-first approaches, it maintains a priority queue (often a heap) of frontier nodes, always expanding the node with the best heuristic value. Proof-Number Search is a specific instantiation of best-first search where the evaluation function is designed to prove or disprove a game-theoretic outcome.

• Core Mechanism: Uses a priority queue to order node expansion.
• Evaluation Function: Critical for guiding the search; in PNS, this is the proof and disproof number.
• Contrast with PNS: Standard best-first search aims to find a goal; PNS aims to prove a Boolean property (win/loss).

An AND/OR tree is the fundamental data structure upon which Proof-Number Search operates. It represents the alternative and sequential decisions in adversarial two-player games.

• OR Nodes: Represent positions where it is the current player's turn. The node is proven if any child (move) leads to a proven position.
• AND Nodes: Represent positions where it is the opponent's turn. The node is proven only if all children (opponent's possible replies) lead to proven positions.
• Game Representation: This structure naturally encodes the alternating turns and the need to consider all opponent responses, making it ideal for game-solving rather than just move selection.
• Connection to PNS: Proof and disproof numbers are computed by propagating values up this AND/OR tree according to min/max rules.

Alpha-Beta Pruning is the dominant algorithm for adversarial search in games with large branching factors, such as chess. It is an optimization of the minimax algorithm that eliminates branches that cannot influence the final decision.

• Primary Goal: To find a good move quickly, not to solve the game (prove a win/loss).
• Contrast with PNS: Alpha-beta is used for depth-limited search with an evaluation function, returning a heuristic score. PNS is used for proof-tree search, expanding nodes until a terminal win/loss/draw is proven, often for endgame databases or puzzles.
• Use Case: Alpha-beta is for real-time decision-making; PNS is for exhaustive analysis of critical positions.

Monte Carlo Tree Search is a best-first search algorithm that guides its exploration using the results of random simulations (rollouts). It is famous for its success in Go.

• Core Difference: MCTS uses random sampling and statistical convergence to estimate node values. PNS uses logical proof numbers derived from the tree structure.
• Exploration/Exploitation: MCTS balances this via the Upper Confidence Bound for Trees (UCT) formula. PNS balances it via the selection of the Most Proving Node.
• Application Scope: MCTS excels in games with high stochasticity or complex evaluation. PNS is particularly strong for deterministic, combinatorial game theory problems like Awari, Checkers, or Chess endgames where exact solutions are sought.

A Transposition Table is a critical performance optimization used alongside Proof-Number Search and other game-solving algorithms. It is a hash table that caches previously computed results for game states.

• Problem Solved: The same board position can often be reached via different sequences of moves (transpositions). Re-computing proof numbers for these identical states is wasteful.
• Integration with PNS: When PNS encounters a node, it first checks the transposition table. If the state is found, it can reuse the stored proof and disproof numbers, pruning the entire subtree below.
• Impact: This can reduce the effective branching factor and search time by orders of magnitude, making the solution of non-trivial games feasible.

Depth-First Proof-Number Search is a memory-efficient variant of PNS that uses iterative deepening and transposition tables to solve much larger problems than standard PNS.

• Memory Issue: Standard PNS (as a best-first search) must keep the entire frontier in memory, which can be prohibitive.
• DFPN Solution: It performs a series of depth-first searches within a threshold, using a proof-number upper bound. It updates thresholds iteratively based on search results.
• Key Advantage: DFPN's memory footprint is proportional to the search depth, not the tree width, enabling the solution of games like Checkers (which was proven to be a draw using DFPN-based algorithms).