人工智能之与或图搜索问题

第二章与或图搜索问题目标目标初始节点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一个α-β剪枝的具体例子，如下图所示。其中最下面一层端节点旁边的数字是假设的估值。