Dafny-Tool beweist Korrektheit von Minimax-Algorithmen
In einer neuen Veröffentlichung auf arXiv (2509.20138v1) demonstriert ein Forschungsteam, wie das Dafny-Verifikationssystem die Korrektheit einer Vielzahl von Minimax-Suchalgorithmen nachweisen kann. Dazu gehören Varianten mit Alpha‑Beta‑Pruning sowie mit Transpositions‑Tabellen.
Besonders hervorzuheben ist die Einführung eines „Witness‑Based“-Korrektheitskriteriums für die Tiefenbegrenzte Suche mit Transpositions‑Tabellen. Dieses Kriterium wurde erfolgreich auf zwei repräsentative Algorithmen angewendet und liefert einen klaren Beweis für deren Richtigkeit.
Alle Verifikationsartefakte – inklusive der formalen Beweise und der zugehörigen Python‑Implementierungen – sind öffentlich zugänglich. Damit bietet die Arbeit einen wertvollen Beitrag für Entwickler und Forscher, die robuste KI‑Suchalgorithmen benötigen.