人工智能之与或图搜索问题(-)课件

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

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

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

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

Grundy博弈：分配物品的问题如果有一堆数目为N的钱币，由两位选手轮流进行分配，要求每个选手每次把其中某一堆分成数目不等的两小堆，直至有一选手不能将钱币分成不等的两堆为止，则判定这位选手为输家。27例Grundy博弈：分配物品的问题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现在取N＝7的简单情况，并由MIN先分注：如果MAX走分钱币问题（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分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）对于比较复杂的博弈问题，只能模拟人的思维“向前看几步”，然后作出决策，选择最有利自己的一步。即只能给出几层走法，然后按照一定的估算办法，决定走一好招。31对于比较复杂的博弈问题，只能模拟人的思维“向前看几步”，然后中国象棋一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。32中国象棋一盘棋平均走50步，总状态数约为10的161次方。3在人工智能中可以采用搜索方法来求解博弈问题，下面就来讨论博弈中两中最基本的搜索方法。

33在人工智能中可以采用搜索方法来求解博弈问题，下面就来讨论博弈对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺利进行。假设由MAX来选择走一步棋，问题是：MAX如何来选择一步好棋？

极大极小过程34对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺极大极小过程

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

对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数值。值越大对MAX越有利，反之越不利；极大极小过程的基本思路：36①对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数②

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

39例：向前看一步的两层博弈树39定义静态函数e(P)的一般原则：40定义静态函数e(P)的一般原则：40OPEN：存放待扩展的节点，此时为队列，即以宽度优先的策略扩展节点。CLOSED：存放已扩展的节点，此时为堆栈，即后扩展的节点先计算。

符号：41OPEN：存放待扩展的节点，此时为队列，即以宽度优先的策略扩极大极小过程的基本思想：(1)当轮到MIN走步的节点时，MAX应考虑最坏的情况（即f(p)取极小值）；(2)当轮到MAX走步的节点时，MAX应考虑最好的情况（即f(p)取极大值）；(3)评价往回倒推时，相应于两位棋手的对抗策略，交替使用（1）和（2）两种方法传递倒推值。42极大极小过程的基本思想：421、将初始节点

S放入

OPEN表中，开始时搜索树

T由初始节点

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

表中第一个节点

n移出放入CLOSED表的前端；极大极小搜索过程为：431、将初始节点S放入OPEN表中，开始时搜索树T4、若n可直接判定为赢、输、或平局，则令对应的e(n)=∞，-∞或0，并转2；否则扩展n，产生n的后继节点集{ni}，将{ni

}放入搜索树T中。此时，若搜索深度d{ni}小于预先设定的深度k，则将{ni}放入OPEN表的末端，转2；否则，ni达到深度k，计算e(ni)，并转2；444、若n可直接判定为赢、输、或平局，则令对应的e(n)5、若CLOSED表为空，则转8；否则取出CLOSED表中的第一个节点，记为

np；Open为空，即已经扩展完节点步2455、若CLOSED表为空，则转8；否则取出CLOSED表中的6、若

np

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

nci

的

e

(

nci

)有值，则：

e

(

np

)=max{

nci

}466、若np属于MAX层，且对于它的属于MIN层的子节点（续）若np属于MIN层，且对于它的属于MAX层的子节点

nci

的

e(nci

)有值，则：

e(np

)=min{

nci

}47（续）477、转5；8、根据

e(S)

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

一字棋的极大极小搜索过程

约定：每一方只向前看一步（扩展出二层）记MAX的棋子为“×”，MIN的棋子为“O”规定MAX先手52例：一字棋的极大极小搜索过程约定：52①

