Spiel-Komplexität

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.<ref name="Allis1994" /> 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.<ref name="Allis1994" /> (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 3⁹ = 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.

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.

Spiel	Brettgröße	Zustandsraum-Komplexität (als log zur Basis 10)	Spielbaum-Komplexität (als log zur Basis 10)	Mittlere Spieldauer in Halbzügen	Komplexitätsklasse einer passenden Verallgemeinerung
Tic-Tac-Toe	9	3	5	7	PSPACE-Vollständig<ref name="Reisch1980" />
Sim	15	3	8	14	?, aber in PSPACE<ref>Wolfgang Slany: The Complexity of Graph Ramsey Games</ref>
Pentominos	64	12	18	10<ref>Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339–344. Online: pdf.</ref>	?, aber in PSPACE
Vier gewinnt	42	14<ref name="Allis1994" />	21<ref name="Allis1994" />	36<ref name="Allis1994" />	?, aber in PSPACE
Dame (8 × 8)	32	20<ref>Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name: Checkers is Solved. In: Science. Vorlage:Cite book/Date (Vorlage:Cite book/URL [abgerufen am -05-]). Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2</ref> oder 18<ref name="Allis1994" />	31<ref name="Allis1994" />	70<ref name="Allis1994" />	EXPTIME-Vollständig<ref name="robson1984">Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name: N by N checkers is Exptime complete. In: SIAM Journal on Computing,. 13. Jahrgang, Nr. 2, Vorlage:Cite book/Date, S. 252–267, doi:10.1137/0213018 (Vorlage:Cite book/URL [abgerufen am -05-]). Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2</ref>
Oware<ref>Spielregeln siehe Allis 1994</ref>	12	12<ref name="Allis1994" />	32<ref name="Allis1994" />	60<ref name="Allis1994" />	Verallgemeinerung unklar
Qubic	64	30<ref name="Allis1994" />	34<ref name="Allis1994" />	20<ref name="Allis1994" />	PSPACE-Vollständig<ref name="Reisch1980" />
Fanorona	45	21<ref name="Schadd2008">Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name: Best Play in Fanorona leads to Draw. In: New Mathematics and Natural Computation. 4. Jahrgang, Nr. 3, Vorlage:Cite book/Date, S. 369–387, doi:10.1142/S1793005708001124 (Vorlage:Cite book/URL [abgerufen am 14. November 2009]). Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2</ref>	46<ref name="Schadd2008" />	22	?, aber in EXPTIME
Mühle	24	10<ref name="Allis1994" />	50<ref name="Allis1994" />	?	?, aber in EXPTIME
Dame (10 × 10)	50	30?<ref name="Allis1994" />	54<ref name="Allis1994" />	90<ref name="Allis1994" />	EXPTIME-Vollständig<ref name="robson1984" />
Halma (2 Spieler)	121	28	?	?	EXPTIME-Vollständig<ref name="pebble">Takumi 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.</ref>
Halma (6 Spieler)	121	78	?	?	EXPTIME-Vollständig<ref name="pebble" />
Lines of Action	64	23<ref name="Winands2004">Mark H.M. Winands: Informed Search in Complex Games. 2004, ISBN 90-5278-429-9 (personeel.unimaas.nl [PDF] Ph.D. Thesis, Maastricht University, Maastricht, The Netherlands). </ref>	64<ref name="Winands2004" />	44<ref name="Winands2004" />	?, aber EXPTIME
Reversi	64	28<ref name="Allis1994" />	58<ref name="Allis1994" />	58<ref name="Allis1994" />	PSPACE-Vollständig<ref>Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name: The Othello game on an n*n board is PSPACE-complete. In: Theor. Comp. Sci. 123. Jahrgang, Nr. 123, Vorlage:Cite book/Date, S. 329–340, doi:10.1016/0304-3975(94)90131-7 (Vorlage:Cite book/URL [abgerufen am -05-]). Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2</ref>
Hex (11 × 11)	121	56	?	40	PSPACE-Vollständig<ref>Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name: Hex ist PSPACE-vollständig (Hex is PSPACE-complete). In: Acta Inf. Nr. 15, Vorlage:Cite book/Date, S. 167–191, doi:10.1007/BF00288964 (Vorlage:Cite book/URL [abgerufen am -05-]). Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2</ref>
Gomoku (15 × 15, Freistil)	225	105?<ref name="Allis1994" />	70<ref name="Allis1994" />	30<ref name="Allis1994" />	PSPACE-Vollständig<ref name="Reisch1980" />
Schach	64	50<ref name="Shannon1950">Die Größe des Zustandsraumes und des Spielbaumes für Schach wurden erstmals abgeschätzt in Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name: Programming a Computer for Playing Chess. In: Philosophical Magazine. 41. Jahrgang, Nr. 314, Vorlage:Cite book/Date (Vorlage:Cite book/URL [abgerufen am 13. Mai 2007]). Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2 Shannon gab die Abschätzungen 10⁴³ bzw. 10¹²⁰ an, kleinere Werte als die in der Tabelle, welche aus der Arbeit von Victor Allis stammen.</ref>	123<ref name="Shannon1950" />	80	EXPTIME-Vollständig (ohne 50-Züge-Regel)<ref name="Fraenkel1981">Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name: Computing a perfect strategy for n×n chess requires time exponential in n. In: J. Comb. Th. A. Nr. 31, Vorlage:Cite book/Date, S. 199–214, doi:10.1016/0097-3165(81)90016-9 (Vorlage:Cite book/URL [abgerufen am -05-]). Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2</ref>
Connect6	361	172	70 oder 140	15 oder 30	PSPACE-Vollständig<ref>On the fairness and complexity of generalized k-in-a-row games</ref>
Backgammon	28	20	144	50–60<ref><templatestyles src="Webarchiv/styles.css" />books.nips.cc (Memento vom 26. Februar 2009 im Internet Archive)</ref>	Verallgemeinerung unklar
Xiangqi	90	40<ref name="Donghwi">Donghwi Park: Space-state complexity of Korean chess and Chinese chess. 2015, arxiv:1507.06401. </ref>	150<ref name="Allis1994">Victor Allis: Searching for Solutions in Games and Artificial Intelligence. 1994, ISBN 90-90-07488-0 (fragrieu.free.fr [PDF] Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands). </ref>	95<ref name="Hsu2004">Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu: Computer Chinese Chess. In: International Computer Games Association Journal. Band 27, Nr. 1, März 2004, S. 3–18 (csie.ndhu.edu.tw [PDF]). </ref>	?, vermutlich in EXPTIME-Vollständig
Janggi	90	44<ref name="Donghwi" />	160	100	?, vermutlich in EXPTIME-Vollständig
Quoridor	81	42	162	?	?, aber in PSPACE
Amazonen (10 × 10)	100	≤ 40	?	?	PSPACE-Vollständig<ref>R. A. Hearn: Amazons is PSPACE-complete. 2. Februar 2005, arxiv:cs/0502013. </ref>
Shōgi	81	71<ref name="Hsu2004" />	226<ref name="Hsu2004" />	110?	EXPTIME-Vollständig<ref>Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name Vorlage:Cite book/Name: Shogi on n × n board is complete in exponential time. In: Trans. IEICE. J70-D. Jahrgang, Vorlage:Cite book/Date, S. 1843–1852 (Vorlage:Cite book/URL [abgerufen am -05-]). Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2</ref>
Arimaa	64	43<ref name="Cox2006">Vorlage:Cite book/Name Vorlage:Cite book/Name: [Internetquelle: archiv-url ungültig Analysis and Implementation of the Game Arimaa.] (PDF; 806 kB) , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL; abgerufen am 15. Februar 2011. Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2 Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung</ref>	296<ref name="Cox2006" />	70<ref>Vorlage:Cite book/Name Vorlage:Cite book/Name: [Internetquelle: archiv-url ungültig Arimaa Branching Factor.] , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL; abgerufen am 15. Februar 2011. Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2 Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung</ref>	?, aber EXPTIME
Go (19 × 19)	361	171<ref>@1@2Vorlage:Toter Link/www.cwi.nlCombinatorics of Go (Seite nicht mehr abrufbar, festgestellt im Mai 2019. Suche im Internet Archive (T)) Diese Arbeit leitet die Abschätzungen 48<log(log(N))<171 für die Anzahl der möglichen Spielverläufe N her.</ref>	360<ref name="Allis1994" />	150<ref name="Allis1994" />	EXPTIME-Vollständig<ref>J. M. Robson: Information Processing; Proceedings of IFIP Congress. 1983, The complexity of Go, S. 413–417. </ref>
Minesweeper	720	?	?	?	NP-Vollständig<ref>R. Kaye: Minesweeper is NP-complete. In: The Mathematical Intelligencer. Band 22, Artikel 2, S. 9–15, Springer-Verlag, 2000, doi:10.1007/BF03025367</ref>

Weblinks

David Eppstein: Computational Complexity of Games and Puzzles (englisch)

Einzelnachweise