人工智能-博弈树的搜索

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

2、中的一种种；可用图搜搜索技术术进行，但效率率很低；博弈的过过程，是是寻找置置对手于于必败态态的过程程；双方都无无法干预预对方的的选择。1.概述2.Grundy博弈下棋的双双方是对对立的，命名博博弈的双双方，一一方为“正方”，这类类节点称称为“MAX”节点；另另一方为为“反方方”，这这类节点点称为“MIN”节点。正正方和反反方是交交替走步步的，因因此MAX节点和MIN节点会交交替出现现。2.Grundy博弈Grundy博弈是一一个分钱钱币的游游戏。有有 一堆堆数目为为N的钱币，由两位位选手轮轮流进行行分堆，要求每每个选手手每次只只把其中中某一堆堆分成数数目不等等的两小小堆。例例如，选选手甲把把N

3、分成两堆堆后，轮轮到选手手乙就可可以挑其其中一堆堆来分，如此进进行下去去，直到到有一位位选手先先无法把把钱币再再分成不不相等的的两堆时时就得认认输。2.Grundy博弈设初始状状态为(7，MIN)，建立问问题的状状态空间间图，图图中所有有终结点点均表示示该选手手必输的的情况，取胜方方的目标标是设法法使棋局局发展为为结束在在对方走走步时的的终结点点上。MIN先走MAX必胜2.Grundy博弈结点A是MAX的搜索目目标，而而结点B，C则为MIN的搜索目目标。2.Grundy博弈搜索策略略要考虑虑的问题题是：对MIN走步后的的每一个个MAX结点，必必须证明明MAX对MIN可能走的的每一个个棋局对对弈

4、后能能获胜，即MAX必须考虑虑应付MIN的所有招招法，这这是一个个与的含含意，因因此含有有MAX符号的结结点可看看成与结结点。 2.Grundy博弈对MAX走步后的的每一个个MIN结点，只只须证明明MAX有一步能能走赢就就可以，即MAX只要考虑虑能走出出一步棋棋使MIN无法招架架就成，因此含含有MIN符号的结结点可看看成或结结点。2.Grundy博弈对弈过程程的搜索索图呈现现出与或或图表示示的形式式。实现一种种取胜的的策略就就是搜索索一个解解图的问问题，解解图就代代表一种种完整的的博弈策策略。2.Grundy博弈中国象棋棋一盘棋平平均走50步，总状状态数约约为10的161次方。假设1毫微秒走走

5、一步，约需10的145次方年。结论：不不可能穷穷举。3.极小极大大搜索过过程对各个局局面进行行评估评估的目目的：对对后面的的状态提提前进行行考虑，并且以以各种状状态的评评估值为为基础作作出最好好的走棋棋选择。评估的方方法：用用评价函函数对棋棋局进行行评估。赢的评评估值设设为+，输的评评估值设设为-，平局的的评估值值设为0。评估的标标准：由由于下棋棋的双方方是对立立的，只只能选择择其中一一方为评评估的标标准方。3.极小极大大搜索过过程MAX节点和MIN节点命名博弈弈的双方方，一方方为“正正方”，对每个个状态的的评估都都是对应应于该方方的输赢赢的。例例如，赢赢2个，输1个等，都都是指正正方的。正方

6、每每走一步步，都在在选择使使自己赢赢得更多多的节点点，因此此这类节节点称为为“MAX”节点；3.极小极大大搜索过过程另一方为为“反方方”，对对每个状状态的评评估都是是对应于于对手的的输赢的的。例如如，赢2个，输一一个，其其实是指指自己输输2个，赢1个的。反反方每走走一步，都在选选择使对对手输得得更多的的节点，因此这这类节点点称为“MIN”节点。3.极小极大大搜索过过程由于正方方和反方方是交替替走步的的，因此此MAX节点和MIN节点会交交替出现现。3.极小极大大搜索过过程正方（MAX节点）从从所有子子节点中中，选取取具有最最大评估估值的节节点。反方（MIN节点）从从其所有有子节点点中，选选取具有

