第5章对抗搜索.ppt
《第5章对抗搜索.ppt》由会员分享,可在线阅读,更多相关《第5章对抗搜索.ppt(58页珍藏版)》请在三一文库上搜索。
1、第5章 对抗搜索,中国科大 计算机学院,第部分 问题求解,本章内容,5.1 博弈 5.2 博弈中的优化决策 5.3 -剪枝 5.4 不完美的实时决策 5.5 随机博弈 5.6 部分可观察的博弈 5.7 博弈程序发展现状 5.8 其他途径,5.1 博弈,概述 Grundy博弈,概述,在博弈问题中比如说象棋搜索是在博弈者双方之间进行的。 任何一方在搜索时,都必须要考虑对方可能要采用的走步。 对于一个优秀的博弈者来说,应考虑的不只是对方一步的走法,而是若干步的走法。 这一过程一般来说是动态进行的。在考虑若干步走法以后,下了一步棋;而在对方走棋之后,还要再次考虑若干步走法,决定下一步的走法,而不是一劳
2、永逸,搜索一次就决定了所有的走法。,概述,本章所讲的博弈:主要指的是类似于象棋这样的游戏问题。 这类问题有以下一些特点: 双人对弈,对垒的双方轮流走步。 信息完备,对垒双方所得到的信息是一样的,不存在一方能看到,而另一方看不到的情况。 零和。即对一方有利的棋,对另一方肯定是不利的,不存在对双方均有利、或均无利的棋。对弈的结果是一方赢,而另一方输,或者双方和棋。,概述,双人完备信息博弈: 指两位选手对垒,轮流走步,这时每一方不仅都知道对方过去已经走过的棋步,而且还能估计出对方未来可能的走步。 对弈的结果是一方赢(另一方则输),或者双方和局。 这类博弈的实例有:一字棋、余一棋、西洋跳棋、国际象棋、
3、中国象棋、围棋等。 机遇性博弈:存在不可预测性的博弈,例如掷币等。 例如:西洋双陆棋。,Grundy博弈,Grundy博弈是一个分钱币的游戏。 有一堆数目为N的钱币,由两位选手轮流进行分堆,要求每个选手每次只把其中某一堆分成数目不等的两小堆。 例如,选手甲把N分成两堆后,轮到选手乙就可以挑其中一堆来分。 如此进行下去,直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。 对于这样的简单博弈问题,可以生成出它的状态空间图。这样就有可能从状态空间图中找出取胜的策略。,Grundy博弈,当初始钱币数为7时的状态空间图,MIN代表对方走 MAX代表我方走,MAX存在完全取胜的策略,Grundy博弈
4、,搜索策略要考虑的问题: 对MIN走步后的每一个MAX节点,必须证明MAX对MIN可能走的每一个棋局对弈后能获胜,即MAX必须考虑应付MIN的所有招法,这是一个与的含意。 因此含有MAX符号的节点可看成与节点。 对MAX走步后的每一个MIN节点,只须证明MAX有一步能走赢就可以,即MAX只要考虑能走出一步棋使MIN无法招架就成。 因此含有MIN符号的节点可看成或节点。 因此,对弈过程的搜索图就呈现出与或图表示的形式。,Grundy博弈,寻找MAX的取胜策略和求与或图的解图相对应。 MAX要取胜,必须对所有与节点取胜,但只需对一个或节点取胜,这就是一个解图。 因此,寻找一种取胜的策略就是搜索一个
5、解图的问题,解图就代表一种完整的博弈策略。 对于Grundy这种较简单的博弈,或者复杂博弈的残局,可以用类似于与或图的搜索技术求出解图,解图代表了从开局到终局任何阶段上的弈法。 显然这对许多博弈问题是不可能实现的。例如,中国象棋,国际象棋和围棋等。,Grundy博弈,对于复杂的博弈问题,因此即使用了强有力的启发式搜索技术,也不可能使分枝压到很少。 因此,这种完全取胜策略(或和局)必须丢弃。 应当把目标确定为寻找一步好棋,等对手回敬后再考虑寻找另一步好棋这种实际可行的实用策略。 这种情况下每一步的结束条件可根据时间限制、存储空间限制或深度限制等因素加以确定。 搜索策略可采用宽度、深度或启发式方法
6、。一个阶段搜索结束后,要从搜索树中提取一个优先考虑的“最好的“走步,这就是实用策略的基本点。,本章内容,5.1 博弈 5.2 博弈中的优化决策 5.3 -剪枝 5.4 不完美的实时决策 5.5 随机博弈 5.6 部分可观察的博弈 5.7 博弈程序发展现状 5.8 其他途径,5.2 博弈中的优化决策,极小极大值法 多人游戏中的最优决策,极小极大搜索过程,人类下棋的方法:实际上采用的是一种试探性的方法。 首先假定走了一步棋,看对方会有那些应法,然后再根据对方的每一种应法,看我方是否有好的回应 这一过程一直进行下去,直到若干步以后,找到了一个满意的走法为止。 初学者可能只能看一、两个回合,而高手则可
7、以看几个,甚至十几个回合。 极小极大搜索方法:模拟的就是人的这样一种思维过程。,极小极大搜索过程,极小极大搜索策略是考虑双方对弈若干步之后,从可能的走步中选一步相对好棋的着法来走,即在有限的搜索深度范围内进行求解。 定义一个静态估计函数f,以便对棋局的势态(节点)作出优劣估值。 这个函数可根据势态优劣特征来定义(主要用于对端节点的“价值”进行度量)。 一般规定:有利于MAX的势态,f(p)取正值;有利于MIN的势态,f(p)取负值;势均力敌的势态,f(p)取0值。 若f(p),则表示MAX赢,若f(p),则表示MIN赢。,极小极大搜索过程,注意:不管设定的搜索深度是多少层,经过一次搜索以后,只
8、决定了我方一步棋的走法。 等到对方回应一步棋之后,需要在新的棋局下重新进行搜索,来决定下一步棋如何走。 极小极大过程是一种假定对手每次回应都正确的情况下,如何从中找出对我方最有利的走步的搜索方法。,极小极大搜索过程,规定:顶节点深度d0,MAX代表程序方,MIN代表对手方。MAX先走。 例:一个考虑2步棋的例子。,极小极大搜索过程,规定:顶节点深度d0,MAX代表程序方,MIN代表对手方。MAX先走。 例:一个考虑2步棋的例子。,端节点给出的数字是用静态估计函数f(p)计算得到。,过程MINIMAX, T:(s,MAX),OPEN:(s),CLOSED:( );开始时树由初始节点构成,OPEN
9、表只含有s。 LOOP1: IF OPEN( )THEN GO LOOP2; n:FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED); IF n可直接判定为赢、输或平局 THEN f(n):0,GO LOOP1 ELSE EXPAND(n)ni,ADD(ni,T) IF d(ni)k THEN ADD(ni,OPEN),GO LOOP1 ELSE 计算f(ni ),GO LOOP1;ni达到深度k,计算各端节点f值。 LOOP2:IF CLOSEDNIL THEN GO LOOP3 ELSE np:FIRST(CLOSED); IF(npMAX)(f(nciMIN
10、)有值) THEN f( np ):maxf(nci),REMOVE(np,CLOSED);若MAX所有子节点均有值,则该MAX取其极大值。 IF ( np MIN)(f( nci MAX)有值) THEN f( np ):minf(nci),REMOVE(np ,CLOSED);若MIN所有子节点均有值,则该MIN取其极小值。 GO LOOP2; LOOP3:IF f(s)NIL THEN EXIT( ENDM(Move,T) );s有值,则结束或标记走步。,过程MINIMAX,该算法分两个阶段进行: 第一阶段:用宽度优先法生成规定深度的全部博弈树,然后对其所有端节点计算其静态估计函数值。
11、第二阶段:从底向上逐级求非端节点的倒推估计值,直到求出初始节点s的倒推值f(s)为止,此时,等对手响应走步后,再以当前的状态作为起始状态s,重复调用该过程。,例:33棋盘的一字棋,33棋盘的一字棋:九宫格棋盘上,两位选手轮流在棋盘上摆各自的棋子(每次一枚),谁先取得三子一线的结果就取胜。 假设: 程序方MAX的棋子用()表示; 对手MIN的棋子用()表示; MAX先走。,例:33棋盘的一字棋,静态估计函数f(p)规定如下: 若p是MAX获胜的格局,则f(p); 若p是MIN获胜的格局,则f(p); 若p对任何一方来说都不是获胜的格局,则f(p)(所有空格都放上MAX的棋子之后,MAX的三子成线
12、(行、列、对角)的总数(所有空格都放上MIN的棋子之后,MIN的三子成线(行、列、对角)的总数)。,例、当p的格局如下时,则可得f(p)642。,在搜索过程中,具有对称性的棋局认为是同一棋局,可以大大减少搜索空间。,例:33棋盘的一字棋,例:33棋盘的一字棋,假定考虑走两步的搜索过程,利用棋盘对称性的条件,则第一次调用算法产生的搜索树为:,例:33棋盘的一字棋,假设MAX走完第一步后,MAX的对手是在之上的格子下棋子,这时MAX在新格局下调用算法,第二次产生的搜索树为:,例:33棋盘的一字棋,类似地,第三次的搜索树为:,至此MAX走完最好的走步后,不论MIN怎么走,都无法挽回败局,因此只好认输
13、了。,博弈中的优化决策,极小极大值法 多人游戏中的最优决策,多人游戏中的最优决策,许多流行的游戏允许多于两个的参加者。 如何把极小极大思想推广到多人游戏中? 在两人的零和游戏中,由于效用值正好相反,所以二维向量可以简化为一个单一值。 每个节点上的单一评估值要替换成一个向量。 例、一个有三个人A, B和C的游戏中,每个节点都与一个向量相关联。 对于终止状态,该向量给出了从每个人的角度出发得到的状态效用值。,多人游戏中的最优决策,一般来讲,节点n的回传值是该游戏者在节点n选择的效用值最高的后继者的效用值向量。,多人游戏中的最优决策,多人游戏通常会涉及在游戏者之间出现正式或者非正式联盟的情况。 随着
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对抗 搜索
链接地址:https://www.31doc.com/p-2533076.html