Formal Verification of Minimax Algorithms
summary
Formal verification uses Dafny to prove correctness of negamax variants with alpha‑beta pruning, depth limits, and transposition tables; the key contribution is a witness‑based correctness criterion that requires a corresponding game tree. The Wikipedia-style algorithm verifies (about 800 lines verified in 4s and Python code available), while the Marsland variant violates the criterion and a concrete counterexample is constructed showing its returned value has no witness.
AI-written summary · about