# 游戏复杂度

## 游戏复杂度的衡量

### 决策树

#### 博弈树复杂度

${\displaystyle GTC\geq b^{d}}$

## 一些知名游戏的复杂度

(格数)

(以10为底数的指数部分)

(以10为底数的指数部分)

(步数英语Ply (game theory))

Sim 15 3 8 14 3.7 PSPACE-complete[3]

Domineering (8 × 8) 64 15 27 30 8 [4] ?, but in PSPACE; in P for certain dimensions[8]

OnTop (2人局) 72 88 62 31 23.77 [17]

Double dummy bridge[註 1] (52) <17 <40 52 5.6

## 注释

1. ^ 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, which motivates including it in the list. 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.

## 参考文献

1. Victor Allis. Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D.论文). University of Limburg, Maastricht, The Netherlands. 1994 [2014-02-12]. ISBN 90-900748-8-0. （原始内容存档 (PDF)于2020-09-27）.
2. Stefan Reisch. Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete). Acta Informatica. 1980, 13: 5966.
3. ^ Wolfgang Slany: The Complexity of Graph Ramsey Games
4. H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck. Games solved: Now and in the future. Artificial Intelligence. 2002, 134 (1–2): 277–311. doi:10.1016/S0004-3702(01)00152-7.
5. ^ Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance页面存档备份，存于互联网档案馆, MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf页面存档备份，存于互联网档案馆）.
6. ^ See van den Herik et al for rules.
7. ^ John Tromp. John's Connect Four Playground. 2010 [2014-02-12]. （原始内容存档于2003-04-08）.
8. ^ Cristopher Moore; Ivan Rapaport. Who wins domineering on rectangular boards?. MSRI Combinatorial Game Theory Research Workshop. July 2000. author-name-list parameters只需其一 (帮助); Authors list列表缺少`|last1=` (帮助)
9. ^ Jonathan Schaeffer; et al. Checkers is Solved. Science. July 6, 2007, 317 (5844): 1518–1522. PMID 17641166. doi:10.1126/science.1144079.
10. J. M. Robson. N by N checkers is Exptime complete. SIAM Journal on Computing,. 1984, 13 (2): 252–267. doi:10.1137/0213018.
11. ^ See Allis 1994 for rules
12. ^ 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 (PDF). New Mathematics and Natural Computation. 2008, 4 (3): 369–387 [2014-02-12]. doi:10.1142/S1793005708001124. （原始内容存档 (PDF)于2020-10-25）.
13. G.I. Bell. The Shortest Game of Chinese Checkers and Related Problems. Integers. 2009 [2020-03-24]. . （原始内容存档于2019-09-02）.
14. Takumi Kasai, Akeo Adachi, and Shigeki Iwata. Classes of Pebble Games and Complete Problems. SIAM Journal on Computing. 1979, 8 (4): 574–586. doi:10.1137/0208046. Proves completeness of the generalization to arbitrary graphs.
15. ^ Mark H.M. Winands. Informed Search in Complex Games (PDF) (Ph.D.论文). Maastricht University, Maastricht, The Netherlands. 2004 [2014-02-12]. ISBN 90-5278-429-9. （原始内容存档 (PDF)于2020-07-31）.
16. ^ S. Iwata and T. Kasai. The Othello game on an n*n board is PSPACE-complete. Theor. Comp. Sci. 1994, 123 (2): 329–340. doi:10.1016/0304-3975(94)90131-7.
17. ^ Robert Briesemeister. Analysis and Implementation of the Game OnTop (PDF) (学位论文). Maastricht University, Dept of Knowledge Engineering. 2009 [2014-02-12]. （原始内容存档 (PDF)于2014-03-06）.
18. ^ Stefan Reisch. Hex ist PSPACE-vollst?ndig (Hex is PSPACE-complete). Acta Inf. 1981, (15): 167–191.
19. John Tromp and Gunnar Farneb?ck. Combinatorics of Go. 2007.[永久失效連結] This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.
20. J. M. Robson. The complexity of Go. Information Processing; Proceedings of IFIP Congress. 1983: 413–417.
21. ^ The size of the state space and game tree for chess were first estimated in Claude Shannon. Programming a Computer for Playing Chess (PDF). Philosophical Magazine. 1950, 41 (314) [2014-02-12]. （原始内容 (PDF)存档于2010-03-15）. Shannon gave estimates of 1043 and 10120 respectively, smaller than the upper bound in the table, which is detailed in Shannon number.
22. ^ Aviezri Fraenkel and D. Lichtenstein. Computing a perfect strategy for n×n chess requires time exponential in n. J. Comb. Th. A. 1981, (31): 199–214.
23. ^ Chang-Ming Xu; Ma, Z.M.; Jun-Jie Tao; Xin-He Xu. Enhancements of proof number search in connect6. 2009 Chinese Control and Decision Conference. 2009: 4525. ISBN 978-1-4244-2722-2. doi:10.1109/CCDC.2009.5191963.
24. ^ On the fairness and complexity of generalized k-in-a-row games
25. ^ 存档副本. [2008-04-15]. （原始内容存档于2009-02-26）.
26. Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu. Computer Chinese Chess (PDF). International Computer Games Association Journal. March 2004, 27 (1): 3–18 [2014-02-12]. （原始内容 (PDF)存档于2007-06-14）.
27. Donghwi Park. Space-state complexity of Korean chess and Chinese chess. 2015 [2015-08-19]. （原始内容存档于2020-08-01）.
28. ^ Chorus, Pascal. Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search (PDF). Dept of Knowledge Engineering, Maastricht University. [29 March 2012]. （原始内容存档 (PDF)于2020-09-18）.
29. ^ Joosten, B. Creating a Havannah Playing Agent (PDF). [29 March 2012]. （原始内容存档 (PDF)于2016-03-03）.
30. ^ Lisa Glendenning. Mastering Quoridor (PDF). Computer Science (B.Sc.论文). University of New Mexico. May 2005 [2014-02-12]. （原始内容 (PDF)存档于2012-03-15）.
31. ^ Cathleen Heyden. Implementing a Computer Player for Carcassonne (PDF) (学位论文). Maastricht University, Dept of Knowledge Engineering. 2009 [2014-02-12]. （原始内容存档 (PDF)于2014-03-06）.
32. ^ The lower branching factor is for the second player.
33. ^ Julien Kloetzer; Hiroyuki Iida; Bruno Bouzy. The Monte-Carlo Approach in Amazons. 2007 [2014-02-12]. （原始内容存档于2012-10-17）.
34. ^ P. P. L. M. Hensgens. A Knowledge-Based Approach of the Game of Amazons (PDF). Universiteit Maastricht, Institute for Knowledge and Agent Technology. 2001 [2014-02-12]. （原始内容存档 (PDF)于2016-03-03）.
35. ^ R. A. Hearn. Amazons is PSPACE-complete. 2005-02-02. .
36. ^ Hiroyuki Iida, Makoto Sakuta, Jeff Rollason. Computer shogi. Artificial Intelligence. january 2002, 134 (1–2): 121–144. doi:10.1016/S0004-3702(01)00157-6.
37. ^ H. Adachi, H. Kamekawa, and S. Iwata. Shogi on n × n board is complete in exponential time. Trans. IEICE. 1987, J70–D: 1843–1852.
38. ^ Christ-Jan Cox. Analysis and Implementation of the Game Arimaa (PDF). 2006 [2014-02-12]. （原始内容存档 (PDF)于2020-10-27）.
39. ^ David Jian Wu. Move Ranking and Evaluation in the Game of Arimaa (PDF). 2011 [2014-02-12]. （原始内容存档 (PDF)于2017-03-17）.
40. ^ Brian Haskin. A Look at the Arimaa Branching Factor. 2006 [2014-02-12]. （原始内容存档于2009-11-07）.
41. ^ A.F.C. Arts. Competitive Play in Stratego (PDF) (学位论文). Maastricht. 2010 [2014-02-12]. （原始内容存档 (PDF)于2016-03-04）.