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

第二章与或图搜索问题目的目的初始节点sabc12.1根本概念与或图是一个超图，节点间经过衔接符衔接。K-衔接符：…...K个2耗散值的计算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集Cn为衔接符的耗散值…...i个nn1n2ni3目的目的初始节点解图：4能解节点终节点是能解节点假设非终节点有“或〞子节点时，当且仅当其子节点至少有一能解时，该非终节点才干解。假设非终节点有“与〞子节点时，当且仅当其子节点均能解时，该非终节点才干解。5不能解节点没有后裔的非终节点是不能解节点。假设非终节点有“或〞子节点，当且仅当一切子节点均不能解时，该非终节点才不能解。假设非终节点有“与〞子节点时，当至少有一个子节点不能解时，该非终节点才不能解。6普通图搜索的情况 f(n)=g(n)+h(n) 对n的评价实践是对从s到n这条途径的评价ns7与或图:对部分图的评价目的目的初始节点abc8两个过程图生成过程，即扩展节点从最优的部分途中选择一个节点扩展计算耗散值的过程对当前的部分图重新计算耗散值9AO*算法举例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K衔接符的耗散值为K目的目的初始节点n0n1n2n3n4n5n6n7n810目的目的初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：311初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)5目的目的初始节点n0n1n2n3n4n5n6n7n812红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目的目的初始节点n0n1n2n3n4n5n6n7n813红色：5黄色：621初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目的目的初始节点n0n1n2n3n4n5n6n7n814博弈是一类具有竞争性的智能活动双人博弈：即两位选手对垒，轮番依次走步，其中任何一方都完全知道对方过去曾经走过的棋步和今后能够的走步，其结果是一方赢(而另一方那么输)，或双方和局2.3博弈树搜索15博弈的例子：一字棋跳棋中国象棋围棋五子棋162.3博弈树搜索博弈问题双人对弈，对垒的双方轮番走步；信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另外一方看不到的情况；零和，即对一方有利的棋，对另一方一定是不利的，不存在对双方均有利或均无利的棋，对弈的结果是一方赢，而另一方输，或者双方和棋。17双方的智能活动，任何一方都不能单独控制博弈过程，而是由双方轮番实施其控制对策的过程。博弈的特点：18如何根据当前的棋局，选择对本人最有利的一步棋？人工智能中研讨的博弈问题：中国象棋19用博弈树来表示，它是一种特殊的与或树。节点代表博弈的格局〔即棋局〕，相当于形状空间中的形状，反映了博弈的信息，并且与节点、或节点隔层交替出现。博弈问题〔求解过程〕的表示：20假设博弈双方为：MAX和MIN在博弈过程中，规那么是双方轮番走步。在博弈树中，相当于博弈双方轮番扩展其所属节点。为什么与节点、或节点隔层交替出现？21从MAX方的角度来看：一切MIN方节点都是与节点理由：由于MIN方必定选择最不利于MAX方的方式来扩展节点，只需MIN方节点的子节点〔下出棋局〕中有一个对MAX方不利，那么该节点就对MAX方不利，故为“与节点〞。MIN好招22从MAX方的角度来看：一切属于MAX方的节点都是或节点理由：由于扩展MAX方节点时，MAX方可选择扩展最有利于本人的节点，只需可扩展的子节点中有一个对已有利，那么该节点就对已有利。MAX好招23总之：从MAX方来说，与节点、或节点交替出现；反之，从MIN方的角度来看，情况正好相反。24在博弈树中，先行一方的初始形状对应着树的根节点，而任何一方获胜的最终格局为目的形状，对应于树的终叶节点〔可解节点或本原问题〕。但是，从MAX的角度出发，一切使MAX获胜的形状格局都是本原问题，是可解节点，而使MIN获胜的形状格局是不可解节点。25博弈树特点(1)博弈的初始形状是初始节点；(2)博弈树的“与〞节点和“或〞节点是逐层交替出现的；(3)整个博弈过程一直站在某一方的立场上，所以能使本人一方获胜的结局都是本原问题，相应的节点也是可解节点，一切使对方获胜的节点都是不可解节点。26例Grundy博弈：分配物品的问题假设有一堆数目为N的钱币，由两位选手轮番进展分配，要求每个选手每次把其中某一堆分成数目不等的两小堆，直至有一选手不能将钱币分成不等的两堆为止，那么断定这位选手为输家。27用数字序列加上一个阐明来表示一个形状：(3,2,1,1,MAX)数字序列：表示不同堆中钱币的个数阐明：表示下一步由谁来分，即取MAX或MIN28如今取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)29分钱币问题〔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在人工智能中可以采用搜索方法来求解博弈问题，下面就来讨论博弈中两中最根本的搜索方法。