若格局P对任何一方都不能获胜，则e(P)=（所有空格上都放上MAX的棋子后，MAX的三个棋子所组成的行、列及对角线的总数）-（所有空格上都放上MIN的棋子后，MIN的三个棋子所组成的行、列及对角线的总数）静态估计函数e(P)定义为：53①若格局P对任何一方都不能获胜，则静态估计函数e(P②

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

若P是MIN获胜，则e(P)=－∞54②若P是MAX获胜，则54例：计算下列棋局的静态估价函数值

e(P)=6-4=2

棋局O××O×××××××OOOO×OOOO行=2列=2对角=2行=2列=2对角=055例：计算下列棋局的静态估价函数值e(P)=6-4=2棋利用棋盘的对称性，有些棋局是等价的

O××OO××O56利用棋盘的对称性，有些棋局是等价的O××OO××O56××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步57××××O×O×O×O×OO×O×O×O×O××O×O101第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX1100158第二步OXXOXOXXOXXOXXXOOXXOOXXOXOX第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-1159第三步OOXXXOOXXOOXXXOOXXXOOXXXOOX×OO××MAXMIN60×OO××MAXMIN60MAXMIN×O××O61MAXMIN×O××O61极大极小搜索过程由两个完全分离的两个步骤组成：第一、用宽度优先算法生成一棵博弈搜索树第二、估计值的倒推计算缺点：这种分离使得搜索的效率比较低62极大极小搜索过程由两个完全分离的两个步骤组成：62极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-360316011极大极小ab注：用□表示MAX，用○表示MIN，端节点上的数字表示它对应的估价函数的值。极大极小63极小极大过程05-333-3022-30-23541-306极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。改进：在博弈树生成过程中同时计算端节点的估计值及倒推值，以减少搜索的次数，这就是α-β过程的思想，也称为α-β剪枝法。剪枝的概念:如果能边生成节点边对节点估值，并剪去一些没用的分枝，这种技术被称为α-β剪枝。64极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生-剪枝极大节点的下界为。极小节点的上界为。剪枝的条件：后辈节点的值≤祖先节点的值时，剪枝后辈节点的值≥祖先节点的值时，剪枝简记为：极小≤极大，剪枝极大≥极小，剪枝65-剪枝极大节点的下界为。65一个α-β剪枝的具体例子，如下图所示。其中最下面一层端节点旁边的数字是假设的估值。在该图中，L、M、N的估值推出节点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。≥4S0≤4A≦011≥4≥5≥0CDE0-6×IJ4≦1KLN461×FG5P58H×M8β值α值β值α值QR×≤0≦-6S××66一个α-β剪枝的具体例子，如下图所示。其中最下面一层86-31453-350-剪枝（续）3-3022-30-239-300-303305411-31661abcdefghijkmn0

剪枝

剪枝

剪枝

剪枝6786-31453-350-剪枝（续）3-3022-30--剪枝的其他应用故障诊断ABCD风险投资68-剪枝的其他应用故障诊断6839、把生活中的每一天，都当作生命中的最后一天。

40、机不可失，时不再来。

41、就算全世界都否定我，还有我自己相信我。

42、不为模糊不清的未来担忧，只为清清楚楚的现在努力。

43、付出才会杰出。

44、成功不是凭梦想和希望，而是凭努力和实践。

45、成功这件事，自己才是老板！

46、暗自伤心，不如立即行动。

47、勤奋是你生命的密码，能译出你一部壮丽的史诗。

48、随随便便浪费的时间，再也不能赢回来。

49、不要轻易用过去来衡量生活的幸与不幸！每个人的生命都是可以绽放美丽的，只要你珍惜。

50、给自己定目标，一年，两年，五年，也许你出生不如别人好，通过努力，往往可以改变%的命运。破罐子破摔只能和懦弱做朋友。

51、当眼泪流尽的时候，留下的应该是坚强。

52、上天完全是为了坚强你的意志，才在道路上设下重重的障碍。

53、没有播种，何来收获；没有辛苦，何来成功；没有磨难，何来荣耀；没有挫折，何来辉煌。

54、只要路是对的，就不怕路远。

55、生命对某些人来说是美丽的，这些人的一生都为某个目标而奋斗。

56、浪花总是着扬帆者的路开放的。

74、失败是什么？没有什么，只是更走近成功一步；成功是什么？就是走过了所有通向失败的路，只剩下一条路，那就是成功的路。

75、要改变命运，首先改变自己。

76、我们若已接受最坏的，就再没有什么损失。

77、在生活中，我跌倒过。我在嘲笑声中站起来，虽然衣服脏了，但那是暂时的，它可以洗净。

78、没有压力的生活就会空虚；没有压力的青春就会枯萎；没有压力的生命就会黯淡。

79、人生就像一杯没有加糖的咖啡，喝起来是苦涩的，回味起来却有久久不会退去的余香。

80、最困难的时候，就是距离成功不远了。

81、知道自己要干什么，夜深人静，问问自己，将来的打算，并朝着那个方向去实现。而不是无所事事和做一些无谓的事。

82、出路出路，走出去了，总是会有路的。困难苦难，困在家里就是难。

83、人生最大的喜悦是每个人都说你做不到，你却完成它了！

84、勇士搏出惊涛骇流而不沉沦，懦夫在风平浪静也会溺水。

85、生活不是林黛玉，不会因为忧伤而风情万种。

86、唯有行动才能改造命运。

87、即使行动导致错误，却也带来了学习与成长；不行动则是停滞与萎缩。

88、光说不干，事事落空；又说又干，马到成功。

89、对于每一个不利条件，都会存在与之相对应的有利条件。

90、人的潜能是一座无法估量的丰富的矿藏，只等着我们去挖掘。

91、要成功，不要与马赛跑，要骑在马上，马上成功。

2、虚心使人进步，骄傲使人落后。

3、谦虚是学习的朋友，自满是学习的敌人。

4、若要精，人前听。

5、喜欢吹嘘的人犹如一面大鼓，响声大腹中空。

6、强中更有强中手，莫向人前自夸口。

7、请教别人不折本，舌头打个滚。

8、人唯虚，始能知人。满招损，谦受益。满必溢，骄必败。39、把生活中的每一天，都当作生命中的最后一天。69第二章与或图搜索问题目标目标初始节点sabc70第二章与或图搜索问题目标目标初始节点sabc12.1基本概念与或图是一个超图，节点间通过连接符连接。K-连接符：…...K个712.1基本概念与或图是一个超图，节点间通过连接符连接。….耗散值的计算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集

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

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

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

Grundy博弈：分配物品的问题如果有一堆数目为N的钱币，由两位选手轮流进行分配，要求每个选手每次把其中某一堆分成数目不等的两小堆，直至有一选手不能将钱币分成不等的两堆为止，则判定这位选手为输家。96例Grundy博弈：分配物品的问题27用数字序列加上一个说明来表示一个状态：(3,2,1,1,MAX)数字序列：表示不同堆中钱币的个数说明：表示下一步由谁来分，即取MAX或MIN97用数字序列加上一个说明来表示一个状态：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)98现在取N＝7的简单情况，并由MIN先分注：如果MAX走分钱币问题（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）对方先走我方必胜99分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）对于比较复杂的博弈问题，只能模拟人的思维“向前看几步”，然后作出决策，选择最有利自己的一步。即只能给出几层走法，然后按照一定的估算办法，决定走一好招。100对于比较复杂的博弈问题，只能模拟人的思维“向前看几步”，然后中国象棋一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。101中国象棋一盘棋平均走50步，总状态数约为10的161次方。3在人工智能中可以采用搜索方法来求解博弈问题，下面就来讨论博弈中两中最基本的搜索方法。

