WPNS

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.

Kernidee und Abgrenzung zu PNS/df-pn

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:

• PNS/df-pn: An einem UND-Knoten wird die Beweiszahl als die Summe der Beweiszahlen aller Kindknoten berechnet. Dies kann bei DAGs zu einer Überbewertung führen, da identische Teilbäume mehrfach gezählt werden (Double-Counting)
• WPNS: An einem Und-Knoten wird die Schwache Proof-Zahl (eng: Weak Proof-Number) berechnet. Sie ergibt sich aus der maximalen Proof-Zahl eines einzelnen Kindknotens plus der Anzahl der verbleibenden Geschwisterknoten (also Anzahl der Kindknoten -1).

Die neue Formel für die Schwache Proof-Zahl p(n) eines UND-Knotens n mit k Nachfolgern lautet somit

p(n) = \max_{1 \le i \le k} p(n_i) + (k-1).

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.

Leistung

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.

Literaturliste