博弈复杂度

博弈复杂度（）可以用许多方法加以衡量。本条目讲述其中的5種方法：状态空间复杂度（）、博弈树的大小（）、策略复杂度（）、博弈树复杂度（）與计算复杂度（）。

博弈复杂度的衡量
 状态空间复杂度 
状态空间复杂度指的是从博弈最开始的状态可以变化出的符合规则的状态的数量。

当这太难以计算时，常常通过包含一些不符合规则的状态或不可能在博弈中出现的状态, 从而计算出一个上界限。

 博弈树的大小 
博弈树的大小指的是博弈可以进行的总次数：从博弈树最初的根节点开始延伸出的叶子节点的数量.

博弈树通常比状态空间要大得多，因为同一个状态可以由不同的行为顺序形成。（例如，在一回合井字棋游戏中，面板上有两个X和一个O，这个状态可能由两个不同的方式形成，具体的形成过程由第一个X的下子位置所决定）。一个博弈树的大小的最大值有时可以这么计算：通过仅增大博弈树的方式，简化博弈的过程（例如，允许一些本来不符合规则的行为），直到博弈树的大小变得易于计算。

不过，对于一些没有行为上限的博弈（比如说没棋盘大小的界限，或者有一个可以重复博弈状态的规则），博弈树的大小将会是无限的。

 决策树 
之后的两种方案用到了决策树的方法。一个决策树是博弈树的子树。决策树的状态会被标记上「玩家A获胜」、「玩家B获胜」或者「平手」；如果有那个状态可以被证明具有一个标记（假设双方都作出了最好的决策），并且光从其它状态就可以得出结论.。（终端的状态可以直接标记；如果现在该A行动：如果下一个状态标志着A的胜利，那么现在的状态可以被标记为「玩家A获胜」；如果下一个状态标志着B的胜利，那么现在的状态可以被标记为「玩家B获胜」；或者可以被标记为「平手」，如果下一个状态是平局或者B胜利。相应的对于现在该B行动也是一样。）

 决策复杂度 
一个博弈的决策复杂度指的是在构成初始状态取值的最小的决策树中，叶子节点的数量。

 博弈树复杂度 
一个博弈的「博弈树复杂度」指的是在构成初始状态取值的最小「整个」决策树中，叶子节点的数量。整个决策树包含树中所有深度的节点。

这是一个为了尝试决定初始状态取值，所做出的对于需要考虑的节点数量的一个极小化极大算法（Minimax）。

就算是去估量博弈树复杂度，那也十分困难。不过对于一些博弈，一个合理的下界限可以由底数为博弈的平均分支因子，指数为博弈的的幂得出，即可以表示为：

 计算复杂度 
一个博弈的計算複雜性理論描述对博弈进行渐近分析的难度，随着它变得过于巨大，用大O符号表示，或者用复杂性类的成员关系表示。这个概念并不应用于特定的博弈，而是用于，它们会变得非常大，通常在一个n宽n高的面板上玩弄它们。（从计算复杂度的角度来看，一个在有限面板上进行的博弈是一个有限问题，可以通过计算O(1)解决。例如遍历从方案到最佳的移动方案的所有方案。）

例子: 井字棋

以井字棋而言，一个简单的状态空间大小的上界限是39 = 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里面。稍微再花点功夫，可以将它变换为。

一些知名博弈的复杂度
由于博弈复杂度非常巨大，下面表中一些数据只显示了以10为底数的指数部分。下面的表中的数值都需要小心对待：在博弈中，一个看起来很微小的规则变换会引起结果的巨大变化（通常依然会被粗略地估计），可能实际情况会比数值估计的结果要大得多。

博弈棋盘大小
(格数)状态空间复杂度
(以10为底数的指数部分)博弈树复杂度
(以10为底数的指数部分)平均博弈长度
()分枝因素引用对应的复杂性类井字棋93594PSPACE-completeSim1538143.7PSPACE-completeWolfgang Slany: The Complexity of Graph Ramsey Games五格骨牌6412181075Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance , MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf .?, but in PSPACE美國播棋See van den Herik et al for rules.141318Generalization is unclear屏風式四子棋421321364?, but in PSPACEDomineering (8 × 8)641527308?, but in PSPACE; in P for certain dimensions馬來播棋141533英國跳棋3220 or 1831702.8or EXPTIME-complete西非播棋See Allis 1994 for rules121232603.5Generalization is unclear多層式四子棋6430342054.2PSPACE-complete迂棋4521464411?, but in EXPTIME直棋2410505010?, but in EXPTIME西洋跳棋503054904EXPTIME-complete中國跳棋(2人)12123EXPTIME-complete  Proves completeness of the generalization to arbitrary graphs.中國跳棋(6人)12178EXPTIME-complete 集結棋6423644429?, but in EXPTIME黑白棋6428585810PSPACE-completeOnTop (2人局)7288623123.77六貫棋121579840280PSPACE-complete五子棋(15x15, 无禁手)2251057030210PSPACE-complete围棋(9x9)813845 This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.EXPTIME-complete國際象棋64471238035The size of the state space and game tree for chess were first estimated in  Shannon gave estimates of 1043 and 10120 respectively, smaller than the upper bound in the table,
which is detailed in Shannon number.EXPTIME-complete (without 50-move drawing rule) 連六棋3611721403046000PSPACE-completeOn the fairness and complexity of generalized k-in-a-row games雙陸棋282014450-60250Generalization is unclear象棋90401509538?, believed to be EXPTIME-complete角力棋61251548760?, but in EXPTIME三寶棋27112715766240?, but in PSPACE韓國將棋904416010040?, believed to be EXPTIME-complete牆棋81421629160?, but in PSPACE卡卡頌(2p base game)72>401957155Generalization is unclear亞馬遜棋1004021284374 or 299The lower branching factor is for the second player.PSPACE-complete围棋(13x13)1697990EXPTIME-complete日本将棋817122611592EXPTIME-complete印度鬥獸棋64434029217281?, but in EXPTIME围棋(19x19)361171360150250EXPTIME-complete西洋陸軍棋9211553538121.739Double dummy bridge(52)<17<40525.6

 注释 

 参考文献 

 外部链接 
 David Eppstein's Computational Complexity of Games and Puzzles 

 参见 

围棋与数学
已解遊戲

list of NP-complete games and puzzles
list of PSPACE-complete games and puzzles
 AlphaZero
 时间复杂度
 計算複雜性理論

Category:组合博弈论
Category:博弈论