Proof-Number-Suche

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, 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.

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 Beweis bzw. Gegenbeweis zu erreichen.

Durch Auswahl der meistbeweisenden bzw. meistwiderlegenden 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[Bearbeiten]

  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[Bearbeiten]