:If Sie suchen 'nach Spielbaum, weil er in der Spieltheorie (nicht kombinatorische Spieltheorie) verwendet wird, sieh bitte Spiel der Umfassenden Form.

In der Spieltheorie ist ein Spielbaum ein geleiteter Graph, dessen Knoten Positionen in einem Spiel sind, und dessen Ränder Bewegungen sind. Der ganze Spielbaum für ein Spiel ist der Spielbaum, der an der anfänglichen Position anfängt und alle möglichen Bewegungen von jeder Position enthält; der ganze Baum ist derselbe Baum wie das, das bei der Spieldarstellung der umfassenden Form erhalten ist.

Das Diagramm zeigt die ersten zwei Niveaus oder Falten im Spielbaum für tic-tac-toe. Wir denken alle Folgen und Nachdenken von Positionen als, gleichwertig zu sein, so hat der erste Spieler drei Wahlen der Bewegung: im Zentrum, am Rand, oder an der Ecke. Der zweite Spieler hat zwei Wahlen für die Antwort, wenn der erste Spieler im Zentrum, sonst fünf Wahlen gespielt hat. Und so weiter.

Die Zahl von Blatt-Knoten im ganzen Spielbaum ist die Zahl von möglichen verschiedenen Weisen, wie das Spiel gespielt werden kann. Zum Beispiel hat der Spielbaum für tic-tac-toe 26,830 Blatt-Knoten.

Spielbäume sind in der künstlichen Intelligenz wichtig, weil eine Weise, die beste Bewegung in einem Spiel aufzupicken, den Spielbaum mit dem minimax Algorithmus oder seinen Varianten suchen soll. Der Spielbaum für tic-tac-toe ist leicht auffindbar, aber die ganzen Spielbäume für größere Spiele wie Schach sind viel zu groß, um zu suchen. Statt dessen sucht ein schachspielendes Programm einen teilweisen Spielbaum: Normalerweise so viele Falten von der aktuellen Position, wie es in der verfügbaren Zeit suchen kann. Abgesehen vom Fall von "pathologischen" Spielbäumen (die scheinen, in der Praxis ziemlich selten zu sein), die Suchtiefe (d. h., die Zahl von Falten gesucht) vergrößernd, verbessert allgemein die Chance, die beste Bewegung aufzupicken.

Zwei-Personen-Spiele können auch als und - oder Bäume vertreten werden. Für den ersten Spieler, um ein Spiel zu gewinnen, dort muss eine Gewinnen-Bewegung für alle Bewegungen des zweiten Spielers bestehen. Das wird in und - oder Baum durch das Verwenden der Trennung vertreten, um die alternativen Bewegungen des ersten Spielers und das Verwenden der Verbindung zu vertreten, um alle Bewegungen des zweiten Spielers zu vertreten.

Das Lösen von Spielbäumen

Mit einem ganzen Spielbaum ist es möglich, das Spiel "zu lösen" - das heißt, finden eine Folge von Bewegungen, denen entweder der erste oder zweite Spieler folgen kann, der entweder einen Gewinn oder Band versichern wird. Der Algorithmus (der allgemein rückwärts gerichtete Induktion oder rückläufige Analyse genannt wird) kann rekursiv wie folgt beschrieben werden.

:#Color wird die Endfalte des Spielbaums, so dass alle Gewinne für den Spieler 1 einen Weg (Blau im Diagramm), alle Gewinne für den Spieler 2 gefärbt werden, einen anderen Weg (Rot im Diagramm) gefärbt, und alle Bande werden einen dritten Weg (Grau im Diagramm) gefärbt.

:#Look an der folgenden Falte. Wenn dort besteht, färbt ein Knoten gefärbt gegenüber als der aktuelle Spieler, diesen Knoten für diesen Spieler ebenso. Wenn alle sofort niedrigeren Knoten für denselben Spieler gefärbt werden, diesen Knoten für denselben Spieler ebenso färben. Färben Sie sonst diesen Knoten ein Band.

:#Repeat für jede Falte, sich aufwärts, bis bewegend, werden alle Knoten gefärbt. Die Farbe des Wurzelknotens wird die Natur des Spiels bestimmen.

Das Diagramm zeigt einen Spielbaum für ein willkürliches Spiel, gefärbt das Verwenden des obengenannten Algorithmus.

Es ist gewöhnlich möglich, ein Spiel zu lösen (in diesem technischen Sinn dessen "lösen") das Verwenden nur einer Teilmenge des Spielbaums, seitdem in vielen Spielen braucht eine Bewegung nicht analysiert zu werden, wenn es eine andere Bewegung gibt, die für denselben Spieler besser ist (zum Beispiel, kann Beschneidung des Alpha-Betas in vielen deterministischen Spielen verwendet werden).

Jeder Subbaum, der verwendet werden kann, um das Spiel zu lösen, ist als ein Entscheidungsbaum bekannt, und die Größen von Entscheidungsbäumen von verschiedenen Gestalten werden als Maßnahmen der Spielkompliziertheit verwendet.

Siehe auch

• Alpha-Beta, das beschneidet
• Umfassendes Form-Spiel
• Zahl von Shannon
• Spielkompliziertheit

Referenzen

Weiterführende Literatur

• Judea Pearl, Heuristik, Addison-Wesley, 1984