人工智能博弈树的搜索(45张)课件

1、2.3博弈树搜索第1页，共46页。20世纪60年代，研制出的西洋跳棋和国际象棋的博弈程序达到了大师级的水平。1958约翰麦卡锡提出博弈树搜索算法1997年，IBM公司研制的“深蓝”国际象棋 程序，采用博弈树搜索算法，该程序战胜了国际象棋世界冠军卡斯帕罗夫。1.概述第2页，共46页。正在与深蓝下棋的卡斯帕罗夫第3页，共46页。博弈问题特点：双人对弈，轮流走步。信息完备，双方所得到的信息是一样的。零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或无利的棋。1.概述第4页，共46页。博弈的特性两个棋手交替地走棋 ；比赛的最终结果，是赢、输和平局中的一种；可用图搜索技术进行，但效率很低

2、；博弈的过程，是寻找置对手于必败态的过程；双方都无法干预对方的选择。1.概述第5页，共46页。2.Grundy 博弈下棋的双方是对立的，命名博弈的双方，一方为“正方”，这类节点称为“MAX”节点；另一方为“反方”，这类节点称为“MIN”节点。正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现。第6页，共46页。2.Grundy 博弈Grundy博弈是一个分钱币的游戏。有 一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如，选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去，直到有一位选手先无法把钱币再分成不相等的两堆时

3、就得认输。第7页，共46页。2.Grundy 博弈设初始状态为(7，MIN)，建立问题的状态空间图，图中所有终结点均表示该选手必输的情况，取胜方的目标是设法使棋局发展为结束在对方走步时的终结点上。第8页，共46页。MIN先走MAX必胜2.Grundy 博弈第9页，共46页。结点A是MAX的搜索目标，而结点B，C则为MIN的搜索目标。2.Grundy 博弈第10页，共46页。搜索策略要考虑的问题是：对MIN走步后的每一个MAX结点，必须证明MAX对MIN可能走的每一个棋局对弈后能获胜，即MAX必须考虑应付MIN的所有招法，这是一个与的含意，因此含有MAX符号的结点可看成与结点。 2.Grundy

4、 博弈第11页，共46页。对MAX走步后的每一个MIN结点，只须证明MAX有一步能走赢就可以，即MAX只要考虑能走出一步棋使MIN无法招架就成，因此含有MIN符号的结点可看成或结点。2.Grundy 博弈第12页，共46页。对弈过程的搜索图呈现出与或图表示的形式。实现一种取胜的策略就是搜索一个解图的问题，解图就代表一种完整的博弈策略。 2.Grundy 博弈第13页，共46页。中国象棋一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。3.极小极大搜索过程第14页，共46页。对各个局面进行评估评估的目的：对后面的状态提前进行考虑，并且

5、以各种状态的评估值为基础作出最好的走棋选择。 评估的方法：用评价函数对棋局进行评估。赢的评估值设为+，输的评估值设为-，平局的评估值设为0。 评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。3.极小极大搜索过程第15页，共46页。MAX节点和MIN节点命名博弈的双方，一方为“正方”，对每个状态的评估都是对应于该方的输赢的。例如，赢2个，输1个等，都是指正方的。正方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为“MAX”节点；3.极小极大搜索过程第16页，共46页。另一方为“反方”，对每个状态的评估都是对应于对手的输赢的。例如，赢2个，输一个，其实是指自己输2个，赢

6、1个的。反方每走一步，都在选择使对手输得更多的节点，因此这类节点称为“MIN”节点。3.极小极大搜索过程第17页，共46页。由于正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现。3.极小极大搜索过程第18页，共46页。正方（MAX节点）从所有子节点中，选取具有最大评估值的节点。反方（MIN节点）从其所有子节点中，选取具有最小评估值的节点。反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为极小极大搜索法。 3.极小极大搜索过程第19页，共46页。3.极小极大搜索过程第20页，共46页。5-333-3022-30-23541-30689-3MINMAX0MAXM

