围棋的博弈树复杂度

    5.2.2　围棋的博弈树复杂度

    另一种经常使用的复杂度是博弈树复杂度。博弈树复杂度指的是从博弈初始状态所产生的、能完整解决该博弈问题的、最小博弈树叶子节点的个数。关于博弈树，请参见第2.1节。博弈树复杂度描述了通过极小极大搜索所能解决博弈的复杂度范围。关于极小极大搜索算法，请参见第2.4节。

    准确计算十九路围棋的博弈树复杂度也几乎是不可能的。虽然如此，我们仍可以使用以下方法粗略地估计围棋的博弈树复杂度。根据围棋比赛记录，我们可以估计每次围棋比赛所下的平均步数。我们也可以类似地估计博弈树节点上的分支数，该分支数可以是个常数，也可以是博弈树深度的一个函数。有了平均步数和节点分支数，我们就可以建立一棵博弈树，并计算该博弈树上叶子节点的个数。对于十九路围棋来讲，如果假设每次围棋比赛所下的平均步数是150，假设平均的节点分支数是250，那么，十九路围棋的博弈树复杂度约为10³⁶⁰。