第二章基于搜索的问题求解之博弈树的搜索ppt课件.ppt

《第二章基于搜索的问题求解之博弈树的搜索ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2.5博弈树的搜索1.博弈树☼●○☼●○☼●○☼●○●☼○●☼○●☼○●☼○博弈的特性：两个棋手交替地走棋；比赛的最终结果，是赢、输和平局中的一种；可用图搜索技术进行，但效率很低；博弈的过程，是寻找置对手于必败态的过程；双方都无法干预对方的选择。三子残局举例：设有一个摆放三个子的象棋残局a)，如下图所示，〇和╳在结束前有三步棋可以走，而且设走第一步的是〇。这时存在着三个空格A，B，C，应该把棋子放到哪一格内是需要进行判断的难点问题。AB〇〇〇╳╳C╳a)如果〇选择在空格A上，则棋盘局面变成

2、b)，如右图所示。AB〇〇〇╳╳C╳〇B〇〇〇╳╳C╳a)b)接着轮到╳走棋。这时可供选择的分枝是剩余的B和C。如果这时╳选择B，则变成平局；如果选择C，则╳能赢。在这种情况下，╳当然会选择放在C，因此局面b）的预估值是输的。AB〇〇〇╳╳C╳〇B〇〇〇╳╳C╳〇╳〇〇〇╳╳C╳〇B〇〇〇╳╳╳╳平局赢a)b)c)d)输另一种情况，是〇选择B时，得到局面e）。接着╳的可选分枝剩下A和C。当╳选择A时，〇会出现两个并排的局面，╳可能会输；当╳选择C时，能够确保╳的赢局。因此，这时╳当然也会选择在C的位置放子，

3、从而局面e）的预估值为输。AB〇〇〇╳╳C╳A〇〇〇〇╳╳C╳╳〇〇〇〇╳╳C╳A〇〇〇〇╳╳╳╳可能输赢a)e)f)g)输最后一种情况，是〇选择C时，得到局面h）。接着╳的可选分枝剩下A和B。当╳选择A时，〇也会出现两个并排的局面，╳可能会输；当╳选择B时，却出现了平局的局面。因此，这时╳会选择放在B的位置，从而局面h）的预估值为平局。AB〇〇〇╳╳C╳AB〇〇〇╳╳〇╳╳B〇〇〇╳╳〇╳A╳〇〇〇╳╳〇╳可能输平局a)h)i)j)平局综合上述分析可以看出，对于局面a）中的〇来说，最好的选择，是将〇放在C

4、的位置上，这时可以导致平局局面。AB〇〇〇╳╳C╳〇B〇〇〇╳╳C╳〇╳〇〇〇╳╳C╳〇B〇〇〇╳╳╳╳b)c)d)a）A〇〇〇〇╳╳C╳╳〇〇〇〇╳╳C╳A〇〇〇〇╳╳╳╳e)f)g)AB〇〇〇╳╳〇╳╳B〇〇〇╳╳〇╳A╳〇〇〇╳╳〇╳h)i)j)2.博弈过程的最小最大化对各个局面进行评估评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋选择。评估的方法：因问题而异。例如，在摆三子的情况下，赢的评估值设为+∞，输的评估值设为-∞，平局的评估值设为0，此外根据与赢局相关的棋子

5、数目，可以设为1，2。评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。MAX节点命名博弈的双方，一方为“正方”。对每个状态的评估都是对应于该方进行的。例如，赢2个，输1个等，都是指正方的。正方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为“MAX”节点；MIN节点另一方为“反方”，对每个状态的评估都是对应于对手进行的。例如，赢2个，输1个，其实是指自己输2个，赢1个的。反方每走一步，都在选择使对手输得更多的节点，因此这类节点称为“MIN”节点。博弈树的最小最大化由于正方和反方是

6、交替走步的，因此MAX节点和MIN节点会交替出现，从而实现博弈树的最小最大化。举例：hebacfdgij0-2-20--00MIN节点MAX节点终端节点极大极小法的引入：如例题中所示，设执〇的这一方是正方，它从所有子节点中，选取具有最大评估值的节点，所以称为MAX节点。另一方执的是反方，它的每一个节点都是从其所有子节点中，选取具有最小评估值的节点，所以称为MIN节点。反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为极大极小法。3.-剪枝法-剪枝法的引入：在极大极小

7、法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的-剪枝法。MAX节点的评估下限值作为正方出现的MAX节点，取它的第一个MIN子节点的评估值。当有其它子节点的评估值超过，则该MAX节点会取新值作为自己的评估值；如果没有，则该MAX节点的评估值就是。总之，该MAX节点的评估值不会低于，这个就称为该MAX节点的评估下限值。例如：对于MAX节点a，取它的第一个MIN子节点b的评估值-

8、作为a的评估下限值，即=-。它表示节点a的最后评估值不会低于该值。heba--00MIN节点MAX节点又例如：对于MAX节点a，取它的第一个MIN子节点b的评估值4作为a的评估下限值，即=4。它表示节点a的最后评估值不会低于该值。heba4104MIN节点MAX节点MIN节点的评估上限值作为反方出现的MIN节点，取它的第一个MAX子节点的评估值。当有其它子节点的评估值低于，则该MIN节点会取