博弈复杂度

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

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

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

注释
参考文献
外部链接

• David Eppstein's [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]

参见
*围棋与数学
*已解遊戲
*
*list of NP-complete games and puzzles
*list of PSPACE-complete games and puzzles

• AlphaZero
• 时间复杂度
• 計算複雜性理論