7、IN3.极小极大搜索过程第21页，共46页。015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN3.极小极大搜索过程第22页，共46页。 在九宫格棋盘上，两位选手轮流在棋盘上摆各自的 棋子(每次一枚)，谁先取得三线的结果就取胜。 设程序方MAX的棋子用()表示， MAX先走。 对手MIN的棋子用(o)表示。 例如：3.极小极大搜索过程MIN取胜第23页，共46页。 估计函数 f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成线数)(所有空格都放上MIN的棋子之后，MIN的三子成线的总数) 若P是MAX获胜的格局，

8、则f(p)=+ ； 若P是MIN获胜的格局，则f(p)- 。3.极小极大搜索过程第24页，共46页。3.极小极大搜索过程估计函数值 f(p)=6-4=2估计函数 f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成线(行、列、对角)数)(所有空格都放上MIN的棋子之后，MIN的三子成线(行、列、对角)的总数)当前棋局f(p)=2第25页，共46页。3.极小极大搜索过程一字棋第一阶段搜索树第26页，共46页。3.极小极大搜索过程一字棋第二阶段搜索树第27页，共46页。3.极小极大搜索过程一字棋第三阶段搜索树第28页，共46页。 设有一个摆放三个子的棋盘残局，如下图所示，和在结束前有三步棋可

9、以走，而且设走第一步的是 。这时存在着三个空格A，B，C，用博弈树搜索算法判断应该把棋子放到哪一格内。 ABC棋盘残局举例：3.极小极大搜索过程第29页，共46页。ABCBCCB0ACCAABBA-1-0-10-0MAX节点MIN节点终端节点3.极小极大搜索过程第30页，共46页。 对于棋盘残局中的来说，最好的选择，是将放在C的位置上，这时可以导致平局局面。 3.极小极大搜索过程第31页，共46页。-剪支法的引入 在极小极大法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的-剪支

10、法。4. -搜索过程第32页，共46页。 作为正方出现的MAX节点，假设它的MIN子节点有N个，那么当它的第一个MIN子节点的评估值为时，则对于其它的子节点，如果有高过的，就取那最高的值作为该MAX节点的评估值；如果没有，则该MAX节点的评估值为。 总之，该MAX节点的评估值不会低于，这个就称为该MAX节点的评估下限值。4. -搜索过程 MAX节点的评估下限值 第33页，共46页。 MIN节点的评估上限值 作为反方出现的MIN节点，假设它的MAX子节点有N个，那么当它的第一个MAX子节点的评估值为时，则对于其它子节点，如果有低于的，就取那个低于的值作为该MIN节点的评估值；如果没有，则该MIN

11、节点的评估值取。 总之，该MIN节点的评估值不会高过，这个就称为该MIN节点的评估上限值。4. -搜索过程第34页，共46页。剪支法 MAX节点MIN节点=剪支ABCD4. -搜索过程 设MAX节点的下限为，则其所有的MIN子节点中，其评估值的上限小于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪支。第35页，共46页。 设MIN节点的上限为，则其所有的MAX子节点中，其评估值的下限大于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪支。MAX节点MIN节点=剪支ABCD4. -搜索过程剪支法 第36页，共46页。A B CDEFG H I J K L N O

12、 M4. -搜索过程MAX节点MAX节点MIN节点终端节点35652164第37页，共46页。MAX节点(5,)35652164(6,)(2,)(-,5)(-,2)(5,)MIN节点终端节点剪支剪支A B CDEFG H I J K L N O MMAX节点4. -搜索过程第38页，共46页。一字棋第一阶段-剪支方法4. -搜索过程第39页，共46页。4. -搜索过程极大节点的下界为。极小节点的上界为。剪支的条件：后辈节点的值祖先节点的值时， 剪支后辈节点的 值祖先节点的值时， 剪支简记为：极小极大， 剪支极大极小， 剪支第40页，共46页。4. -搜索过程86-31453-3503-3022

