Kombinatorische Spieltheorie hat mehrere Weisen, Spielkompliziertheit zu messen. Dieser Artikel beschreibt fünf von ihnen: Zustandraumkompliziertheit, Spielbaumgröße, Entscheidungskompliziertheit, Spielbaum-Kompliziertheit und rechenbetonte Kompliziertheit.

Maßnahmen der Spielkompliziertheit

Staatsraumkompliziertheit

Die Zustandraumkompliziertheit eines Spiels ist die Zahl von gesetzlichen von der anfänglichen Position des Spiels erreichbaren Spielpositionen.

Nützlich, wenn das zu hart ist, um zu rechnen, kann ein gebundener oberer häufig durch das Umfassen ungesetzlicher Positionen oder Positionen geschätzt werden, die im Laufe eines Spiels nie entstehen können.

Spielbaumgröße

Die Spielbaumgröße ist die Gesamtzahl von möglichen Spielen, die gespielt werden können: Es ist die Zahl von Blatt-Knoten im an der anfänglichen Position des Spiels eingewurzelten Spielbaum.

Der Spielbaum ist normalerweise gewaltig größer als der Zustandraum, weil dieselben Positionen in vielen Spielen durch das Bilden von Bewegungen in einer verschiedenen Ordnung vorkommen können (zum Beispiel, in einem tic-tac-toe Spiel mit zwei X und ein O auf dem Ausschuss, könnte diese Position auf zwei verschiedene Weisen je nachdem erreicht worden sein, wohin das erste X gelegt wurde). Ein für die Größe des Spielbaums gebundener oberer kann manchmal durch die Vereinfachung des Spiels in einem Weg geschätzt werden, der nur die Größe des Spielbaums vergrößert (zum Beispiel, durch das Erlauben ungesetzlicher Bewegungen), bis es lenksam wird.

Jedoch für Spiele, wo die Zahl von Bewegungen nicht beschränkt wird (zum Beispiel durch die Größe des Ausschusses, oder durch eine Regel über die Wiederholung der Position) ist der Spielbaum unendlich.

Entscheidungsbäume

Die folgenden zwei Maßnahmen verwenden die Idee von einem Entscheidungsbaum. Ein Entscheidungsbaum ist ein Subbaum des Spielbaums mit jeder Position, die mit dem "Spieler Gewinne etikettiert ist," "gewinnt Spieler B" oder "gezogen", wenn, wie man beweisen kann, diese Position diesen Wert (das Annehmen besten Spieles durch beide Seiten) durch das Überprüfen einziger weiterer Positionen im Graphen hat. (Endpositionen können direkt etikettiert werden; eine Position mit dem Spieler, um sich zu bewegen, kann "Spieler Gewinne" etikettiert werden, wenn eine Nachfolger-Position ein Gewinn für A, oder etikettiert "Gewinne des Spielers B" ist, wenn alle Nachfolger-Positionen Gewinne für B sind, oder etikettiert "ziehen", wenn alle Nachfolger-Positionen entweder gezogen werden oder Gewinne für B. Und entsprechend für Positionen mit B, um sich zu bewegen.)

Entscheidungskompliziertheit

Die Entscheidungskompliziertheit eines Spiels ist die Zahl von Blatt-Knoten im kleinsten Entscheidungsbaum, der den Wert der anfänglichen Position gründet. Solch ein Baum schließt alle möglichen Entscheidungen für den Spieler ein, sich zweit zu bewegen, aber nur eine Möglichkeit für jede Entscheidung für den Spieler, der das Spiel anfängt.

Spielbaum-Kompliziertheit

Die Spielbaum-Kompliziertheit eines Spiels ist die Zahl von Blatt-Knoten im kleinsten Entscheidungsbaum der vollen Breite, der den Wert der anfänglichen Position gründet. Ein Baum der vollen Breite schließt alle Knoten an jeder Tiefe ein.

Das ist eine Schätzung der Zahl von Positionen, die wir in einer Minimax-Suche würden bewerten müssen, um den Wert der anfänglichen Position zu bestimmen.