7、有最小评评估值的的节点。反复进行行这种选选取，就就可以得得到双方方各个节节点的评评估值。这种确确定棋步步的方法法，称为为极小极大大搜索法法。3.极小极大大搜索过过程3.极小极大大搜索过过程5-333-3022-30-23541-30689-3MINMAX0MAXMIN3.极小极大大搜索过过程015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN3.极小极大大搜索过过程在九宫格格棋盘上上，两位位选手轮轮流在棋棋盘上摆摆各自的的棋子(每次一枚枚)，谁先取取得三线线的结果果就取胜胜。设程序方方MAX的棋子用用()表示，MAX先走

8、。对手MIN的棋子用用(o)表示。例如：3.极小极大大搜索过过程MIN取胜估计函数数f(p)=(所有空格格都放上上MAX的棋子之之后，MAX的三子成成线数)(所有空格格都放上上MIN的棋子之之后，MIN的三子成成线的总总数)若P是MAX获胜的格格局，则则f(p)=+；若P是MIN获胜的格格局，则则f(p)-。3.极小极大大搜索过过程3.极小极大大搜索过过程估计函数数值f(p)=6-4=2估计函数数f(p)=(所有空格格都放上上MAX的棋子之之后，MAX的三子成成线(行、列、对角)数)(所有空格格都放上上MIN的棋子之之后，MIN的三子成成线(行、列、对角)的总数)当前棋局局f(p)=23.极小

9、极大大搜索过过程一字棋第第一阶段段搜索树树3.极小极大大搜索过过程一字棋第第二阶段段搜索树树3.极小极大大搜索过过程一字棋第第三阶段段搜索树树设有一个个摆放三三个子的的棋盘残局，如如下图所所示，和在结束前前有三步步棋可以以走，而而且设走走第一步步的是。这时存存在着三三个空格格A，B，C，用博弈弈树搜索索算法判判断应该该把棋子子放到哪哪一格内内。ABC棋盘残局局举例：3.极小极大大搜索过过程ABCBCCB0ACCAABBA-1-0-10-0MAX节点MIN节点终端节点点3.极小极大大搜索过过程对于棋盘盘残局中中的来说，最最好的选选择，是是将放在C的位置上上，这时时可以导导致平局局局面。3.极小极

10、大大搜索过过程-剪支法的的引入在极小极极大法中中，必须须求出所所有终端端节点的的评估值值，当预预先考虑虑的棋步步比较多多时，计计算量会会大大增增加。为为了提高高搜索的的效率，引入了了通过对对评估值值的上下下限进行行估计，从而减减少需进进行评估估的节点点范围的的-剪支法。4.-搜索过程程作为正方方出现的的MAX节点，假假设它的的MIN子节点有有N个，那么么当它的的第一个个MIN子节点的的评估值值为时，则则对于其其它的子子节点，如果有有高过的，就就取那最最高的值值作为该该MAX节点的评评估值；如果没没有，则则该MAX节点的评评估值为为。总之，该该MAX节点的评评估值不不会低于于，这这个就就称为该该

11、MAX节点的评评估下限限值。4.-搜索过程程MAX节点的评评估下限限值MIN节点的评评估上限限值作为反方方出现的的MIN节点，假假设它的的MAX子节点有有N个，那么么当它的的第一个个MAX子节点的的评估值值为时，则则对于其其它子节节点，如如果有低低于的的，就取取那个低低于的的值作为为该MIN节点的评评估值；如果没没有，则则该MIN节点的评评估值取取。总之，该该MIN节点的评评估值不不会高过过，这这个就就称为该该MIN节点的评评估上限限值。4.-搜索过程程剪支法MAX节点MIN节点=剪支ABCD4.-搜索过程程设MAX节点的下下限为，则其其所有的MIN子节点中中，其评评估值的的上限小小于等于于的

12、节节点，其其以下部部分的搜搜索都可可以停止止了，即即对这部部分节点点进行了了剪支支。设MIN节点的上上限为，则其其所有的MAX子节点中中，其评评估值的的下限大大于等于于的节节点，其其以下部部分的搜搜索都可可以停止止了，即即对这部部分节点点进行了了剪支支。MAX节点MIN节点=剪支ABCD4.-搜索过程程剪支法A B CDEFG H I J K L N O M4.-搜索过程程MAX节点MAX节点MIN节点终端节点点35652164MAX节点(5,)35652164(6,)(2,)(-,5)(-,2)(5,)MIN节点终端节点点剪支剪支A B CDEFG H I J K L N O MMAX节点4

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