# 游戏复杂度

## 游戏复杂度的衡量

### 决策树

#### 游戏树的复杂度

$GTC \geq b^d$

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

(格数)

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

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

(步数plies)

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[41] (52) <17 <40 52 5.6

## 注释与引用

1. ^ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 Victor Allis. Searching for Solutions in Games and Artificial Intelligence (Ph.D.论文). University of Limburg, Maastricht, The Netherlands. 1994. ISBN 90-900748-8-0.
2. ^ 2.0 2.1 2.2 2.3 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. ^ 4.0 4.1 4.2 4.3 4.4 4.5 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.
8. ^ Michael Lachmann. Who wins domineering on rectangular boards?. MSRI Combinatorial Game Theory Research Workshop. July 2000.
9. ^ Jonathan Schaeffer et al. Checkers is Solved. Science. July 6, 2007, 317 (5844): 1518–1522. doi:10.1126/science.1144079. PMID 17641166.
10. ^ 10.0 10.1 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. New Mathematics and Natural Computation. 2008, 4 (3): 369–387. doi:10.1142/S1793005708001124.
13. ^ 13.0 13.1 G.I. Bell. The Shortest Game of Chinese Checkers and Related Problems. Integers. 2009. arXiv:0803.1245.
14. ^ 14.0 14.1 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 (Ph.D.论文). Maastricht University, Maastricht, The Netherlands. 2004. ISBN 90-5278-429-9.
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 (论文). Maastricht University, Dept of Knowledge Engineering. 2009.
18. ^ Stefan Reisch. Hex ist PSPACE-vollst?ndig (Hex is PSPACE-complete). Acta Inf. 1981, (15): 167–191.
19. ^ 19.0 19.1 19.2 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. ^ 20.0 20.1 20.2 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. Philosophical Magazine. 1950, 41 (314). 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. 4525. 2009. doi:10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2.
24. ^ On the fairness and complexity of generalized k-in-a-row games
25. ^ http://books.nips.cc/papers/txt/nips04/0259.txt
26. ^ 26.0 26.1 Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu. Computer Chinese Chess. International Computer Games Association Journal. March 2004, 27 (1): 3–18.
27. ^ Chorus, Pascal. Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search. Dept of Knowledge Engineering, Maastricht University. [29 March 2012].
28. ^ Joosten, B. Creating a Havannah Playing Agent. [29 March 2012].
29. ^ Lisa Glendenning. Mastering Quoridor (B.Sc.论文). University of New Mexico. May 2005.
30. ^ Cathleen Heyden. Implementing a Computer Player for Carcassonne (论文). Maastricht University, Dept of Knowledge Engineering. 2009.
31. ^ The lower branching factor is for the second player.
32. ^ Julien Kloetzer; Hiroyuki Iida; Bruno Bouzy. The Monte-Carlo Approach in Amazons. 2007.
33. ^ P. P. L. M. Hensgens. A Knowledge-Based Approach of the Game of Amazons. Universiteit Maastricht, Institute for Knowledge and Agent Technology. 2001.
34. ^ R. A. Hearn. Amazons is PSPACE-complete. arXiv:cs.CC/0502013 [cs.CC]. 2005-02-02.
35. ^ 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.
36. ^ H. Adachi, H. Kamekawa, and S. Iwata. Shogi on n × n board is complete in exponential time. Trans. IEICE. 1987,. J70-D: 1843–1852.
37. ^ Christ-Jan Cox. Analysis and Implementation of the Game Arimaa. 2006.
38. ^ David Jian Wu. Move Ranking and Evaluation in the Game of Arimaa. 2011.
39. ^ Brian Haskin. A Look at the Arimaa Branching Factor. 2006.
40. ^ A.F.C. Arts. Competitive Play in Stratego (论文). 2010.
41. ^ 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.