💻 computer science

Formal Verification of Minimax Algorithms

This paper presents a formal verification of minimax search algorithms with alpha-beta pruning and transposition tables using the Dafny system, introducing a witness-based correctness criterion that successfully proves one practical variant while exposing a correctness violation in another.

Original authors: Wieger Wesselink, Kees Huizing, Huub van de Wetering

Published 2026-04-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Wieger Wesselink, Kees Huizing, Huub van de Wetering

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a complex board game like Chess or Checkers against a super-smart computer. To decide its next move, the computer doesn't just guess; it builds a giant "tree" of possibilities in its mind. It asks, "If I go here, you'll go there, then I'll go there..." and so on, trying to predict the best outcome. This is called a Minimax algorithm.

However, building this entire tree for a game like Chess is impossible because it's too huge. So, computers use tricks to speed things up:

Alpha-Beta Pruning: Like a detective ignoring dead-end alleys, the computer stops looking down paths that are clearly bad.
Transposition Tables: This is a "sticky note" system. If the computer has already calculated a specific board position before, it just looks up the answer on the sticky note instead of re-calculating it.

The Problem:
These tricks are incredibly clever, but they are also messy. Because the computer skips steps and reuses old notes, it's very hard to prove mathematically that the final answer is actually correct. Sometimes, the computer might skip a path that would have led to a win, just because an old sticky note told it to stop looking.

The Solution (The Paper's Mission):
The authors of this paper wanted to use a "mathematical proof machine" (a tool called Dafny) to check if these game-playing algorithms are actually telling the truth. They didn't just run tests (which might miss rare errors); they tried to prove the code is perfect.

The Big Idea: The "Witness"

The hardest part was dealing with the "sticky notes" (Transposition Tables). When a computer reuses an old answer, it's like looking at a map of a city you visited last year. But what if the city has changed? Or what if you only looked at part of the city last time?

The authors invented a new way to check correctness called a "Witness."

The Analogy: Imagine the computer claims, "I know the best move is to go Left."
The Old Way: "Trust me, I did the math."
The Witness Way: "Show me the map." The computer must produce a specific, complete "sub-tree" (a witness) that proves, step-by-step, why "Left" is the best move. If the computer can't build this specific map using the data it has, the answer is considered suspicious, even if it looks right.

The Experiment: Two Competitors

The authors took two popular versions of this algorithm and put them through the "Witness" test.

1. The Wikipedia Version (NegamaxTTW)

How it works: It's a bit cautious. When it sees a sticky note, it checks: "Does this note guarantee I can stop looking right now?" If the note is vague or from a different context, it ignores it and does the full calculation.
The Result: Pass. The authors successfully proved with the Dafny machine that this version always produces a valid "Witness." It's safe, reliable, and mathematically sound.

2. The Marsland Version (NegamaxTTM)

How it works: This version is more aggressive. When it sees a sticky note saying "The value is at least 3," it immediately shrinks its search window, thinking, "Great, I don't need to look at anything lower than 3!"
The Result: Fail. The authors found a specific scenario (a "counterexample") where this aggression backfired.
- The Trap: The computer saw a note saying "Value is at least 3." It used this to stop looking at a branch that actually contained a value of 1 (which was better for the opponent). Because it stopped looking, it missed the better move and returned a wrong answer.
- The Proof: The computer could not produce a "Witness" for its answer. It was like a detective claiming to have solved a case but refusing to show the evidence because they stopped looking too early.

Why This Matters

This paper is like a safety inspector for the "black box" of game AI.

It shows that formal verification (using math to prove code is correct) is possible even for these complex, optimized algorithms.
It reveals that small changes in how an algorithm handles "sticky notes" can lead to big errors.
It provides a new standard (the "Witness") for how we should judge if a game AI is actually playing correctly, rather than just getting lucky.

In a nutshell: The authors built a mathematical microscope to inspect game-playing code. They proved one popular method is safe and sound, but they caught another popular method making a subtle, dangerous mistake by trusting its own notes too quickly. This ensures that the AI we play against is playing by the rules of logic, not just guessing.

1. Problem Statement

Minimax algorithms, particularly those enhanced with alpha-beta pruning and transposition tables (TT), are the backbone of classical game-playing engines (e.g., chess, checkers). Despite their ubiquity, these algorithms are notoriously difficult to reason about due to:

Subtlety and Optimization: They rely on complex heuristics and aggressive pruning to improve efficiency.
Depth-Limited Search: Unlike theoretical depth-unlimited search, practical engines use depth limits. This creates "truncated" trees where cached results from deeper searches in different parts of the tree are reused.
Semantic Ambiguity: The interaction between cached values (stored at varying depths and under different search windows) and the current search context breaks the simple tree-traversal semantics used to justify standard minimax correctness.
Testing Limitations: Non-obvious errors caused by these interactions are difficult to detect through testing alone, as they often depend on specific sequences of table hits and pruning conditions.

The paper addresses the lack of a rigorous formal foundation for verifying the correctness of these depth-limited, transposition-table-based algorithms.

2. Methodology

The authors utilize the Dafny verification system, a programming language and verifier based on Floyd-Hoare logic, to formally verify imperative implementations of minimax and negamax algorithms.

Key Methodological Innovations:

Witness-Based Correctness Criterion:
The core challenge is defining what "correct" means when a search reuses cached results from different depths. The authors introduce a witness-based correctness criterion.
- Concept: A returned value is correct if there exists a "witness" tree—an explicit expansion of the truncated game tree that merges the current search path with the subtrees implied by reused transposition table entries.
- Formal Definition: A result is valid if there exists a witness $u'$ $u^{'}$ such that:
  1. $u'$ is a subtree of the original tree $u$ .
  2. $u'$ contains the complete depth- $d$ truncation of $u$ .
  3. $u'$ respects an "all-or-none" child inclusion rule (no arbitrary subsets of children).
  4. The algorithm's returned value matches the negamax alpha-beta result computed on the witness $u'$ .
