wiki.neuro.tu-berlin.de

proof-number search

Proof-Number Search (kurz PN-Search oder PNS) ist ein Algorithmus, der den spieltheoretischen Wert in Spielbäumen von zwei-Spieler-Spielen bestimmt.
Er wurde 1994 von L. Victor Allis, Maarten van der Meulen und H. Jaap van den Herik auf der Grundlage von conspiracy-number search (vorgestellt in den 80er-Jahren von McAllester[1][2]) entwickelt und in diesem [3] Paper vorgestellt, das diesem Wiki-Artikel als Grundlage dient.

Ansatz[3:1]

Um den spieltheoretischen Wert, den Ausgang des Spiels bei optimalem Spiel beider Parteien, zu ermitteln, wird zuerst eine Annahme über den Ausgang des Spiels getroffen. Daraufhin ist es das Ziel des Algorithmus, diese Annahme mit Hilfe der namensgebenden Proof- und Disproof-Zahlen schnellstmöglich zu beweisen oder zu widerlegen.

Das ist einfacher für Spiele mit binärem Ausgang, hier wird ein Sieg für die in der aktuellen Position ziehenden Partei angenommen.
Für Spiele mit mehrwertigem Ausgang, wie beispielsweise Awari oder Go mit Punktwertung, ist dies etwas komplizierter. Hier wird die Annahme getroffen, dass die ziehende Partei das Spiel mit mindestens k Punkten gewinnt, für ein gewähltes k (für genauere Betrachtung siehe unten).

UND-/ODER-Bäume

Spielbäume bestehen aus sog. UND- und ODER-Knoten, und werden deshalb auch als UND-/ODER-Bäume (engl: AND-/OR-Trees) bezeichnet.
Die Namen entsprechen dabei Min- und Max-Knoten aus Minimax, und hängen von der Partei ab, von der aus man den Spielbaum betrachtet. Will man den Spielwert aus Sicht von Weiß bestimmen, so sind alle Knoten, in denen Weiß zieht, ODER-Knoten, da nur für einen der Kindknoten eine Gewinnstrategie existieren muss.
Die Knoten, in denen Schwarz zieht, heißen UND-Knoten, da Schwarz hier in allen Kindknoten verlieren muss, damit Weiß gewinnt.

Theoretische Grundlagen[3:2]

Im folgenden werden einige für das Verständnis essentielle Grundlagen für den Algorithmus vorgestellt.

Vielversprechendster Knoten

Minimax verfolgt einen depth-first-Ansatz, durchläuft also die Knoten des Spielbaums in einer festgelegten Reihenfolge, um letztendlich den spieltheoretischen Wert zu ermitteln.

PN-Search dagegen setzt bei der Wahl des nächsten Knotens einen best-first-Ansatz. Hierbei wird gezielt derjenige Knoten ausgewählt, der im optimalen Fall am schnellsten dazu beiträgt, die anfangs getroffene Annahme zu beweisen oder zu widerlegen. Dieser Knoten wird als vielversprechendster Knoten (engl: most-proving node) bezeichnet.

Beispiel


Abb. 1 Beispielhafter Spielbaum mit vielversprechendstem Knoten h

In Position a ist Weiß am Zug, und hat zwei Zugmöglichkeiten die zu Position b und c führen, in denen Schwarz zieht.
h ist der vielversprechendste Knoten, denn sollte sich h als Gewinnposition für Weiß erweisen, hätte Weiß von Position a aus eine sicher zum Sieg führende Zugmöglichkeit und somit das Spiel gewonnen.
Der andere Teilbaum ist weniger vielversprechend, denn Weiß müsste sowohl in e als auch in f gewinnen. Da Schwarz in b am Zug ist, wäre nur in diesem Fall ein Sieg für Weiß garantiert.

Ist der aktuelle Knoten ein UND-Knoten, ist es einfacher, die Annahme zu widerlegen, als sie zu beweisen. Denn das kann durch einen einzelnen Kindknoten geschehen (der Beweis müsste mit allen Kindknoten geführt werden).