102在人工智能中可以采用搜索方法来求解博弈问题，下面就来讨论博弈对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺利进行。假设由MAX来选择走一步棋，问题是：MAX如何来选择一步好棋？

极大极小过程103对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺极大极小过程

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

对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数值。值越大对MAX越有利，反之越不利；极大极小过程的基本思路：105①对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数②

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

108例：向前看一步的两层博弈树39定义静态函数e(P)的一般原则：109定义静态函数e(P)的一般原则：40OPEN：存放待扩展的节点，此时为队列，即以宽度优先的策略扩展节点。CLOSED：存放已扩展的节点，此时为堆栈，即后扩展的节点先计算。

符号：110OPEN：存放待扩展的节点，此时为队列，即以宽度优先的策略扩极大极小过程的基本思想：(1)当轮到MIN走步的节点时，MAX应考虑最坏的情况（即f(p)取极小值）；(2)当轮到MAX走步的节点时，MAX应考虑最好的情况（即f(p)取极大值）；(3)评价往回倒推时，相应于两位棋手的对抗策略，交替使用（1）和（2）两种方法传递倒推值。111极大极小过程的基本思想：421、将初始节点

S放入

OPEN表中，开始时搜索树

T由初始节点

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

表中第一个节点

n移出放入CLOSED表的前端；极大极小搜索过程为：1121、将初始节点S放入OPEN表中，开始时搜索树T4、若n可直接判定为赢、输、或平局，则令对应的e(n)=∞，-∞或0，并转2；否则扩展n，产生n的后继节点集{ni}，将{ni

}放入搜索树T中。此时，若搜索深度d{ni}小于预先设定的深度k，则将{ni}放入OPEN表的末端，转2；否则，ni达到深度k，计算e(ni)，并转2；1134、若n可直接判定为赢、输、或平局，则令对应的e(n)5、若CLOSED表为空，则转8；否则取出CLOSED表中的第一个节点，记为

