人工智能-4与或图搜索.ppt

第三章 与或图的搜索 目标 目标 初始节点 与或图（树）表示问题 三解梵塔问题 A B C 12 3 三解梵塔问题 (1,1,1) (3,3,3) (1,1,1) (1,2,2) (1,2,2) (3,2,2)(3,2,2) (3,3,3) (1,1,1) (1,1,3) (1,1,3) (1,2,3) (1,2,3) (1,2,2) (3,2,2) (3,2,1) (3,2,1) (3,3,1) (3,3,1) (3,3,3) (1, 1, 1) A, B, C 3.1 与或图 初始节点 与或图 目标 目标 初始节点 基本概念 与或图是一个超图，节点间通过连接符 连接。 K-连接符： . K个 与或 耗散值的计算 k(n, N) = Cn+k(n1, N)+k(ni, N) 其中：N为终节点集 Cn为连接符的耗散值 . i个 n n1 n2 ni 目标 目标 初始节点 解图： 能解节点 终节点是能解节点 若非终节点有“或”子节点时，当且仅当其 子节点至少有一能解时，该非终节点才 能解。 若非终节点有“与”子节点时，当且仅当其 子节点均能解时，该非终节点才能解。 不能解节点 没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点，当且仅当所有 子节点均不能解时，该非终节点才不能 解。 若非终节点有“与”子节点时，当至少有一 个子节点不能解时，该非终节点才能解 。 3.2 与或图启发式搜索算法AO* 目标 目标 初始节点 与或图的启发式搜索算法 AO*算法 105-106 两个过程： 图生成过程，即扩展节点 计算耗散值的过程 AO*算法举例 其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0 设：K连接符 的耗散值为K 目标 目标 初始节点 n0 n1 n2 n3 n4 n5 n6 n7 n8 目标 目标 初始节点 n0 n1 n2 n3 n4 n5 n6 n7 n8 初始节点 n0 n1(2) n4(1) n5(1) 红色：4=1+1+1+1 黑色：3=2+1 目标 目标 初始节点 n0 n1 n2 n3 n4 n5 n6 n7 n8 初始节点 n0 n4(1) n5(1) 红色：4 黑色：6 n1 n2(4) n3(4) 5 目标 目标 初始节点 n0 n1 n2 n3 n4 n5 n6 n7 n8 红色：5 黑色：6 初始节点 n0 n4(1) n5(1) n1 n2(4) n3(4) 5 n6(2) n7(0) n8(0) 2 目标 目标 初始节点 n0 n1 n2 n3 n4 n5 n6 n7 n8 红色：5 黑色：6 初始节点 n0 n4(1) n5(1) n1 n2(4) n3(4) 5 n6(2) n7(0) n8(0) 2 1 3.3 博弈树(Game tree)搜索 3.3 博弈树(Game tree)搜索 20世纪60年代，研制出的西洋跳棋和国际象棋 的博弈程序达到了大师级的水平。 1958约翰麦卡锡提出博弈树搜索算法 1997年，IBM公司研制的“深蓝”国际象棋 程序，采用博弈树搜索算法，该程序战胜了 国际象棋世界冠军卡斯帕罗夫。 1.概述 博弈问题特点： 双人对弈，轮流走步。 信息完备，双方所得到的信息是一样的。 零和，即对一方有利的棋，对另一方肯定 是不利的，不存在对双方均有利或无利的 棋。 1.概述 博弈的特性 两个棋手交替地走棋 ； 比赛的最终结果，是赢、输和平局中的 一种； 可用图搜索技术进行，但效率很低； 博弈的过程，是寻找置对手于必败态的 过程； 双方都无法干预对方的选择。 1.概述 2.Grundy博弈 下棋的双方是对立的，命名博弈的双方， 一方为“正方”，这类节点称为“MAX”节点 ；另一方为“反方”，这类节点称为“MIN” 节点。正方和反方是交替走步的，因此 MAX节点和MIN节点会交替出现。 2.Grundy博弈 Grundy博弈是一个分钱币的游戏。有 一堆数目为N的钱币，由两位选手轮流进 行分堆，要求每个选手每次只把其中某 一堆分成数目不等的两小堆。例如，选 手甲把N分成两堆后，轮到选手乙就可以 挑其中一堆来分，如此进行下去，直到 有一位选手无法把钱币再分成不相等的 两堆时就得认输。 2.Grundy博弈 设初始状态为(7，MIN)，建立问题的状 态空间图，图中所有终结点均表示该选 手必输的情况，取胜方的目标是设法使 棋局发展为结束在对方走步时的终结点 上。 （7） （6,1）（5,2）（4,3） （5,1,1） （4,2,1）（3,2,2） （3,3,1） （4,1,1,1） （3,2,1,1）（2,2,2,1） （3,1,1,1,1）（2,2,1,1,1） （2,1,1,1,1,1） 对方-min先走 我方-max胜A B C 2.Grundy博弈 有向图中有四个出度为零的结点:A,B,C 结点A是MAX(我方)的搜索目标，而结 点B，C则为MIN(对方)的搜索目标。 2.Grundy博弈 搜索策略要考虑的问题是： 对MIN走步后的每一个MAX结点，必须证 明MAX对MIN可能走的每一个棋局对弈后 能获胜，即MAX必须考虑应付MIN的所有 招法，这是一个与的含意，因此含有MAX 符号的结点可看成与结点。 2.Grundy 博弈 对MAX走步后的每一个MIN结点，只须证 明MAX有一步能走赢就可以，即MAX只要 考虑能走出一步棋使MIN无法招架就成， 因此含有MIN符号的结点可看成或结点。 2.Grundy 博弈 对弈过程的搜索图呈现出与或图表示的形式 。 实现一种取胜的策略就是搜索一个解图的问 题，解图就代表一种完整的博弈策略。 2.Grundy 博弈 中国象棋 一盘棋平均走50步，总状态数约为10的 161次方。 假设1毫微秒走一步，约需10的145次方 年。 结论：不可能穷举。 3.极小极大搜索过程 对各个局面进行评估 评估的目的：对后面的状态提前进行考虑， 并且以各种状态的评估值为基础作出最好的 走棋选择。 评估的方法：用评价函数对棋局进行评估。 赢的评估值设为+，输的评估值设为-， 平局的评估值设为0。 评估的标准：由于下棋的双方是对立的，只 能选择其中一方为评估的标准方。 3.极小极大搜索过程 MAX节点和MIN节点 命名博弈的双方，一方为“正方”，对每个 状态的评估都是对应于该方的输赢的。例 如，赢2个，输1个等，都是指正方的。正 方每走一步，都在选择使自己赢得更多的 节点，因此这类节点称为“MAX”节点； 3.极小极大搜索过程 另一方为“反方”，对每个状态的评估都 是对应于对手的输赢的。例如，赢2个， 输一个，其实是指自己输2个，赢1个的 。反方每走一步，都在选择使对手输得 更多的节点，因此这类节点称为“MIN” 节点。 3.极小极大搜索过程 由于正方和反方是交替走步的，因此 MAX节点和MIN节点会交替出现。 3.极小极大搜索过程 正方（MAX节点）从所有子节点中，选 取具有最大评估值的节点。 反方（MIN节点）从其所有子节点中， 选取具有最小评估值的节点。 反复进行这种选取，就可以得到双方各 个节点的评估值。这种确定棋步的方法 ，称为极小极大搜索法。 3.极小极大搜索过程 3.极小极大搜索过程 5 -3 33 -3022 -30-235 41-3 0 6 8 9-3 MIN MAX 0 MAX MIN 3.极小极大搜索过程 0 1 5 -3 33 -3022 -30-235 41-3 0 6 8 9-3 0-3 3-3 -3-2 1 -3 6 -3 0316 01 MAX MIN MAX MIN 3.极小极大搜索过程 在九宫格棋盘上，两位选手轮流在棋盘上摆各自的 棋子(每次一枚)，谁先取得三线的结果就取胜。 设程序方MAX的棋子用()表示， MAX先走。 对手MIN的棋子用(o)表示。 例如： 3.极小极大搜索过程 MIN取胜 估价函数 f(p)=(所有空格都放上MAX的 棋子之后，MAX的三子成线数)(所有空 格都放上MIN的棋子之后，MIN的三子成 线的总数) 若P是MAX获胜的格局，则f(p)=+ ； 若P是MIN获胜的格局，则f(p)- 。 3.极小极大搜索过程 3.极小极大搜索过程 估计函数值 f(p)=6-4=2 估价函数 f(p)=(所有空格都放上MAX的棋子之后，MAX的三子 成线(行、列、对角)数)(所有空格都放上MIN的棋子之后， MIN的三子成线(行、列、对角)的总数) 当前棋局f(p)=2 空格都放MAX的棋子空格都放MIN的棋子 3.极小极大搜索过程 一字棋第一阶段搜索树 3.极小极大搜索过程 一字棋第二阶段搜索树 3.极小极大搜索过程 一字棋第三阶段搜索树 设有一个摆放三个子的棋盘残局，如下图所示 ，和在结束前有三步棋可以走，而且设走第一步 的是 。这时存在着三个空格A，B，C，用博弈树 搜索算法判断应该把棋子放到哪一格内。 AB C 棋盘残局举例 3.极小极大搜索过程 AB C B C C B 0 A C C A A B B A -1 - 0 - 1 0 - 0 MAX节点 MIN节点 终端节点 3.极小极大搜索过程 对于棋盘残局中的来说，最好的选择，是将放 在C的位置上，这时可以导致平局局面。 3.极小极大搜索过程 -剪支法的引入 在极小极大法中，必须求出所有终端 节点的评估值，当预先考虑的棋步比较 多时，计算量会大大增加。为了提高搜 索的效率，引入了通过对评估值的上下 限进行估计，从而减少需进行评估的节 点范围的-剪支法。 4. -搜索过程 作为正方出现的MAX节点，假设它的MIN 子节点有N个，那么当它的第一个MIN子节点 的评估值为时，则对于其它的子节点，如果 有高过的，就取那最高的值作为该MAX节点 的评估值；如果没有，则该MAX节点的评估值 为。 总之，该MAX节点的评估值不会低于， 这个就称为该MAX节点的评估下限值。 4. -搜索过程 n MAX节点的评估下限值 MIN节点的评估上限值 作为反方出现的MIN节点，假设它的MAX 子节点有N个，那么当它的第一个MAX子节点 的评估值为时，则对于其它子节点，如果有低 于的，就取那个低于的值作为该MIN节点的 评估值；如果没有，则该MIN节点的评估值取 。 总之，该MIN节点的评估值不会高过，这 个就称为该MIN节点的评估上限值。 4. -搜索过程 剪支法 MAX节点 MIN节点 = 剪支 A B CD 4. -搜索过程 设MAX节点的下限为，则其所有的MIN子节点 中，其评估值的上限小于等于的节点，其以下部分 的搜索都可以停止了，即对这部分节点进行了剪支。 设MIN节点的上限为，则其所有的MAX子节 点中，其评估值的下限大于等于的节点，其以下 部分的搜索都可以停止了，即对这部分节点进行了 剪支。 MAX节点 MIN节点 = 剪支 A B C D 4. -搜索过程 n剪支法 A B C DEF G H I J K L N O M 4. -搜索过程 MAX节点 MAX节点 MIN节点 终端节点 35652164 MAX节点(5,) 35652164 (6,)(2,) (-,5)(- ,2) (5,) MIN节点 终端节点 剪支 剪支 A B C DEF G H I J K L N O M MAX节点 4. -搜索过程 一字棋第一阶段-剪支方法 4. -搜索过程 4. -搜索过程 极大节点的下界为。 极小节点的上界为。 剪支的条件： 后辈节点的值祖先节点的值时， 剪支 后辈节点的 值祖先节点的值时， 剪支 简记为： 极小极大， 剪支 极大极小， 剪支 4. -搜索过程 8 6-3 145 3-350 3-30 2 2 -3 0 -2 3 0 9 -3 0 0 -3 0 3 3 0 5 41 1 -3 1 6 6 1 a b c d e f g h i j k m n MAX MIN MAX MIN 改进方法 使用-剪支技术，当不满足剪支条件( 即)时或值比值大不了多少或极相近 时，这时也可以进行剪支，以便有条件把 搜索集中到会带来更大效果的其他路径上 ，这就是中止对效益不大的一些子树的搜 索，以提高搜索效率。 4. -搜索过程 不严格限制搜索的深度。当到达深度限制时 ，如出现博弈格局有可能发生较大变化时， 则应多