Proof-/Disproof-Zahlen

Um den aktuell vielversprechendsten Knoten zu finden, werden für jeden Knoten im Spielbaum Proof- und Disproof-Zahlen gespeichert, die den minimalen nötigen Aufwand beschreiben, um die Annahme zu beweisen/widerlegen. Einen neuen Knoten zu betrachten, wird dabei mir einer imaginären Aufwandseinheit berechnet.
Die beiden Zahlen können dabei als Paar (x,y) angegeben werden, wobei x die Proof- und y die Disproof-Zahl ist.

Die konkreten Proof- und Disproof-Zahlen hängen dabei von der Art des Knotens ab:

Beispiel


Abb. 2 beispielhafter Spielbaum mit eingezeichneten Proof- und Disproof-Zahlen

Nachdem ein Knoten expandiert wurde, werden die Proof-/Disproof-Zahlen im Baum aktualisiert. Der vielversprechendste Knoten wird dann mithilfe dieser Zahlen bestimmt.

Mehrwertige Spiele

Mehrwertige Spiele müssen gesondert betrachtet werden, da der Algorithmus in seiner Grundform nur für binäre Ergebnisse konzipiert ist. Hier kann nicht nur nach einem Sieg gesucht werden.

Um den Algorithmus anzuwenden, wird ein k aus dem Wertebereich der möglichen Spielausgänge gewählt. Anschließend wird das Spiel durch die folgenden Regeln so behandelt, als hätte es einen binären Ausgang:

Dadurch kann der Algorithmus wie bisher beschrieben angewendet werden.

Noch nicht beachtet wurde bis jetzt die Wahl von k.
Um den spieltheoretischen Wert ermitteln, können mit einer linearen oder binären Suche verschiedene Werte getestet und bewiesen/widerlegt werden. Dadurch kann der Spielausgang durch eine Folge von zwei-wertigen Analysen ermittelt und bewiesen werden.

Der Algorithmus im Detail[3:3]

Die folgenden Pseudocode-Blöcke beinhalten die wesentlichen Bestandteile des PNS-Algorithmus, und sind aus dem Paper übernommen.

Proof-/Disproof-Zahlen

Der folgende Pseudocode formalisiert die oben beschriebenen Regeln zur Berechnung der Proof-/Disproof-Zahlen für einen Knoten J. Der Wert v entspricht dabei der zu beweisenden Annahme (z.B. Sieg oder ein konkreter Punkwert).

if is_a_terminal_node(J) then
  	if evaluation_value_known then
    		if value(J) >= v then
      			proof(J) := 0
      			disproof(J) := infinity
    		else
      			proof(J) := infinity
            disproof(J) := 0
        endif
    else
        proof(J) := 1
        disproof(J) := 1
    endif
else if is_an_internal_node(J) then
    if max_node(J) then
        proof(J) := min of { proof(j) : j in childs(J) }
        disproof(J) := sum of { disproof(j) : j in childs(J) }
    else
        proof(J) := sum of { proof(j) : j in childs(J) }
        disproof(J) := min of { disproof(j) : j in childs(J) }
    endif
endif

den vielversprechendsten Knoten auswählen

Diese Funktion wählt den vielversprechendsten Knoten aus, indem sie vom Wurzelknoten J aus dem Pfad des geringsten Beweisaufwands anhand der Proof-/Disproof-Zahlen folgt.
Da bei gleicher Proof-/Disproof-Zahl kein Unterschied zwischen den verschiedenen Knoten ausgemacht werden kann, wird in diesem Fall das linkeste Kind (leftmost child) des Knotens ausgewählt.

function select_most_proving_node(J)
begin
    while is_an_internal_node(J) do
        if max_node(J) then
            J := leftmost_child_with_equal_proof_number(J)
        else
            J := leftmost_child_with_equal_disproof_number(J)
        endif
    done
    return J