Es ist sogar hart, die Spielbaum-Kompliziertheit zu schätzen, aber für einige Spiele kann ein tiefer gebundener angemessener durch die Aufhebung des durchschnittlichen sich verzweigenden Faktors des Spiels zur Macht der Zahl von Falten in einem durchschnittlichen Spiel gegeben werden.

Rechenbetonte Kompliziertheit

Die rechenbetonte Kompliziertheit eines Spiels beschreibt die asymptotische Schwierigkeit eines Spiels, weil es willkürlich groß, ausgedrückt in der großen O Notation oder als Mitgliedschaft in einer Kompliziertheitsklasse wächst. Dieses Konzept gilt für besondere Spiele, aber eher für Spiele nicht, die so verallgemeinert worden sind, können sie willkürlich groß normalerweise gemacht werden, indem sie sie auf einem n-by-n Ausschuss spielen. (Aus dem Gesichtswinkel von der rechenbetonten Kompliziertheit ist ein Spiel auf einer festen Größe des Ausschusses ein begrenztes Problem, das in O (1), zum Beispiel durch eine Nachschlagetabelle von Positionen bis die beste Bewegung in jeder Position gelöst werden kann.)

Beispiel: tic-tac-toe

Für tic-tac-toe ist ein einfacher für die Größe des Zustandraums gebundener oberer 3 = 19,683. (Es gibt drei Staaten für jede Zelle und neun Zellen.) Schließt diese Zählung viele ungesetzliche Positionen, wie eine Position mit fünf Kreuzen und keiner Null, oder eine Position ein, in der beide Spieler eine Reihe drei haben. Eine sorgfältigere Zählung, diese ungesetzlichen Positionen entfernend, gibt 5,478. Und wenn Folgen und Nachdenken von Positionen identisch betrachtet werden, gibt es nur 765 im Wesentlichen verschiedene Positionen.

Ein einfacher für die Größe des Spielbaums gebundener oberer ist 9! = 362,880. (Es gibt neun Positionen für die erste Bewegung, acht für das zweite und so weiter.) Schließt das ungesetzliche Spiele ein, die weitergehen, nachdem eine Seite gewonnen hat. Eine sorgfältigere Zählung gibt 255,168 mögliche Spiele. Wenn Folgen und Nachdenken von Positionen als dasselbe betrachtet werden, gibt es nur 26,830 mögliche Spiele.

Die rechenbetonte Kompliziertheit von tic-tac-toe hängt ab, wie es verallgemeinert wird. Eine natürliche Generalisation ist zur M, n, den K-Spielen: Gespielt auf einer M durch den n Ausschuss mit dem Sieger, der der erste Spieler ist, um k hintereinander zu bekommen. Es ist sofort klar, dass dieses Spiel in DSPACE (mn) durch die Suche des kompletten Spielbaums gelöst werden kann. Das legt es in die wichtige Kompliziertheitsklasse PSPACE. Mit noch etwas Arbeit, wie man zeigen kann, ist es PSPACE-abgeschlossen.

Kompliziertheiten von einigen wohl bekannten Spielen

Wegen der großen Größe von Spielkompliziertheiten gibt dieser Tisch die Decke ihres Logarithmus, um 10 zu stützen. Alle folgenden Zahlen sollten mit der Verwarnung betrachtet werden: Anscheinend geringe Änderungen zu den Regeln eines Spiels können die Zahlen ändern (die häufig Überschlagsrechnungen irgendwie sind) durch enorme Faktoren, die leicht viel größer sein könnten als die gezeigten Zahlen.

Siehe auch

• Gehen Sie und Mathematik
• Gelöstes Spiel
• Zahl von Shannon
• Liste von NP-complete Spielen und Rätseln
• Liste von PSPACE-ganzen Spielen und Rätseln

Zeichen und Verweisungen

Links

• Die rechenbetonte Kompliziertheit von David Eppstein von Spielen und Rätseln