13、-30-2309-300-303305411-31661abcdefghijkmnMAXMINMAXMIN第41页，共46页。改进方法 使用-剪支技术，当不满足剪支条件(即)时或值比值大不了多少或极相近时，这时也可以进行剪支，以便有条件把搜索集中到会带来更大效果的其他路径上，这就是中止对效益不大的一些子树的搜索，以提高搜索效率。 4. -搜索过程第42页，共46页。 不严格限制搜索的深度。当到达深度限制时，如出现博弈格局有可能发生较大变化时，则应多搜索几层，使格局进入较稳定状态后再中止，这样可使倒推值计算的结果比较合理，避免考虑不充分产生的影响，这是等候状态平稳后中止搜索的方法。 4. -搜索

14、过程第43页，共46页。当算法给出所选的走步后，不要马上停止搜索，而是在原先估计可能的路径上再往前搜索几步，再次检验会不会出现意外，这是一种增添辅助搜索的方法。 4. -搜索过程第44页，共46页。对某些博弈的开局阶段和残局阶段，往往总结了一些固定的对弈模式，因此可以利用这些知识编好走步表，以便在开局和结局时使用查表法。只是在进入中盘阶段后，再调用其他有效的搜索算法，来选择最优的走步。4. -搜索过程第45页，共46页。1、不是井里没有水，而是你挖的不够深。不是成功来得慢，而是你努力的不够多。2、孤单一人的时间使自己变得优秀，给来的人一个惊喜，也给自己一个好的交代。3、命运给你一个比别人低的起

15、点是想告诉你，让你用你的一生去奋斗出一个绝地反击的故事，所以有什么理由不努力!4、心中没有过分的贪求，自然苦就少。口里不说多余的话，自然祸就少。腹内的食物能减少，自然病就少。思绪中没有过分欲，自然忧就少。大悲是无泪的，同样大悟无言。缘来尽量要惜，缘尽就放。人生本来就空，对人家笑笑，对自己笑笑，笑着看天下，看日出日落，花谢花开，岂不自在，哪里来的尘埃!5、心情就像衣服，脏了就拿去洗洗，晒晒，阳光自然就会蔓延开来。阳光那么好，何必自寻烦恼，过好每一个当下，一万个美丽的未来抵不过一个温暖的现在。6、无论你正遭遇着什么，你都要从落魄中站起来重振旗鼓，要继续保持热忱，要继续保持微笑，就像从未受伤过一样。

16、7、生命的美丽，永远展现在她的进取之中;就像大树的美丽，是展现在它负势向上高耸入云的蓬勃生机中;像雄鹰的美丽，是展现在它搏风击雨如苍天之魂的翱翔中;像江河的美丽，是展现在它波涛汹涌一泻千里的奔流中。8、有些事，不可避免地发生，阴晴圆缺皆有规律，我们只能坦然地接受;有些事，只要你愿意努力，矢志不渝地付出，就能慢慢改变它的轨迹。9、与其埋怨世界，不如改变自己。管好自己的心，做好自己的事，比什么都强。人生无完美，曲折亦风景。别把失去看得过重，放弃是另一种拥有;不要经常艳羡他人，人做到了，心悟到了，相信属于你的风景就在下一个拐弯处。10、有些事想开了，你就会明白，在世上，你就是你，你痛痛你自己，你累累

17、你自己，就算有人同情你，那又怎样，最后收拾残局的还是要靠你自己。11、人生的某些障碍，你是逃不掉的。与其费尽周折绕过去，不如勇敢地攀登，或许这会铸就你人生的高点。12、有些压力总是得自己扛过去，说出来就成了充满负能量的抱怨。寻求安慰也无济于事，还徒增了别人的烦恼。13、认识到我们的所见所闻都是假象，认识到此生都是虚幻，我们才能真正认识到佛法的真相。钱多了会压死你，你承受得了吗?带，带不走，放，放不下。时时刻刻发悲心，饶益众生为他人。14、梦想总是跑在我的前面。努力追寻它们，为了那一瞬间的同步，这就是动人的生命奇迹。15、懒惰不会让你一下子跌倒，但会在不知不觉中减少你的收获;勤奋也不会让你一夜成功，但会在不知不觉中积累你的成果。人生需