np；Open为空，即已经扩展完节点步21145、若CLOSED表为空，则转8；否则取出CLOSED表中的6、若

np

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

nci

的

e

(

nci

)有值，则：

e

(

np

)=max{

nci

}1156、若np属于MAX层，且对于它的属于MIN层的子节点（续）若np属于MIN层，且对于它的属于MAX层的子节点

nci

的

e(nci

)有值，则：

e(np

)=min{

nci

}116（续）477、转5；8、根据

e(S)

的值，标记走步或者结束（-∞，∞或0）。1177、转5；48第一阶段为1、2、3、4步，用宽度优先算法生成规定深度k的全部博弈树，然后对其所有端节点计算e(P)；第二阶段为5、6、7、8步，是自下而上逐级求节点的倒推估价值，直至求出初始节点的e(S)为止，再由e(S)选得相对较好的走法，过程结束。算法分成两个阶段：118第一阶段为1、2、3、4步，用宽度优先算法生成规定深度k等对手走出相应的棋，再以当前的格局作为初始节点，重复此过程，选择对自己有利的走法。119等对手走出相应的棋，再以当前的格局作为初始节点，重复此过程，极大极小过程120极大极小过程51例：

一字棋的极大极小搜索过程

约定：每一方只向前看一步（扩展出二层）记MAX的棋子为“×”，MIN的棋子为“O”规定MAX先手121例：一字棋的极大极小搜索过程约定：52①

若格局P对任何一方都不能获胜，则e(P)=（所有空格上都放上MAX的棋子后，MAX的三个棋子所组成的行、列及对角线的总数）-（所有空格上都放上MIN的棋子后，MIN的三个棋子所组成的行、列及对角线的总数）静态估计函数e(P)定义为：122①若格局P对任何一方都不能获胜，则静态估计函数e(P②

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

若P是MIN获胜，则e(P)=－∞123②若P是MAX获胜，则54例：计算下列棋局的静态估价函数值

e(P)=6-4=2

棋局O××O×××××××OOOO×OOOO行=2列=2对角=2行=2列=2对角=0124例：计算下列棋局的静态估价函数值e(P)=6-4=2棋利用棋盘的对称性，有些棋局是等价的

O××OO××O125利用棋盘的对称性，有些棋局是等价的O××OO××O56××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步126××××O×O×O×O×OO×O×O×O×O××O×O101第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX11001127第二步OXXOXOXXOXXOXXXOOXXOOXXOXOX第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-11128第三步OOXXXOOXXOOXXXOOXXXOOXXXOOX×OO××MAXMIN129×OO××MAXMIN60MAXMIN×O××O130MAXMIN×O××O61极大极小搜索过程由两个完全分离的两个步骤组成：第一、用宽度优先算法生成一棵博弈搜索树第二、估计值的倒推计算缺点：这种分离使得搜索的效率比较低131极大极小搜索过程由两个完全分离的两个步骤组成：62极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-360316011极大极小ab注：用□表示MAX，用○表示MIN，端节点上的数字表示它对应的估价函数的值。极大极小132极小极大过程05-333-3022-30-23541-306极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。改进：在博弈树生成过程中同时计算端节点的估计值及倒推值，以减少搜索的次数，这就是α-β过程的思想，也称为α-β剪枝法。剪枝的概念:如果能边生成节点边对节点估值，并剪去一些没用的分枝，这种技术被称为α-β剪枝。133极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生-剪枝极大节点的下界为。极小节点的上界为。剪枝的条件：后辈节点的值≤祖先节点的值时，剪枝后辈节点的值≥祖先节点的值时，剪枝简记为：极小≤极大，剪枝极大≥极小，剪枝134-剪枝极大节点的下界为。65一个α-β剪枝的具体例子，如下图所示。其中最下面一层端节点旁边的数字是假设的估值。在该图中，L、M、N的估值推出节点F的倒推值为4，即F的β值为4，由此可推出节点C的倒推值≥4。记C的倒推值的下界为4，不可能再比