请输入您要查询的百科知识：

　

词条 Game complexity
释义

  1. Measures of game complexity

      State-space complexity    Game tree size    Decision trees    Decision complexity    Game-tree complexity    Computational complexity  

  2. Example: tic-tac-toe (noughts and crosses)

  3. Complexities of some well-known games

  4. Notes

  5. See also

  6. References

  7. External links

Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.

Measures of game complexity

State-space complexity

The state-space complexity of a game is the number of legal game positions reachable from the initial position of the game.[1]

When this is too hard to calculate, an upper bound can often be computed by including illegal positions or positions that can never arise in the course of a game.

Game tree size

The game tree size is the total number of possible games that can be played: the number of leaf nodes in the game tree rooted at the game's initial position.

The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order (for example, in a tic-tac-toe game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed). An upper bound for the size of the game tree can sometimes be computed by simplifying the game in a way that only increases the size of the game tree (for example, by allowing illegal moves) until it becomes tractable.

However, for games where the number of moves is not limited (for example by the size of the board, or by a rule about repetition of position) the game tree is infinite.

Decision trees

The next two measures use the idea of a decision tree, which is a subtree of the game tree, with each position labelled with "player A wins", "player B wins" or "drawn", if that position can be proved to have that value (assuming best play by both sides) by examining only other positions in the graph. (Terminal positions can be labelled directly; a position with player A to move can be labelled "player A wins" if any successor position is a win for A, or labelled "player B wins" if all successor positions are wins for B, or labelled "draw" if all successor positions are either drawn or wins for B. And correspondingly for positions with B to move.)

Decision complexity

Decision complexity of a game is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position.

Game-tree complexity

The game-tree complexity of a game is the number of leaf nodes in the smallest full-width decision tree that establishes the value of the initial position.[1] A full-width tree includes all nodes at each depth.

This is an estimate of the number of positions one would have to evaluate in a minimax search to determine the value of the initial position.

It is hard even to estimate the game-tree complexity, but for some games a reasonable lower bound can be given by raising the game's average branching factor to the power of the number of plies in an average game, or:

.

Computational complexity

The computational complexity of a game describes the asymptotic difficulty of a game as it grows arbitrarily large, expressed in big O notation or as membership in a complexity class. This concept doesn't apply to particular games, but rather to games that have been generalized so they can be made arbitrarily large, typically by playing them on an n-by-n board. (From the point of view of computational complexity a game on a fixed size of board is a finite problem that can be solved in O(1), for example by a look-up table from positions to the best move in each position.)

The asymptotic complexity is defined by the most efficient (in terms of whatever computational resource one is considering) algorithm for solving the game; the most common complexity measure (computation time) is always lower-bounded by the logarithm of the asymptotic state-space complexity, since a solution algorithm must work for every possible state of the game. It will be upper-bounded by the complexities of each individual algorithm for the family of games. Similar remarks apply to the second-most commonly used complexity measure, the amount of space or computer memory used by the computation. It is not obvious that there is any lower bound on the space complexity for a typical game, because the algorithm need not store game states; however many games of interest are known to be PSPACE-hard, and it follows that their space complexity will be lower-bounded by the logarithm of the asymptotic state-space complexity as well (technically the bound is only a polynomial in this quantity; but it is usually known to be linear).

  • The depth-first minimax strategy will use computation time proportional to game's tree-complexity, since it must explore the whole tree, and an amount of memory polynomial in the logarithm of the tree-complexity, since the algorithm must always store one node of the tree at each possible move-depth, and the number of nodes at the highest move-depth is precisely the tree-complexity.
  • Backward induction will use both memory and time proportional to the state-space complexity as it must compute and record the correct move for each possible position.

Example: tic-tac-toe (noughts and crosses)

