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

第二章与或图搜索问题目标目标初始节点sabc1人工智能之与或图搜索问题第1页2.1基本概念与或图是一个超图，节点间经过连接符连接。K-连接符：…...K个2人工智能之与或图搜索问题第2页耗散值计算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集

Cn为连接符耗散值…...i个nn1n2ni3人工智能之与或图搜索问题第3页目标目标初始节点解图：4人工智能之与或图搜索问题第4页能解节点终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点最少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。5人工智能之与或图搜索问题第5页不能解节点没有后代非终节点是不能解节点。若非终节点有“或”子节点，当且仅当全部子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当最少有一个子节点不能解时，该非终节点才不能解。6人工智能之与或图搜索问题第6页普通图搜索情况 f(n)=g(n)+h(n) 对n评价实际是对从s到n这条路径评价ns7人工智能之与或图搜索问题第7页与或图:对局部图评价目标目标初始节点abc8人工智能之与或图搜索问题第8页两个过程图生成过程，即扩展节点从最优局部途中选择一个节点扩展计算耗散值过程对当前局部图从新计算耗散值9人工智能之与或图搜索问题第9页AO*算法举例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K连接符耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n810人工智能之与或图搜索问题第10页目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：311人工智能之与或图搜索问题第11页初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)5目标目标初始节点n0n1n2n3n4n5n6n7n812人工智能之与或图搜索问题第12页红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目标目标初始节点n0n1n2n3n4n5n6n7n813人工智能之与或图搜索问题第13页红色：5黄色：621初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目标目标初始节点n0n1n2n3n4n5n6n7n814人工智能之与或图搜索问题第14页博弈是一类含有竞争性智能活动双人博弈：即两位选手对垒，轮番依次走步，其中任何一方都完全知道对方过去已经走过棋步和今后可能走步，其结果是一方赢(而另一方则输)，或双方和局2.3博弈树搜索15人工智能之与或图搜索问题第15页博弈例子：一字棋跳棋中国象棋围棋五子棋16人工智能之与或图搜索问题第16页2.3博弈树搜索博弈问题双人对弈，对垒双方轮番走步；信息完备，对垒双方所得到信息是一样，不存在一方能看到，而另外一方看不到情况；零和，即对一方有利棋，对另一方必定是不利，不存在对双方都有利或均无利棋，对弈结果是一方赢，而另一方输，或者双方和棋。17人工智能之与或图搜索问题第17页双方智能活动，任何一方都不能单独控制博弈过程，而是由双方轮番实施其控制对策过程。博弈特点：18人工智能之与或图搜索问题第18页怎样依据当前棋局，选择对自己最有利一步棋？人工智能中研究博弈问题：中国象棋19人工智能之与或图搜索问题第19页用博弈树来表示，它是一个特殊与或树。节点代表博弈格局（即棋局），相当于状态空间中状态，反应了博弈信息，而且与节点、或节点隔层交替出现。博弈问题（求解过程）表示：20人工智能之与或图搜索问题第20页假设博弈双方为：MAX和MIN在博弈过程中，规则是双方轮番走步。在博弈树中，相当于博弈双方轮番扩展其所属节点。为何与节点、或节点隔层交替出现？21人工智能之与或图搜索问题第21页从MAX方角度来看：全部MIN方节点都是与节点理由：因为MIN方必定选择最不利于MAX方方式来扩展节点，只要MIN方节点子节点（下出棋局）中有一个对MAX方不利，则该节点就对MAX方不利，故为“与节点”。MIN好招22人工智能之与或图搜索问题第22页从MAX方角度来看：

全部属于MAX方节点都是或节点理由：因为扩展MAX方节点时，MAX方可选择扩展最有利于自己节点，只要可扩展子节点中有一个对已经有利，

