3.6 Summary (本章小结)

我们从考虑标准的搜索问题（我们只是试图找到从起点到某个目标的路径）转向考虑对抗搜索问题（我们可能有试图阻碍我们达到目标的对手）。主要考虑了两种算法：

Minimax - 当我们的对手表现最优时使用，并且可以使用 \(\alpha\)-\(\beta\) 剪枝进行优化。Minimax 提供的动作比 expectimax 更保守，因此当对手未知时，往往也能产生有利的结果。
Expectimax - 当我们面对次优对手时使用，使用我们认为他们将采取的移动的概率分布来计算状态的期望值。

在大多数情况下，将上述算法一直运行到所考虑的博弈树的终止节点在计算上太昂贵了，因此我们引入了用于提前终止的评估函数的概念。对于具有大分支因子的问题，我们描述了 MCTS 和 UCT 算法。这些算法很容易并行化，允许使用现代硬件进行大量的 rollouts（模拟）。

最后，我们考虑了通用博弈的问题，其中的规则不一定是零和的。