资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,人 工 智 能,Artificial Intelligence(AI),2026/11/19,2.4,博弈问题的搜索技术,2.4.1,博弈问题的表达,2.4.2,极大极小搜索过程,2.4.3,-,剪枝法,2026/11/19,2.4.1,博弈问题的表达,博弈,是一类具有竞争性的智能活动,双人博弈,:即两位选手对垒,轮流依次走步,其中任何一方都完全知道对方过去已经走过的棋步和今后可能的走步,其结果是一方赢,(,而另一方则输,),,或双方和局,2026/11/19,博弈的例子,:,一字棋,跳棋,中国象棋,围棋,五子棋,2026/11/19,双方的智能活动,任何一方都不能单独控制博弈过程,而是由双方轮流实施其控制对策的过程,博弈的特点,:,2026/11/19,如何根据当前的棋局,选择对自己最有利的一步棋?!,人工智能中研究的博弈问题,:,2026/11/19,用博弈树来表示,它是一种特殊的与或图。节点代表博弈的格局(即棋局),相当于状态空间中的状态,反映了博弈的信息。,与节点、或节点隔层交替出现,博弈问题的表示,:,2026/11/19,假设博弈双方为:,MAX,和,MIN,在博弈过程中,规则是双方轮流走步。在博弈树中,相当于博弈双方轮流扩展其所属节点,为什么,与节点,、,或节点,隔层交替出现,?,2026/11/19,从,MAX,方的角度来看,:,所有,MIN,方节点都是,与节点,理由,:,因为,MIN,方必定选择最,不利于,MAX,方的方式来扩展节点,只要,MIN,方节点的子节点中有一个对,MAX,方不利,则该节点就对,MAX,方不利,故为“,与节点,”,MIN,好招,2026/11/19,从,MAX,方的角度来看,:,所有属于,MAX,方的节点都是“,或节点,”,理由,:,因为扩展,MAX,方节点时,,MAX,方可选择扩展最有利于自己的节点,只要可扩展的子节点中有一个对已有利,,则该节点就对已有利,MAX,好招,2026/11/19,总之,从,MAX,方来说,与节点、或节点交替出现;反之,从,MIN,方的角度来看,情况正好相反,2026/11/19,在博弈树中,先行一方的初始状态对应着树的,根节点,,而任何一方获胜的最终格局为目标状态,对应于树的,终叶节点,(可解节点或本原问题),但是,从,MAX,的角度出发,所有使,MAX,获胜的状态格局都是本原问题,是可解节点,而使,MIN,获胜的状态格局是不可解节点,2026/11/19,例,Grundy,博弈:,分配物品的问题,如果有一堆数目为,N,的钱币,由两位选手轮流进行分配,要求每个选手每次把其中某一堆分成数目,不等,的两小堆,直至有一选手不能将钱币分成不等的两堆为止,则判定这位选手为输家,2026/11/19,用数字序列加上一个说明来表示一个状态:,(,3,2,1,1,MAX,),数字序列,:表示不同堆中钱币的个数,说明,:,表示下一步由谁来分,即取,MAX,或,MIN,2026/11/19,现在取,N,7,的简单情况,,并由,MIN,先分,注,:如果,MAX,走红箭头的分法,必定获胜,所有可能的分法,(7,MIN),(6,1,MAX),(5,2,MAX),(4,3,MAX),(5,1,1,MIN),(4,2,1,MIN),(3,2,2,MIN),(3,3,1,MIN),(4,1,1,1,MAX),(3,2,1,1,MAX),(2,2,2,1,MAX),(2,2,1,1,1,MIN),(3,1,1,1,1,MIN),(2,1,1,1,1,1,MAX),2026/11/19,对于比较复杂的博弈问题,只能模拟人的思维“,向前看几步,”,然后作出决策,选择最有利自己的一步。即,只能给出几层走法,然后按照一定的估算办法,,决定走一好招,2026/11/19,2.4.2,极大极小过程,对于复杂的博弈问题,要规定搜索深度与时间,以便于博弈搜索能顺利进行,假设由,MAX,来选择走一步棋,问题是:,MAX,如何来选择一步好棋,?,2026/11/19,对于每一格局(棋局)给出(定义或者倒推)一个静态估价函数值。值越大对,MAX,越有利,反之越不利,极大极小过程的基本思路,:,2026/11/19,对于给定的格局,,MAX,给出可能的走法,然后,MIN,对应地给出相应的走法,这样重复若干次,得到一组端节点(必须由,MIN,走后得到的,由,MAX,下的棋局)。这一过程相当于节点扩展,注,:博弈树深度或层数一定是偶数,2026/11/19,对于每一个端节点,计算出它们的静态估价函数,然后自下而上地逐层计算倒推值,直到,MAX,开始的格局。在,MIN,下的格局中取估值的最小值,在,MAX,下格局中取估值的最大值,取估值最大的格局作为,MAX,要走的一招棋,2026/11/19,例,:,向前看一步的两层博弈树,2026/11/19,定义静态函数,e(P),的一般原则,:,2026/11/19,OPEN,:,存放待扩展的节点,此时为队列,即以宽度优先的策略扩展节点,CLOSED,:,存放已扩展的节点,此时为堆栈,即后扩展的节点先计算静态估价函数值,符号,:,2026/11/19,1,、将初始节点,S,放入,OPEN,表中,开始时搜索树,T,由初始节点,S,构成,2,、若,OPEN,表为空,则转5,3,、将,OPEN,表中第一个节点,n,移出放入,CLOSED,表的前端,极大极小搜索过程,为,:,2026/11/19,4,、若,n,可直接判定为赢、输、或平局,则令对应的,e,(,n,)=,-,或 0,并转2;否则扩展,n,,,产生,n,的后继节点集,n,i,,,将,n,i,放入搜索树,T,中,2026/11/19,此时,若搜索深度,d,n,i,小于预先设定的深度,k,,,则将,n,i,放入,OPEN,表的末端,转2;否则,,n,i,达到深度,k,,,计算,e,(,n,i,),,并转2,(续),2026/11/19,5,、若,CLOSED,表为空,则转8;否则取出,CLOSED,表中的第一个节点,记为,n,p,Open,为空,即已经扩展完节点,步,2,2026/11/19,6,、,若,n,p,属于,MAX,层,且对于它的属于,MIN,层的子节点,n,ci,的,e,(,n,ci,),有值,则:,e,(,n,p,)=max,n,ci,某一个节点属于,MAX,的含义是该节点等待,MAX,来扩展,2026/11/19,(续),若,n,p,属于,MIN,层,且对于它的属于,MAX,层的子节点,n,ci,的,e,(,n,ci,),有值,则:,e,(,n,p,)=min,n,ci,2026/11/19,7,、转5,8,、根据,e,(S),的值,标记走步或者结束(-,或 0),2026/11/19,第一阶段,为1、2、3、4步,用宽度优先算法生成规定深度,k,的全部博弈树,然后对其所有端节点计算,e(P,),第二阶段,为5、6、7、8步,是自下而上逐级求节点的倒推估价值,直至求出初始节点的,e(S,),为止,再由,e(S,),选得相对较好的走法,过程结束,算法分成两个阶段,:,2026/11/19,等对手走出相应的棋,再以当前的格局作为初始节点,重复此过程,选择对自己有利的走法,2026/11/19,2026/11/19,例,:,一字棋的极大极小搜索过程,约定,:,每一方只向前看一步,(扩展出二层),记,MAX,的棋子为“,”,,MIN,的棋子为“,O,”,规定,MAX,先手,2026/11/19,若格局,P,对任何一方都不能获胜,则,e(P)=(,所有空格上都放上,MAX,的棋子后,,MAX,的三个棋子所组成的行、列及对角线的总数,)-(,所有空格上都放上,MIN,的棋子后,,MIN,的三个棋子所组成的行、列及对角线的总数,),静态估计函数,e(P),定义为,:,2026/11/19,若,P,是,MAX,获胜,则,e(P)=+,若,P,是,MIN,获胜,则,e(P)=,2026/11/19,例:,计算下列棋局的静态估价函数值,e(P)=6-4=2,棋局,O,O,O,O,O,O,O,O,O,O,行=2,列=2,对角=2,行=2,列=2,对角=0,2026/11/19,利用棋盘的对称性,有些棋局是等价的,O,O,O,O,2026/11/19,O,O,O,O,O,O,O,O,O,O,O,O,1,0,1,0,-1,-1,0,-1,0,-2,1,2,1,-2,-1,1,MAX,MIN,MAX,MAX,的走步,2026/11/19,第二步,O,X,X,O,X,O,X,X,O,X,X,O,X,X,X,O,O,X,X,O,O,X,X,O,X,O,X,O,X,O,X,O,X,O,2,1,3,2,1,1,O,O,X,X,O,X,X,O,O,X,X,O,O,X,X,O,O,X,X,O,1,0,2,0,1,O,O,X,X,1,0,O,O,X,X,O,O,X,X,O,O,X,X,O,X,O,X,O,X,X,O,O,X,X,O,2,2,3,1,2,2,1,O,O,X,X,O,X,O,X,O,O,X,X,1,1,0,0,1,X,O,X,O,3,MIN,2026/11/19,第三步,O,O,X,X,X,O,O,X,X,O,O,X,X,X,O,O,X,X,X,O,O,X,X,X,O,O,X,X,X,X,O,O,O,X,X,X,O,O,X,X,O,X,O,O,X,X,O,X,O,O,X,O,X,O,O,O,X,X,X,O,O,O,X,X,X,O,O,X,X,X,O,O,O,X,X,X,O,O,O,O,X,X,X,O,O,X,X,X,O,O,O,X,X,X,O,O,O,X,X,O,X,O,O,O,X,X,X,O,O,O,X,X,X,O,O,X,X,O,X,O,O,X,O,X,X,O,O,O,X,X,X,O,O,O,X,X,X,O,O,X,X,X,O,O,O,X,O,X,X,-,0,2,1,-,-,-,1,2,2,1,0,1,-,-,-,1,1,1,1,1,1,2,-,1,1,2026/11/19,O,O,MAX,MIN,2026/11/19,MAX,MIN,O,O,2026/11/19,上机实验作业,:,用,C/C+,语言编写“,一字棋,”的游戏程序,基本要求:,必须实现极大极小过程,能够进行“人,-,机”对垒、“机,-,机”对垒,简单地显示对垒过程,实验形式:两人或者一人一组,2026/11/19,实验报告格式,:,“一字棋”游戏的计算机程序,学号:姓名:专业:,摘要,1,一字棋游戏的文字描述,2,一字棋对垒过程的计算机描述和实现,3,实例(人机对垒的过程、机机对垒的过程),4,体会,5,参考文献,附录:程序使用的简单说明,2026/11/19,提交的材料,:,1,、文字报告;,2,、程序原代码,提交的方式,:以学号姓名为压缩文件名(,发送到,wgqu,提交的时间,:,11,月,21,日,口头报告,:介绍报告的主要内容和演示程序,特别是自己觉得有特色的地方。初步时间是,12,月初。,2026/11/19,2.4.3,-,剪枝法,极大极小搜索过程由两个完全分离的两个步骤组成:,1,、,用宽度优先算法生成一棵博弈搜索树。,2,、,估计值的倒推计算。,缺点,:这种分离使得搜索的效率比较低。,2026/11/19,改进,:在博弈树生成过程中同时计算端节点的估计值及倒推值,以减少搜索的次数,这就是,-,过程的思想,也称为,-,剪枝法。,其中,,表示,MAX,节点的估值的,下界,(已经搜索到的,MAX,节点的,最小值,),。,表示,MIN,节点的估值的,上界,(已经搜索到的,MIN,节点,的,最大值,),。,2026/11/19,极大极小过程,:,采用宽度优先的方式来扩展节点,-,剪枝法,:,改用,深度优先,的策略来扩展节,2026/11/19,一字棋的左边部分,MAX,MIN,现扩展,B,得到,C,,其值为,-1,,则,B,的倒推值小于等于,-1,,即,-1,。再扩展,B,的子节点,,B,的值也不会大于,-1,。结果是,B,比,A,差,不用再扩展,B,的其他子节点了。此处,,MIN,节点,B,的,值小于等于其先辈,MAX,节点,S,的,值,,,停止扩展。,C,扩展,S,生成,A,B,.,。扩展,A,生成,5,个子节点,倒推得到,A,的值为,-1,。可以得到,S,的值大于等于,-1,,即,-1,。,2026/11/19,更一般的情况,MIN,节点的,不大于,其先辈,MAX,节点的,值,则可以中止扩展,MAX,节点的,不小于,其先辈,MIN,节点的,值,则可以中止扩展,2026/11/19,一般而言,当某一个节点的后继节点倒推值已经给定时,则倒推值的上下界可以被修正。,注意,:,MAX,节点的,值非减,,MIN,节点的,值非增。,2026/11/19,、,值的计算方法,:,第一,、一个,MAX,节点的,值等于其后继节点当前,最大,的最终倒推值。,第二,、一个,MIN,节点的,值等于其后继节点当前,最小,的最终倒推值。,2026/11/19,-,剪枝的规则为,:,1,、若任何,MIN,结点的,值,小于或等于,任何它的先辈,MAX,结点的,值,则可,中止,该,MIN,结点以下的搜索,此时这个,MIN,结点的最终倒推值就是已得到的,值。,该值与真正的极大极小的搜索结果的倒推值可能不相同,但是对起始结点而言,倒推值是相同的,使用它选择的走步也是相同的。,2026/11/19,2,、若任何,MAX,结点的,值,大于,或,等于,它的,MIN,先辈结点的,值,则可以中止该,MAX,结点以下的搜索,此时这个,MAX,结点处的倒推值就是已得到的,值。,2026/11/19,当搜索用,规则1,终止时,我们称进行了,剪枝,,而当搜索用规则2终止时,我们称进行了,剪枝,。,在搜索过程中,保存,和,值,如果出现满足使用两条规则的条件,我们就中止某一些搜索,这一过程称为,-(,剪枝)过程,。,2026/11/19,-,过程的主要思想(步骤):,1,、采用有界的深度优先搜索算法。,2,、立即计算端节点的估值。,3,、,剪枝,4,、,剪枝,5,、,当初始节点的所有后继节点的最终倒推值全部给出后,搜索过程结束。,2026/11/19,例,:,图中矩形表示,MAX,的节点,圆圈表示,MIN,的节点,多个画线表示被修剪的枝。,原来有,38,个节点,现在只有,22,个节点必须估值。,每一次扩展一个节点。,2026/11/19,MAX,MAX,MAX,MIN,MIN,2026/11/19,若以最理想的情况进行搜索,即对,MIN,节点先扩展最低估值的节点,,MAX,能先扩展最高估值的节点,则搜索深度为,D,,,每一个节点都有,B,个后继节点。,对于极大极小过程,搜索端节点的数目:,对于,-,过程,搜索端节点数目为:,若,B,2,,,D,4,,则极大极小过程的端节点为,16,,,-,过程的节点为,7,。,2026/11/19,
展开阅读全文