Spiel-Komplexität

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springenZur Suche springen

In derkombinatorischen Spieltheorie gibt es mehrere Möglichkeiten, dieSpiel-Komplexität zu messen. Im Folgenden werden diese Metriken beschrieben:

  • Zustandsraum-Komplexität
  • Spielbaumgröße
  • Entscheidungs-Komplexität
  • Spielbaum-Komplexität
  • Rechenaufwand

Inhaltsverzeichnis

Metriken der Spiel-Komplexität

[Bearbeiten |Quelltext bearbeiten]
  • DieZustandsraum-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 eineobere Schranke bestimmt werden, indem man unzulässige Stellungen oder solche, die im Spielverlauf nicht erreicht werden können, mitzählt.
  • DieSpielbaumgröße ist die Gesamtzahl der möglichen Spielverläufe. Sie entspricht der Anzahl der Blattknoten desSpielbaumes.
  • 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. beimTic-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 einesEntscheidungsbaums. 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.

  • DieEntscheidungskomplexitä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.
  • DieSpielbaumkomplexität eines Spiels ist die Anzahl der Blattknoten im kleinsten Entscheidungsbaum involler 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 einemMinimax-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ünftigeuntere Schranke gefunden werden, indem man den Verzweigungsfaktor mit der Anzahl der Halbzüge eines durchschnittlichen Spiels potenziert.
  • Derkomplexitätstheoretische Rechenaufwand eines Spiels beschreibt denasymptotischen Schwierigkeitsgrad eines Spieles, wenn es beliebig groß wird. Dies wird ausgedrückt in derO-Notation oder als Zugehörigkeit zu einerKomplexitätsklasse. Dieses Konzept ist nicht überall anwendbar, aber es gibt Spiele, die verallgemeinert wurden, so dass sie beliebig groß werden. Typischerweise wird auf einemn×n-Brett gespielt. (Aus der Sicht derKomplexitätstheorie ist ein Spiel, dessen Brettgröße fest ist, einendlicher 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

[Bearbeiten |Quelltext bearbeiten]

FürTic-Tac-Toe ist eine einfacheobere 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 einemn×m-Brett gewinnt der Spieler, der als ersterk Kästchen in einer Reihe zu füllen vermag. Es wird direkt deutlich, dass es inDSPACE(mn) durch Durchsuchen des kompletten Spielbaumes gelöst werden kann. Damit befindet es sich in der KomplexitätsklassePSPACE. Es kann gezeigt werden, dass esPSPACE-vollständig ist.[2]

Komplexitäten einiger bekannter Spiele

[Bearbeiten |Quelltext bearbeiten]

Wegen der enormen Größe einiger Spiel-Komplexitäten gibt die folgende Tabelle nur ihrenLogarithmus 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

(alslog zur Basis 10)

Spielbaum-Komplexität

(alslog zur Basis 10)

Mittlere Spieldauer in HalbzügenKomplexitätsklasse einer passenden Verallgemeinerung
Tic-Tac-Toe9357PSPACE-Vollständig[2]
Sim153814?, aber inPSPACE[3]
Pentominos64121810[4]?, aber inPSPACE
Vier gewinnt4214[1]21[1]36[1]?, aber inPSPACE
Dame (8 × 8)3220[5] oder 18[1]31[1]70[1]EXPTIME-Vollständig[6]
Oware[7]1212[1]32[1]60[1]Verallgemeinerung unklar
Qubic6430[1]34[1]20[1]PSPACE-Vollständig[2]
Fanorona4521[8]46[8]22?, aber inEXPTIME
Mühle2410[1]50[1]??, aber inEXPTIME
Dame (10 × 10)5030?[1]54[1]90[1]EXPTIME-Vollständig[6]
Halma (2 Spieler)12128??EXPTIME-Vollständig[9]
Halma (6 Spieler)12178??EXPTIME-Vollständig[9]
Lines of Action6423[10]64[10]44[10]?, aberEXPTIME
Reversi6428[1]58[1]58[1]PSPACE-Vollständig[11]
Hex (11 × 11)12156?40PSPACE-Vollständig[12]
Gomoku (15 × 15, Freistil)225105?[1]70[1]30[1]PSPACE-Vollständig[2]
Schach6450[13]123[13]80EXPTIME-Vollständig (ohne50-Züge-Regel)[14]
Connect636117270 oder 14015 oder 30PSPACE-Vollständig[15]
Backgammon282014450–60[16]Verallgemeinerung unklar
Xiangqi9040[17]150[1]95[18]?, vermutlich inEXPTIME-Vollständig
Janggi9044[17]160100?, vermutlich inEXPTIME-Vollständig
Quoridor8142162??, aber inPSPACE
Amazonen (10 × 10)100≤ 40??PSPACE-Vollständig[19]
Shōgi8171[18]226[18]110?EXPTIME-Vollständig[20]
Arimaa6443[21]296[21]70[22]?, aberEXPTIME
Go (19 × 19)361171[23]360[1]150[1]EXPTIME-Vollständig[24]
Minesweeper720???NP-Vollständig[25]

Weblinks

[Bearbeiten |Quelltext bearbeiten]

Einzelnachweise

[Bearbeiten |Quelltext bearbeiten]
  1. ↑abcdefghijklmnopqrstuvwxyzaaabVictor 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. ↑abcdStefan Reisch:Gobang istPSPACE-vollständig (Gobang is PSPACE-complete). In:Acta Informatica. 13. Jahrgang,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 inGames 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. ↑abJ. M. Robson:N by N checkers is Exptime complete. In:SIAM Journal on Computing,. 13. Jahrgang,Nr. 2, 1984,S. 252–267,doi:10.1137/0213018. 
  7. ↑Spielregeln siehe Allis 1994
  8. ↑abM.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. In:New Mathematics and Natural Computation. 4. Jahrgang,Nr. 3, 2008,S. 369–387,doi:10.1142/S1793005708001124 (personeel.unimaas.nl (Memento desOriginals vom 17. Juli 2011 imInternet Archive) [abgerufen am 14. November 2009]). 
  9. ↑abTakumi 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. ↑abcMark 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. Jahrgang,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. ↑abDie Größe des Zustandsraumes und des Spielbaumes für Schach wurden erstmals abgeschätzt inClaude Shannon:Programming a Computer for Playing Chess. In:Philosophical Magazine. 41. Jahrgang,Nr. 314, 1950 (computerhistory.org [PDF; 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 vonVictor Allis stammen.
  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 imInternet Archive)
  17. ↑abDonghwi Park:Space-state complexity of Korean chess and Chinese chess. 2015,arxiv:1507.06401. 
  18. ↑abcShi-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]). 
  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. Jahrgang, 1987,S. 1843–1852. 
  21. ↑abChrist-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, festgestellt im Mai 2019.Suche in Webarchiven) Diese Arbeit leitet die Abschätzungen 48<log(log(N))<171 für die Anzahl der möglichen SpielverläufeN 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
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Spiel-Komplexität&oldid=246070877“
Kategorien:
Versteckte Kategorien: