《第二章 基于搜索的问题求解之博弈树的搜索.ppt》由会员分享，可在线阅读，更多相关《第二章 基于搜索的问题求解之博弈树的搜索.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2.5 博弈树的搜索博弈树的搜索1.1.博弈树博弈树博弈的特性：博弈的特性：两个棋手交替地走棋两个棋手交替地走棋；比赛的最终结果，是赢、输和平局中的一比赛的最终结果，是赢、输和平局中的一种种；可用图搜索技术进行，但效率很低；可用图搜索技术进行，但效率很低；博弈的过程，是寻找置对手于必败态的过博弈的过程，是寻找置对手于必败态的过程；程；双方都无法干预对方的选择。双方都无法干预对方的选择。三子残局举例：三子残局举例：设有一个摆放三个子的象棋残局设有一个摆放三个子的象棋残局a)，如下，如下图所示，和图所示，和 在结束前有三步棋可以走，而在结束前有三步棋可以走，而且设走第一步的是。这时存在着三个空格且
2、设走第一步的是。这时存在着三个空格A，B，C，应该把棋子放到哪一格内是需要进，应该把棋子放到哪一格内是需要进行判断的难点问题。行判断的难点问题。A AB BC Ca)如果选择在如果选择在空格空格A上，则棋盘上，则棋盘局面变成局面变成b)，如右，如右图所示。图所示。A AB BC CB B C Ca)b)接着轮到接着轮到 走棋。这走棋。这时可供选择的分枝是剩时可供选择的分枝是剩余的余的B和和C。如果这时。如果这时 选选择择B，则变成平局；如果，则变成平局；如果选择选择C，则，则 能赢。在这能赢。在这种情况下，种情况下，当然会选择当然会选择放在放在C，因此局面，因此局面b）的）的预估值是输的。预估
3、值是输的。A AB BC CB B C CC CB B 平局平局赢赢 a)b)c)d)输输 另一种情况，是选另一种情况，是选择择B时，得到局面时，得到局面e）。）。接着接着 的可选分枝剩下的可选分枝剩下A和和C。当。当 选择选择A时，会时，会出现两个并排的局面，出现两个并排的局面，可能会输；当可能会输；当 选择选择C时，时，能够确保能够确保 的赢局。因此，的赢局。因此，这时这时 当然也会选择在当然也会选择在C的位置放子，从而局面的位置放子，从而局面e）的预估值为输。）的预估值为输。A AB BC CA A C CC CA A 可能输可能输赢赢 a)e)f)g)输输 最后一种情况，是最后一种情况
4、，是选择选择C时，得到局面时，得到局面h）。接着）。接着 的可选分枝的可选分枝剩下剩下A和和B。当。当 选择选择A时，时，也会出现两个并排的也会出现两个并排的局面，局面，可能会输；当可能会输；当 选择选择B时，却出现了平局时，却出现了平局的局面。因此，这时的局面。因此，这时 会会选择放在选择放在B的位置，从而的位置，从而局面局面h）的预估值为平局。）的预估值为平局。A AB BC CA AB B B BA A 可能输可能输平局平局 a)h)i)j)平局平局综合上述分析可以看出，对于局面综合上述分析可以看出，对于局面a）中的来说，最）中的来说，最好的选择，是将放在好的选择，是将放在C的位置上，这
5、时可以导致平的位置上，这时可以导致平局局面。局局面。A A B BC CB B C C C CB B b)c)d)a）A A C C C CA A e)f)g)A A B BB B A A h)i)j)2.博弈过程的最小最大化博弈过程的最小最大化对各个局面进行评估对各个局面进行评估评估的目的：对后面的状态提前进行考虑，并评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋且以各种状态的评估值为基础作出最好的走棋选择。选择。评估的方法：因问题而异。例如，在摆三子的评估的方法：因问题而异。例如，在摆三子的情况下，赢的评估值设为情况下，赢的评估值设为+，输的评估值设为，输
6、的评估值设为-，平局的评估值设为，平局的评估值设为0，此外根据与赢局相，此外根据与赢局相关的棋子数目，可以设为关的棋子数目，可以设为1，2。评估的标准：由于下棋的双方是对立的，只能评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。选择其中一方为评估的标准方。MAX节点节点命名博弈的双方，一方为命名博弈的双方，一方为“正方正方”。对每。对每个状态的评估都是对应于该方进行的。例个状态的评估都是对应于该方进行的。例如，赢如，赢2个，输个，输1个等，都是指个等，都是指正方正方的。正的。正方每走一步，都在选择使自己赢得更多的方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为节点
7、，因此这类节点称为“MAX”节点；节点；MIN节点节点另一方为另一方为“反方反方”，对每个状态的评估都，对每个状态的评估都是对应于对手进行的。例如，赢是对应于对手进行的。例如，赢2个，输个，输1个，其实是指自己输个，其实是指自己输2个，赢个，赢1个的。个的。反方反方每走一步，都在选择使对手输得更多的节每走一步，都在选择使对手输得更多的节点，因此这类节点称为点，因此这类节点称为“MIN”节点。节点。博弈树的最小最大化博弈树的最小最大化由于由于正方正方和和反方反方是交替走步的，因此是交替走步的，因此MAX节点和节点和MIN节点会交替出现，从而实现博弈节点会交替出现，从而实现博弈树的最小最大化。树的
8、最小最大化。举例：举例：hebacfdgij0-2-20-00MIN节点节点MAX节点节点终端节点终端节点极大极大极小极小法法的引入：的引入：如例题中所示，设执的这一方是如例题中所示，设执的这一方是正方正方，它从所有子节点中，选取具有最大评估值它从所有子节点中，选取具有最大评估值的节点，所以称为的节点，所以称为MAX节点。节点。另一方执另一方执 的是的是反方反方，它的每一个节点都是，它的每一个节点都是从其所有子节点中，选取具有最小评估值从其所有子节点中，选取具有最小评估值的节点，所以称为的节点，所以称为MIN节点。节点。反复进行这种选取，就可以得到双方各个反复进行这种选取，就可以得到双方各个节
9、点的评估值。这种确定棋步的方法，称节点的评估值。这种确定棋步的方法，称为为极大极大极小极小法法。3.-剪枝法剪枝法-剪枝法的剪枝法的引入：引入：在极大极小法中，必须求出所有终端节点的评在极大极小法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行对评估值的上下限进行估计，从而减少需进行评估的节点范围的评估的节点范围的-剪枝法。剪枝法。MAX节点的评估下限值节点的评估下限值 作为作为正方正方出现的出现的MAX节点，取它的
10、第一个节点，取它的第一个MIN子节点的评估值子节点的评估值。当有其它子节点的。当有其它子节点的评估值超过评估值超过，则该，则该MAX节点会取新值作为节点会取新值作为自己的评估值；如果没有，则该自己的评估值；如果没有，则该MAX节点节点的评估值就是的评估值就是 。总之，该总之，该MAX节点的评估值不会低于节点的评估值不会低于，这，这个个 就称为该就称为该MAX节点的评估下限值。节点的评估下限值。例如：例如：对于对于MAX节点节点a，取它的第一个取它的第一个MIN子节点子节点b的评估值的评估值-作为作为a的评估下限值的评估下限值，即，即=-。它表示节点。它表示节点a的最后评估值不会低于该的最后评估
11、值不会低于该值。值。heba-00MIN节点节点MAX节点节点又例如：又例如：对于对于MAX节点节点a，取它的第一个取它的第一个MIN子节点子节点b的评估值的评估值4作为作为a的评估下限值的评估下限值，即，即=4。它表示节点它表示节点a的最后评估值不会低于该值。的最后评估值不会低于该值。heba41 104MIN节点节点MAX节点节点MIN节点的评估上限值节点的评估上限值 作为作为反方反方出现的出现的MIN节点，取它的第一个节点，取它的第一个MAX子节点的评估值子节点的评估值。当有其它子节点的。当有其它子节点的评估值低于评估值低于，则该，则该MIN节点会取新值作为节点会取新值作为自己的评估值；
12、如果没有，则该自己的评估值；如果没有，则该MIN节点的节点的评估值就是评估值就是。总之，该总之，该MIN节点的评估值不会高过节点的评估值不会高过，这，这个个 就称为该就称为该MIN节点的评估上限值。节点的评估上限值。例如：例如：对于对于MIN节点节点b，取它的第一个子节点的评，取它的第一个子节点的评估值估值0作为作为b的评估上限值的评估上限值，即，即=0。它表。它表示节点示节点b的最后评估值不会超过该值。的最后评估值不会超过该值。bcd0-MIN节点节点终端节点终端节点又例如：又例如：对于对于MIN节点节点h，取它的第一个子节点的评，取它的第一个子节点的评估值估值0作为作为b的评估上限值的评估
13、上限值，即，即=0。它表。它表示节点示节点b的最后评估值不会超过该值。的最后评估值不会超过该值。hij02 20 0MIN节点节点终端节点终端节点 剪枝法：剪枝法：设设MAX节点的下限为节点的下限为，则其，则其所有的所有的MIN子子节点中，其评估值节点中，其评估值小于等于小于等于 的，其下部分的，其下部分的搜索都可以停止了，即对这部分节点进的搜索都可以停止了，即对这部分节点进行了行了 剪枝。剪枝。ABCDMAX节点节点(,+)MIN节点节点 剪枝剪枝 剪枝法：剪枝法：设设MIN节点的上限为节点的上限为，则其，则其所有的所有的MAX子子节点中，其评估值节点中，其评估值大于等于大于等于 的，其下部
14、分的，其下部分的搜索都可以停止了，即对这部分节点进的搜索都可以停止了，即对这部分节点进行了行了 剪枝。剪枝。BAMAX节点节点(-,)MIN节点节点 剪枝剪枝CB举例：举例：MAX节点节点MIN节点节点 D H356?21?I J K L M N O E FGB CAMAX节点节点终端节点终端节点 D H35 I(5,)对于对于MAX节点节点D，取第一个子节点，取第一个子节点H的评估值的评估值作为它的下限作为它的下限，当另一个子节点，当另一个子节点I的评估值的评估值超过超过 时，它最后的评估值定为时，它最后的评估值定为5以上。以上。D H35 I(5,)对于对于MIN节点节点B，取第一个子节点
15、，取第一个子节点D的评估值的评估值5作为它的上限作为它的上限，最后评估值是否能定为最后评估值是否能定为5，还要看其它子节点的评估值。还要看其它子节点的评估值。B(-,5,5)D H35 I(5,)对于对于MAX节点节点E，取第一个子节点，取第一个子节点J的评估值的评估值6作为它的下限作为它的下限，它表示节点它表示节点E的最后评估的最后评估值一定不会低于值一定不会低于6的。的。B(-,5,5)6?J K E(6,)剪枝剪枝的过程：的过程：对于对于MIN节点节点B，它显然是不可能选择节点，它显然是不可能选择节点E的。因为的。因为E的评估值超过了节点的评估值超过了节点B的上限的上限，这就确定了与这就
16、确定了与K的评估值没有关系，所以的评估值没有关系，所以没有必要去求它的评估值。这种剪枝，是没有必要去求它的评估值。这种剪枝，是由于节点由于节点E的评估值超过了它的双亲节点的评估值超过了它的双亲节点（节点（节点B），所以被称为），所以被称为剪枝剪枝。D H356?I J K EB(5,)(-,5,5)(6,)D H356?I J K EBA(5,)(-,5,5)(6,)对于对于MAX节点节点A，取第一个子节点，取第一个子节点B的评估值的评估值5作为它的下限作为它的下限，最后评估值是否能定为最后评估值是否能定为5，还要看其它子节点的评估值。还要看其它子节点的评估值。(5,)21 L M F对于对于
17、MAX节点节点F，取第一个子节点，取第一个子节点L的评估值的评估值2作为它的下限作为它的下限，当另一个子节点，当另一个子节点M的评估的评估值小于值小于 时，它最后的评估值取时，它最后的评估值取 。(2,)21 L M F C(2,)对于对于MIN节点节点C，取第一个子节点，取第一个子节点F的评估值的评估值2作为它的上限作为它的上限，表示节点表示节点C最后的评估值不最后的评估值不会超过会超过。(-,2,2)剪枝剪枝的过程：的过程：由于由于MAX节点节点A的评估下限值为的评估下限值为5，其子节，其子节点点C的评估值未能超过该下限，因此不可能的评估值未能超过该下限，因此不可能被节点被节点A选中。这说明选中。这说明MAX节点节点G的值已没的值已没有评价的意义了，因此也就没有必要去求有评价的意义了，因此也就没有必要去求节点节点N和和O的评估值了。这种剪枝，由于节的评估值了。这种剪枝，由于节点点C的评估值低于它的双亲节点（节点的评估值低于它的双亲节点（节点A）的的值，被称为值，被称为剪枝剪枝。21?L M N O FG CA(2,)(-,2,2)(5,)结果：结果：MAX节点节点MIN节点节点 D H(5,)356?21?I J K L M N O E FG(6,)(2,)B C(-,5,5)(-,2,2)A(5,)MAX节点节点终端节点终端节点 剪枝剪枝 剪枝剪枝