知识卡片

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

极小极大交替评估双方选择

理解等级:中级

以初始玩家为固定评分视角:轮到该玩家的MAX节点取子节点最大值,轮到对手的MIN节点取最小值,递归到终局或深度上限后评价。根节点选择能保证最佳最坏结果的走法。

这依赖双人、轮流、确定性、完全信息及零和等建模假设;有限深度时结果还受评估函数和截断影响,不是对真实胜率的无条件保证。

205说明返回的最佳走法由给定深度和评估函数决定;终局状态应按实际胜负处理,无合法走法是否表示终局也由游戏规则决定。

206图03358使用 b!/(b−i)! 的逐层递减分支模型,b=10、d=6得到187300个非根节点;若每层都固定有b个走法,则应使用 Σb^i,不能将两个模型混用。评估值需要从固定玩家视角一致地解释。

207的03359–03361实现复制根状态,递归中执行与撤销走法,并由比较器在MAX和MIN之间切换;撤销必须完整恢复状态,异常或提前退出也应保证恢复。

208图03362给出 Σ(i=0..d)b^i,b=30、d=5得到25137931个节点;缓存和对称性可能减少重复搜索,但缓存键必须包含行动方、深度及影响局面的规则信息。

209图03363展示深度2的井字棋搜索,完整展开有固定分支b、深度d时节点量为 O(b^d)。若某分支已不可能改善祖先可保证的结果,可通过正确的上下界剪枝而不改变同一搜索深度下的极小极大值。

