博弈複雜度

博弈複雜度（英語：game complexity）可以用許多方法加以衡量。本條目講述其中的5種方法：狀態空間複雜度（state-space complexity）、博弈樹的大小（game tree size）、策略複雜度（decision complexity）、博弈樹複雜度（game-tree complexity）與計算複雜度（computational complexity）。

博弈複雜度的衡量

狀態空間複雜度

狀態空間複雜度指的是從博弈最開始的狀態可以變化出的符合規則的狀態的數量。^[1]

當這太難以計算時，常常通過包含一些不符合規則的狀態或不可能在博弈中出現的狀態, 從而計算出一個上界限。

博弈樹的大小

博弈樹的大小指的是博弈可以進行的總次數：從博弈樹最初的根節點開始延伸出的葉子節點的數量.

博弈樹通常比狀態空間要大得多，因為同一個狀態可以由不同的行為順序形成。（例如，在一回合井字棋遊戲中，面板上有兩個X和一個O，這個狀態可能由兩個不同的方式形成，具體的形成過程由第一個X的下子位置所決定）。一個博弈樹的大小的最大值有時可以這麼計算：通過僅增大博弈樹的方式，簡化博弈的過程（例如，允許一些本來不符合規則的行為），直到博弈樹的大小變得易於計算。

不過，對於一些沒有行為上限的博弈（比如說沒棋盤大小的界限，或者有一個可以重複博弈狀態的規則），博弈樹的大小將會是無限的。

決策樹

之後的兩種方案用到了決策樹的方法。一個決策樹是博弈樹的子樹。決策樹的狀態會被標記上「玩家A獲勝」、「玩家B獲勝」或者「平手」；如果有那個狀態可以被證明具有一個標記（假設雙方都作出了最好的決策），並且光從其它狀態就可以得出結論.。（終端的狀態可以直接標記；如果現在該A行動：如果下一個狀態標誌着A的勝利，那麼現在的狀態可以被標記為「玩家A獲勝」；如果下一個狀態標誌着B的勝利，那麼現在的狀態可以被標記為「玩家B獲勝」；或者可以被標記為「平手」，如果下一個狀態是平局或者B勝利。相應的對於現在該B行動也是一樣。）

決策複雜度

一個博弈的決策複雜度指的是在構成初始狀態取值的最小的決策樹中，葉子節點的數量。

博弈樹複雜度

一個博弈的「博弈樹複雜度」指的是在構成初始狀態取值的最小「整個」決策樹中，葉子節點的數量。^[1] 整個決策樹包含樹中所有深度的節點。

這是一個為了嘗試決定初始狀態取值，所做出的對於需要考慮的節點數量的一個極小化極大算法（Minimax）。

就算是去估量博弈樹複雜度，那也十分困難。不過對於一些博弈，一個合理的下界限可以由底數為博弈的平均分支因子，指數為博弈的平均步數（英語：Ply (game theory)）的冪得出，即可以表示為：

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

計算複雜度

一個博弈的計算複雜性理論描述對博弈進行漸近分析的難度，隨着它變得過於巨大，用大O符號表示，或者用複雜性類的成員關係表示。這個概念並不應用於特定的博弈，而是用於廣義的博弈（英語：Generalized game），它們會變得非常大，通常在一個n寬n高的面板上玩弄它們。（從計算複雜度的角度來看，一個在有限面板上進行的博弈是一個有限問題，可以通過計算O(1)解決。例如遍歷從方案到最佳的移動方案的所有方案。）

例子: 井字棋

參見：井字棋

以井字棋而言，一個簡單的狀態空間大小的上界限是3⁹ = 19,683。（ 每一個格子中有3種狀態,，有9個格子）這樣計算包含了許多不合規則的狀態，比如有5個X卻沒有0的狀態，或者兩方玩家都有形成一字的狀態。一個更精細的計算，除去了這些不合規則的狀態之後，留下5,478個狀態。然後，如果把旋轉或翻轉後會得到相同結果的狀態算作同一個的狀態話，那麼就可以得出765個真正本質上不同的狀態。

一個簡單的博弈樹大小的上界限是9! = 362,880。（一開始有9個格子可以下子,，第二回合變為8個，以此類推）這包括了一方玩家獲勝後繼續下子的不符合規則的情況。一個更精細的計算得出的是255,168種博弈過程。如果把旋轉或翻轉後會得到相同結果的狀態當作相同的話，那麼就僅有26,830種博弈過程。

