游戏复杂度(game complexity)，有许多方法来衡量之。本条目讲述其中的5种方法：状态空间复杂度（state-space complexity），游戏树的大小（game tree size），策略复杂度（decision complexity），游戏树的复杂度（game-tree complexity），和计算复杂度（computational complexity）。

[micxp_threadbk] [micxp_title] 游戏复杂度的衡量 游戏树的大小 决策树 游戏树的复杂度 计算复杂度 例子: 井字棋 一些知名游戏的复杂度 参考 注释与引用 外部链接 [/micxp_title] [#] [##] 游戏树的大小指的是游戏可以被玩弄的总次数: 从游戏树( game tree )最初的根节点开始延伸出的叶子节点的数量. 游戏树通常比状态空间要大得多, 因为同一个状态可以由不同的行为顺序形成. ( 例如, 在一次井字棋( tic-tac-toe )游戏中, 面板上有两个X和一个O, 这个状态可能由两个不同的方式形成, 具体的形成过程由第一个X的下子位置所决定 ). 一个游戏树的大小的最大值有时可以这么计算: 通过仅增大游戏树的方式, 简化游戏的过程( 例如, 允许一些本来不符合规则的行为 ), 直到游戏树的大小变得易于计算. 不过, 对于一些没有行为上限的游戏( 比如说没棋盘大小的界限, 或者有一个可以重复游戏状态的规则 ), 游戏树的大小将会是无限的. [###] 之后的两种方案用到了决策树的方法. 一个决策树是游戏树的子树. 决策树的状态会被标记上"玩家A获胜", "玩家B获胜", 或者"平局": 如果有那个状态可以被证明具有一个标记( 假设双方都作出了最好的决策 ), 并且光从其它状态就可以得出结论. ( 终端的状态可以直接标记; 如果现在该A行动: 如果下一个状态标志着A的胜利, 那么现在的状态可以被标记为"玩家A获胜"; 如果下一个状态标志着B的胜利, 那么现在的状态可以被标记为"玩家B获胜"; 或者可以被标记为"平局", 如果下一个状态是平局或者B胜利. 相应的对于现在该B行动也是一样. ) [####] 一个游戏的"游戏数的复杂度"指的是在构成初始状态取值的最小"整个"决策树中, 叶子节点的数量.[1] 整个决策树包含树中所有深度的节点. 这是一个为了尝试决定初始状态取值, 所做出的对于需要考虑的节点数量的一个极小化极大算法( Minimax ). 就算是去估量游戏树的复杂度, 那也是很困难的. 不过对于一些游戏, 一个合理的下界限可以由底数为游戏的平均分支因子（英语：branching factor），指数为游戏的平均步数( plies )的幂得出, 可以表示为: ${\displaystyle GTC\ge b^d}$ [#####] 一个游戏的计算复杂度( computational complexity ) 描述了对游戏进行渐近分析( asymptotic )的难度, 随着它变得过于巨大, 用大O符号( big O notation )表示, 或者用复杂性类( complexity class )的成员关系表示. 这个概念并不应用于特定的游戏, 而是用于广义的游戏( generalized ), 它们会变得非常大, 通常在一个n宽n高的面板上玩弄它们. ( 从计算复杂度的角度来看, 一个在有限面板上进行的游戏是一个有限问题, 可以通过计算O(1)解决. 例如遍历从方案到最佳的移动方案的所有方案. ) [######] 对于井字棋( tic-tac-toe )来说, 一个简单的状态空间大小的上界限是39 = 19,683. ( 每一个格子中有3种状态, 有9个格子. ) 这样计算包含了许多不合规则的状态, 比如有5个X却没有0的状态, 或者两方玩家都有形成一字的状态. 一个更精细的计算, 除去了这些不合规则的状态之后, 留下5,478个状态. 然后, 如果把旋转或翻转后会得到相同结果的状态算作同一个的状态话, 那么就可以得出765个真正本质上不同的状态. 一个简单的游戏树大小的上界限是9! = 362,880. ( 一开始有9个格子可以下子, 第二回合变为8个, 以此类推. ) 这包括了一方玩家获胜后继续下子的不符合规则的情况. 一个更精细的计算得出的是255,168种游戏过程. 如果把旋转或翻转后会得到相同结果的状态当作相同的话, 那么就仅有26,830种游戏过程. 井字棋的计算复杂度取决与它如何广义化( generalized ). 一种自然的广义化是将其变为m,n,k型游戏( m,n,k-games ): 在一个"m"宽"n"高的棋盘上, 第一个将"k"个子连成一线的玩家获胜. 很容易就可以发现, 这个游戏可以通过查找整个游戏树, 解DSPACE(mn), 得出结果. 这将它归类到了重要的复杂性类PSPACE里面. 稍微再花点功夫, 可以将它变换为PSPACE-complete.[2] [#######] 由于游戏复杂度非常巨大, 下面表中一些数据只显示了以10为底数的指数部分. 下面的表中的数值都需要小心对待: 在游戏中, 一个看起来很微小的规则变换会引起结果的巨大变化( 通常依然会被粗略地估计 ), 可能实际情况会比数值估计的结果要大得多.

游戏	棋盘大小 (格数)	状态空间复杂度 (以10为底数的指数部分)	游戏树的复杂度 (以10为底数的指数部分)	平均游戏长度 (步数plies)	分枝因素	引用	对应广义化游戏的复杂性类
井字棋Tic-tac-toe	9	3	5	9	4		PSPACE-complete[2]
Sim	15	3	8	14	3.7		PSPACE-complete[3]
五格骨牌Pentominoes	64	12	18	10	75	[4] [5]	?, but in PSPACE
美国播棋Kalah [6]	14	13	18			[4]	Generalization is unclear
屏风式四子棋Connect Four	42	13	21	36	4	[7] [1]	?, but in PSPACE
Domineering (8 × 8)	64	15	27	30	8	[4]	?, but in PSPACE; in P for certain dimensions[8]
马来播棋Congkak	14	15	33			[4]
英国跳棋English draughts (8x8) (checkers)	32	20 or 18	31	70	2.8	[9] or [1]	EXPTIME-complete[10]
西非播棋Awari[11]	12	12	32	60	3.5	[1]	Generalization is unclear
多层式四子棋Qubic	64	30	34	20	54.2	[1]	PSPACE-complete[2]
迂棋Fanorona	45	21	46	44	11	[12]	?, but in EXPTIME
直棋Nine Men's Morris	24	10	50	50	10	[1]	?, but in EXPTIME
西洋跳棋International draughts (10x10)	50	30	54	90	4	[1]	EXPTIME-complete[10]
中国跳棋Chinese checkers (2人)	121	23				[13]	EXPTIME-complete [14]
中国跳棋Chinese checkers (6人)	121	78				[13]	EXPTIME-complete [14]
集结棋Lines of Action	64	23	64	44	29	[15]	?, but in EXPTIME
黑白棋Reversi	64	28	58	58	10	[1]	PSPACE-complete[16]
OnTop (2人局)	72	88	62	31	23.77	[17]
六贯棋Hex (11x11)	121	57	98	40	280	[4]	PSPACE-complete[18]
五子棋Gomoku (15x15, 无禁手)	225	105	70	30	210	[1]	PSPACE-complete[2]
围棋Go (9x9)	81	38		45		[19] [1]	EXPTIME-complete[20]
国际象棋Chess	64	47	123	80	35	[21]	EXPTIME-complete (without 50-move drawing rule) [22]
连六棋Connect6	361	172	140	30	46000	[23]	PSPACE-complete[24]
双陆棋Backgammon	28	20	144	50-60	250	[25]	Generalization is unclear
象棋Xiangqi	90	40	150	95	38	[1] [26][27]	?, believed to be EXPTIME-complete
角力棋Abalone	61	25	154	87	60	[28]	?, but in EXPTIME
三宝棋Havannah	271	127	157	66	240	[4] [29]	?, but in PSPACE
韩国将棋Janggi	90	44	160	100	40	[27]	?, believed to be EXPTIME-complete
墙棋Quoridor	81	42	162	91	60	[30]	?, but in PSPACE
卡卡颂Carcassonne (2p base game)	72	>40	195	71	55	[31]	Generalization is unclear
亚马逊棋Amazons (10x10)	100	40	212	84	374 or 299[32]	[33] [34]	PSPACE-complete[35]
围棋(13x13)	169	79		90		[1] [19]	EXPTIME-complete[20]
将棋	81	71	226	115	92	[26] [36]	EXPTIME-complete[37]
印度斗兽棋Arimaa	64	43	402	92	17281	[38] [39] [40]	?, but in EXPTIME
围棋Go (19x19)	361	171	360	150	250	[19] [1]	EXPTIME-complete[20]
西洋陆军棋Stratego	92	115	535	381	21.739	[41]
Double dummy bridge[42]	(52)	<17	<40	52	5.6

[########]

• Go and mathematics
• 已解游戏
• Shannon number
• list of NP-complete games and puzzles
• list of PSPACE-complete games and puzzles

[#########]

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 (PDF) (Ph.D. thesis). 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. ^ 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; 等. Checkers is Solved. Science. July 6, 2007, 317 (5844): 1518–1522. doi:10.1126/science.1144079. PMID 17641166.  引文格式1维护：显式使用等标签 (link)
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 (PDF). 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 (PDF) (Ph.D. thesis). 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 (PDF) (Thesis). 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 48N))<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 (PDF). 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. 2009 Chinese Control and Decision Conference: 4525. 2009. doi:10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2.  |chapter=被忽略 (帮助)
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 (PDF). International Computer Games Association Journal. March 2004, 27 (1): 3–18. 
27. ^ 27.0 27.1 Donghwi Park. Space-state complexity of Korean chess and Chinese chess. 2015. 
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]. 
29. ^ Joosten, B. Creating a Havannah Playing Agent (PDF). [29 March 2012]. 
30. ^ Lisa Glendenning. Mastering Quoridor (PDF). Computer Science (B.Sc. thesis). University of New Mexico. May 2005. 
31. ^ Cathleen Heyden. Implementing a Computer Player for Carcassonne (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering. 2009. 
32. ^ The lower branching factor is for the second player.
33. ^ Julien Kloetzer; Hiroyuki Iida; Bruno Bouzy. The Monte-Carlo Approach in Amazons. 2007. 
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. 
35. ^ R. A. Hearn. Amazons is PSPACE-complete. arXiv:cs.CC/0502013 [cs.CC]. 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.  请检查|date=中的日期值 (帮助)
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. 
39. ^ David Jian Wu. Move Ranking and Evaluation in the Game of Arimaa (PDF). 2011. 
40. ^ Brian Haskin. A Look at the Arimaa Branching Factor. 2006. 
41. ^ A.F.C. Arts. Competitive Play in Stratego (PDF) (Thesis). 2010.  已忽略未知参数|university= (帮助)
42. ^ 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.

[##########]

• David Eppstein's Computational Complexity of Games and Puzzles

分类：

• 组合博弈论
• 博弈论

隐藏分类：

• 含有冗余参数的引用的页面
• 引文格式1错误：缺少作者或编者
• 引文格式1维护：显式使用等标签
• 引文格式1错误：章节参数被忽略
• 引文格式1错误：日期
• 含有未知参数的引用的页面
• 含有英语的条目

[/micxp_threadbk]

游戏复杂度(game complexity)，有许多方法来衡量之。本条目讲述其中的5种方法：状态空间复杂度（state-space complexity），游戏树的大小（game tree size），策略复杂度（decision complexity），游戏树的复杂度（game-tree complexity），和计算复杂度（computational complexity）。

[micxp_threadbk] [micxp_title] 游戏复杂度的衡量 游戏树的大小 决策树 游戏树的复杂度 计算复杂度 例子: 井字棋 一些知名游戏的复杂度 参考 注释与引用 外部链接 [/micxp_title] [#] [##] 游戏树的大小指的是游戏可以被玩弄的总次数: 从游戏树( game tree )最初的根节点开始延伸出的叶子节点的数量. 游戏树通常比状态空间要大得多, 因为同一个状态可以由不同的行为顺序形成. ( 例如, 在一次井字棋( tic-tac-toe )游戏中, 面板上有两个X和一个O, 这个状态可能由两个不同的方式形成, 具体的形成过程由第一个X的下子位置所决定 ). 一个游戏树的大小的最大值有时可以这么计算: 通过仅增大游戏树的方式, 简化游戏的过程( 例如, 允许一些本来不符合规则的行为 ), 直到游戏树的大小变得易于计算. 不过, 对于一些没有行为上限的游戏( 比如说没棋盘大小的界限, 或者有一个可以重复游戏状态的规则 ), 游戏树的大小将会是无限的. [###] 之后的两种方案用到了决策树的方法. 一个决策树是游戏树的子树. 决策树的状态会被标记上"玩家A获胜", "玩家B获胜", 或者"平局": 如果有那个状态可以被证明具有一个标记( 假设双方都作出了最好的决策 ), 并且光从其它状态就可以得出结论. ( 终端的状态可以直接标记; 如果现在该A行动: 如果下一个状态标志着A的胜利, 那么现在的状态可以被标记为"玩家A获胜"; 如果下一个状态标志着B的胜利, 那么现在的状态可以被标记为"玩家B获胜"; 或者可以被标记为"平局", 如果下一个状态是平局或者B胜利. 相应的对于现在该B行动也是一样. ) [####] 一个游戏的"游戏数的复杂度"指的是在构成初始状态取值的最小"整个"决策树中, 叶子节点的数量.[1] 整个决策树包含树中所有深度的节点. 这是一个为了尝试决定初始状态取值, 所做出的对于需要考虑的节点数量的一个极小化极大算法( Minimax ). 就算是去估量游戏树的复杂度, 那也是很困难的. 不过对于一些游戏, 一个合理的下界限可以由底数为游戏的平均分支因子（英语：branching factor），指数为游戏的平均步数( plies )的幂得出, 可以表示为: ${\displaystyle GTC\ge b^d}$ [#####] 一个游戏的计算复杂度( computational complexity ) 描述了对游戏进行渐近分析( asymptotic )的难度, 随着它变得过于巨大, 用大O符号( big O notation )表示, 或者用复杂性类( complexity class )的成员关系表示. 这个概念并不应用于特定的游戏, 而是用于广义的游戏( generalized ), 它们会变得非常大, 通常在一个n宽n高的面板上玩弄它们. ( 从计算复杂度的角度来看, 一个在有限面板上进行的游戏是一个有限问题, 可以通过计算O(1)解决. 例如遍历从方案到最佳的移动方案的所有方案. ) [######] 对于井字棋( tic-tac-toe )来说, 一个简单的状态空间大小的上界限是39 = 19,683. ( 每一个格子中有3种状态, 有9个格子. ) 这样计算包含了许多不合规则的状态, 比如有5个X却没有0的状态, 或者两方玩家都有形成一字的状态. 一个更精细的计算, 除去了这些不合规则的状态之后, 留下5,478个状态. 然后, 如果把旋转或翻转后会得到相同结果的状态算作同一个的状态话, 那么就可以得出765个真正本质上不同的状态. 一个简单的游戏树大小的上界限是9! = 362,880. ( 一开始有9个格子可以下子, 第二回合变为8个, 以此类推. ) 这包括了一方玩家获胜后继续下子的不符合规则的情况. 一个更精细的计算得出的是255,168种游戏过程. 如果把旋转或翻转后会得到相同结果的状态当作相同的话, 那么就仅有26,830种游戏过程. 井字棋的计算复杂度取决与它如何广义化( generalized ). 一种自然的广义化是将其变为m,n,k型游戏( m,n,k-games ): 在一个"m"宽"n"高的棋盘上, 第一个将"k"个子连成一线的玩家获胜. 很容易就可以发现, 这个游戏可以通过查找整个游戏树, 解DSPACE(mn), 得出结果. 这将它归类到了重要的复杂性类PSPACE里面. 稍微再花点功夫, 可以将它变换为PSPACE-complete.[2] [#######] 由于游戏复杂度非常巨大, 下面表中一些数据只显示了以10为底数的指数部分. 下面的表中的数值都需要小心对待: 在游戏中, 一个看起来很微小的规则变换会引起结果的巨大变化( 通常依然会被粗略地估计 ), 可能实际情况会比数值估计的结果要大得多.

游戏	棋盘大小 (格数)	状态空间复杂度 (以10为底数的指数部分)	游戏树的复杂度 (以10为底数的指数部分)	平均游戏长度 (步数plies)	分枝因素	引用	对应广义化游戏的复杂性类
井字棋Tic-tac-toe	9	3	5	9	4		PSPACE-complete[2]
Sim	15	3	8	14	3.7		PSPACE-complete[3]
五格骨牌Pentominoes	64	12	18	10	75	[4] [5]	?, but in PSPACE
美国播棋Kalah [6]	14	13	18			[4]	Generalization is unclear
屏风式四子棋Connect Four	42	13	21	36	4	[7] [1]	?, but in PSPACE
Domineering (8 × 8)	64	15	27	30	8	[4]	?, but in PSPACE; in P for certain dimensions[8]
马来播棋Congkak	14	15	33			[4]
英国跳棋English draughts (8x8) (checkers)	32	20 or 18	31	70	2.8	[9] or [1]	EXPTIME-complete[10]
西非播棋Awari[11]	12	12	32	60	3.5	[1]	Generalization is unclear
多层式四子棋Qubic	64	30	34	20	54.2	[1]	PSPACE-complete[2]
迂棋Fanorona	45	21	46	44	11	[12]	?, but in EXPTIME
直棋Nine Men's Morris	24	10	50	50	10	[1]	?, but in EXPTIME
西洋跳棋International draughts (10x10)	50	30	54	90	4	[1]	EXPTIME-complete[10]
中国跳棋Chinese checkers (2人)	121	23				[13]	EXPTIME-complete [14]
中国跳棋Chinese checkers (6人)	121	78				[13]	EXPTIME-complete [14]
集结棋Lines of Action	64	23	64	44	29	[15]	?, but in EXPTIME
黑白棋Reversi	64	28	58	58	10	[1]	PSPACE-complete[16]
OnTop (2人局)	72	88	62	31	23.77	[17]
六贯棋Hex (11x11)	121	57	98	40	280	[4]	PSPACE-complete[18]
五子棋Gomoku (15x15, 无禁手)	225	105	70	30	210	[1]	PSPACE-complete[2]
围棋Go (9x9)	81	38		45		[19] [1]	EXPTIME-complete[20]
国际象棋Chess	64	47	123	80	35	[21]	EXPTIME-complete (without 50-move drawing rule) [22]
连六棋Connect6	361	172	140	30	46000	[23]	PSPACE-complete[24]
双陆棋Backgammon	28	20	144	50-60	250	[25]	Generalization is unclear
象棋Xiangqi	90	40	150	95	38	[1] [26][27]	?, believed to be EXPTIME-complete
角力棋Abalone	61	25	154	87	60	[28]	?, but in EXPTIME
三宝棋Havannah	271	127	157	66	240	[4] [29]	?, but in PSPACE
韩国将棋Janggi	90	44	160	100	40	[27]	?, believed to be EXPTIME-complete
墙棋Quoridor	81	42	162	91	60	[30]	?, but in PSPACE
卡卡颂Carcassonne (2p base game)	72	>40	195	71	55	[31]	Generalization is unclear
亚马逊棋Amazons (10x10)	100	40	212	84	374 or 299[32]	[33] [34]	PSPACE-complete[35]
围棋(13x13)	169	79		90		[1] [19]	EXPTIME-complete[20]
将棋	81	71	226	115	92	[26] [36]	EXPTIME-complete[37]
印度斗兽棋Arimaa	64	43	402	92	17281	[38] [39] [40]	?, but in EXPTIME
围棋Go (19x19)	361	171	360	150	250	[19] [1]	EXPTIME-complete[20]
西洋陆军棋Stratego	92	115	535	381	21.739	[41]
Double dummy bridge[42]	(52)	<17	<40	52	5.6

[########]

• Go and mathematics
• 已解游戏
• Shannon number
• list of NP-complete games and puzzles
• list of PSPACE-complete games and puzzles

[#########]

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 (PDF) (Ph.D. thesis). 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. ^ 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; 等. Checkers is Solved. Science. July 6, 2007, 317 (5844): 1518–1522. doi:10.1126/science.1144079. PMID 17641166.  引文格式1维护：显式使用等标签 (link)
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 (PDF). 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 (PDF) (Ph.D. thesis). 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 (PDF) (Thesis). 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 48N))<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 (PDF). 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. 2009 Chinese Control and Decision Conference: 4525. 2009. doi:10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2.  |chapter=被忽略 (帮助)
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 (PDF). International Computer Games Association Journal. March 2004, 27 (1): 3–18. 
27. ^ 27.0 27.1 Donghwi Park. Space-state complexity of Korean chess and Chinese chess. 2015. 
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]. 
29. ^ Joosten, B. Creating a Havannah Playing Agent (PDF). [29 March 2012]. 
30. ^ Lisa Glendenning. Mastering Quoridor (PDF). Computer Science (B.Sc. thesis). University of New Mexico. May 2005. 
31. ^ Cathleen Heyden. Implementing a Computer Player for Carcassonne (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering. 2009. 
32. ^ The lower branching factor is for the second player.
33. ^ Julien Kloetzer; Hiroyuki Iida; Bruno Bouzy. The Monte-Carlo Approach in Amazons. 2007. 
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. 
35. ^ R. A. Hearn. Amazons is PSPACE-complete. arXiv:cs.CC/0502013 [cs.CC]. 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.  请检查|date=中的日期值 (帮助)
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. 
39. ^ David Jian Wu. Move Ranking and Evaluation in the Game of Arimaa (PDF). 2011. 
40. ^ Brian Haskin. A Look at the Arimaa Branching Factor. 2006. 
41. ^ A.F.C. Arts. Competitive Play in Stratego (PDF) (Thesis). 2010.  已忽略未知参数|university= (帮助)
42. ^ 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.

[##########]

• David Eppstein's Computational Complexity of Games and Puzzles

分类：

• 组合博弈论
• 博弈论

隐藏分类：

• 含有冗余参数的引用的页面
• 引文格式1错误：缺少作者或编者
• 引文格式1维护：显式使用等标签
• 引文格式1错误：章节参数被忽略
• 引文格式1错误：日期
• 含有未知参数的引用的页面
• 含有英语的条目

[/micxp_threadbk]