alpha-beta 剪枝

极小极大

• 定深的 DFS
• 假设对手采取最优策略
• 有一个评估局面的函数，每一步自己希望选评分最高的走法，对手希望选评分最低的走法（评分指的是站在你的视角看盘面的评分）

$\alpha -\beta$ 剪枝

本质和极小极大搜索相同，只是剪去了对无用分支的搜索

• 极大节点的下界为 $\alpha$
• 极小节点的上界为 $\beta$
• 当后辈节点的 $\beta$ 值 $\le$ 祖先节点的 $\alpha$ 值时，$\alpha$ 剪枝
• 当后辈节点的 $\alpha$ 值 $\ge$ 祖先节点的 $\beta$ 值时，$\beta$ 剪枝

具体来讲，进行定深的 DFS，每当一个节点完成探索或被剪枝，向上传递自己的结果更新父节点。当一个节点被更新时：

• 若当前节点是 Min 节点，且 $\beta$ 值已经小于祖先节点传下来的 $\alpha$ 值，说明当前节点完整探索后的结果肯定比 $\alpha$ 值小，祖先不可能最终选择这个分支，因此当前节点的其他孩子不需要再探索

• 若当前节点是 Max 节点，类似，情况相反

• 实际实现中，alpha 和 beta 值在函数参数中传递，但是当前节点需要维护一个独立的局部变量用来表示自己的孩子中的最大值或最小值

• 总的来讲，收到子节点更新时，更新自己的 $\alpha /\beta$ 值，检查当前区间是否为空集，是则剪枝，上传更新

• ! 搜索得到的只是一步结果，下一步搜索不能复用上次的结果

问题

• 依赖于对局面评估的准确性