end

Proof-/Disproof-Zahlen aktualisieren

Nachdem der vielversprechendste Knoten expandiert wurde, werden die (Dis-)Proof-Zahlen seiner Vorfahren durch diese Funktion aktualisiert.

procedure update_proof_numbers(J)
begin
    while J != NIL do
        if max_node(J) then
            proof(J) := min of { proof(j) : j in childs(J) }
            disproof(J) := sum of { disproof(j) : j in childs(J) }
        else
            proof(J) := sum of { proof(j) : j in childs(J) }
            disproof(J) := min of { disproof(j) : j in childs(J) }
        endif
        J := parent(J)
    done
end

PN-Search für zweiwertige Spielbäume

Dies ist die Hauptschleife des Algorithmus für zweiwertige Probleme. Sie startet mit einem Baum, der nur aus dem Wurzelknoten besteht.
In jeder Iteration wird der vielversprechendste Knoten ausgewählt und expandiert, und die (Dis-)Proof-Zahlen werden aktualisiert. Die Schleife endet, sobald die Annahme für den Wurzelknoten bewiesen (proof(root) == 0) oder widerlegt (disproof(root) == 0) ist.

function two_valued_pn_search
begin
    create_root(root)
    while proof(root) != 0 and disproof(root) != 0 do
        most_proving := select_most_proving_node(root)
        expand_node(most_proving)
        update_proof_numbers(most_proving)
    done
    if proof(root) = 0 then
        return v
    else
        return not v
    endif
end

PN-Search für mehrwertige Spielbäume

Der Pseudocode für mehrwertige Spiele implementiert eine binäre Suche, um den exakten Spielwert zu finden. Dabei wird der two_valued_pn_search-Algorithmus wiederholt aufgerufen, um die untere (lower) und obere (upper) Schranke des möglichen Spielwerts schrittweise einzugrenzen, bis der exakte Wert feststeht.

function multi_valued_pn_search
begin
    while lower < upper do
        v := integer_greater_or_equal((lower + upper) / 2)
        if two_valued_pn_search = v then
            lower := v
        else
            upper := v - 1
        endif
    done
    return upper
end

Optimierungen[3:4]

Proof-Number Search behält für den Suchprozess, den gesamten Suchbaum im Speicher, da jeder Knoten, der noch nicht expandiert wurde, als vielversprechendster Knoten ausgewählt wurde. In dieser Hinsicht sind depth-first Algorithmen wie die α-β-Suche effizienter.
Die folgenden Techniken können jedoch dabei helfen, den Speicherbedarf zu reduzieren:

Zudem kann die Laufzeit durch folgende kleine Optimierungen verbessert werden:

Evaluation[3:5]

Im Vergleich zu α-β-Suche ist die Anzahl der besuchten Knoten bei PN-Search deutlich kleiner, wenn der Suchbaum eine bestimmte Größe erreicht.
Der Hauptnachteil liegt im erhöhten Speicherbedarf, da der ganze Suchbaum im Speicher gehalten werden muss. Das kann bei großen Suchbäumen problematisch sein.

Weiterführend

Proof-Number Search bildet die Grundlage für einige erweiterte Algorithmen. In diesem Wiki sind dazu die Varianten df-pn und WPNS zu finden.

Bildquellen

Abb. 1: übernommen aus [3:6] (Figure 1)
Abb. 2: übernommen aus [3:7] (Figure 5)

Literaturliste

  1. McAllester, D. A. (1985). A new procedure for growing mini-max trees (Technical Report). MIT Artificial Intelligence Laboratory. ↩︎

  2. McAllester, D. A. (1988). Conspiracy numbers for min-max search. Artificial Intelligence, 35(3), 287-310. ↩︎

  3. Allis, L. V., Van Der Meulen, M., & Van Den Herik, H. J. (1994). Proof-number search. Artificial Intelligence, 66(1), 91-124. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