知识卡片
极小极大交替评估双方选择
以初始玩家为固定评分视角:轮到该玩家的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要小,那么就不会搜索这棵子树。同
- · 查看原书依据
不用设置追寻深度。