人工智能第二章与或图搜索问题68

1第二章与或图搜索问题目标目标初始节点sabc22.1基本概念与或图是一个超图，节点间通过连接符连接。K-连接符：…...K个3耗散值的计算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集Cn为连接符的耗散值…...i个nn1n2ni4目标目标初始节点•解图：5能解节点终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。6不能解节点没有后裔的非终节点是不能解节点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。7普通图搜索的情况f(n)=g(n)+h(n)对n的评价实际是对从s到n这条路径的评价ns8与或图:对局部图的评价目标目标初始节点abc9两个过程图生成过程，即扩展节点从最优的局部途中选择一个节点扩展计算耗散值的过程对当前的局部图从新计算耗散值10AO*算法举例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n811目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：312初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)5目标目标初始节点n0n1n2n3n4n5n6n7n813红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目标目标初始节点n0n1n2n3n4n5n6n7n814红色：5黄色：621初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目标目标初始节点n0n1n2n3n4n5n6n7n815博弈是一类具有竞争性的智能活动双人博弈：即两位选手对垒，轮流依次走步，其中任何一方都完全知道对方过去已经走过的棋步和今后可能的走步，其结果是一方赢(而另一方则输)，或双方和局2.3博弈树搜索16博弈的例子：一字棋跳棋中国象棋围棋五子棋172.3博弈树搜索博弈问题双人对弈，对垒的双方轮流走步；信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另外一方看不到的情况；零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或均无利的棋，对弈的结果是一方赢，而另一方输，或者双方和棋。18双方的智能活动，任何一方都不能单独控制博弈过程，而是由双方轮流实施其控制对策的过程。博弈的特点：19如何根据当前的棋局，选择对自己最有利的一步棋？人工智能中研究的博弈问题：中国象棋20用博弈树来表示，它是一种特殊的与或树。节点代表博弈的格局（即棋局），相当于状态空间中的状态，反映了博弈的信息，并且与节点、或节点隔层交替出现。博弈问题（求解过程）的表示：21假设博弈双方为：MAX和MIN在博弈过程中，规则是双方轮流走步。在博弈树中，相当于博弈双方轮流扩展其所属节点。为什么与节点、或节点隔层交替出现？22从MAX方的角度来看：所有MIN方节点都是与节点理由：因为MIN方必定选择最不利于MAX方的方式来扩展节点，只要MIN方节点的子节点（下出棋局）中有一个对MAX方不利，则该节点就对MAX方不利，故为“与节点”。MIN好招23从MAX方的角度来看：所有属于MAX方的节点都是或节点理由：因为扩展MAX方节点时，MAX方可选择扩展最有利于自己的节点，只要可扩展的子节点中有一个对已有利，则该节点就对已有利。MAX好招24总之：从MAX方来说，与节点、或节点交替出现；反之，从MIN方的角度来看，情况正好相反。25在博弈树中，先行一方的初始状态对应着树的根节点，而任何一方获胜的最终格局为目标状态，对应于树的终叶节点（可解节点或本原问题）。但是，从MAX的角度出发，所有使MAX获胜的状态格局都是本原问题，是可解节点，而使MIN获胜的状态格局是不可解节点。26博弈树特点(1)博弈的初始状态是初始节点；(2)博弈树的“与”节点和“或”节点是逐层交替出现的；(3)整个博弈过程始终站在某一方的立场上，所以能使自己一方获胜的终局都是本原问题，相应的节点也是可解节点，所有使对方获胜的节点都是不可解节点。27例Grundy博弈：分配物品的问题如果有一堆数目为N的钱币，由两位选手轮流进行分配，要求每个选手每次把其中某一堆分成数目不等的两小堆，直至有一选手不能将钱币分成不等的两堆为止，则判定这位选手为输家。28用数字序列加上一个说明来表示一个状态：(3,2,1,1,MAX)数字序列：表示不同堆中钱币的个数说明：表示下一步由谁来分，即取MAX或MIN29现在取N＝7的简单情况，并由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)30分钱币问题（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）对方先走我方必胜31对于比较复杂的博弈问题，只能模拟人的思维“向前看几步”，然后作出决策，选择最有利自己的一步。即只能给出几层走法，然后按照一定的估算办法，决定走一好招。32中国象棋一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。33在人工智能中可以采用搜索方法来求解博弈问题，下面就来讨论博弈中两中最基本的搜索方法。34对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺利进行。假设由MAX来选择走一步棋，问题是：MAX如何来选择一步好棋？极大极小过程35极大极小过程极大极小过程是考虑双方对弈若干步之后，从可能的走法中选一步相对好的走法来走，即在有限的搜索深度范围内进行求解。需要定义一个静态估价函数e,以便对棋局的态势做出评估。36①对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数值。值越大对MAX越有利，反之越不利；极大极小过程的基本思路：37②对于给定的格局，MAX给出可能的走法，然后MIN对应地给出相应的走法，这样重复若干次，得到一组端节点（必须由MIN走后得到的，等待MAX下的棋局）。这一过程相当于节点扩展；注：博弈树深度或层数一定是偶数。38③对于每一个端节点，计算出它们的静态估价函数，然后自下而上地逐层计算倒推值，直到MAX开始的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值；④取估值最大的格局作为MAX要走的一招棋。39例：向前看一步的两层博弈树40定义静态函数e(P)的一般原则：0MAXMIN()00MAXMINeP占优，不利势均力敌不利，占优41OPEN：存放待扩展的节点，此时为队列，即以宽度优先的策略扩展节点。CLOSED：存放已扩展的节点，此时为堆栈，即后扩展的节点先计算。符号：42极大极小过程的基本思想：(1)当轮到MIN走步的节点时，MAX应考虑最坏的情况（即f(p)取极小值）；(2)当轮到MAX走步的节点时，MAX应考虑最好的情况（即f(p)取极大值）；(3)评价往回倒推时，相应于两位棋手的对抗策略，交替使用（1）和（2）两种方法传递倒推值。431、将初始节点S放入OPEN表中，开始时搜索树T由初始节点S构成；2、若OPEN表为空（节点扩展结束），则转5；3、将OPEN表中第一个节点n移出放入CLOSED表的前端；极大极小搜索过程为：444、若n可直接判定为赢、输、或平局，则令对应的e(n)=∞，-∞或0，并转2；否则扩展n，产生n的后继节点集{ni}，将{ni}放入搜索树T中。此时，若搜索深度d{ni}小于预先设定的深度k，则将{ni}放入OPEN表的末端，转2；否则，ni达到深度k，计算e(ni)，并转2；455、若CLOSED表为空，则转8；否则取出CLOSED表中的第一个节点，记为np；Open为空，即已经扩展完节点步2466、若np属于MAX层，且对于它的属于MIN层的子节点nci的e(nci)有值，则：e(np)=max{nci}47（续）若np属于MIN层，且对于它的属于MAX层的子节点nci的e(nci)有值，则：e(np)=min{nci}487、转5；8、根据e(S)的值，标记走步或者结束（-∞，∞或0）。49第一阶段为1、2、3、4步，用宽度优先算法生成规定深度k的全部博弈树，然后对其所有端节点计算e(P)；第二阶段为5、6、7、8步，是自下而上逐级求节点的倒推估价值，直至求出初始节点的e(S)为止，再由e(S)选得相对较好的走法，过程结束。算法分成两个阶段：50等对手走出相应的棋，再以当前的格局作为初始节点，重复此过程，选择对自己有利的走法。51极大极小过程52例：一字棋的极大极小搜索过程约定：每一方只向前看一步（扩展出二层）记MAX的棋子为“×”，MIN的棋子为“O”规定MAX先手53①若格局P对任何一方都不能获胜，则e(P)=（所有空格上都放上MAX的棋子后，MAX的三个棋子所组成的行、列及对角线的总数）-（所有空格上都放上MIN的棋子后，MIN的三个棋子所组成的行、列及对角线的总数）静态估计函数e(P)定义为：54②若P是MAX获胜，则e(P)=+∞③若P是MIN获胜，则e(P)=－∞55例：计算下列棋局的静态估价函数值e(P)=6-4=2棋局O××O×××××××OOOO×OOOO行=2列=2对角=2行=2列=2对角=056利用棋盘的对称性，有些棋局是等价的O××OO××O57××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步58第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX1100159第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-1160×OO××MAXMIN61MAXMIN×O××O62极大极小搜索过程由两个完全分离的两个步骤组成：第一、用宽度优先算法生成一棵博弈搜索树第二、估计值的倒推计算缺点：这种分离使得搜索的效率比较低63极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-360316011极大极小ab注：用□表示MAX，用○表示MIN，端节点上的数字表示它对应的估价函数的值。极大极小64极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。改进：在博弈树生成过程中同时计算端节点的估计值及倒推值，以减少搜索的次数，这就是α-β过程的思想，也称为α-β剪枝法。剪枝的概念:如果能边生成节点边对节点估值，并剪去一些没用的分枝，这种技术被称为α-β剪枝。65