For tic-tac-toe, a simple upper bound for the size of the state space is 39 = 19,683. (There are three states for each cell and nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count, removing these illegal positions, gives 5,478. And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.

A simple upper bound for the size of the game tree is 9! = 362,880. (There are nine positions for the first move, eight for the second, and so on.) This includes illegal games that continue after one side has won. A more careful count gives 255,168 possible games. When rotations and reflections of positions are considered the same, there are only 26,830 possible games.

The computational complexity of tic-tac-toe depends on how it is generalized. A natural generalization is to m,n,k-games: played on an m by n board with winner being the first player to get k in a row. It is immediately clear that this game can be solved in DSPACE(mn) by searching the entire game tree. This places it in the important complexity class PSPACE. With some more work it can be shown to be PSPACE-complete.[1]

Complexities of some well-known games

Due to the large size of game complexities, this table gives the ceiling of their logarithm to base 10. (In other words, the number of digits). All of the following numbers should be considered with caution: seemingly-minor changes to the rules of a game can change the numbers (which are often rough estimates anyway) by tremendous factors, which might easily be much greater than the numbers shown.

Note: ordered by game tree size

GameBoard size

(positions)

State-space complexity

(as log to base 10)

Game-tree complexity

(as log to base 10)

Average game length

(plies)

Branching factorRefComplexity class of suitable generalized game
Tic-tac-toe93594PSPACE-complete[1]
Sim1538143.7PSPACE-complete[2]
Pentominoes6412181075[6][3]?, but in PSPACE
Kalah [4]141318[6]Generalization is unclear
Connect Four421321364[1][5]?, but in PSPACE
Domineering (8 × 8)641527308[6]?, but in PSPACE; in P for certain dimensions[6]
Congkak141533[7]
English draughts (8x8) (checkers)3220 or 1831702.8[1][8]EXPTIME-complete[9]
Awari[10]121232603.5[1]Generalization is unclear
Qubic6430342054.2[1]PSPACE-complete[1]
group=nb|Double dummy bridge (i.e. double dummy problems in the context of contract bridge) is not a proper board game but has a similar game tree, and is studied in computer bridge. The bridge table can be regarded as having one slot for each player and trick to play a card in, which corresponds to board size 52. Game-tree complexity is a very weak upper bound: 13! to the power of 4 players regardless of legality. State-space complexity is for one given deal; likewise regardless of legality but with many transpositions eliminated. Note that the last 4 plies are always forced moves with branching factor 1.}}(52)<17<40525.6PSPACE-complete[11]
Fanorona4521464411[12]?, but in EXPTIME
Nine Men's Morris2410505010[1]?, but in EXPTIME
International draughts (10x10)503054904[1]EXPTIME-complete[9]
Chinese checkers (2 sets)12123[13]EXPTIME-complete [14]
Chinese checkers (6 sets)12178[13]EXPTIME-complete [14]
Reversi (Othello)6428585810[1]PSPACE-complete[15]
OnTop (2p base game)7288623123.77[16]
Lines of Action6423644429[17]?, but in EXPTIME
Gomoku (15x15, freestyle)2251057030210[1]PSPACE-complete[1]
Hex (11x11)12157985096[7]PSPACE-complete[18]
Chess64471237035[19]EXPTIME-complete (without 50-move drawing rule)[20]
Bejeweled and Candy Crush (8x8)64<50[21]NP-hard
GIPF37251329029.3[22]
Connect63611721403046000[23]PSPACE-complete[24]
Backgammon282014455250[25]Generalization is unclear
Xiangqi90401509538[26][27][28]?, believed to be EXPTIME-complete
Abalone61251548760[29][30]PSPACE-hard, and in EXPTIME
Havannah27112715766240[7][31]PSPACE-complete[32]
Twixt57214015960452[33]
Janggi904416010040[28]?, believed to be EXPTIME-complete
Quoridor81421629160[34]?, but in PSPACE
Carcassonne (2p base game)72>401957155[35]Generalization is unclear
Amazons (10x10)1004021284374 or 299[36][37][38]PSPACE-complete[39]
Shogi817122611592[27][40]EXPTIME-complete[41]
Go (19x19)361170360150250[26][42][43]EXPTIME-complete[44]
Arimaa64434029217281[45][46][47]?, but in EXPTIME
Stratego9211553538121.739[48]
group=nb|Infinite chess is a class of games, which includes Chess on an Infinite Plane and Trappist-1 as examples.[49][50]}}unboundedEXPTIME-complete (without 50-move drawing rule)[20]

Notes

