1、第二章 与或图搜索问题,1,2.1 基本概念,与或图是一个超图，节点间通过连接符连接。K-连接符：,2,耗散值的计算,k(n,N)=Cn+k(n1,N)+k(ni,N)其中：N为终节点集 Cn为连接符的耗散值,3,目标,目标,初始节点,解图：,4,能解节点,终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。,5,不能解节点,没有后裔的非终节点是不能解节点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能
2、解时，该非终节点才不能解。,6,普通图搜索的情况,f(n)=g(n)+h(n)对n的评价实际是对从s到n这条路径的评价,n,s,7,与或图:对局部图的评价,目标,目标,初始节点,a,b,c,8,两个过程,图生成过程，即扩展节点从最优的局部途中选择一个节点扩展计算耗散值的过程对当前的局部图从新计算耗散值,9,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,10,初始节点,n0,n1(2),n4(1),n5(1),红色：4黄色：3,11,红色：4黄色：6,n
3、1,n2(4),n3(4),5,12,红色：5黄色：6,2,13,红色：5黄色：6,2,1,14,博弈 是一类具有竞争性的智能活动双人博弈：即两位选手对垒，轮流依次走步，其中任何一方都完全知道对方过去已经走过的棋步和今后可能的走步，其结果是一方赢(而另一方则输)，或双方和局,2.3 博弈树搜索,15,博弈的例子：一字棋跳棋中国象棋围棋五子棋,16,2.3 博弈树搜索,博弈问题双人对弈，对垒的双方轮流走步；信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另外一方看不到的情况；零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或均无利的棋，对弈的结果是一方赢，而另一方输，
4、或者双方和棋。,17,双方的智能活动，任何一方都不能单独控制博弈过程，而是由双方轮流实施其控制对策的过程。,博弈的特点：,18,如何根据当前的棋局，选择对自己最有利的一步棋？,人工智能中研究的博弈问题：,中国象棋,19,用博弈树来表示，它是一种特殊的与或树。节点代表博弈的格局（即棋局），相当于状态空间中的状态，反映了博弈的信息，并且与节点、或节点隔层交替出现。,博弈问题（求解过程）的表示：,20,假设博弈双方为：MAX和MIN在博弈过程中，规则是双方轮流走步。在博弈树中，相当于博弈双方轮流扩展其所属节点。,为什么与节点、或节点隔层交替出现？,21,从MAX方的角度来看：所有MIN方节点都是与节
5、点理由：因为MIN方必定选择最不利于MAX方的方式来扩展节点，只要MIN方节点的子节点（下出棋局）中有一个对MAX方不利，则该节点就对MAX方不利，故为“与节点”。,22,从MAX方的角度来看：所有属于MAX方的节点都是或节点理由：因为扩展MAX方节点时，MAX方可选择扩展最有利于自己的节点，只要可扩展的子节点中有一个对已有利，则该节点就对已有利。,MAX,好招,23,总之：从MAX方来说，与节点、或节点交替出现；反之，从MIN方的角度来看，情况正好相反。,24,在博弈树中，先行一方的初始状态对应着树的根节点，而任何一方获胜的最终格局为目标状态，对应于树的终叶节点（可解节点或本原问题）。,但是
6、，从MAX的角度出发，所有使MAX获胜的状态格局都是本原问题，是可解节点，而使MIN获胜的状态格局是不可解节点。,25,博弈树特点,(1)博弈的初始状态是初始节点；(2)博弈树的“与”节点和“或”节点是逐层交替出现的；(3)整个博弈过程始终站在某一方的立场上，所以能使自己一方获胜的终局都是本原问题，相应的节点也是可解节点，所有使对方获胜的节点都是不可解节点。,26,例 Grundy博弈：分配物品的问题如果有一堆数目为N的钱币，由两位选手轮流进行分配，要求每个选手每次把其中某一堆分成数目不等的两小堆，直至有一选手不能将钱币分成不等的两堆为止，则判定这位选手为输家。,27,用数字序列加上一个说明来
7、表示一个状态：(3,2,1,1,MAX)数字序列：表示不同堆中钱币的个数说明：表示下一步由谁来分，即取MAX或MIN,28,现在取 N7 的简单情况，并由MIN先分,注：如果MAX走红箭头的分法，必定获胜。,所有可能的分法,(7,MIN),(6,1,MAX),(5,2,MAX),(4,3,MAX),(5,1,1,MIN),(4,2,1,MIN),(3,2,2,MIN),(3,3,1,MIN),(4,1,1,1,MAX),(3,2,1,1,MAX),(2,2,2,1,MAX),(2,2,1,1,1,MIN),(3,1,1,1,1,MIN),(2,1,1,1,1,1,MAX),29,分钱币问题,（
8、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）,对方先走,我方必胜,30,对于比较复杂的博弈问题，只能模拟人的思维“向前看几步”，然后作出决策，选择最有利自己的一步。即只能给出几层走法，然后按照一定的估算办法，决定走一好招。,31,中国象棋,一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。,32,在人工智能中可以采用搜索方法来求解博弈问题，
9、下面就来讨论博弈中两中最基本的搜索方法。,33,对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺利进行。,假设由MAX来选择走一步棋，问题是：MAX如何来选择一步好棋？,极大极小过程,34,极大极小过程,极大极小过程是考虑双方对弈若干步之后，从可能的走法中选一步相对好的走法来走，即在有限的搜索深度范围内进行求解。需要定义一个静态估价函数e,以便对棋局的态势做出评估。,35,对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数值。值越大对MAX越有利，反之越不利；,极大极小过程的基本思路：,36,对于给定的格局，MAX给出可能的走法，然后MIN对应地给出相应的走法，这样重复若干次
10、，得到一组端节点（必须由MIN走后得到的，等待MAX下的棋局）。这一过程相当于节点扩展；注：博弈树深度或层数一定是偶数。,37,对于每一个端节点，计算出它们的静态估价函数，然后自下而上地逐层计算倒推值，直到MAX开始的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值；取估值最大的格局作为MAX要走的一招棋。,38,例：向前看一步的两层博弈树,39,定义静态函数e(P)的一般原则：,40,OPEN：存放待扩展的节点，此时为队列，即以宽度优先的策略扩展节点。CLOSED：存放已扩展的节点，此时为堆栈，即后扩展的节点先计算。,符号：,41,极大极小过程的基本思想：(1)当轮到M
11、IN走步的节点时，MAX应考虑最坏的情况（即f(p)取极小值）；(2)当轮到MAX走步的节点时，MAX应考虑最好的情况（即f(p)取极大值）；(3)评价往回倒推时，相应于两位棋手的对抗策略，交替使用（1）和（2）两种方法传递倒推值。,42,1、将初始节点 S 放入 OPEN 表中，开始时搜索树 T 由初始节点 S 构成；2、若 OPEN 表为空（节点扩展结束），则转5；3、将 OPEN 表中第一个节点 n 移出放入CLOSED 表的前端；,极大极小搜索过程为：,43,4、若 n 可直接判定为赢、输、或平局，则令对应的 e(n)=，-或 0，并转2；否则扩展 n，产生 n 的后继节点集 ni，将
12、 ni 放入搜索树 T 中。此时，若搜索深度d ni 小于预先设定的深度 k，则将 ni 放入OPEN表的末端，转2；否则，ni 达到深度k，计算e(ni)，并转2；,44,5、若CLOSED表为空，则转8；否则取出CLOSED表中的第一个节点，记为 np；,Open为空，即已经扩展完节点,步2,45,6、若 np 属于MAX层，且对于它的属于MIN层的子节点 nci 的 e(nci)有值，则：e(np)=max nci,46,（续）若 np 属于MIN层，且对于它的属于MAX层的子节点 nci 的 e(nci)有值，则：e(np)=min nci,47,7、转5；8、根据 e(S)的值，标记
13、走步或者结束（-，或 0）。,48,第一阶段为1、2、3、4步，用宽度优先算法生成规定深度 k 的全部博弈树，然后对其所有端节点计算 e(P)；第二阶段为5、6、7、8步，是自下而上逐级求节点的倒推估价值，直至求出初始节点的 e(S)为止，再由 e(S)选得相对较好的走法，过程结束。,算法分成两个阶段：,49,等对手走出相应的棋，再以当前的格局作为初始节点，重复此过程，选择对自己有利的走法。,50,极大极小过程,51,例：一字棋的极大极小搜索过程,约定：每一方只向前看一步（扩展出二层）记MAX的棋子为“”，MIN的棋子为“O”规定MAX先手,52,若格局 P 对任何一方都不能获胜，则e(P)=
14、（所有空格上都放上MAX的棋子后，MAX的三个棋子所组成的行、列及对角线的总数）-（所有空格上都放上MIN的棋子后，MIN的三个棋子所组成的行、列及对角线的总数）,静态估计函数e(P)定义为：,53,若 P 是MAX获胜，则 e(P)=+若 P 是MIN获胜，则 e(P)=,54,例：计算下列棋局的静态估价函数值,e(P)=6-4=2,棋局,行=2列=2对角=2,行=2列=2对角=0,55,利用棋盘的对称性，有些棋局是等价的,56,1,0,1,0,-1,-1,0,-1,0,-2,1,2,1,-2,-1,1,MAX,MIN,MAX,MAX的走步,57,第二步,2,1,3,2,1,1,1,0,2,
15、0,1,1,0,2,2,3,1,2,2,1,1,1,0,0,1,58,第三步,-,0,2,1,-,-,-,1,2,2,1,0,1,-,-,-,1,1,1,1,1,1,2,-,1,1,59,MAX,MIN,60,MAX,MIN,O,O,61,极大极小搜索过程由两个完全分离的两个步骤组成：第一、用宽度优先算法生成一棵博弈搜索树第二、估计值的倒推计算缺点：这种分离使得搜索的效率比较低,62,极小极大过程,0,-3,3,-3,-3,-2,1,-3,6,0,3,1,6,0,1,1,极大,极小,a,b,注：用表示MAX，用表示MIN，端节点上的数字表示它对应的估价函数的值。,极大,极小,63,极大极小过程
16、是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。改进：在博弈树生成过程中同时计算端节点的估计值及倒推值，以减少搜索的次数，这就是-过程的思想，也称为-剪枝法。剪枝的概念:如果能边生成节点边对节点估值，并剪去一些没用的分枝，这种技术被称为-剪枝。,64,-剪枝,极大节点的下界为。极小节点的上界为。剪枝的条件：后辈节点的值祖先节点的值时，剪枝后辈节点的 值祖先节点的值时，剪枝简记为：极小极大，剪枝极大极小，剪枝,65,一个-剪枝的具体例子，如下图所示。其中最下面一层端节点旁边的数字是假设的估值。在该图中，L、M、N的
17、估值推出节点F的倒推值为4，即F的值为4，由此可推出节点C的倒推值4。记C的倒推值的下界为4，不可能再比4小，故C的值为4。,由节点N的估值推知节点G的倒推值小于1,无论G的其它子节点的估只是多少，G的倒推值都不可能比1大。因此，1是G的倒推值的上界，所以G的值1。另已知C的倒推值4，G的其它子节点又不可能使C的倒推值增大。因此对G的其它分支不必再搜索，相当于把这些分枝剪去。,由F、G的倒推值可推出节点C的倒推值4，再由C可推出节点A的倒推值4，即A的值为4。另外，由节点P、Q推出的节点H的倒推值为5，因此D的倒推值5，即D的值为5。此时，D的其它子节点的倒推值无论是多少都不能使D及A的倒推值减少或增大，所以D的其他分枝被减去，并可确定A的倒推值为4。以此类推，最终推出S0的倒推值为4。,66,8,6,-3,1,4,5,3,-3,5,0,-剪枝（续）,3,-3,0,2,2,-3,0,-2,3,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,0,剪枝,剪枝,剪枝,剪枝,67,-剪枝的其他应用,故障诊断 A B C D风险投资,68,