Modeling Transposition Tables:
The authors model the TT as a partial map from nodes to entries containing a value, depth, and flag (Exact, Lower Bound, or Upper Bound). They adopt a permissive model where table contents can change arbitrarily (simulating hash collisions and overwrites) as long as every entry in the table is justified by some valid witness.
Implementation:
They translated pseudocode for standard Minimax, Negamax, and two specific TT-based variants into Dafny. The verification process involved defining loop invariants, pre/post-conditions, and specific lemmas to handle the complex quantifiers inherent in game tree structures.

3. Key Contributions

Formal Definition of Witness-Based Correctness: The paper introduces a novel, flexible correctness criterion that accounts for the complex interplay between depth-limited search, alpha-beta pruning, and transposition table reuse. This moves beyond simple execution traces to structural properties of expanded game trees.
Mechanized Verification of NegamaxTTW: The authors successfully provided a fully mechanized correctness proof for NegamaxTTW, a variant commonly found in community resources (e.g., Wikipedia). This is the first formal proof of correctness for a depth-limited negamax search with alpha-beta pruning and transposition tables.
Discovery of a Counterexample for NegamaxTTM: The authors attempted to verify NegamaxTTM (a variant based on Marsland's work). The verification failed, leading to the construction of a concrete counterexample. This counterexample demonstrates that NegamaxTTM can return values that violate the witness-based correctness criterion.
Comparative Analysis: The paper provides a detailed technical comparison explaining why one algorithm works and the other fails, highlighting subtle differences in table lookup strategies and window management.

4. Results

Success: NegamaxTTW

Verification: The Dafny verifier successfully proved the correctness of NegamaxTTW in approximately 4 seconds.
Mechanism: This algorithm uses a conservative table lookup strategy. It only returns a cached value if it immediately guarantees a cutoff (i.e., the cached value is strictly outside the current alpha-beta window). If the cached value does not guarantee a cutoff, the algorithm discards it and performs a full search. This conservative approach ensures that a valid witness tree always exists.

Failure: NegamaxTTM

Counterexample: The authors identified a scenario where NegamaxTTM returns an incorrect value.
- Scenario: A node $v$ is searched at depth 4 with a narrow window $(0, 2)$ , returning a lower bound of 3. Later, $v$ is searched at depth 2 with a wider window $(0, 5)$ .
- The Flaw: NegamaxTTM reuses the lower bound (3) from the previous search to narrow the current window to $(3, 5)$ . This premature narrowing causes the algorithm to prune a branch that would have yielded a better value (1), resulting in a return value of 2.
- Violation: No valid witness tree exists that justifies the return value of 2. The algorithm effectively "hid" a better move by reusing a bound computed under different constraints.
Root Cause: The deviation lies in the Table Lookup phase. NegamaxTTM uses stored bounds to shrink the search window, which is unsafe when the bound was computed under a different (narrower) window.

5. Significance and Impact

Rigorous Foundation for Game AI: The work provides the first formal semantic foundation for reasoning about the correctness of depth-limited search with transposition tables, a critical component of modern game engines.
Validation of Common Practices: By verifying NegamaxTTW, the paper confirms that the "Wikipedia-style" implementation is mathematically sound under the proposed criterion.
Exposure of Subtle Bugs: The counterexample for NegamaxTTM demonstrates that even well-known algorithms from literature can contain subtle logical flaws that are invisible to testing but fatal to formal correctness. It highlights the danger of reusing bounds across different search windows without strict conditions.
Tooling Demonstration: The paper showcases Dafny's capability to handle complex, stateful, recursive algorithms with non-trivial invariants, serving as a blueprint for verifying other AI search algorithms (e.g., SSS*, MTD(f)).
Open Source: All artifacts, including Dafny proofs and executable Python implementations, are publicly available, fostering reproducibility and further research.

In conclusion, the paper establishes that while formal verification is challenging for optimized game search algorithms, it is feasible and essential. It proves that specific algorithmic variations (like NegamaxTTW) are correct while exposing critical flaws in others (NegamaxTTM), emphasizing the need for precise semantic models in the development of game-playing engines.