井字棋的計算複雜度取決與它如何廣義化。一種自然的廣義化是將其變為m,n,k型博弈：在一個寬"m"高"n"的棋盤上，第一個將"k"個子連成一線的玩家獲勝。很容易就可以發現，這個博弈可以通過查找整個博弈樹，解DSPACE(mn)，得出結果。這將它歸類到了重要的複雜性類PSPACE裏面。稍微再花點功夫，可以將它變換為PSPACE完整（英語：PSPACE-complete）。^[2]

一些知名博弈的複雜度

由於博弈複雜度非常巨大，下面表中一些數據只顯示了以10為底數的指數部分。下面的表中的數值都需要小心對待：在博弈中，一個看起來很微小的規則變換會引起結果的巨大變化（通常依然會被粗略地估計），可能實際情況會比數值估計的結果要大得多。

博弈	棋盤大小 (格數)	狀態空間複雜度 (以10為底數的指數部分)	博弈樹複雜度 (以10為底數的指數部分)	平均博弈長度 (步數（英語：Ply (game theory)）)	分枝因素	引用	對應廣義化博弈（英語：generalized game）的複雜性類
井字棋	9	3	5	9	4		PSPACE-complete[2]
Sim	15	3	8	14	3.7		PSPACE-complete[3]
五格骨牌	64	12	18	10	75	[4] [5]	?, but in PSPACE
美國播棋[6]	14	13	18			[4]	Generalization is unclear
屏風式四子棋	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]
馬來播棋	14	15	33			[4]
英國跳棋	32	20 or 18	31	70	2.8	[9] or [1]	EXPTIME-complete[10]
西非播棋[11]	12	12	32	60	3.5	[1]	Generalization is unclear
多層式四子棋	64	30	34	20	54.2	[1]	PSPACE-complete[2]
迂棋	45	21	46	44	11	[12]	?, but in EXPTIME
直棋	24	10	50	50	10	[1]	?, but in EXPTIME
西洋跳棋	50	30	54	90	4	[1]	EXPTIME-complete[10]
中國跳棋(2人)	121	23				[13]	EXPTIME-complete [14]
中國跳棋(6人)	121	78				[13]	EXPTIME-complete [14]
集結棋	64	23	64	44	29	[15]	?, but in EXPTIME
黑白棋	64	28	58	58	10	[1]	PSPACE-complete[16]
OnTop (2人局)	72	88	62	31	23.77	[17]
六貫棋	121	57	98	40	280	[4]	PSPACE-complete[18]
五子棋(15x15, 無禁手)	225	105	70	30	210	[1]	PSPACE-complete[2]
圍棋(9x9)	81	38		45		[19] [1]	EXPTIME-complete[20]
國際象棋	64	47	123	80	35	[21]	EXPTIME-complete (without 50-move drawing rule) [22]
連六棋	361	172	140	30	46000	[23]	PSPACE-complete[24]
雙陸棋	28	20	144	50-60	250	[25]	Generalization is unclear
象棋	90	40	150	95	38	[1] [26][27]	?, believed to be EXPTIME-complete
角力棋	61	25	154	87	60	[28]	?, but in EXPTIME
三寶棋	271	127	157	66	240	[4] [29]	?, but in PSPACE
韓國將棋	90	44	160	100	40	[27]	?, believed to be EXPTIME-complete
牆棋	81	42	162	91	60	[30]	?, but in PSPACE
卡卡頌(2p base game)	72	>40	195	71	55	[31]	Generalization is unclear
亞馬遜棋	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]
印度鬥獸棋	64	43	402	92	17281	[38] [39] [40]	?, but in EXPTIME
圍棋(19x19)	361	171	360	150	250	[19] [1]	EXPTIME-complete[20]
西洋陸軍棋	92	115	535	381	21.739	[41]
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. 引文格式1維護：顯式使用等標籤 (link)
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]. arXiv:0803.1245 . （原始內容存檔於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 10⁴³ and 10¹²⁰ 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. arXiv:cs.CC/0502013 .
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 [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）.

外部連結

• David Eppstein's Computational Complexity of Games and Puzzles （頁面存檔備份，存於互聯網檔案館）

參見

• 圍棋與數學
• 已解遊戲
• 香農數（英語：Shannon number）
• list of NP-complete games and puzzles
• list of PSPACE-complete games and puzzles
• AlphaZero
• 時間複雜度
• 計算複雜性理論