知识卡片
上下界剪枝保留极小极大值
搜索维护当前路径上的α、β界:α是MAX方已能保证的下界,β是MIN方可限制的上界;当α≥β时,该分支后续结果无法改变祖先决策,可以停止搜索。NegMax形式递归时交换并取负窗口 [−β,−α]。
在相同树、深度、评价和正确边界处理下,AlphaBeta得到与Minimax相同的根值;多个走法并列时具体返回哪个还取决于遍历与平局规则。剪枝数量依走法顺序而异,并非保证跳过所有无用节点。
218说明接口与Minimax相同;搜索顺序会影响工作量,而正确剪枝不改变固定深度下的根值。
219的03371–03372在子调用传入−beta、−alpha,撤销走法后以负分更新alpha,在alpha≥beta时返回。整数哨兵应支持安全取负,执行与撤销需要保持状态一致。
220强调剪枝效果;正确算法不是近似结果,但并列最优走法可能受顺序影响。
221描述理想排序下常见的 O(b^(d/2)) 量级与最坏 O(b^d);具体节点数依深度奇偶、终局和顺序而异。03373–03375表与旋转棋盘说明遍历顺序可显著改变扩展量,历史样例不能保证固定加速倍数。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 上下界剪枝保留极小极大值
- · 输入/输出
- · 解决方案
- · 结论
- · 分析
原书出处 · 5 处
- · 查看原书依据
AlphaBeta算法(图7-20)使用一个固定的策略来从搜索树中剪除无效的搜索,而不是在搜索中采取特殊的策略来使用信息。使用AlphaBeta算法的博弈树等价扩展如图7-21所示。 图 7-20 AlphaBeta详解 图 7-21 AlphaBeta追寻深度为2时的搜索 AlphaBeta算法也
- · 查看原书依据
输入输出和Minimax相同。主要的区别是AlphaBeta将会利用已经计算过的状态来决定是否继续搜索特定的子树。
- · 查看原书依据
AlphaBeta实现基于NegMax扩展。一旦当前局面状态下,玩家不能保证一个更好的位置(α剪枝)或者对手不能强迫玩家走到一个更坏的位置(β剪枝),那么搜索终止。 例7-8:AlphaBeta实现
- · 查看原书依据
节省了时间,大量的状态被从博弈树中剪除掉了。
- · 查看原书依据
最好情况下我们只需要评价对手的第一种走法。在图7-21中,由于走法有序,在评价了一些走法之后,就能够进行剪枝,所以在这棵博弈树下,走法排序并不是最优的。 最好情况下,AlphaBeta在每一级为玩家评价b个局面状态,但是只评价对手的一个局面状态。所以,在博弈树的第d级,AlphaBeta只需要评价b