1. ^1 2 3 {{cite journal | author = Stefan Reisch | title = Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete) | journal = Acta Informatica | volume = 13 | issue = 1 | pages = 59–66 | year = 1980 | doi=10.1007/bf00288536}}
2. ^{{cite book|url=http://dl.acm.org/citation.cfm?id=647481.728124|title=The Complexity of Graph Ramsey Games|first=Wolfgang|last=Slany|date=26 October 2000|publisher=Springer-Verlag|pages=186–203|accessdate=12 April 2018|via=dl.acm.org|isbn=9783540430803}}
3. ^Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf.
4. ^See van den Herik et al for rules.
5. ^{{cite web | title = John's Connect Four Playground | author = John Tromp | year = 2010 | url = https://tromp.github.io/c4/c4.html}}
6. ^{{cite journal| author=Michael Lachmann | author2= Cristopher Moore | author3=Ivan Rapaport|title=Who wins domineering on rectangular boards? | volume=MSRI Combinatorial Game Theory Research Workshop | date=July 2000 }}
7. ^1 2 3 4 5 {{cite journal | title= Games solved: Now and in the future | author = H. J. van den Herik | author2 = J. W. H. M. Uiterwijk | author3 = J. van Rijswijck | year = 2002 | journal = Artificial Intelligence | volume = 134 | issue=1–2 | pages=277–311 | doi= 10.1016/S0004-3702(01)00152-7}}
8. ^{{cite journal | author = Jonathan Schaeffer| title = Checkers is Solved | journal = Science | date = July 6, 2007 | doi=10.1126/science.1144079 | volume=317 |issue= 5844 |pages= 1518–1522 | pmid=17641166 |display-authors=etal|bibcode=2007Sci...317.1518S }}
9. ^1 {{cite journal | author = J. M. Robson | title = N by N checkers is Exptime complete | journal = SIAM Journal on Computing | volume = 13 | issue = 2 | pages = 252–267 | year = 1984 | doi = 10.1137/0213018}}
10. ^See Allis 1994 for rules
11. ^{{Cite book|last=Bonnet|first=Édouard|last2=Jamain|first2=Florian|last3=Saffidine|first3=Abdallah|date=2013-08-03|title=On the complexity of trick-taking card games|url=http://dl.acm.org/citation.cfm?id=2540128.2540199|publisher=AAAI Press|pages=482–488|isbn=9781577356332}}
12. ^{{cite journal|author1=M.P.D. Schadd |author2=M.H.M. Winands |author3=J.W.H.M. Uiterwijk |author4=H.J. van den Herik |author5=M.H.J. Bergsma | year = 2008 | title = Best Play in Fanorona leads to Draw | journal = New Mathematics and Natural Computation | volume = 4 |issue = 3 | pages = 369–387| url = https://dke.maastrichtuniversity.nl/m.winands/documents/Fanorona.pdf| doi = 10.1142/S1793005708001124}}
13. ^1 {{cite journal|author=G.I. Bell|title=The Shortest Game of Chinese Checkers and Related Problems |journal=Integers|year=2009|arxiv=0803.1245|url = http://emis.ams.org|bibcode=2008arXiv0803.1245B}}
14. ^1 {{cite journal|title=Classes of Pebble Games and Complete Problems|journal= SIAM Journal on Computing| volume = 8| year = 1979 |pages= 574–586|author1=Takumi Kasai |author2=Akeo Adachi |author3=Shigeki Iwata |doi=10.1137/0208046|issue=4}} Proves completeness of the generalization to arbitrary graphs.
15. ^{{cite journal |author1=S. Iwata |author2=T. Kasai | title = The Othello game on an n*n board is PSPACE-complete | journal = Theor. Comput. Sci. | issue = 2 | year = 1994 | pages = 329–340 | volume = 123 | doi = 10.1016/0304-3975(94)90131-7}}
16. ^{{cite thesis | title=Analysis and Implementation of the Game OnTop |url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Briesemeister_Thesis.pdf |author = Robert Briesemeister | year=2009 | publisher = Maastricht University, Dept of Knowledge Engineering }}
17. ^{{cite thesis | author = Mark H.M. Winands | year = 2004 | title = Informed Search in Complex Games | degree = Ph.D. |publisher= Maastricht University, Maastricht, The Netherlands | isbn = 90-5278-429-9 | url = https://dke.maastrichtuniversity.nl/m.winands/documents/informed_search.pdf}}
18. ^{{cite journal | author = Stefan Reisch | title = Hex ist PSPACE-vollständig (Hex is PSPACE-complete) | journal = Acta Inf. | issue = 15 | year = 1981 | pages = 167–191}}
19. ^The size of the state space and game tree for chess were first estimated in {{cite journal |author=Claude Shannon |title=Programming a Computer for Playing Chess |journal=Philosophical Magazine |volume=41 |issue=314 |year=1950 |url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf |deadurl=yes |archiveurl=https://www.webcitation.org/5oFLE7Mgx?url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf |archivedate=2010-03-15 |df= }} Shannon gave estimates of 1043 and 10120 respectively, smaller than the upper bound in the table,which is detailed in Shannon number.
20. ^1 {{Citation |author1=Aviezri Fraenkel |author2=D. Lichtenstein | title = Computing a perfect strategy for n×n chess requires time exponential in n | journal = J. Combin. Theory Ser. A | volume = 31 | year = 1981 | pages = 199–214 | doi = 10.1016/0097-3165(81)90016-9 | issue = 2}}
21. ^{{cite arXiv |author1=L. Gualà |author2=S. Leucci |author3=E. Natale | title = Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard | eprint= 1403.5830| year = 2014|class=cs.CC }}
22. ^{{cite thesis | title=Analysis and Implementation of the game Gipf |url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Wentink_thesis.pdf |author = Diederik Wentink | year=2001 | publisher = Maastricht University}}
23. ^{{cite book | title=2009 Chinese Control and Decision Conference | doi=10.1109/CCDC.2009.5191963 | chapter=Enhancements of proof number search in connect6 | year=2009 | last1=Chang-Ming Xu | last2=Ma | first2=Z.M. | last3=Jun-Jie Tao | last4=Xin-He Xu | isbn=978-1-4244-2722-2 | pages=4525 }}
24. ^{{cite journal|url=http://dl.acm.org/citation.cfm?id=1290195.1290250|title=On the fairness and complexity of generalized k -in-a-row games|first1=Ming Yu|last1=Hsieh|first2=Shi-Chun|last2=Tsai|date=1 October 2007|journal=Theoretical Computer Science|volume=385|issue=1–3|pages=88–100|accessdate=12 April 2018|via=dl.acm.org|doi=10.1016/j.tcs.2007.05.031}}
25. ^{{cite journal|title=Practical issues in temporal difference learning|first=Gerald|last=Tesauro|date=1 May 1992|journal=Machine Learning|volume=8|issue=3–4|pages=257–277|doi=10.1007/BF00992697}}
26. ^1 2 3 4 5 6 7 8 9 10 11 {{cite thesis | author = Victor Allis | year = 1994 | title = Searching for Solutions in Games and Artificial Intelligence | degree = Ph.D. |publisher= University of Limburg, Maastricht, The Netherlands | isbn = 90-900748-8-0 | url = https://project.dke.maastrichtuniversity.nl/games/files/phd/SearchingForSolutions.pdf}}
27. ^1 {{cite journal | author1 = Shi-Jim Yen, Jr-Chang Chen | author2 = Tai-Ning Yang | author3 = Shun-Chin Hsu | title = Computer Chinese Chess | date = March 2004 | journal = International Computer Games Association Journal | volume = 27 | issue = 1 | pages = 3–18 | url = http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf | deadurl = yes | archiveurl = https://web.archive.org/web/20070614111609/http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf | archivedate = 2007-06-14 | df = | doi=10.3233/ICG-2004-27102 }}
28. ^1 {{cite arXiv | author = Donghwi Park | title = Space-state complexity of Korean chess and Chinese chess | eprint= 1507.06401| year = 2015| class = math.GM }}
29. ^{{cite web|last=Chorus|first=Pascal|title=Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/pcreport.pdf|publisher=Dept of Knowledge Engineering, Maastricht University|accessdate=29 March 2012}}
30. ^{{cite thesis |first=Jacob S |last=Kopczynski |title=Pushy Computing: Complexity Theory and the Game Abalone |publisher=Reed College |year=2014}}
31. ^{{cite web|last=Joosten|first=B|title=Creating a Havannah Playing Agent|url=https://project.dke.maastrichtuniversity.nl/games/files/bsc/bscHavannah.pdf|accessdate=29 March 2012}}
32. ^{{cite arXiv |author1=E. Bonnet |author2=F. Jamain |author3=A. Saffidine | title = Havannah and TwixT are PSPACE-complete | date = 2014-03-25 | eprint = 1403.6518 | class = cs.CC}}
33. ^{{cite thesis | title=TWIXT: THEORY, ANALYSIS AND IMPLEMENTATION |url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Thesis_Moesker.pdf |author = Kevin Moesker | year=2009 | publisher = Maastricht University, Faculty of Humanities and Sciences of Maastricht University }}
34. ^{{cite thesis|author=Lisa Glendenning |title=Mastering Quoridor |date=May 2005 |department=Computer Science |degree=B.Sc. |publisher=University of New Mexico |url=http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf |deadurl=yes |archiveurl=https://web.archive.org/web/20120315192840/http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf |archivedate=2012-03-15 |df= }}
35. ^{{cite thesis | title=Implementing a Computer Player for Carcassonne |url = https://project.dke.maastrichtuniversity.nl/games/files/msc/MasterThesisCarcassonne.pdf |author = Cathleen Heyden | year=2009 | publisher = Maastricht University, Dept of Knowledge Engineering }}
36. ^The lower branching factor is for the second player.
37. ^{{cite journal | author = Julien Kloetzer | author2 = Hiroyuki Iida | author3 = Bruno Bouzy | title = The Monte-Carlo Approach in Amazons | year = 2007 | citeseerx = 10.1.1.79.7640 }}
38. ^{{cite journal | author = P. P. L. M. Hensgens | title = A Knowledge-Based Approach of the Game of Amazons | year = 2001 | publisher = Universiteit Maastricht, Institute for Knowledge and Agent Technology | url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Hensgens_thesis.pdf}}
39. ^{{cite arXiv | author = R. A. Hearn | title = Amazons is PSPACE-complete | date = 2005-02-02 | eprint = cs.CC/0502013 }}
40. ^{{cite journal | title = Computer shogi | doi = 10.1016/S0004-3702(01)00157-6 | journal = Artificial Intelligence | volume=134 | issue=1–2 |date=January 2002 | pages=121–144 | author= Hiroyuki Iida |author2=Makoto Sakuta |author3=Jeff Rollason }}
41. ^{{cite journal |author1=H. Adachi |author2=H. Kamekawa |author3=S. Iwata | title = Shogi on n × n board is complete in exponential time | journal = Trans. IEICE | volume= J70-D | pages = 1843–1852 | year = 1987}}
42. ^{{cite web | title = Combinatorics of Go |author1=John Tromp |author2=Gunnar Farnebäck | year = 2007 | url = https://tromp.github.io/go/gostate.ps}} This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.
43. ^{{cite web | title=Number of legal Go positions | author=John Tromp | year=2016 | url=https://tromp.github.io/go/legal.html}}
44. ^{{Cite book | author = J. M. Robson | chapter = The complexity of Go | title = Information Processing; Proceedings of IFIP Congress | year = 1983 | pages = 413–417}}
45. ^{{cite web | title = Analysis and Implementation of the Game Arimaa | author = Christ-Jan Cox | year = 2006 | url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Cox_thesis1.pdf}}
46. ^{{cite web | title = Move Ranking and Evaluation in the Game of Arimaa | author = David Jian Wu | year = 2011 | url = http://icosahedral.net/downloads/djwuthesis.pdf}}
47. ^{{cite web | title = A Look at the Arimaa Branching Factor | author = Brian Haskin | year = 2006 | url = http://arimaa.janzert.com/bf_study/}}
48. ^{{cite thesis | author = A.F.C. Arts | title = Competitive Play in Stratego | year = 2010 | url =https://project.dke.maastrichtuniversity.nl/games/files/msc/Arts_thesis.pdf | publisher = Maastricht }}
49. ^Chess on an Infinite Plane game rules
50. ^Trappist-1 game rules

See also

  • Go and mathematics
  • Solved game
  • Solving chess
  • Shannon number
  • list of NP-complete games and puzzles
  • list of PSPACE-complete games and puzzles

References

External links

  • David Eppstein's Computational Complexity of Games and Puzzles
{{Game theory}}

2 : Combinatorial game theory|Game theory
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/11/12 8:02:18