33对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺利进展。假设由MAX来选择走一步棋，问题是：MAX如何来选择一步好棋？极大极小过程34极大极小过程极大极小过程是思索双方对弈假设干步之后，从能够的走法中选一步相对好的走法来走，即在有限的搜索深度范围内进展求解。需求定义一个静态估价函数e,以便对棋局的态势做出评价。35①对于每一格局〔棋局〕给出〔定义或者倒推〕一个静态估价函数值。值越大对MAX越有利，反之越不利；极大极小过程的根本思绪：36②对于给定的格局，MAX给出能够的走法，然后MIN对应地给出相应的走法，这样反复假设干次，得到一组端节点〔必需由MIN走后得到的，等待MAX下的棋局〕。这一过程相当于节点扩展；注：博弈树深度或层数一定是偶数。37③对于每一个端节点，计算出它们的静态估价函数，然后自下而上地逐层计算倒推值，直到MAX开场的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值；④取估值最大的格局作为MAX要走的一招棋。38例：向前看一步的两层博弈树39定义静态函数e(P)的普通原那么：40OPEN：存放待扩展的节点，此时为队列，即以宽度优先的战略扩展节点。CLOSED：存放已扩展的节点，此时为堆栈，即后扩展的节点先计算。符号：41极大极小过程的根本思想：(1)当轮到MIN走步的节点时，MAX应思索最坏的情况〔即f(p)取极小值〕；(2)当轮到MAX走步的节点时，MAX应思索最好的情况〔即f(p)取极大值〕；(3)评价往回倒推时，相应于两位棋手的对抗战略，交替运用〔1〕和〔2〕两种方法传送倒推值。421、将初始节点S放入OPEN表中，开场时搜索树T由初始节点S构成；2、假设OPEN表为空〔节点扩展终了〕，那么转5；3、将OPEN表中第一个节点n移出放入CLOSED表的前端；极大极小搜索过程为：434、假设n可直接断定为赢、输、或平局，那么令对应的e(n)=∞，-∞或0，并转2；否那么扩展n，产生n的后继节点集{ni}，将{ni}放入搜索树T中。此时，假设搜索深度d{ni}小于预先设定的深度k，那么将{ni}放入OPEN表的末端，转2；否那么，ni到达深度k，计算e(ni)，并转2；445、假设CLOSED表为空，那么转8；否那么取出CLOSED表中的第一个节点，记为np；Open为空，即曾经扩展完节点步2456、假设np属于MAX层，且对于它的属于MIN层的子节点nci的e(nci)有值，那么：e(np)=max{nci}46〔续〕假设np属于MIN层，且对于它的属于MAX层的子节点nci的e(nci)有值，那么：e(np)=min{nci}477、转5；8、根据e(S)的值，标志走步或者终了〔-∞，∞或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)=〔一切空格上都放上MAX的棋子后，MAX的三个棋子所组成的行、列及对角线的总数〕-〔一切空格上都放上MIN的棋子后，MIN的三个棋子所组成的行、列及对角线的总数〕静态估计函数e(P)定义为：53②假设P是MAX获胜，那么e(P)=+∞③假设P是MIN获胜，那么e(P)=－∞54例：计算以下棋局的静态估价函数值e(P)=6-4=2棋局O××O×××××××OOOO×OOOO行=2列=2对角=2行=2列=2对角=055利用棋盘的对称性，有些棋局是等价的O××OO××O56××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步57第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX1100158第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-1159×OO××MAXMIN60MAXMIN×O××O61极大极小搜索过程由两个完全分别的两个步骤组成：第一、用宽度优先算法生成一棵博弈搜索树第二、估计值的倒推计算缺陷：这种分别使得搜索的效率比较低62极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-360316011极大极小ab注：用□表示MAX，用○表示MIN，端节点上的数字表示它对应的估价函数的值。极大极小63极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分别的搜索方式，需求生成规定深度内的一切节点，因此搜索效率较低。改良：在博弈树生成过程中同时计算端节点的估计值及倒推值，以减少搜索的次数，这就是α-β过程的思想，也称为α-β剪枝法。剪枝的概念:假设能边生成节点边对节点估值，并剪去一些没用的分枝，这种技术被称为α-β剪枝。64-剪枝极大节点的下界为。极小节点的上界为。剪枝的条件：后辈节点的值≤祖先节点的值时，剪枝后辈节点的值≥祖先节点的值时，剪枝简记为：极小≤极大，剪枝极大≥极小，剪枝65一个α-β剪枝的详细例子，如以下图所示。其中最下面一层端节点旁边的数字是假设的估值。在该图中，L、M、N的估值推出节点F