Stub-Warnung: Dieser Artikel ist sehr kurz und behandelt nur die grundlegendsten Aspekte des Themas.
Der Artikel zu Proof-Number Search enthält Erläuterungen für einige der Begriffe und Konzepte, die auch für diesen Artikel relevant sind. Zur besseren Klarheit empfiehlt es sich deswegen, den Artikel zu PNS zuerst zu lesen.
Weak Proof-Number Search (kurz WPNS) ist ein Suchalgorithmus für UND-/ODER-Bäume, der spieltheoretische Werte in komplexen Domänen wie Shogi oder Othello beweist.
Der Algorithmus wurde als Verbesserung des bekannten Proof-Number Search (PNS) und seiner speichereffizienten, tiefenbasierten Variante df-pn entwickelt. Hauptziel von WPNS ist es, das sogenannte "Double-Counting"-Problem" zu beheben, das beim Suchen in DAGs auftritt und die Laufzeiteffizienz von PNS und df-pn beeinträchtigen kann.
Dieser Artikel basiert auf den in diesem [1] Paper vorgestellten Untersuchungen.
Wie seine Vorgänger nutzt WPNS Proof- und Disproof-Zahlen, um den Suchprozess zu steuern. Der entscheidende Unterschied liegt in der Berechnung der Beweiszahlen an UND-Knoten:
Die neue Formel für die Schwache Proof-Zahl eines UND-Knotens mit Nachfolgern lautet somit
Diese Berechnung ist eine Heuristik, die die tatsächliche Beweiszahl tendenziell unterschätzt, aber weniger anfällig für das Double-Counting-Problem ist.
Dieser Ansatz kombiniert die Stärken von PNS (Nutzung von Beweiszahlen) mit denen des Branch Number Search (BNS) Algorithmus, der den Verzweigungsfaktor als primäre Heuristik nutzt.
Experimente in Tsume-Shogi (japanisches Schachmatt-Problem) und Othello haben gezeigt, dass die Leistung von WPNS stark vom jeweiligen Anwendungsfall abhängt:
Tsume-Shogi: Bei Problemen mit kürzeren Lösungen war df-pn leicht überlegen. Bei Problemen mit längeren Lösungen zeigte WPNS eine bessere Leistung. Generell übertrifft WPNS den BNS-Algorithmus deutlich.
Othello: In diesem Spiel mit einem höheren durchschnittlichen Verzweigungsfaktor (ca. 10 im Vergleich zu ca. 5 bei Shogi) übertrifft WPNS sowohl df-pn als auch BNS. Dies stützt die These, dass WPNS besonders bei Spielen mit hohen Verzweigungsfaktoren und häufigen DAGs vorteilhaft ist.
Ueda, T., Hashimoto, T., Hashimoto, J., & Iida, H. (2008). Weak proof-number search. In Computers and Games: 6th International Conference, CG 2008, Beijing, China, September 29-October 1, 2008. Proceedings 6 (pp. 157-168). Springer Berlin Heidelberg. ↩︎