搜索
§2.5博弈树的搜索1.博弈树☼●○☼●○☼●○☼●○●☼○●☼○●☼○●☼○博弈的特性：①两个棋手交替地走棋；②比赛的最终结果，是赢、输和平局中的一种；③可用图搜索技术进行，但效率很低；④博弈的过程，是寻找置对手于必败态的过程；⑤双方都无法干预对方的选择。三子残局举例：设有一个摆放三个子的象棋残局a)，如下图所示，〇和╳在结束前有三步棋可以走，而且设走第一步的是〇。这时存在着三个空格A，B，C，应该把棋子放到哪一格内是需要进行判断的难点问题。AB〇〇〇╳╳C╳a)如果〇选择在空格A上，则棋盘局面变成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的位置放子，从而局面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的位置上，这时可以导致平局局面。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，此外根据与赢局相关的棋子数目，可以设为1，2。–评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。MAX节点•命名博弈的双方，一方为“正方”。对每个状态的评估都是对应于该方进行的。例如，赢2个，输1个等，都是指正方的。正方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为“MAX”节点；MIN节点•另一方为“反方”，对每个状态的评估都是对应于对手进行的。例如，赢2个，输1个，其实是指自己输2个，赢1个的。反方每走一步，都在选择使对手输得更多的节点，因此这类节点称为“MIN”节点。博弈树的最小最大化•由于正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现，从而实现博弈树的最小最大化。举例：hebacfdgij0-2-20--00MIN节点MAX节点终端节点极大极小法的引入：•如例题中所示，设执〇的这一方是正方，它从所有子节点中，选取具有最大评估值的节点，所以称为MAX节点。•另一方执的是反方，它的每一个节点都是从其所有子节点中，选取具有最小评估值的节点，所以称为MIN节点。•反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为极大极小法。3.-剪枝法•-剪枝法的引入：–在极大极小法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的-剪枝法。MAX节点的评估下限值•作为正方出现的MAX节点，取它的第一个MIN子节点的评估值。当有其它子节点的评估值超过，则该MAX节点会取新值作为自己的评估值；如果没有，则该MAX节点的评估值就是。•总之，该MAX节点的评估值不会低于，这个就称为该MAX节点的评估下限值。例如：•对于MAX节点a，取它的第一个MIN子节点b的评估值-作为a的评估下限值，即=-。它表示节点a的最后评估值不会低于该值。heba--00MIN节点MAX节点又例如：•对于MAX节点a，取它的第一个MIN子节点b的评估值4作为a的评估下限值，即=4。它表示节点a的最后评估值不会低于该值。heba4104MIN节点MAX节点MIN节点的评估上限值•作为反方出现的MIN节点，取它的第一个MAX子节点的评估值。当有其它子节点的评估值低于，则该MIN节点会取新值作为自己的评估值；如果没有，则该MIN节点的评估值就是。•总之，该MIN节点的评估值不会高过，这个就称为该MIN节点的评估上限值。例如：•对于MIN节点b，取它的第一个子节点的评估值0作为b的评估上限值，即=0。它表示节点b的最后评估值不会超过该值。bcd0--MIN节点终端节点又例如：•对于MIN节点h，取它的第一个子节点的评估值0作为b的评估上限值，即=0。它表示节点b的最后评估值不会超过该值。hij020MIN节点终端节点剪枝法：•设MAX节点的下限为，则其所有的MIN子节点中，其评估值小于等于的，其下部分的搜索都可以停止了，即对这部分节点进行了剪枝。ABCDMAX节点(,+)MIN节点剪枝剪枝法：•设MIN节点的上限为，则其所有的MAX子节点中，其评估值大于等于的，其下部分的搜索都可以停止了，即对这部分节点进行了剪枝。BAMAX节点(-,)MIN节点剪枝CB举例：MAX节点MIN节点DH356?21??IJKLMNOEFGBCAMAX节点终端节点DH35I(5,)•对于MAX节点D，取第一个子节点H的评估值作为它的下限，当另一个子节点I的评估值超过时，它最后的评估值定为5以上。DH35I(5,)•对于MIN节点B，取第一个子节点D的评估值5作为它的上限，最后评估值是否能定为5，还要看其它子节点的评估值。B(-,5)DH35I(5,)•对于MAX节点E，取第一个子节点J的评估值6作为它的下限，它表示节点E的最后评估值一定不会低于6的。B(-,5)6?JKE(6,)剪枝的过程：•对于MIN节点B，它显然是不可能选择节点E的。因为E的评估值超过了节点B的上限，这就确定了与K的评估值没有关系，所以没有必要去求它的评估值。这种剪枝，是由于节点E的评估值超过了它的双亲节点（节点B），所以被称为β剪枝。DH356?IJKEB(5,)(-,5)(6,)DH356?IJKEBA(5,)(-,5)(6,)•对于MAX节点A，取第一个子节点B的评估值5作为它的下限，最后评估值是否能定为5，还要看其它子节点的评估值。(5,)21LMF•对于MAX节点F，取第一个子节点L的评估值2作为它的下限，当另一个子节点M的评估值小于时，它最后的评估值取。(2,)21LMFC(2,)•对于MIN节点C，取第一个子节点F的评估值2作为它的上限，表示节点C最后的评估值不会超过。(-,2)剪枝的过程：•由于MAX节点A的评估下限值为5，其子节点C的评估值未能超过该下限，因此不可能被节点A选中。这说明MAX节点G的值已没有评价的意义了，因此也就没有必要去求节点N和O的评估值了。这种剪枝，由于节点C的评估值低于它的双亲节点（节点A）的α值，被称为α剪枝。21??LMNOFGCA(2,)(-,2)(5,)结果：MAX节点MIN节点DH(5,)356?21??IJKLMNOEFG(6,)(2,)BC(-,5)(-,2)A(5,)MAX节点终端节点剪枝剪枝