《搜索(博弈树的启发式搜索).ppt》由会员分享，可在线阅读，更多相关《搜索(博弈树的启发式搜索).ppt（35页珍藏版）》请在三一办公上搜索。
1、搜索策略,博弈树的启发式搜索,2,博弈问题,如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的“二人零和、全信息、非偶然”博弈，其特征如下：双人对弈，对垒的双方轮流走步。零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的碰运气因素。即双方都是很理智地决定自己的行动。,博弈是一类富有智能行为的
2、竞争活动，如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈，就是两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈，是指存在不可预测性的博弈，例如掷币等。对机遇性博弈，由于不具备完备信息，因此我们不作讨论。,4,5,这里我们主要讨论双人完备信息博弈问题。在双人完备信息博弈过程中，双方都希望自己能够获胜。因此，当任何一方走步时，都是选择对自己最为有利，而对另一方最为不利的行动方案。假设博弈的一方为MAX，另一方为MIN。在博弈过程的每一步
3、，可供MAX和MIN选择的行动方案都可能有多种。从MAX方的观点看，可供自己选择的那些行动方案之间是“或”的关系，原因是主动权掌握在MAX手里，选择哪个方案完全是由自己决定的；而对那些可供MIN选择的行动方案之间则是“与”的关系，原因是主动权掌握在MIN的手里，任何一个方案都有可能被MIN选中，MAX必须防止那种对自己最为不利的情况的发生。,6,若把双人完备信息博弈过程用图表示出来，就可得到一棵与/或树，这种与/或树被称为博弈树。在博弈树中，那些下一步该MAX走步的节点称为MAX节点，而下一步该MIN走步的节点称为MIN节点。博弈树具有如下特点：（l）博弈的初始状态是初始节点；（2）博弈树中的
4、“或”节点和“与”节点是逐层交替出现的；（3）整个博弈过程始终站在某一方的立场上，所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。例如，站在MAX方，所有能使MAX方获胜的节点都是可解节点，所有能使MIN方获胜的节点都是不可解节点。,一.博弈树概述,博弈问题空间模型化,只考虑两个游戏者:MAX和MIN,两个人轮流出招,直到游戏结束.四元组：（初始状态，操作集合，终止测试（非目标测试），判定函数）初始状态：包括棋局的局面和确定该哪个游戏者出招后继函数：返回(move,state)对的一个列表,其中每一对表示一个合法 的着数和其结果状态终止测试：判
5、断游戏是否结束,游戏结束的状态称为终止状态判定函数：又称为目标函数或者收益函数,对终止状态给出一个数值.（比如：可以-1表示输，0表示和局，1表示赢）,博弈的初始格局是初始节点,在博弈树中，或节点和与节点是逐层交替出现的。,如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是“或”关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。,当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是与关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能
6、被MIN方选中，MAX方必须应付每一种情况的发生。,9,对简单的博弈问题，可以生成整个博弈树，找到必胜的策略。但对于复杂的博弈，如国际象棋，大约有10120个节点，可见要生成整个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，由于该博弈树的叶节点一般不是哪一方的获胜节点，因此，需利用估价函数f(n)对叶节点进行静态评估，对MAX有利的节点其估价函数取正值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于0的值。,二.极大极小过程,为了计算非叶节点的值，必须从叶节点向上倒推。对于MAX节点，由于 MAX方总是选择估值最大的走步，因此，M
7、AX节点的倒推值应该取其后继节点估值的最大值。对于MIN节点，由于MIN方总是选择使估值最小的走步，因此MIN节点的倒推值应取其后继节点估值的最小值。这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。由于我们是站在MAX的立场上，因此应选择具有最大倒推值的走步。这一过程称为极大极小过程。下面给出一个极大极小过程的例子。,极小极大法,基本思想:首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利;当评价函数小于0时，表示棋局对我方不利，对对方有利;而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，
8、表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜;假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。,人下棋的思考方式,人下棋实际上采用一种试探性的方法:假定走了一步棋,看对方会有哪些应法;再根据对方的每一种应法,看我方是否有好的回应;这一过程一直进行下去,直到若干步后,找到一个满意的走法为止.极大极小搜索方法模拟的就是人的这样一种思维过程.,极大极小搜索方法是一种在有限搜索深度范围进行求解的方法.,定义一个静态估计函数f,以便对棋局的叶子节点作出优劣估值,2.非叶子节点的估值由倒推取值的方法取得,a.MAX走步必然选择
9、对自己最有利的一步,如A节点的估计值是3,b.MIN走步必然选择对自己最有利的一步,如D节点的估计值是2,1.首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。,获得根节点取值的那一分枝，即为所选择的最佳走步,节点A,轮到MAX下棋.,算法框架整个算法分为四个步骤：1、以当前状态为根结点产生一个博弈树。2、对博弈树的每一个叶结点，利用判定函数给出它的判定值。3、从叶结点开始，一层一层地回溯。在回溯过程中，利用最大/最小判定为每一个结点给出其判定值。4、MAX方选择下一层中判定值最大的结点，作为它的下一状态。Function Minimax-Decision(st
10、ate)return an action vMax-Value(state)return action in successors(state)with value vFunction Max-Value(state)return a utility value if Terminal-Test(state)then return Utility(state)v-for s in successors(state)do v Max(v,Min_Value(s)Return vFunction Min-Value(state)return an utility value if Terminal
11、-Test(state)then return Utility(state)v+for s in successors(state)do v Min(v,Max_Value(s)Return v,14,例：一字棋游戏。设有一个三行三列的棋盘，如下图所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。设MAX方的棋子用标记，MIN方的棋子用 标记，并规定MAX方先走步。解：为了对叶节点进行静态估值，规定估价函数e（P）如下：若 P是 MAX的必胜局，则 e（P）=+；若 P是 MIN 的必胜局，则 e（P）=-；,若P对MAX、MIN都是胜负未定局，则
12、 e（P）=e（+P）e（-P）其中，e（+P）表示棋局 P上有可能使 成三子一线的数目；e（-P）表示棋局 P上有可能使 成三子一线的数目。,二.极大极小过程,15,例如，对图1所示的棋局有估价函数值 e（P）6-42,在搜索过程中，具有对称性的棋局认为是同一棋局。例如，图2所示的棋局可以认为是同一个棋局，这样可以大大减少搜索空间。图3给出了第一着走棋以后生成的博弈树。图中叶节点下面的数字是该节点的静态估值，非叶节点旁边的数字是计算出的倒推值。从图中可以看出，对MAX来说S2是一着最好的走棋，它具有较大的倒推值。,16,图3 一子棋的极大极小搜索,S0,S1,S2,S3,S4,S5,-1,1
13、,-2,6-5=1,5-5=0,6-5=1,5-5=0,4-5=-1,5-6=-1,5-5=0,6-6=0,5-6=-1,4-6=-2,5-4=1,6-4=2,一字棋游戏极小极大树,定义一个静态估计函数f,以便对棋局的叶子节点作出优劣估值,2.非叶子节点的估值由倒推取值的方法取得,a.MAX走步必然选择对自己最有利的一步,如节点的估计值是1,b.MIN走步必然选择对自己最有利的一步,如节点的估计值是-2,1.首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。,获得根节点取值的那一分枝，即为所选择的最佳走步,MAX在初始节点时应该怎么走,一字棋游戏极小极大树,MA
14、X在第二步应该怎么走,-剪枝,在极小极大搜索方法中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加呈指数增长。这极大地限制了极小极大搜索方法的使用。-剪枝的基本思想:边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。,A,-,+,-,3,3,12,8,3,+,-,+2,2,3,3,-14,14,3,14,5,2,2,2,3,3,-剪枝,=到目前为止我们在路径上的任意选择点发现MAX的最佳(即极大值)选择=到目前为止我们在路径上的任意选择点发现MIN的最
15、佳(即极小值)选择,算法框架(1)对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响)。这一过程称为剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响)。这一过程称为剪枝。算法特点：(1)MAX节点(包括起始节点)的值永不减少；(2)MIN节点(包括
16、起始节点)的值永不增加。和值的计算方法：(1)一个MAX节点的值等于其后继节点当前最大的最终倒推值。(2)一个MIN节点的值等于其后继节点当前最小的最终倒推值。,一字棋第一阶段-剪枝方法,第一个被访问的叶子节点,访问完节点1,初始节点s的取值范围是-1,+,开始访问完节点7,访问完节点8,节点7的取值范围是-,-1 节点7的父节点是s 此时,节点7不必在分裂下去了,即剪掉该枝,深度搜索,例,若以最理想的情况进行搜索，即对MIN节点先扩展最低估值的节点（若从左向右顺序进行，则设节点估计值从左向右递增排序），MAX先扩展最高估值的节点（设估计值从左向右递减排序）。则当搜索树深度为D，分枝因子为B时
17、，若不使用-剪枝技术，搜索树的端节点数ND=BD；若使用-剪枝技术可以证明理想条件下生成的端节点数最少，有 ND2BD/2-1（D为偶数）NDB(D+1)/2+B(D-1)/2-1（D为奇数）比较后得出最佳-搜索技术所生成深度为D处的端节点数约等于不用-搜索技术所生成深度为D2处的端节点数。这就是说，在一般条件下使用-搜索技术，在同样的资源限制下，可以向前考虑更多的走步数，这样选取当前的最好优先走步，将带来更大的取胜优势。,剪枝效率,评价函数,搜索算法几乎不可能搜索全部空间直到终止状态,而应该可能早的截断搜索,把启发式评价函数用于搜索中的状态,有效地把非终节点变成了叶子终止节点.评价函数与真正
18、的效用函数一致时间效率问题对于非终止状态,评价函数与取胜机会密切相关大多数的评价函数的工作方式是:计算状态的不同特征值.这些特征在一起定义了状态的各种类别或等价类:每类中的状态对所有特征都有相同的值.一般来说,任何给定的类都会包括某些致胜的状态,某些导致和局的状态以及会导致失败的状态.评价函数可以返回一个反映每个结果中状态所占比例的单一值.一个线形的加权函数例子:EVAL(s)=w1f1(s)+wnfn(s)(合理吗?),关于截断搜索,截断搜索在某深度终止搜索,并用评价函数对非终止结点进行估值,并以此作为对未来棋局的判断.当截断的位置刚好处于局面大幅波动的地方,该判断会产生重大的偏差.静止的棋
19、局 显然,评价函数只适用于那些静止的棋局-也就是评估的价值在很近的未来不会出现很大的摇摆变化的棋局.例如在国际象棋中,有很好的吃招的棋局对于只统计子力的评价函数来说就不能算是静止的。非静止的棋局可以进一步扩展直到静止的棋局.这种额外的搜索称为静止搜索.地平线效应 当对手的应对可能导致我方的重大损失并且是不可避免的情况,如国际象棋中黑棋领先较多,但对方白棋如果能够把接近底线的兵推进到底线升格为皇后,那么白棋基本上就赢了.黑棋会尽力的延缓这种情况发生,但搜索的深度有限,黑棋的这种努力有可能不断的把白兵升后的行棋推出”搜索的地平线”,将其推到无法检测到的空间,称为地平线效应.,28,上述极大极小过程
20、是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。如果能边生成节点边对节点估值，从而可以剪去一些没用的分枝，这种技术称为-剪枝过程。,再论-剪枝,=2,3,对于一个与节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称该值为值。对于一个或节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称该值为 值。,29,-剪枝的方法如下：（1）MAX节点的值为当前子节点的最大倒推值；（2）MIN 节点的值为当前子节点的最小倒推值；（3）-剪枝的规则如下：任何MAX节点n的值大于或等于它先辈节点的值，则n以下的分
21、枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。任何MIN节点n的值小于或等于它先辈节点的值，则n以下的分枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。下面看一个-剪枝的具体例子，如下页图所示。其中最下面一层端节点下面的数字是假设的估值。,再论-剪枝,30,4,4,1,4,4,5,5,4,4,0,0,0,-6,0,0,4,-剪枝的例子,31,在上页图中，由节点K、L、M的估值推出节点F的倒推值为4，即F的值为4，由此可推出节点C的倒推值4。记C的倒推值的下界为4，不可能再比4小，故C的值为4。由节点N的估值推知节点G的倒推值小于l，无论G的其他子节点的估值是多少，G的倒推值都不可
22、能比1大。事实上，随着子节点的增多，G的倒推值只可能是越来越小。因此，1是G的倒推值的上界，所以G的值为1。另外，已经知道C的倒推值4，G的其他子节点又不可能使C的倒推值增大。因此，对G的其他分支不必再进行搜索，这就相当于把这些分枝剪去。由F、G的倒推值可推出节点C的倒推值为4，再由C可推出节点A的倒推值4，即A的值为4。另外，由节点P、Q推出的节点H的倒推值为5，此时可推出D的倒推值5，即D的值为5。此时，D的其他子节点的倒推值无论是多少都不能使D及A的倒推值减少或增大，所以D的其他分枝被减去，并可确定A的倒推值为4。用同样方法可推出其他分枝的剪枝情况，最终推出S0的倒推值为4。,国际象棋对
23、弈程序:深蓝,开发者:IBM 的Murry Campbell,Feng-Hsiung Hsu 和Joseph Hoane采用30个IBM RS/6000处理器来运行软件搜索使用480个定制VLSI国际象棋处理器执行生成行棋的功能树的最后几层的”硬件搜索”以及对叶节点的评价.每秒平均搜索12.6亿种走法，峰值时每秒钟搜索33亿个节点.每走一步至多能够预先计算300亿种个棋局,常规搜索深度是14步.机器的核心算法是使用调换表的标准迭代深入-搜索,而且对关键的点具备产生超越搜索深度的扩展能力,在某些情况下可以达到40层的深度.评价函数采用了超过8000个特征;使用一本有4000个棋局的”开局手册”以及一个存有70万个大师级比赛棋谱的数据库;使用一个大型残局数据库保存已解决的棋局.,33,练习题：,34,练习题：,35,实验题1：,编写程序，采用宽度优先搜索或有界深度优先搜索实现八数码难题。,
