资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.5,博弈树的搜索,1.博弈树,博弈的特性：,两个棋手交替地走棋,；,比赛的最终结果，是赢、输和平局中的一种,；,可用图搜索技术进行，但效率很低；,博弈的过程，是寻找置对手于必败态的过程；,双方都无法干预对方的选择。,三子残局举例：,设有一个摆放三个子的象棋残局a)，如下图所示，和,在结束前有三步棋可以走，而且设走第一步的是。这时存在着三个空格A，B，C，应该把棋子放到哪一格内是需要进行判断的难点问题。,A,B,C,a),如果选择在空格A上，则棋盘局面变成b)，如右图所示。,A,B,C,B,C,a),b),接着轮到,走棋。这时可供选择的分枝是剩余的B和C。如果这时,选择B，则变成平局；如果选择C，则,能赢。在这种情况下，,当然会选择放在C，因此局面b）的预估值是输的。,A,B,C,B,C,C,B,平局,赢,a),b),c),d),输,另一种情况，是选择B时，得到局面e）。接着,的可选分枝剩下A和C。当,选择A时，会出现两个并排的局面，,可能会输；当,选择C时，能够确保,的赢局。因此，这时,当然也会选择在C的位置放子，从而局面e）的预估值为输。,A,B,C,A,C,C,A,可能输,赢,a),e),f),g),输,最后一种情况，是选择C时，得到局面h）。接着,的可选分枝剩下A和B。当,选择A时，也会出现两个并排的局面，,可能会输；当,选择B时，却出现了平局的局面。因此，这时,会选择放在B的位置，从而局面h）的预估值为平局。,A,B,C,A,B,B,A,可能输,平局,a),h),i),j),平局,综合上述分析可以看出，对于局面a）中的来说，最好的选择，是将放在C的位置上，这时可以导致平局局面。,A,B,C,B,C,C,B,b),c),d),a）,A,C,C,A,e),f),g),A,B,B,A,h),i),j),2.博弈过程的最小最大化,对各个局面进行评估,评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋选择。,评估的方法：因问题而异。例如，在摆三子的情况下，赢的评估值设为,+,，输的评估值设为,-,，平局的评估值设为,0,，此外根据与赢局相关的棋子数目，可以设为,1,，,2,。,评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。,MAX节点,命名博弈的双方，一方为“,正方,”。对每个状态的评估都是对应于该方进行的。例如，赢2个，输1个等，都是指,正方,的。正方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为“,MAX,”节点；,MIN节点,另一方为“,反方,”，对每个状态的评估都是对应于对手进行的。例如，赢2个，输1个，其实是指自己输2个，赢1个的。,反方,每走一步，都在选择使对手输得更多的节点，因此这类节点称为“,MIN,”节点。,博弈树的最小最大化,由于,正方,和,反方,是交替走步的，因此,MAX,节点和,MIN,节点会交替出现，从而实现博弈树的最小最大化。,举例：,h,e,b,a,c,f,d,g,i,j,0,-,2,-,2,0,-,-,0,0,MIN节点,MAX节点,终端节点,极大,极小,法,的引入：,如例题中所示，设执的这一方是,正方,，它从所有子节点中，选取具有最大评估值的节点，所以称为,MAX,节点。,另一方执,的是,反方,，它的每一个节点都是从其所有子节点中，选取具有最小评估值的节点，所以称为,MIN,节点。,反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为,极大,极小,法,。,3.,-,剪枝法,-剪枝法的,引入：,在极大极小法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的,-,剪枝法。,MAX,节点的评估下限值,作为,正方,出现的,MAX,节点，取它的第一个,MIN,子节点的评估值,。当有其它子节点的评估值超过,，则该,MAX,节点会取新值作为自己的评估值；如果没有，则该,MAX,节点的评估值就是,。,总之，该,MAX,节点的评估值不会低于,，这个,就称为该,MAX,节点的评估下限值。,例如：,对于,MAX,节点,a,，,取它的第一个,MIN,子节点,b,的评估值,-,作为a的评估下限值,，即,=,-,。它表示节点a的最后评估值不会低于该值。,h,e,b,a,-,-,0,0,MIN节点,MAX节点,又例如：,对于,MAX,节点,a,，,取它的第一个,MIN,子节点,b,的评估值,4,作为a的评估下限值,，即,=,4,。它表示节点a的最后评估值不会低于该值。,h,e,b,a,4,1,0,4,MIN节点,MAX节点,MIN,节点的评估上限值,作为,反方,出现的,MIN,节点，取它的第一个,MAX,子节点的评估值,。当有其它子节点的评估值低于,，则该,MIN,节点会取新值作为自己的评估值；如果没有，则该,MIN,节点的评估值就是,。,总之，该,MIN,节点的评估值不会高过,，这个,就称为该,MIN,节点的评估上限值。,例如：,对于,MIN,节点,b,，取它的第一个子节点的评估值0作为,b,的评估上限值,，即,=0。它表示节点,b,的最后评估值不会超过该值。,b,c,d,0,-,-,MIN节点,终端节点,又例如：,对于,MIN,节点,h,，取它的第一个子节点的评估值0作为,b,的评估上限值,，即,=0。它表示节点,b,的最后评估值不会超过该值。,h,i,j,0,2,0,MIN节点,终端节点,剪枝法：,设,MAX,节点的下限为,，则其,所有的,MIN,子节点中，其评估值,小于等于,的，其下部分的搜索都可以停止了，即对这部分节点进行了,剪枝。,A,B,C,D,MAX节点,(,+),MIN节点,剪枝,剪枝法：,设,MIN,节点的上限为,，则其,所有的,MAX,子节点中，其评估值,大于等于,的，其下部分的搜索都可以停止了，即对这部分节点进行了,剪枝。,B,A,MAX节点,(-,),MIN节点,剪枝,C,B,举例：,MAX节点,MIN节点,D,H,3,5,6,?,2,1,?,?,I,J,K,L,M,N,O,E,F,G,B,C,A,MAX节点,终端节点,D,H,3,5,I,(5,),对于,MAX,节点,D,，取第一个子节点H的评估值作为它的下限,，当另一个子节点I的评估值超过,时，它最后的评估值定为5以上。,D,H,3,5,I,(5,),对于,MIN,节点,B,，取第一个子节点,D,的评估值5作为它的上限,，,最后评估值是否能定为5，还要看其它子节点的评估值。,B,(-,5,),D,H,3,5,I,(5,),对于,MAX,节点,E,，取第一个子节点J的评估值6作为它的下限,，,它表示节点,E,的最后评估值一定不会低于,6,的。,B,(-,5,),6,?,J,K,E,(6,),剪枝,的过程：,对于,MIN,节点,B,，它显然是不可能选择节点,E,的。因为,E,的评估值超过了节点,B,的上限,，,这就确定了与K的评估值没有关系，所以没有必要去求它的评估值。这种剪枝，是由于节点,E,的评估值超过了它的双亲节点（节点,B,），所以被称为,剪枝,。,D,H,3,5,6,?,I,J,K,E,B,(5,),(-,5,),(6,),D,H,3,5,6,?,I,J,K,E,B,A,(5,),(-,5,),(6,),对于,MAX,节点,A,，取第一个子节点,B,的评估值,5,作为它的下限,，,最后评估值是否能定为,5,，还要看其它子节点的评估值。,(5,),2,1,L,M,F,对于,MAX,节点,F,，取第一个子节点L的评估值2作为它的下限,，当另一个子节点M的评估值小于,时，它最后的评估值取,。,(2,),2,1,L,M,F,C,(2,),对于,MIN,节点,C,，取第一个子节点,F,的评估值,2,作为它的上限,，,表示节点,C,最后的评估值不会超过,。,(-,2,),剪枝,的过程：,由于,MAX,节点,A,的评估下限值为,5,，其子节点,C,的评估值未能超过该下限，因此不可能被节点,A,选中。这说明,MAX,节点,G,的值已没有评价的意义了，因此也就没有必要去求节点N和O的评估值了。这种剪枝，由于节点,C,的评估值低于它的双亲节点（节点,A,）的,值，被称为,剪枝,。,2,1,?,?,L,M,N,O,F,G,C,A,(2,),(-,2,),(5,),结果：,MAX节点,MIN节点,D,H,(5,),3,5,6,?,2,1,?,?,I,J,K,L,M,N,O,E,F,G,(6,),(2,),B,C,(-,5,),(-,2,),A,(5,),MAX节点,终端节点,剪枝,剪枝,
展开阅读全文