Formal Verification of Minimax Algorithms

Wieger Wesselink, Kees Huizing, Huub van de Wetering · 2025

Read Formal Verification of Minimax Algorithms by Wieger Wesselink, Kees Huizing, Huub van de Wetering (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-20138.txt.

Description

Wieger Wesselink, Kees Huizing, and Huub van de Wetering wrote this 2025 arXiv paper on game-playing software. Minimax search with alpha-beta pruning sits at the heart of classical game engines. These routines are heavily optimized and notoriously subtle. Small errors can hide from ordinary testing for years.

Using the Dafny verification system, the authors formally verified a family of minimax algorithms. The set includes versions with pruning and with transposition tables that cache past positions. For depth-limited search, they propose a witness-based rule for when a returned value is justified. One practical variant passed a complete machine-checked proof. For another, they built a concrete counterexample that breaks the proposed rule. All proofs and runnable Python versions are public.

Catalog record

CREATORWieger Wesselink, Kees Huizing, Huub van de Wetering
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-20138

Browse the full library · About the Tower of Babel