time-complexity - 您如何得出alpha-beta修剪的时间复杂度？

Question

我了解minimax和alpha-beta修剪的基础知识。在所有文献中，他们都讨论了最佳情况下的时间复杂度为O(b ^(d/2))，其中b =分支因子，d =树的深度，而基本情况是所有首选节点都为首先扩展。

在“最佳情况”的示例中，我有一个4级的二叉树，因此在16个终端节点中，我最多需要扩展7个节点。这与O(b ^(d/2))有什么关系？

我不明白他们是如何得出O(b ^(d/2))的。

Answer 1

O(b ^(d/2))对应于alpha-beta修剪的最佳情况时间复杂度。 Explanation:

With an (average or constant) branching factor of b, and a search depth of d plies, the maximum number of leaf node positions evaluated (when the move ordering is pessimal) is O(bb...*b) = O(b^d) – the same as a simple minimax search. If the move ordering for the search is optimal (meaning the best moves are always searched first), the number of leaf node positions evaluated is about O(b*1*b*1*...*b) for odd depth and O(b*1*b*1*...*1) for even depth, or O(b^(d/2)). In the latter case, where the ply of a search is even, the effective branching factor is reduced to its square root, or, equivalently, the search can go twice as deep with the same amount of computation.

The explanation of b*1*b*1*... is that all the first player's moves must be studied to find the best one, but for each, only the best second player's move is needed to refute all but the first (and best) first player move – alpha–beta ensures no other second player moves need be considered.

简而言之，您每两个级别“跳过”一次:

O描述了当参数趋于特定值或无穷大时函数的极限行为，因此在您的情况下，将O(b ^(d/2))与b和d的较小值进行精确比较实际上没有任何意义。