则该节点就对已经有利。MAX好招23人工智能之与或图搜索问题第23页总之：从MAX方来说，与节点、或节点交替出现；反之，从MIN方角度来看，情况恰好相反。24人工智能之与或图搜索问题第24页在博弈树中，先行一方初始状态对应着树根节点，而任何一方获胜最终格局为目标状态，对应于树终叶节点（可解节点或本原问题）。不过，从MAX角度出发，全部使MAX获胜状态格局都是本原问题，是可解节点，而使MIN获胜状态格局是不可解节点。25人工智能之与或图搜索问题第25页博弈树特点(1)博弈初始状态是初始节点；(2)博弈树“与”节点和“或”节点是逐层交替出现；(3)整个博弈过程一直站在某一方立场上，所以能使自己一方获胜终局都是本原问题，对应节点也是可解节点，全部使对方获胜节点都是不可解节点。26人工智能之与或图搜索问题第26页例

Grundy博弈：分配物品问题假如有一堆数目为N钱币，由两位选手轮番进行分配，要求每个选手每次把其中某一堆分成数目不等两小堆，直至有一选手不能将钱币分成不等两堆为止，则判定这位选手为输家。27人工智能之与或图搜索问题第27页用数字序列加上一个说明来表示一个状态：(3,2,1,1,MAX)数字序列：表示不一样堆中钱币个数说明：表示下一步由谁来分，即取MAX或MIN28人工智能之与或图搜索问题第28页现在取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人工智能之与或图搜索问题第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人工智能之与或图搜索问题第30页对于比较复杂博弈问题，只能模拟人思维“向前看几步”，然后作出决议，选择最有利自己一步。即只能给出几层走法，然后按照一定估算方法，决定走一好招。31人工智能之与或图搜索问题第31页中国象棋一盘棋平均走50步，总状态数约为10161次方。假设1毫微秒走一步，约需10145次方年。结论：不可能穷举。32人工智能之与或图搜索问题第32页在人工智能中能够采取搜索方法来求解博弈问题，下面就来讨论博弈中两中最基本搜索方法。

33人工智能之与或图搜索问题第33页对于复杂博弈问题，要要求搜索深度与时间，方便于博弈搜索能顺利进行。假设由MAX来选择走一步棋，问题是：MAX怎样来选择一步好棋？

极大极小过程34人工智能之与或图搜索问题第34页极大极小过程

极大极小过程是考虑双方对弈若干步之后，从可能走法中选一步相对好走法来走，即在有限搜索深度范围内进行求解。需要定义一个静态估价函数e,方便对棋局态势做出评定。35人工智能之与或图搜索问题第35页①

对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数值。值越大对MAX越有利，反之越不利；极大极小过程基本思绪：36人工智能之与或图搜索问题第36页②

对于给定格局，MAX给出可能走法，然后MIN对应地给出对应走法，这么重复若干次，得到一组端节点（必须由MIN走后得到，等候MAX下棋局）。这一过程相当于节点扩展；注：博弈树深度或层数一定是偶数。37人工智能之与或图搜索问题第37页③对于每一个端节点，计算出它们静态估价函数，然后自下而上地逐层计算倒推值，直到MAX开始格局。在MIN下格局中取估值最小值，在MAX下格局中取估值最大值；④取估值最大格局作为MAX要走一招棋。38人工智能之与或图搜索问题第38页例：向前看一步两层博弈树

39人工智能之与或图搜索问题第39页定义静态函数e(P)普通标准：40人工智能之与或图搜索问题第40页OPEN：存放待扩展节点，此时为队列，即以宽度优先策略扩展节点。CLOSED：存放已扩展节点，此时为堆栈，即后扩展节点先计算。

符号：41人工智能之与或图搜索问题第41页极大极小过程基本思想：(1)当轮到MIN走步节点时，MAX应考虑最坏情况（即f(p)取极小值）；(2)当轮到MAX走步节点时，MAX应考虑最好情况（即f(p)取极大值）；(3)评价往回倒推时，对应于两位棋手反抗策略，交替使用（1）和（2）两种方法传递倒推值。42人工智能之与或图搜索问题第42页1、将初始节点

S放入

OPEN表中，开始时搜索树

T由初始节点

S组成；2、若OPEN表为空（节点扩展结束），则转5；3、将OPEN

表中第一个节点

