知识卡片
AlphaBeta剪去无关分支
在同一深度和叶子估值下,α–β 剪枝返回与普通极大极小相同的根值。α 记录最大化一方已经能保证的下界,β 记录最小化一方已经能保证的上界。若某个最小化分支已出现一个不高于 α 的结果,最大化一方有更好的备选,该分支其余子节点可以跳过。最大化分支越过 β 时同理。将最有希望的动作先展开,有机会更早收紧边界。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 博弈强化学习 13.3 Alpha-Beta搜索 · 查看原书依据
在图13-7中,节点A的值应是节点B和节点C中值较大者。现在已知节点B的值大于节点D的值。由于节点C的值应是它的所有子节点中值极小者,此极小值一定小于等于节点D的值,因此也一定小于节点B的值,这表明,继续搜索节点C的其他子节点,如E,F,…已没有意义,它们不能做任何贡献,于是把节点C其余子树全部剪去,这种优化称为Alpha剪枝。
参考来源
- 位置:《强化学习》第13章《博弈强化学习》(来源项目 book-source,`extracted/强化学习/_epub-src/OEBPS/Text/1-022.xhtml#isbn9787302538295_13_1_3`)
- 结论依据:原文分别给出极大值与极小值冗余例,并总结可剪枝的两条判据。
- 原始内容:在图13-7中,节点A的值应是节点B和节点C中值较大者。现在已知节点B的值大于节点D的值。由于节点C的值应是它的所有子节点中值极小者,此极小值一定小于等于节点D的值,因此也一定小于节点B的值,这表明,继续搜索节点C的其他子节点,如E,F,…已没有意义,它们不能做任何贡献,于是把节点C其余子树全部剪去,这种优化称为Alpha剪枝。