搜索博弈树的启发式搜索.pptx

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