Spiel-Komplexität

In d​er kombinatorischen Spieltheorie g​ibt es mehrere Möglichkeiten d​ie Spiel-Komplexität z​u messen. Im Folgenden werden d​iese 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.[1] 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 a​uf der Idee e​ines Entscheidungsbaums. Ein Entscheidungsbaum i​st ein Unterbaum d​es Spielbaums, b​ei dem j​ede Stellung m​it "Spieler A gewinnt", "Spieler B gewinnt" o​der "weiterer Zug" markiert wurde. Endstellungen werden d​abei direkt markiert. Eine Stellung, m​it der Spieler A e​ine "Spieler A gewinnt"-Stellung erreichen kann, w​ird ebenfalls m​it "Spieler A gewinnt" markiert. Ebenso w​ird 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.[1] (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 i​st eine einfache obere Schranke für d​ie Größe d​es Zustandsraums 39 = 19.683. (Es g​ibt 3 Zustände für j​edes Kästchen u​nd 9 Kästchen.) Diese Zahl enthält v​iele unzulässige Stellungen, w​ie z. B. Stellungen m​it 5 Kreuzen u​nd keinen Nullen o​der Stellungen, i​n denen b​eide Spieler e​ine Reihe v​oll haben. Bei e​iner genaueren Schätzung k​ann man d​aher die Anzahl a​uf 5.478 reduzieren. Wenn m​an Spiegelungen u​nd Drehungen a​ls identisch betrachtet, s​ind nur n​och 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 v​on Tic Tac Toe hängt d​avon ab, w​ie es verallgemeinert wurde. Eine einfache Verallgemeinerung i​st das m,n,k-Spiel. Auf e​inem nxm-Brett gewinnt d​er Spieler, d​er als erster k Kästchen i​n einer Reihe z​u füllen vermag. Es w​ird direkt deutlich, d​ass es i​n DSPACE(mn) d​urch Durchsuchen d​es kompletten Spielbaumes gelöst werden kann. Damit befindet e​s sich i​n der Komplexitätsklasse PSPACE. Es k​ann gezeigt werden, d​ass es PSPACE-vollständig ist.[2]

Komplexitäten einiger bekannter Spiele

Wegen d​er enormen Größe einiger Spiel-Komplexitäten g​ibt die folgende Tabelle n​ur ihren Logarithmus z​ur Basis 10 an. Alle Zahlen sollten m​it Vorsicht betrachtet werden, d​a scheinbar kleine Änderungen d​er Regeln große Änderungen d​er Zahlen bewirken können, d​ie oft ohnehin n​ur grobe Schätzungen sind.

Spiel Brettgröße Zustandsraum-Komplexität

(als log z​ur Basis 10)

Spielbaum-Komplexität

(als log z​ur Basis 10)

Mittlere Spieldauer in Halbzügen Komplexitätsklasse einer passenden Verallgemeinerung
Tic-Tac-Toe 9 3 5 7 PSPACE-Vollständig[2]
Sim 15 3 8 14 ?, aber in PSPACE[3]
Pentominos 64 12 18 10[4] ?, aber in PSPACE
Vier gewinnt 42 14[1] 21[1] 36[1] ?, aber in PSPACE
Dame (8 × 8) 32 20[5] oder 18[1] 31[1] 70[1] EXPTIME-Vollständig[6]
Oware[7] 12 12[1] 32[1] 60[1] Verallgemeinerung unklar
Qubic 64 30[1] 34[1] 20[1] PSPACE-Vollständig[2]
Fanorona 45 21[8] 46[8] 22 ?, aber in EXPTIME
Mühle 24 10[1] 50[1]  ? ?, aber in EXPTIME
Dame (10 × 10) 50 30?[1] 54[1] 90[1] EXPTIME-Vollständig[6]
Halma (2 Spieler) 121 28  ?  ? EXPTIME-Vollständig[9]
Halma (6 Spieler) 121 78  ?  ? EXPTIME-Vollständig[9]
Lines of Action 64 23[10] 64[10] 44[10] ?, aber EXPTIME
Reversi 64 28[1] 58[1] 58[1] PSPACE-Vollständig[11]
Hex (11 × 11) 121 56  ? 40 PSPACE-Vollständig[12]
Gomoku (15 × 15, Freistil) 225 105?[1] 70[1] 30[1] PSPACE-Vollständig[2]
Schach 64 50[13] 123[13] 80 EXPTIME-Vollständig (ohne 50-Züge-Regel)[14]
Connect6 361 172 70 oder 140 15 oder 30 PSPACE-Vollständig[15]
Backgammon 28 20 144 50–60[16] Verallgemeinerung unklar
Xiangqi 90 40[17] 150[1] 95[18] ?, vermutlich in EXPTIME-Vollständig
Janggi 90 44[17] 160 100 ?, vermutlich in EXPTIME-Vollständig
Quoridor 81 42 162 ? ?, aber in PSPACE
Amazonen (10 × 10) 100  40  ?  ? PSPACE-Vollständig[19]
Shōgi 81 71[18] 226[18] 110? EXPTIME-Vollständig[20]
Arimaa 64 43[21] 296[21] 70[22] ?, aber EXPTIME
Go (19 × 19) 361 171[23] 360[1] 150[1] EXPTIME-Vollständig[24]
Minesweeper 720  ?  ?  ? NP-Vollständig[25]

Einzelnachweise

  1. 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).
  2. Stefan Reisch: Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete). In: Acta Informatica. 13, Nr. 1, 1980, S. 59–66. doi:10.1007/BF00288536.
  3. Wolfgang Slany: The Complexity of Graph Ramsey Games
  4. Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339–344. Online: pdf.
  5. Jonathan Schaeffer et al.: Checkers is Solved. In: Science. 6. Juli 2007.
  6. J. M. Robson: N by N checkers is Exptime complete. In: SIAM Journal on Computing,. 13, Nr. 2, 1984, S. 252–267. doi:10.1137/0213018.
  7. Spielregeln siehe Allis 1994
  8. M.P.D. Schadd, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik and M.H.J. Bergsma: Best Play in Fanorona leads to Draw Archiviert vom Original am 17. Juli 2011. In: New Mathematics and Natural Computation. 4, Nr. 3, 2008, S. 369–387. doi:10.1142/S1793005708001124. Abgerufen am 14. November 2009.
  9. 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.
  10. 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).
  11. S. Iwata and T. Kasai: The Othello game on an n*n board is PSPACE-complete. In: Theor. Comp. Sci.. 123, Nr. 123, 1994, S. 329–340. doi:10.1016/0304-3975(94)90131-7.
  12. Stefan Reisch: Hex ist PSPACE-vollständig (Hex is PSPACE-complete). In: Acta Inf.. Nr. 15, 1981, S. 167–191. doi:10.1007/BF00288964.
  13. Die Größe des Zustandsraumes und des Spielbaumes für Schach wurden erstmals abgeschätzt in Claude Shannon: Programming a Computer for Playing Chess Archiviert vom Original am 15. März 2010. In: Philosophical Magazine. 41, Nr. 314, 1950. Abgerufen am 13. Mai 2007. Shannon gab die Abschätzungen 1043 bzw. 10120 an, kleinere Werte als die in der Tabelle, welche aus der Arbeit von Victor Allis's stammen. Siehe auch Shannon number für Einzelheiten.
  14. Aviezri Fraenkel, D. Lichtenstein: Computing a perfect strategy for n×n chess requires time exponential in n. In: J. Comb. Th. A. Nr. 31, 1981, S. 199–214. doi:10.1016/0097-3165(81)90016-9.
  15. On the fairness and complexity of generalized k-in-a-row games
  16. books.nips.cc (Memento vom 26. Februar 2009 im Internet Archive)
  17. Donghwi Park: Space-state complexity of Korean chess and Chinese chess. 2015, arxiv:1507.06401.
  18. 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]). csie.ndhu.edu.tw (Memento vom 9. Juli 2015 im Internet Archive)
  19. R. A. Hearn: Amazons is PSPACE-complete. 2. Februar 2005, arxiv:cs/0502013.
  20. H. Adachi, H. Kamekawa, and S. Iwata: Shogi on n × n board is complete in exponential time. In: Trans. IEICE. J70-D, 1987, S. 1843–1852.
  21. Christ-Jan Cox: Analysis and Implementation of the Game Arimaa (PDF; 806 kB) 2006. Abgerufen am 15. Februar 2011.
  22. Brian Haskin: Arimaa Branching Factor. 2007. Abgerufen am 15. Februar 2011.
  23. Combinatorics of Go@1@2Vorlage:Toter Link/www.cwi.nl (Seite nicht mehr abrufbar, Suche in Webarchiven) Diese Arbeit leitet die Abschätzungen 48<log(log(N))<171 für die Anzahl der möglichen Spielverläufe N her.
  24. J. M. Robson: Information Processing; Proceedings of IFIP Congress. 1983, The complexity of Go, S. 413–417.
  25. R. Kaye: Minesweeper is NP-complete. In: The Mathematical Intelligencer. Band 22, Artikel 2, S. 9–15, Springer-Verlag, 2000, doi:10.1007/BF03025367
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.