n移出放入CLOSED表前端；极大极小搜索过程为：43人工智能之与或图搜索问题第43页4、若n可直接判定为赢、输、或平局，则令对应e(n)=∞，-∞或0，并转2；不然扩展n，产生n后继节点集{ni}，将{ni

}放入搜索树T中。此时，若搜索深度d{ni}小于预先设定深度k，则将{ni}放入OPEN表末端，转2；不然，ni到达深度k，计算e(ni)，并转2；44人工智能之与或图搜索问题第44页5、若CLOSED表为空，则转8；不然取出CLOSED表中第一个节点，记为

np；Open为空，即已经扩展完节点步245人工智能之与或图搜索问题第45页6、若

np

属于MAX层，且对于它属于MIN层子节点

nci

e

(

nci

)有值，则：

e

(

np

)=max{

nci

}46人工智能之与或图搜索问题第46页（续）若np属于MIN层，且对于它属于MAX层子节点

nci

e(nci

)有值，则：

e(np

)=min{

nci

}47人工智能之与或图搜索问题第47页7、转5；8、依据

e(S)

值，标识走步或者结束（-∞，∞或0）。48人工智能之与或图搜索问题第48页第一阶段为1、2、3、4步，用宽度优先算法生成要求深度k全部博弈树，然后对其全部端节点计算e(P)；第二阶段为5、6、7、8步，是自下而上逐层求节点倒推估价值，直至求出初始节点e(S)为止，再由e(S)选得相对很好走法，过程结束。算法分成两个阶段：49人工智能之与或图搜索问题第49页等对手走出对应棋，再以当前格局作为初始节点，重复此过程，选择对自己有利走法。50人工智能之与或图搜索问题第50页极大极小过程51人工智能之与或图搜索问题第51页例：

一字棋极大极小搜索过程

约定：每一方只向前看一步（扩展出二层）记MAX棋子为“×”，MIN棋子为“O”要求MAX先手52人工智能之与或图搜索问题第52页①

若格局P对任何一方都不能获胜，则e(P)=（全部空格上都放上MAX棋子后，MAX三个棋子所组成行、列及对角线总数）-（全部空格上都放上MIN棋子后，MIN三个棋子所组成行、列及对角线总数）静态预计函数e(P)定义为：53人工智能之与或图搜索问题第53页②

若P是MAX获胜，则e(P)=+∞③

若P是MIN获胜，则e(P)=－∞54人工智能之与或图搜索问题第54页例：计算以下棋局静态估价函数值

e(P)=6-4=2

棋局O××O×××××××OOOO×OOOO行=2列=2对角=2行=2列=2对角=055人工智能之与或图搜索问题第55页利用棋盘对称性，有些棋局是等价

O××OO××O56人工智能之与或图搜索问题第56页××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX走步57人工智能之与或图搜索问题第57页第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX1100158人工智能之与或图搜索问题第58页第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-1159人工智能之与或图搜索问题第59页×OO××MAXMIN60人工智能之与或图搜索问题第60页MAXMIN×O××O61人工智能之与或图搜索问题第61页极大极小搜索过程由两个完全分离两个步骤组成：第一、用宽度优先算法生成一棵博弈搜索树第二、预计值倒推计算缺点：这种分离使得搜索效率比较低62人工智能之与或图搜索问题第62页极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-360316011极大极小ab注：用□表示MAX，用○表示MIN，端节点上数字表示它对应估价函数值。极大极小63人工智能之与或图搜索问题第63页极大极小过程是先生成与/或树，然后再计算各节点估值，这种生成节点和计算估值相分离搜索方式，需要生成要求深度内全部节点，所以搜索效率较低。改进：在博弈树生成过程中同时计算端节点预计值及倒推值，以降低搜索次数，这就是α-β过程思想，也称为α-β剪枝法。剪枝概念:假如能边生成节点边对节点估值，并剪去一些没用分枝，这种技术被称为α-β剪枝。64人工智能之与或图搜索问题第64页-剪枝极大节点下界为。极小节点上界为。剪枝条件：后辈节点值≤祖先节点值时，剪枝后辈节点值≥祖先节点值时，剪枝简记为：