Proof-Number-Suche
Proof-Number-Suche (kurz: PN-Suche) bzw. Beweiszahlsuche ist ein Spielbaum-Suchalgorithmus, der von Victor Allis, ursprünglich zur Lösung der Spiele Vier gewinnt und Qubic, erfunden wurde. Anwendungen sind hauptsächlich die Endspiellösung und Teilziele während des Spiels. Das Verfahren eignet sich besonders für Probleme, deren Lösung eine hohe Zahl an Zügen erfordern, auf die der verteidigende Spieler jeweils nur eine geringe Zahl an sinnvollen Erwiderungen hat (forcierte Züge). Während bei der klassischen Alpha-Beta-Suche der gesamte Spielbaum bis zu einer vorher festgelegten Tiefe ausgewertet wird, können bei der PN-Suche auch frühzeitig beweisende oder widerlegende Teilbäume gefunden werden, die zwar tief sind, aber wenig verzweigen. (Genauer: Für deren Beweis oder Widerlegung nur vergleichsweise wenig Terminalpositionen ausgewertet werden müssen.)
Algorithmus
Zur Anwendung des Algorithmus wird ein binäres Ziel definiert (z. B. Spieler am Zug gewinnt) und der Spielbaum in einen Und-Oder-Baum transformiert. Dies ist einfach möglich, indem maximierende Knoten als ODER-Knoten betrachtet werden und minimierende Knoten als UND-Knoten (Vgl. Minimax-Algorithmus).
Zahlen für den Beweis (Beweiszahlen, proof numbers) und Gegenbeweis (Widerlegzahlen, disproof numbers) von Knoten werden in den Knoten geführt und während der Suche aktualisiert. Sie sind definiert als untere Schranke der noch zu expandierenden Knoten, um einen Beweis bzw. Gegenbeweis zu erreichen. Für einen UND-Knoten berechnet sich die Beweiszahl als Summe der Beweiszahl aller Kinder-Knoten. (Um einen UND-Knoten zu beweisen müssen sämtliche Kinder-Knoten bewiesen werden.) Die Widerlegzahl ist das Minimum der Widerlegzahlen aller Kinder-Knoten. (Zur Widerlegung genügt die Widerlegung eines Kind-Knotens.) Entsprechend ergibt sich für einen ODER-Knoten die Beweiszahl als Minimum der Beweiszahlen aller Kinder und die Widerlegzahl als Summe der Widerlegzahlen aller Kinder. Für Endknoten, die nach den Regeln des Spiels bewiesen werden können, wird die Beweiszahl auf 0 und die Widerlegzahl auf ∞ gesetzt. Kann der Endknoten widerlegt werden, so ist die Beweiszahl ∞ und die Widerlegzahl 0. Innere Knoten des Suchbaums, die noch nicht expandiert sind, werden auf einen geschätzten Wert initialisiert, im einfachsten Fall beide Zahlen auf 1.
Schrittweise werden nun Endknoten expandiert, deren Beweis bzw. Widerlegung am ehesten zur Lösung des Wurzelknotens beiträgt. Die Heuristik, welche diesen sogenannten most proving node (MPN) auswählt, basiert auf den in jedem Knoten des Baums mitgeführten Beweis- und Widerlegzahlen: Ausgehend vom Wurzelknoten wird für jeden ODER-Knoten das Kind mit der kleinsten Beweiszahl gewählt, während man bei UND-Knoten zum Kind-Knoten mit der kleinsten Widerlegzahl absteigt. Der so erreichte Endknoten ist der MPN und wird im nächsten Schritt expandiert.
In einer Iteration werden folgende Punkte abgearbeitet:
- Auswahl eines MPN.
- Expansion. Für jeden gültigen Zug wird ein Kindknoten erstellt.
- Auswertung. Den neuen Kindknoten werden Beweis- und Widerlegzahlen zugeordnet.
- Aktualisierung. Die Beweis- und Widerlegzahlen aller Vorgängerknoten bis hin zur Wurzel werden neu berechnet.
Der Algorithmus bricht ab, wenn die Beweiszahl / Widerlegzahl des Wurzelknoten den Wert 0 hat und dieser damit bewiesen / widerlegt ist.
Erweiterungen
Ein entscheidender Nachteil der PN-Suche ist der Speicherverbrauch, welcher mit fortlaufender Suche kontinuierlich ansteigt. Die Komplexität der lösbaren Probleme ist deshalb durch den verfügbaren Arbeitsspeicher begrenzt. Es existieren jedoch Varianten, die diese Limitierung lockern und deutlich mehr Positionen bewerten können, z. B. PN^2, PDS-PN.[1]
Siehe auch
Literatur
- Akihiro Kishimoto, Mark H.M. Winands, Martin Müller, Jahn-Takeshi Saito: Game-Tree Search using Proof Numbers: The first twenty years. ICGA Journal pp. 3, 2012.
Quellen
- Mark H.M. Winands, Jos W.H.M. Uiterwijk, and H. Jaap van den Herik: PDS-PN: A New Proof-Number Search Algorithm. (PDF) In: Lecture Notes in Computer Science. 2003.