【摘要】：复杂度是计算机博弈中的一个基本概念，用来衡量使用计算机程序解决博弈问题时所需资源的多少。①状态空间复杂度：对于某个博弈而言，其状态空间复杂度指的是从该博弈的初始状态开始所能达到的、所有不同的合法博弈状态的个数。从本质上，状态空间复杂度描述了通过枚举方法所能解决博弈复杂度的范围。在很多情况下，准确地计算某种博弈的状态空间复杂度和博弈树复杂度都是比较困难的。
2.2.1 博弈的复杂度
复杂度是计算机博弈中的一个基本概念，用来衡量使用计算机程序解决博弈问题时所需资源的多少。在衡量时间资源时，使用时间复杂度的概念；在衡量空间资源时，使用空间复杂度的概念。在计算机博弈理论中有多种描述博弈复杂度的方法，比较常使用的两个分别是状态空间复杂度和博弈树复杂度。
①状态空间复杂度：对于某个博弈而言，其状态空间复杂度指的是从该博弈的初始状态开始所能达到的、所有不同的合法博弈状态的个数。从本质上，状态空间复杂度描述了通过枚举方法所能解决博弈复杂度的范围。
②博弈树复杂度：对于某个博弈而言，其博弈树复杂度指的是从该博弈的初始状态所产生的、能完整解决该博弈问题的最小博弈树中叶子节点的个数。从本质上，博弈树复杂度描述了通过在博弈树上搜索方法所能解决博弈复杂度的范围。
在很多情况下，准确地计算某种博弈的状态空间复杂度和博弈树复杂度都是比较困难的。但我们通常可以通过近似的方法，估计该博弈的状态空间复杂度和博弈树复杂度。
表2.1列出了除围棋之外的主要博弈种类的空间状态复杂度和博弈树复杂度。
表2.1 围棋之外主要博弈的状态空间复杂度和博弈树复杂度
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
