Is this Monte Carlo search?

No. Basic proof-number search uses AND - OR proof structure, rather than estimating values through random simulated games.

Does a proof number of zero mean high confidence?

It marks an established proposition under the model and evaluation rules, not a probability estimate.

Can it handle repeated game positions?

Variants can, but transpositions, cycles, and history-sensitive repetition rules require more care than the simple tree description.

AI Glossary / Graphs and symbolic AI / Intermediate

Proof-number search

Definition

Proof-number search is a best-first search method for proving or disproving a proposition represented by an AND - OR tree. It is especially associated with solving game positions, such as determining whether a player can force a win. It directs expansion using proof and disproof numbers rather than treating an intermediate position score as a demonstrated result.

What it means

Suppose the proposition is “the designated player can force a win.” At that player's turn, finding one winning move suffices, so the node behaves as OR. At the opponent's turn, every legal response must still allow the designated player to win, so the node behaves as AND.
The search keeps track of how many currently unresolved leaves would need to be established to prove or disprove a node in the current tree. These counts guide effort; they are not winning probabilities or exact predictions of future runtime. A small proof number can identify an attractive line to investigate without establishing that the line actually wins.

How it works

In the basic initialization, an unresolved leaf receives proof and disproof numbers (1, 1). A proven leaf receives (0, infinity); a disproven leaf receives (infinity, 0). At an OR node, the proof number is the minimum child proof number and the disproof number is the sum of child disproof numbers. At an AND node, those operations switch: sum the proof numbers and take the minimum disproof number.
Select a most-proving leaf by following minimum proof numbers at OR nodes and minimum disproof numbers at AND nodes. Expand it, evaluate its children, and update ancestors. A zero root proof number establishes the proposition; a zero disproof number refutes it within the modeled problem.

Three practical examples

A game-solving program can investigate whether a specified position permits a forced win despite every opposing reply.
An educational AND - OR puzzle can demonstrate why choosing one successful alternative differs from satisfying all requirements.
A research prototype can compare search effort on binary outcome problems with uneven branching, where some proof routes may be much smaller than others.

Think of it this way

Think of choosing between application routes. One route needs every listed requirement, while success through any complete route is enough overall. You investigate the route that currently looks easiest to settle. The analogy is limited because game responses are adversarial choices, and proof-number counts concern unresolved tree leaves rather than the monetary cost or real-world difficulty of gathering evidence.

Worked example

Consider an invented OR root R with two AND children, A and B. A has two unresolved leaves, a1 and a2; B has three unresolved leaves, b1, b2, and b3. Every leaf begins with (proof, disproof) = (1, 1).
A therefore has (2, 1), B has (3, 1), and R has (2, 2): its proof number is min(2, 3), while its disproof number is 1 + 1. The search initially chooses A because its proof number is smaller. Within A, the equal disproof numbers require a tie-breaking choice; suppose a1 is selected.
Suppose further search proves a1, changing it to (0, infinity). A becomes (1, 1), and R becomes (1, 2). If further search instead disproves a2, giving it (infinity, 0), A becomes (infinity, 0). The root then becomes (3, 1), and attention shifts to B. Refuting one required child refutes A, but it does not refute the OR root while B remains possible.
If all three leaves below B are eventually proved, B becomes (0, infinity), and so does R. The root proposition is then established through B, regardless of A's failure.

Illustrative case study

Fictional case: Reed Games builds a small endgame teaching tool. Its first display labels a proof number of 1 as “almost certain to win.” Reviewers replace that label with “one unresolved leaf in the current proof structure” and show the proposition separately from search status.
They also add examples where that remaining leaf expands into a large subtree or is disproved. The fictional lesson is that an economical-looking proof route may still fail. This is an invented interface exercise, not a claim that a particular game was solved or that runtime improved.

Common misconceptions and mistakes

Do not interpret proof numbers as calibrated confidence or as the total number of positions the search will visit. Expansion can reveal a much more complicated subtree. Do not swap the AND and OR recurrence rules: proving an AND node requires all children, whereas disproving it needs only one counterexample.
Define the proposition and terminal outcomes clearly. If the claim is a forced win, a draw does not establish it. Shared positions and cycles require careful handling; naively applying tree counting to a graph can double-count work, and repetition rules can make results depend on history. A resource limit ending the search is not itself a disproof.

Business use

The method is most directly useful for specialized solvers that need a binary result with a verifiable search argument. A business using such a component should identify the exact proposition, the modeled rules, and the evidence returned when the search terminates.
For a pilot, use small instances with known outcomes and inspect both successful proofs and disproved alternatives. Record memory use as well as time, since maintaining a best-first tree can be expensive. Avoid promising that the method finds the shortest winning strategy or always beats another search algorithm; those are separate claims requiring suitable definitions and evidence.

Check your understanding

If an AND node has children with pairs (0, infinity) and (1, 1), what pair does it receive?

Answer: Its proof number is 0 + 1 = 1 and its disproof number is min(infinity, 1) = 1. One child remains unresolved, so the node is neither proved nor disproved.

Related terms

And - or tree
Best-first search
Minimax
game-tree search
proof number
disproof number
transposition
depth-first proof-number search

Learn next

Learn AND - OR search and transposition handling next. Reverse R in the worked example from OR to AND and recompute its initial pair. Explain why proving only B would then be insufficient for proving R.

Sources

L. Victor Allis, Maarten van der Meulen and H. Jaap van den Herik, Proof-number search, original paper abstract: https://www.sciencedirect.com/science/article/pii/0004370294900043 Akihiro Kishimoto and colleagues, Game-Tree Search Using Proof Numbers: The First Twenty Years, author-hosted technical account: https://webdocs.cs.ualberta.ca/~mmueller/ps/ICGA2012PNS.pdf

Previous: Proof by Contradiction Next: Propensity scores