人工智能-博弈树的搜索.ppt

对于棋盘残局中的╳来说，最好的选择，是将╳放在C的位置上，这时可以导致平局局面。 3.极小极大搜索过程 ?-?剪支法的引入 在极小极大法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的?-?剪支法。 4. ?-?搜索过程 作为正方出现的MAX节点，假设它的MIN子节点有N个，那么当它的第一个MIN子节点的评估值为?时，则对于其它的子节点，如果有高过?的，就取那最高的值作为该MAX节点的评估值；如果没有，则该MAX节点的评估值为?。 总之，该MAX节点的评估值不会低于?，这个?就称为该MAX节点的评估下限值。 4. ?-?搜索过程 MAX节点的评估下限值? MIN节点的评估上限值? 作为反方出现的MIN节点，假设它的MAX子节点有N个，那么当它的第一个MAX子节点的评估值为?时，则对于其它子节点，如果有低于?的，就取那个低于?的值作为该MIN节点的评估值；如果没有，则该MIN节点的评估值取?。 总之，该MIN节点的评估值不会高过?，这个?就称为该MIN节点的评估上限值。 4. ?-?搜索过程 ?剪支法 MAX节点 ?? MIN节点 ?=? ??? ??? ?剪支 A B C D 4. ?-?搜索过程 设MAX节点的下限为?，则其所有的MIN子节点中，其评估值的?上限小于等于?的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了?剪支。 设MIN节点的上限为?，则其所有的MAX子节点中，其评估值的?下限大于等于?的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了?剪支。 MAX节点 ?? MIN节点 ?=? ??? ??? ?剪支 A B C D 4. ?-?搜索过程 ?剪支法 A B C D E F G H I J K L N O M 4. ?-?搜索过程 MAX节点 MAX节点 MIN节点 终端节点 3 5 6 5 2 1 6 4 MAX节点 (5,?) 3 5 6 5 2 1 6 4 (6,?) (2,?) (-?,5) (-?,2) (5,?) MIN节点 终端节点 ?剪支 ?剪支 A B C D E F G H I J K L N O M MAX节点 4. ?-?搜索过程 一字棋第一阶段?-?剪支方法 4. ?-?搜索过程 4. ?-?搜索过程 极大节点的下界为?。 极小节点的上界为?。 剪支的条件： 后辈节点的?值≤祖先节点的?值时， ?剪支 后辈节点的? 值≥祖先节点的?值时， ?剪支 简记为： 极小≤极大， ?剪支 极大≥极小， ?剪支 4. ?-?搜索过程 8 6 -3 1 4 5 3 -3 5 0 3 -3 0 2 2 -3 0 -2 3 0 9 -3 0 0 -3 0 3 3 0 5 4 1 1 -3 1 6 6 1 a b c d e f g h i j k m n MAX MIN MAX MIN ??● ○ ??● ○ ??● ○ ?? ● ○ ● ?? ○ ● ?? ○ ● ?? ○ ● ?? ○ 2.3 博弈树搜索 20世纪60年代，研制出的西洋跳棋和国际象棋的博弈程序达到了大师级的水平。 1958约翰?麦卡锡提出博弈树搜索算法 1997年，IBM公司研制的“深蓝”国际象棋 程序，采用博弈树搜索算法，该程序战胜了国际象棋世界冠军卡斯帕罗夫。 1.概述 正在与深蓝下棋的卡斯帕罗夫 博弈问题特点： 双人对弈，轮流走步。 信息完备，双方所得到的信息是一样的。 零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或无利的棋。 1.概述 博弈的特性 两个棋手交替地走棋 ； 比赛的最终结果，是赢、输和平局中的一种； 可用图搜索技术进行，但效率很低； 博弈的过程，是寻找置对手于必败态的过程； 双方都无法干预对方的选择。 1.概述 2.Grundy 博弈 Grundy博弈是一个分钱币的游戏。有 一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如，选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去，直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。 2.Grundy 博弈 设初始状态为(7，MIN)，建立问题的状态空间图，图中所有终结点均表示该选手必输的情况，取胜方的目标是设法使棋局发展为结束在对方走步时的终结点上。 MIN先走 MAX必胜 2.Gru