知识卡片

普通读书笔记卡 · 5654.d.1.f.4.n.10 · 生成模型:未记录

上下界剪枝保留极小极大值

理解等级:中级

搜索维护当前路径上的α、β界:α是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

    参考来源

    - 位置:《算法技术手册》第7章《AlphaBeta》(spine1622;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1585.html;u217-ch07-011)。 - 结论依据:217全文、03368–03370伪代码与两组井字棋搜索树实读。 - 原始内容:AlphaBeta算法(图7-20)使用一个固定的策略来从搜索树中剪除无效的搜索,而不是在搜索中采取特殊的策略来使用信息。使用AlphaBeta算法的博弈树等价扩展如图7-21所示。 图 7-20 AlphaBeta详解 图 7-21 AlphaBeta追寻深度为2时的搜索 AlphaBeta算法也 - 位置:《算法技术手册》第7章《输入/输出》(spine1622;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1585.html;u218-ch07-011)。 - 结论依据:218说明接口与Minimax相同;搜索顺序会影响工作量,而正确剪枝不改变固定深度下的根值。 - 原始内容:输入输出和Minimax相同。主要的区别是AlphaBeta将会利用已经计算过的状态来决定是否继续搜索特定的子树。 - 位置:《算法技术手册》第7章《解决方案》(spine1623;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1586.html;u219-ch07-011)。 - 结论依据:219的03371–03372在子调用传入−beta、−alpha,撤销走法后以负分更新alpha,在alpha≥beta时返回。整数哨兵应支持安全取负,执行与撤销需要保持状态一致。 - 原始内容:AlphaBeta实现基于NegMax扩展。一旦当前局面状态下,玩家不能保证一个更好的位置(α剪枝)或者对手不能强迫玩家走到一个更坏的位置(β剪枝),那么搜索终止。 例7-8:AlphaBeta实现 - 位置:《算法技术手册》第7章《结论》(spine1624;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1587.html;u220-ch07-011)。 - 结论依据:220强调剪枝效果;正确算法不是近似结果,但并列最优走法可能受顺序影响。 - 原始内容:节省了时间,大量的状态被从博弈树中剪除掉了。 - 位置:《算法技术手册》第7章《分析》(spine1625;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1588.html;u221-ch07-011)。 - 结论依据:221描述理想排序下常见的 O(b^(d/2)) 量级与最坏 O(b^d);具体节点数依深度奇偶、终局和顺序而异。03373–03375表与旋转棋盘说明遍历顺序可显著改变扩展量,历史样例不能保证固定加速倍数。 - 原始内容:最好情况下我们只需要评价对手的第一种走法。在图7-21中,由于走法有序,在评价了一些走法之后,就能够进行剪枝,所以在这棵博弈树下,走法排序并不是最优的。 最好情况下,AlphaBeta在每一级为玩家评价b个局面状态,但是只评价对手的一个局面状态。所以,在博弈树的第d级,AlphaBeta只需要评价b