210说可在树完全可处理时取消深度限制;游戏若存在循环,仍需终局规则或重复状态处理,不能只凭状态有限就保证朴素递归结束。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 7 处

    • · 查看原书依据

      Minimax 玩家希望搜索程序能够最大化从指定位置开始走,获得胜利的概率(或者至少要保平)。程序不会仅仅考虑当时的局面状态以及当时的可行走法,还需要考虑对手会采取的任何对策。程序需要假设对手会采取最完美的走法,并且不会犯错。程序假设存在一个评估函数score(state,player),返回一个整

    • · 查看原书依据

      追寻深度。 输出 返回所有可行走法中最能使得玩家赢得比赛的走法,由评估函数决定。 假设 评估局面状态是非常复杂的,程序员需要依靠评估函数来选择最好的局面状态。事实上,在设计智能程序中,开发一个精确的评估函数,例如象棋、跳棋,或者黑白棋,是一件非常困难的事情。我们假设已经有一些这样的函数。

    • · 查看原书依据

      评估函数的精度。在Minimax的递归调用中,评估函数需要保持一致,不会因为调用者而改变。

    • · 查看原书依据

      Java代码返回了给定局面状态下,玩家的最好走法。 例7-6:Minimax Java实现 MAX和MIN选择器简单地计算出得分,然后按需选出最大的或则最小的分数。实现使用了IComparator接口,如图7-16所示。这个接口定义了MAX和MIN,使得能够更加正确地为玩家挑选出最优走法。oppos

    • · 查看原书依据

      巨大数量的局面状态。在国际象棋中,在棋面上,平均走法的数目是30个(Laramée,2000),也就是说,仅仅向前预计算5步(即b=30,d=5),那么就需要评估25 137 931个棋面状态。这个值是这样计算出来的: Minimax可以利用局面状态的对称性(例如棋盘的旋转或者反转),缓存已经检查过

    • · 查看原书依据

      指数级增长。 我们看看图7-17的结果,肯定有办法能够消除掉无用的局面状态。玩家MAX试着最大化局面状态的得分,因为每一步都会被评价,玩家MAX计算出他能够保证的最大值maxValue。因为我们假设对手不会犯错,一旦指向一棵MIN子树的走法得到的结果比maxValue要小,那么就不会搜索这棵子树。同

    • · 查看原书依据

      不用设置追寻深度。

    参考来源

    - 位置:《算法技术手册》第7章《Minimax》(spine1611;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1574.html;u204-ch07-008)。 - 结论依据:204全文及03357伪代码和树实读。 - 原始内容:Minimax 玩家希望搜索程序能够最大化从指定位置开始走,获得胜利的概率(或者至少要保平)。程序不会仅仅考虑当时的局面状态以及当时的可行走法,还需要考虑对手会采取的任何对策。程序需要假设对手会采取最完美的走法,并且不会犯错。程序假设存在一个评估函数score(state,player),返回一个整 - 位置:《算法技术手册》第7章《输入/输出》(spine1611;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1574.html;u205-ch07-008)。 - 结论依据:205说明返回的最佳走法由给定深度和评估函数决定;终局状态应按实际胜负处理,无合法走法是否表示终局也由游戏规则决定。 - 原始内容:追寻深度。 输出 返回所有可行走法中最能使得玩家赢得比赛的走法,由评估函数决定。 假设 评估局面状态是非常复杂的,程序员需要依靠评估函数来选择最好的局面状态。事实上,在设计智能程序中,开发一个精确的评估函数,例如象棋、跳棋,或者黑白棋,是一件非常困难的事情。我们假设已经有一些这样的函数。 - 位置:《算法技术手册》第7章《使用环境》(spine1612;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1575.html;u206-ch07-008)。 - 结论依据:206图03358使用 b!/(b−i)! 的逐层递减分支模型,b=10、d=6得到187300个非根节点;若每层都固定有b个走法,则应使用 Σb^i,不能将两个模型混用。评估值需要从固定玩家视角一致地解释。 - 原始内容:评估函数的精度。在Minimax的递归调用中,评估函数需要保持一致,不会因为调用者而改变。 - 位置:《算法技术手册》第7章《解决方案》(spine1613;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1576.html;u207-ch07-008)。 - 结论依据:207的03359–03361实现复制根状态,递归中执行与撤销走法,并由比较器在MAX和MIN之间切换;撤销必须完整恢复状态,异常或提前退出也应保证恢复。 - 原始内容:Java代码返回了给定局面状态下,玩家的最好走法。 例7-6:Minimax Java实现 MAX和MIN选择器简单地计算出得分,然后按需选出最大的或则最小的分数。实现使用了IComparator接口,如图7-16所示。这个接口定义了MAX和MIN,使得能够更加正确地为玩家挑选出最优走法。oppos - 位置:《算法技术手册》第7章《结论》(spine1614;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1577.html;u208-ch07-008)。 - 结论依据:208图03362给出 Σ(i=0..d)b^i,b=30、d=5得到25137931个节点;缓存和对称性可能减少重复搜索,但缓存键必须包含行动方、深度及影响局面的规则信息。 - 原始内容:巨大数量的局面状态。在国际象棋中,在棋面上,平均走法的数目是30个(Laramée,2000),也就是说,仅仅向前预计算5步(即b=30,d=5),那么就需要评估25 137 931个棋面状态。这个值是这样计算出来的: Minimax可以利用局面状态的对称性(例如棋盘的旋转或者反转),缓存已经检查过 - 位置:《算法技术手册》第7章《分析》(spine1615;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1578.html;u209-ch07-008)。 - 结论依据:209图03363展示深度2的井字棋搜索,完整展开有固定分支b、深度d时节点量为 O(b^d)。若某分支已不可能改善祖先可保证的结果,可通过正确的上下界剪枝而不改变同一搜索深度下的极小极大值。 - 原始内容:指数级增长。 我们看看图7-17的结果,肯定有办法能够消除掉无用的局面状态。玩家MAX试着最大化局面状态的得分,因为每一步都会被评价,玩家MAX计算出他能够保证的最大值maxValue。因为我们假设对手不会犯错,一旦指向一棵MIN子树的走法得到的结果比maxValue要小,那么就不会搜索这棵子树。同 - 位置:《算法技术手册》第7章《变种》(spine1616;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1579.html;u210-ch07-008)。 - 结论依据:210说可在树完全可处理时取消深度限制;游戏若存在循环,仍需终局规则或重复状态处理,不能只凭状态有限就保证朴素递归结束。 - 原始内容:不用设置追寻深度。