【摘要】：极小极大值算法从当前状态计算极小极大决策。它使用了简单的递归算法，计算每个后继的极小极大值，直接实现定义公式。递归算法自上而下一直前进到树的叶节点，然后随着递归回溯，通过树把极小极大值回传。最后我们在3、2和2中选取最大值3作为回传值返回给根节点。函数MAX-VALUE和MIN-VALUE穿过整个博弈树一直到叶节点，以决定每一个状态的回传值极小极大值算法对博弈树执行了一个完整的深度优先探索。
6.2.2 极小极大值算法
极小极大值算法（图6.3）从当前状态计算极小极大决策。它使用了简单的递归算法，计算每个后继的极小极大值，直接实现定义公式。递归算法自上而下一直前进到树的叶节点，然后随着递归回溯，通过树把极小极大值回传。例如，在图6.2中，算法先递归到三个底层的叶节点，对它们调用UTILITY函数发现它们的值分别是3、12和8。然后它取三个值中的最小值3作为回传值返回给节点B。类似的过程分别把回传值2赋给C和D。最后我们在3、2和2中选取最大值3作为回传值返回给根节点。
图6.3 计算极小极大值决策的算法。返回最佳可能招数对应的行动，也就是，在假设对手的招数是为了使效用最小的前提下，能够导致最佳效用值结果的招数。函数MAX-VALUE和MIN-VALUE穿过整个博弈树一直到叶节点，以决定每一个状态的回传值
极小极大值算法对博弈树执行了一个完整的深度优先探索。如果树的最大深度是m，在每个节点合法的招数有 b 个，那么极小极大算法的时间复杂度是 O(bm)。对于一次性生成所有的后继节点的算法，空间复杂度是O(bm)，而对于每次生成一个后继的算法（参见第3.4.3节），空间复杂度是O(m)。当然，对于真实的游戏，这样的时间开销完全不实用，不过这个算法可以作为对游戏进行数学分析的基础和其它实用算法的基础。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
