In der kombinatorischen Spieltheorie gibt es mehrere Möglichkeiten, die Spiel-Komplexität zu messen. Im Folgenden werden diese Metriken beschrieben: Zustandsraum-Komplexität Spielbaumgröße Entscheidungs-Komplexität Spielbaum-Komplexität Rechenaufwand
Metriken der Spiel-Komplexität Die Zustandsraum-Komplexität eines Spiels ist die Anzahl von erreichbaren Stellungen von der Ausgangsposition des Spieles aus. Wenn diese zu schwierig zu errechnen ist, kann oft eine obere Schranke bestimmt werden, indem man unzulässige Stellungen oder solche, die im Spielverlauf nicht erreicht werden können, mitzählt. Die Spielbaumgröße ist die Gesamtzahl der möglichen Spielverläufe. Sie entspricht der Anzahl der Blattknoten des Spielbaumes. Der Spielbaum ist normalerweise erheblich größer als der Zustandsraum, da hier dieselben Stellungen in verschiedenen Spielen auftreten, indem Züge in unterschiedlicher Reihenfolge ausgeführt werden (z. B. beim Tic-Tac-Toe-Spiel, mit zwei X und einem O, kann die Stellung auf zwei verschiedene Arten erreicht werden, abhängig davon, wo das erste X platziert wurde). Eine obere Schranke für die Größe des Spielbaums kann manchmal durch Vereinfachungen des Spiels, die die Spielbaumgröße nur erhöhen (z. B. unzulässige Spielzüge erlauben), errechnet werden. Jedoch ist der Spielbaum für Spiele, bei denen die Anzahl der Züge nicht begrenzt ist (z. B. wegen der Brettgröße, oder wenn Stellungswiederholungen erlaubt sind), unendlich.
Die nächsten beiden Metriken basieren auf der Idee eines Entscheidungsbaums. Ein Entscheidungsbaum ist ein Unterbaum des Spielbaums, bei dem jede Stellung mit "Spieler A gewinnt", "Spieler B gewinnt" oder "weiterer Zug" markiert wurde. Endstellungen werden dabei direkt markiert. Eine Stellung, mit der Spieler A eine "Spieler A gewinnt"-Stellung erreichen kann, wird ebenfalls mit "Spieler A gewinnt" markiert. Ebenso wird für Spieler B verfahren.
Die Entscheidungskomplexität eines Spieles ist die Anzahl der Blattknoten im kleinsten Entscheidungsbaum, welcher die Markierung der Ausgangsstellung beibehält (z. B. "Spieler A gewinnt"). Ein solcher Baum enthält alle Entscheidungsmöglichkeiten für den zweiten Spieler, aber nur jeweils eine Möglichkeit für den Spieler, der das Spiel beginnt. Die Spielbaumkomplexität eines Spiels ist die Anzahl der Blattknoten im kleinsten Entscheidungsbaum in voller Breite, der den Wert der Ausgangsstellung beibehält. (Ein Baum in voller Breite enthält immer alle Knoten einer Tiefe.) Dies ist die Anzahl der Stellungen, die man in einem Minimax-Verfahren durchsuchen muss, um den Wert der Ausgangsstellung zu bestimmen. Es ist schwierig, die Spielbaum-Komplexität abzuschätzen. Aber für einige Spiele kann eine vernünftige untere Schranke gefunden werden, indem man den Verzweigungsfaktor mit der Anzahl der Halbzüge eines durchschnittlichen Spiels potenziert. Der komplexitätstheoretische Rechenaufwand eines Spiels beschreibt den asymptotischen Schwierigkeitsgrad eines Spieles, wenn es beliebig groß wird. Dies wird ausgedrückt in der O-Notation oder als Zugehörigkeit zu einer Komplexitätsklasse. Dieses Konzept ist nicht überall anwendbar, aber es gibt Spiele, die verallgemeinert wurden, so dass sie beliebig groß werden. Typischerweise wird auf einem n×n-Brett gespielt. (Aus der Sicht der Komplexitätstheorie ist ein Spiel, dessen Brettgröße fest ist, ein endlicher Automat, der in O(1) gelöst werden kann, z. B. über eine Tabelle in der für jede Stellung der beste Zug steht.)
Beispiel: Tic Tac Toe Für Tic-Tac-Toe ist eine einfache obere Schranke für die Größe des Zustandsraums 39 = 19.683. (Es gibt 3 Zustände für jedes Kästchen und 9 Kästchen.) Diese Zahl enthält viele unzulässige Stellungen, wie z. B. Stellungen mit 5 Kreuzen und keinen Nullen oder Stellungen, in denen beide Spieler eine Reihe voll haben. Bei einer genaueren Schätzung kann man daher die Anzahl auf 5.478 reduzieren. Wenn man Spiegelungen und Drehungen als identisch betrachtet, sind nur noch 765 grundsätzlich verschiedene Stellungen möglich.
Eine einfache obere Schranke für den Spielbaum ist 9! = 362.880 (9 Möglichkeiten für den ersten Zug, 8 für den zweiten, 7 für den dritten usw.). Wenn man unzulässige Züge ausschließt, erhält man maximal 255.168 mögliche Spiele. Durch Berücksichtigung der Spiegelungen und Drehungen reduziert sich die Anzahl auf 26.830.
Der komplexitätstheoretische Rechenaufwand von Tic Tac Toe hängt davon ab, wie es verallgemeinert wurde. Eine einfache Verallgemeinerung ist das m,n,k-Spiel. Auf einem n×m-Brett gewinnt der Spieler, der als erster k Kästchen in einer Reihe zu füllen vermag. Es wird direkt deutlich, dass es in DSPACE(mn) durch Durchsuchen des kompletten Spielbaumes gelöst werden kann. Damit befindet es sich in der Komplexitätsklasse PSPACE. Es kann gezeigt werden, dass es PSPACE-vollständig ist.
Komplexitäten einiger bekannter Spiele Wegen der enormen Größe einiger Spiel-Komplexitäten gibt die folgende Tabelle nur ihren Logarithmus zur Basis 10 an. Alle Zahlen sollten mit Vorsicht betrachtet werden, da scheinbar kleine Änderungen der Regeln große Änderungen der Zahlen bewirken können, die oft ohnehin nur grobe Schätzungen sind. SpielBrettgrößeZustandsraum-Komplexität (als log zur Basis 10)Spielbaum-Komplexität (als log zur Basis 10)Mittlere Spieldauer in HalbzügenKomplexitätsklasse einer passenden VerallgemeinerungTic-Tac-Toe 9 3 5 7PSPACE-VollständigSim 15 3 8 14?, aber in PSPACEWolfgang Slany: The Complexity of Graph Ramsey GamesPentominos 64 12 18 10Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339–344. Online: pdf.?, aber in PSPACEVier gewinnt 42 14 21 36?, aber in PSPACEDame (8 × 8) 32 20 oder 18 31 70EXPTIME-VollständigOwareSpielregeln siehe Allis 1994 12 12 32 60Verallgemeinerung unklarQubic 64 30 34 20PSPACE-VollständigFanorona 45 21 46 22?, aber in EXPTIMEMühle 24 10 50 ??, aber in EXPTIMEDame (10 × 10) 50 30? 54 90EXPTIME-VollständigHalma (2 Spieler) 121 28 ? ?EXPTIME-VollständigTakumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574–586. Beweist die Vollständigkeit der Verallgemeinerung auf beliebige Graphen.Halma (6 Spieler) 121 78 ? ?EXPTIME-VollständigLines of Action 64 23 64 44?, aber EXPTIMEReversi 64 28 58 58PSPACE-VollständigHex (11 × 11) 121 56 ? 40PSPACE-VollständigGomoku (15 × 15, Freistil) 225 105? 70 30PSPACE-VollständigSchach 64 50Die Größe des Zustandsraumes und des Spielbaumes für Schach wurden erstmals abgeschätzt in Shannon gab die Abschätzungen 1043 bzw. 10120 an, kleinere Werte als die in der Tabelle, welche aus der Arbeit von Victor Allis stammen. 123 80EXPTIME-Vollständig (ohne 50-Züge-Regel)Connect6 361 172 70 oder 140 15 oder 30PSPACE-VollständigOn the fairness and complexity of generalized k-in-a-row gamesBackgammon 28 20 144 50–60Verallgemeinerung unklarXiangqi 90 40 150 95?, vermutlich in EXPTIME-VollständigJanggi 90 44 160 100?, vermutlich in EXPTIME-VollständigQuoridor 81 42 162??, aber in PSPACEAmazonen (10 × 10) 100 ≤ 40 ? ?PSPACE-VollständigShōgi 81 71 226 110?EXPTIME-VollständigArimaa 64 43 296 70?, aber EXPTIMEGo (19 × 19) 361 171 Diese Arbeit leitet die Abschätzungen 48<log(log(N))<171 für die Anzahl der möglichen Spielverläufe N her. 360 150EXPTIME-VollständigMinesweeper 720 ? ? ?NP-VollständigR. Kaye: Minesweeper is NP-complete. In: The Mathematical Intelligencer. Band 22, Artikel 2, S. 9–15, Springer-Verlag, 2000, doi:10.1007/BF03025367
Weblinks David Eppstein: Computational Complexity of Games and Puzzles (englisch)
Einzelnachweise
Kategorie:Spieltheorie Kategorie:Kombinatorik