Proof-Number-Suche

Proof-Number-Suche (kurz: PN-Suche) bzw. Beweiszahlsuche ist ein Spielbaum-Suchalgorithmus, erfunden von Victor Allis, ursprünglich zur Lösung der Spiele Vier gewinnt, Qubic (1990). Anwendungen sind hauptsächlich in der Endspiel-Lösung und für Teilziele während des Spiels.

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) und Gegenbeweis (Widerlegzahlen) von Knoten (proof and disproof numbers) 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 (Gegen-)beweis zu erreichen.

Durch Auswahl der meist-beweisenden/meist-widerlegenden Knoten für die nächste Expansion wird eine effiziente Suche generiert.

Wegen der hohen Zahl der erzeugten Knoten ist die PN-Suche 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].

Quellen

1. ↑ 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.

Siehe auch

• Alpha-Beta-Suche
• Minimax-Regel