Spielbaum – Enzyklopädie

In der Spieltheorie ist ein Spielbaum ein gerichteter Graph, dessen Knoten Positionen in einem Spiel und dessen Kanten Bewegungen sind. Der vollständige Spielbaum für ein Spiel ist der Spielbaum, der an der Anfangsposition beginnt und alle möglichen Züge von jeder Position enthält. Der vollständige Baum ist derselbe Baum wie der, der aus der Spieldarstellung in ausgedehnter Form erhalten wurde.

Die ersten beiden Lagen des Spielbaums für Tic-Tac-Toe.

Das Diagramm zeigt die ersten beiden Ebenen oder Lagen im Spielbaum für Tic-Tac-Toe. Die Rotationen und Reflexionen der Positionen sind äquivalent, so dass der erste Spieler drei Bewegungsmöglichkeiten hat: in der Mitte, am Rand oder in der Ecke. Der zweite Spieler hat zwei Auswahlmöglichkeiten für die Antwort, wenn der erste Spieler in der Mitte gespielt hat, ansonsten fünf Auswahlmöglichkeiten. Und so weiter.

Die Anzahl der Blattknoten im gesamten Spielbaum gibt die Anzahl der möglichen unterschiedlichen Arten an, auf die das Spiel gespielt werden kann. Zum Beispiel hat der Spielbaum für Tic-Tac-Toe 255.168 Blattknoten.

Spielbäume sind für die künstliche Intelligenz wichtig, da eine Möglichkeit, den besten Zug in einem Spiel auszuwählen, darin besteht, den Spielbaum mit einer großen Anzahl von Baumsuchalgorithmen zu durchsuchen, kombiniert mit Minimax-ähnlichen Regeln, um den Baum zu beschneiden. Der Spielbaum für Tic-Tac-Toe ist leicht zu durchsuchen, aber die vollständigen Spielbäume für größere Spiele wie Schach sind viel zu groß, um gesucht zu werden. Stattdessen durchsucht ein Schachspielprogramm einen Teilspielbaum : Typischerweise so viele Lagen von der aktuellen Position, wie es in der verfügbaren Zeit suchen kann. Mit Ausnahme von "pathologischen" Wildbäumen [1] (die in der Praxis recht selten zu sein scheinen) verbessert eine Erhöhung der Suchtiefe (d. H. Der Anzahl der durchsuchten Lagen) im Allgemeinen die Chance, den besten Zug zu wählen.

Zwei-Personen-Spiele können auch als und-oder Bäume dargestellt werden. Damit der erste Spieler ein Spiel gewinnt, muss für alle Züge des zweiten Spielers ein Gewinnzug vorhanden sein. Dies wird im und-oder-Baum dargestellt, indem Disjunktion verwendet wird, um die alternativen Züge des ersten Spielers darzustellen, und Konjunktion verwendet wird, um alle Züge des zweiten Spielers darzustellen.

Lösen von Spielbäumen Bearbeiten

Deterministische Algorithmusversion Bearbeiten

Ein beliebiger Spielbaum, der vollständig eingefärbt wurde [19659003] Mit einem vollständigen Spielbaum ist es möglich, das Spiel "zu lösen" – das heißt, eine Folge von Zügen zu finden, die entweder der erste oder der zweite Spieler ausführen kann, um das bestmögliche Ergebnis für diesen Spieler zu erzielen (normalerweise ein Gewinn) oder ein Unentschieden). Der Algorithmus (der allgemein als Rückwärtsinduktions- oder retrograde Analyse bezeichnet wird) kann rekursiv wie folgt beschrieben werden.

  1. Färben Sie die letzte Lage des Spielbaums so, dass alle Gewinne für Spieler 1 in eine Richtung gefärbt werden (Blau im Diagramm), alle Gewinne für Spieler 2 in eine andere Richtung gefärbt werden (Rot im Diagramm), und alle Unentschieden sind gefärbt ein dritter Weg (grau im Diagramm).
  2. Schauen Sie sich die nächste Lage an. Wenn es einen Knoten gibt, der gegenüber dem aktuellen Spieler farbig ist, färben Sie diesen Knoten auch für diesen Spieler. Wenn alle unmittelbar unteren Knoten für denselben Spieler gefärbt sind, färben Sie diesen Knoten auch für denselben Spieler. Andernfalls färben Sie diesen Knoten mit einer Krawatte.
  3. Wiederholen Sie diesen Vorgang für jede Lage und bewegen Sie sich nach oben, bis alle Knoten gefärbt sind. Die Farbe des Wurzelknotens bestimmt die Art des Spiels.

Das Diagramm zeigt einen Spielbaum für ein beliebiges Spiel, der mit dem obigen Algorithmus eingefärbt wurde.

Es ist normalerweise möglich, ein Spiel (in diesem technischen Sinne von "lösen") nur mit einer Teilmenge des Spielbaums zu lösen, da in vielen Spielen ein Zug nicht analysiert werden muss, wenn es einen anderen Zug gibt, der für das Spiel besser ist Der gleiche Spieler (zum Beispiel kann Alpha-Beta-Beschneiden in vielen deterministischen Spielen verwendet werden).

Jeder Teilbaum, der zum Lösen des Spiels verwendet werden kann, ist als Entscheidungsbaum bekannt, und die Größen von Entscheidungsbäumen verschiedener Formen werden als Maß für die Komplexität des Spiels verwendet. [2]

Version mit randomisierten Algorithmen [19659009] [ edit ]

Randomisierte Algorithmen können zum Lösen von Spielbäumen verwendet werden. Diese Art der Implementierung bietet zwei Hauptvorteile: Schnelligkeit und Praktikabilität. Während eine deterministische Version des Lösens von Spielbäumen in Ο ( n ) durchgeführt werden kann, hat der folgende randomisierte Algorithmus eine erwartete Laufzeit von θ ( n 0,792 ) . Darüber hinaus ist es praktisch, weil zufällige Algorithmen in der Lage sind, "einen Feind zu vereiteln", was bedeutet, dass ein Gegner das System der Spielbäume nicht schlagen kann, indem er den Algorithmus kennt, der zum Lösen des Spielbaums verwendet wird, da die Reihenfolge des Lösens zufällig ist.

Das Folgende ist eine Implementierung des Lösungsalgorithmus für zufällige Spielbäume: [3]

 def   gt_eval_rand  ( u ): 
     '' 'Gibt True zurück, wenn dieser Knoten zu a ausgewertet wird gewinnen, sonst falsch '' '
     if   u .  leaf : 
         return   u .  win 
     else  : 
         random_children   =   ( gt_eval_rand  ( child )  
                            for   child   in   random_order  19659030] u .  Kinder ). 
         if   u .  op   ==   'OR' : 
             return   any  ( random_children ) 
         if   u .  op   ==   'AND' : [19659067] return   all  ( random_children ) 

Der Algorithmus verwendet die Idee des "Kurzschließens": wenn die Wurzel Knoten wird als Operator " OR " betrachtet, und sobald einer True gefunden wurde, wird die Wurzel als True klassifiziert. Wenn umgekehrt der Wurzelknoten als " AND " -Operator betrachtet wird, wird die Wurzel als False klassifiziert, sobald ein False gefunden wurde.

Siehe auch [ Bearbeiten ]

Bearbeiten [ Bearbeiten

Weiterführende Literatur Bearbeiten

Leave a Reply

Your email address will not be published. Required fields are marked *