第5部分对抗搜索.ppt
58页
第5部分对抗搜索Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope有生命必有希望有生命必有希望 本章内容本章内容•5.1 博弈博弈•5.2 博弈中的优化决策博弈中的优化决策•5.3 - 剪枝剪枝•5.4 不完美的实时决策不完美的实时决策•5.5 随机博弈随机博弈•5.6 部分可观察的博弈部分可观察的博弈•5.7 博弈程序发展现状博弈程序发展现状•5.8 其他途径其他途径 5.1 博弈博弈•概述概述•Grundy博弈博弈 概述概述•在博弈问题中在博弈问题中——比如说象棋比如说象棋——搜索是在博弈者搜索是在博弈者双方之间进行的双方之间进行的–任何一方在搜索时，都必须要考虑任何一方在搜索时，都必须要考虑对方对方可能要采可能要采用的走步用的走步–对于一个优秀的博弈者来说，应考虑的不只是对对于一个优秀的博弈者来说，应考虑的不只是对方方一步一步的走法，而是的走法，而是若干步若干步的走法–这一过程一般来说是这一过程一般来说是动态动态进行的在考虑若干步进行的在考虑若干步走法以后，下了一步棋；而在对方走棋之后，还走法以后，下了一步棋；而在对方走棋之后，还要再次考虑若干步走法，决定下一步的走法，而要再次考虑若干步走法，决定下一步的走法，而不是一劳永逸，搜索一次就决定了所有的走法。
不是一劳永逸，搜索一次就决定了所有的走法 概述概述•本章所讲的本章所讲的博弈博弈：主要指的是类似于象棋这样的游：主要指的是类似于象棋这样的游戏问题•这类问题有以下一些特点：这类问题有以下一些特点：①①双人对弈双人对弈，对垒的双方轮流走步对垒的双方轮流走步②②信息完备信息完备，对垒双方所得到的信息是一样的，不，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况存在一方能看到，而另一方看不到的情况③③零和零和即对一方有利的棋，对另一方肯定是不利即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋对弈的，不存在对双方均有利、或均无利的棋对弈的结果是一方赢，而另一方输，或者双方和棋的结果是一方赢，而另一方输，或者双方和棋 概述概述•双人完备信息博弈双人完备信息博弈：：–指两位选手对垒，轮流走步，这时每一方不仅都指两位选手对垒，轮流走步，这时每一方不仅都知道对方过去已经走过的棋步，而且还能估计出知道对方过去已经走过的棋步，而且还能估计出对方未来可能的走步对方未来可能的走步–对弈的结果是一方赢（另一方则输），或者双方对弈的结果是一方赢（另一方则输），或者双方和局。
和局–这类博弈的实例有：这类博弈的实例有：一字棋、余一棋、西洋跳棋、一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等国际象棋、中国象棋、围棋等•机遇性博弈机遇性博弈：存在不可预测性的博弈，例如掷币等存在不可预测性的博弈，例如掷币等–例如：例如：西洋双陆棋西洋双陆棋 Grundy博弈博弈 •Grundy博弈博弈是一个分钱币的游戏是一个分钱币的游戏–有一堆数目为有一堆数目为N的钱币，由两位选手轮流进行分的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆不等的两小堆–例如，选手甲把例如，选手甲把N分成两堆后，轮到选手乙就可分成两堆后，轮到选手乙就可以挑其中一堆来分以挑其中一堆来分–如此进行下去，直到有一位选手先无法把钱币再如此进行下去，直到有一位选手先无法把钱币再分成不相等的两堆时就得认输分成不相等的两堆时就得认输•对于这样的简单博弈问题，可以生成出它的对于这样的简单博弈问题，可以生成出它的状态空状态空间图间图这样就有可能从状态空间图中找出取胜的策这样就有可能从状态空间图中找出取胜的策略 Grundy博弈博弈•当初始钱币数为当初始钱币数为7时的状态空间图时的状态空间图 MIN代表对方走代表对方走MAX代表我方走代表我方走MAX存在完存在完全取胜的策略全取胜的策略 Grundy博弈博弈•搜索策略要考虑的问题：搜索策略要考虑的问题：–对对MIN走步后的每一个走步后的每一个MAX节点，必须证明节点，必须证明MAX对对MIN可能走的每一个棋局对弈后能获胜，即可能走的每一个棋局对弈后能获胜，即MAX必须考虑应付必须考虑应付MIN的所有招法，这是一个的所有招法，这是一个与与的含意。
的含意•因此含有因此含有MAX符号的节点可看成符号的节点可看成与节点与节点–对对MAX走步后的每一个走步后的每一个MIN节点，只须证明节点，只须证明MAX有一步能走赢就可以，即有一步能走赢就可以，即MAX只要考虑能走出一只要考虑能走出一步棋使步棋使MIN无法招架就成无法招架就成•因此含有因此含有MIN符号的节点可看成符号的节点可看成或节点或节点•因此，对弈过程的搜索图就呈现出与或图表示的形式因此，对弈过程的搜索图就呈现出与或图表示的形式 Grundy博弈博弈•寻找寻找MAX的取胜策略的取胜策略和求和求与或图的解图与或图的解图相对应–MAX要取胜，必须对所有与节点取胜，但只需对要取胜，必须对所有与节点取胜，但只需对一个或节点取胜，这就是一个解图一个或节点取胜，这就是一个解图•因此，寻找一种取胜的策略就是搜索一个解图的问因此，寻找一种取胜的策略就是搜索一个解图的问题，题，解图解图就代表就代表一种完整的博弈策略一种完整的博弈策略•对于对于Grundy这种较简单的博弈，或者复杂博弈的残这种较简单的博弈，或者复杂博弈的残局，可以用类似于与或图的搜索技术求出解图，解局，可以用类似于与或图的搜索技术求出解图，解图代表了从开局到终局任何阶段上的弈法。
图代表了从开局到终局任何阶段上的弈法–显然这对许多博弈问题是显然这对许多博弈问题是不可能不可能实现的例如，实现的例如，中国象棋，国际象棋和围棋等中国象棋，国际象棋和围棋等 Grundy博弈博弈•对于复杂的博弈问题，因此即使用了强有力的启发对于复杂的博弈问题，因此即使用了强有力的启发式搜索技术，也不可能使式搜索技术，也不可能使分枝分枝压到很少压到很少–因此，这种完全取胜策略（或和局）必须丢弃因此，这种完全取胜策略（或和局）必须丢弃•应当把目标确定为应当把目标确定为寻找一步好棋寻找一步好棋，等，等对手回敬对手回敬后再后再考虑寻找考虑寻找另一步好棋另一步好棋这种实际可行的实用策略这种实际可行的实用策略–这种情况下每一步的结束条件可根据这种情况下每一步的结束条件可根据时间限制、时间限制、存储空间限制或深度限制存储空间限制或深度限制等因素加以确定等因素加以确定–搜索策略可采用宽度、深度或启发式方法一个搜索策略可采用宽度、深度或启发式方法一个阶段搜索结束后，要从搜索树中提取一个优先考阶段搜索结束后，要从搜索树中提取一个优先考虑的虑的"最好的最好的"走步，这就是实用策略的基本点走步，这就是实用策略的基本点。
本章内容本章内容•5.1 博弈博弈•5.2 博弈中的优化决策博弈中的优化决策•5.3 - 剪枝剪枝•5.4 不完美的实时决策不完美的实时决策•5.5 随机博弈随机博弈•5.6 部分可观察的博弈部分可观察的博弈•5.7 博弈程序发展现状博弈程序发展现状•5.8 其他途径其他途径 5.2 博弈中的优化决策博弈中的优化决策•极小极大值法极小极大值法•多人游戏中的最优决策多人游戏中的最优决策 极小极大搜索过程极小极大搜索过程•人类下棋的方法人类下棋的方法：实际上采用的是一种试探性的方：实际上采用的是一种试探性的方法–首先假定走了一步棋，看对方会有那些应法，然首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的后再根据对方的每一种应法，看我方是否有好的回应回应......–这一过程一直进行下去，直到若干步以后，找到这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止了一个满意的走法为止–初学者可能只能看一、两个回合，而高手则可以初学者可能只能看一、两个回合，而高手则可以看几个，甚至十几个回合看几个，甚至十几个回合•极小极大搜索方法：极小极大搜索方法：模拟的就是人的这样一种思维模拟的就是人的这样一种思维过程。
过程 极小极大搜索过程极小极大搜索过程•极小极大搜索策略极小极大搜索策略是考虑双方对弈若干步之后，从可能的走是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在步中选一步相对好棋的着法来走，即在有限的搜索深度有限的搜索深度范围范围内进行求解内进行求解•定义一个定义一个静态估计函数静态估计函数f，以便对棋局的势态（节点）作出优，以便对棋局的势态（节点）作出优劣估值–这个函数可根据这个函数可根据势态优劣特征势态优劣特征来定义（主要用于对端节点来定义（主要用于对端节点的的“价值价值”进行度量）进行度量）–一般规定：有利于一般规定：有利于MAX的势态，的势态，f（（p）取正值；有利于）取正值；有利于MIN的势态，的势态，f（（p）取负值；势均力敌的势态，）取负值；势均力敌的势态，f（（p）取）取0值–若若f（（p）＝＋）＝＋∞，则表示，则表示MAX赢，若赢，若f（（p）＝－）＝－∞，则表，则表示示MIN赢 极小极大搜索过程极小极大搜索过程•注意：注意：不管设定的搜索深度是多少层，经过一次搜不管设定的搜索深度是多少层，经过一次搜索以后，只决定了我方一步棋的走法索以后，只决定了我方一步棋的走法。
–等到对方回应一步棋之后，需要在新的棋局下重等到对方回应一步棋之后，需要在新的棋局下重新进行搜索，来决定下一步棋如何走新进行搜索，来决定下一步棋如何走•极小极大过程是一种极小极大过程是一种假定对手每次回应都正确假定对手每次回应都正确的情的情况下，如何从中找出对我方最有利的走步的搜索方况下，如何从中找出对我方最有利的走步的搜索方法 极小极大搜索过程极小极大搜索过程•规定：规定：顶节点深度顶节点深度d＝＝0，，MAX代表程序方，代表程序方，MIN代代表对手方表对手方MAX先走•例：例：一个考虑一个考虑2步棋的例子步棋的例子 极小极大搜索过程极小极大搜索过程•规定：规定：顶节点深度顶节点深度d＝＝0，，MAX代表程序方，代表程序方，MIN代代表对手方表对手方MAX先走•例：例：一个考虑一个考虑2步棋的例子步棋的例子端节点给出的数字是用静态估计函数端节点给出的数字是用静态估计函数f（（p）计算得到计算得到 过程过程MINIMAX ①① T:＝（＝（s，，MAX），），OPEN:＝（＝（s），），CLOSED:＝（＝（ ）；）；开始时树由初开始时树由初始节点构成，始节点构成，OPEN表只含有表只含有s。
②② LOOP1: IF OPEN＝（＝（ ））THEN GO LOOP2；；③③ n:＝＝FIRST(OPEN)，，REMOVE(n，，OPEN)，，ADD(n，，CLOSED)；；④④ IF n可直接判定为赢、输或平局可直接判定为赢、输或平局THEN f（（n））:＝＝∞∨∨－－∞∨∨0，，GO LOOP1ELSE 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 CLOSED＝＝NIL THEN GO LOOP3ELSE np:＝＝FIRST（（CLOSED）；）；⑥⑥ IF（（np∈ ∈MAX））∧∧（（f（（nci∈ ∈MIN）有值））有值）THEN f（（ np ））:＝＝max{f（（nci））}，，REMOVE(np，，CLOSED)；；若若MAX所所有子节点均有值，则该有子节点均有值，则该MAX取其极大值取其极大值。
IF （（ np ∈ ∈MIN））∧∧（（f（（ nci ∈ ∈MAX）有值））有值）THEN f（（ np ））:＝＝min{f（（nci））}，，REMOVE(np ，，CLOSED)；；若若MIN所所有子节点均有值，则该有子节点均有值，则该MIN取其极小值取其极小值⑦⑦ GO LOOP2；；⑧⑧ LOOP3：：IF f（（s））≠NIL THEN EXIT( END∨ ∨M(Move，，T) )；；s有值，则有值，则结束或标记走步结束或标记走步 过程过程MINIMAX•该算法分两个阶段进行该算法分两个阶段进行:–第一阶段第一阶段②②～～④④：：用宽度优先法生成规定深度的用宽度优先法生成规定深度的全部博弈树，然后对其所有全部博弈树，然后对其所有端节点端节点计算其静态估计算其静态估计函数值计函数值–第二阶段第二阶段⑥⑥～～⑧⑧：：从底向上逐级求从底向上逐级求非端节点非端节点的倒的倒推估计值，直到求出初始节点推估计值，直到求出初始节点s的倒推值的倒推值f（（s）为）为止，此时止，此时•等对手响应走步后，再以当前的状态作为起始状态等对手响应走步后，再以当前的状态作为起始状态s，重复调用，重复调用该过程。
该过程 例：例：3×3棋盘的一字棋棋盘的一字棋•3×3棋盘的一字棋棋盘的一字棋：九宫格棋盘上，两位选手轮流在：九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜一线的结果就取胜•假设：假设：–程序方程序方MAX的棋子用（的棋子用（×）表示；）表示；–对手对手MIN的棋子用（的棋子用（○）表示；）表示；–MAX先走 例：例：3×3棋盘的一字棋棋盘的一字棋•静态估计函数静态估计函数f（（p））规定如下：规定如下：–若若p是是MAX获胜的格局，则获胜的格局，则f（（p）＝）＝∞；；–若若p是是MIN获胜的格局，则获胜的格局，则f（（p）＝－）＝－∞；；–若若p对任何一方来说都不是获胜的格局，则对任何一方来说都不是获胜的格局，则f（（p）＝）＝（所有空格都放上（所有空格都放上MAX的棋子之后，的棋子之后，MAX的三子成的三子成线（行、列、对角）的总数－（所有空格都放上线（行、列、对角）的总数－（所有空格都放上MIN的棋子之后，的棋子之后，MIN的三子成线（行、列、对角）的三子成线（行、列、对角）的总数）的总数）•例例、当、当p的格局如下时，则可得的格局如下时，则可得f（（p）＝）＝6－－4＝＝2。
•在搜索过程中，具有在搜索过程中，具有对称性对称性的棋局认为是同一棋局，的棋局认为是同一棋局，可以大大减少搜索空间可以大大减少搜索空间 对称棋局的例子对称棋局的例子例：例：3×3棋盘的一字棋棋盘的一字棋 例：例：3×3棋盘的一字棋棋盘的一字棋•假定假定考虑走两步的搜索过程考虑走两步的搜索过程，，利用棋盘对称性的条利用棋盘对称性的条件件，则第一次调用算法产生的搜索树为：，则第一次调用算法产生的搜索树为： 例：例：3×3棋盘的一字棋棋盘的一字棋•假假 设设MAX走走 完完第第 一一 步步 后后 ，，MAX的的对对手手是是在在×之之上上的的格格子子下下棋棋子子，，这这时时MAX在在新新格格局局下下调调用用算算法法，，第第二二次次产产生生的的搜搜索索树树为为：： 例：例：3×3棋盘的一字棋棋盘的一字棋•类似地，第三次的搜索树为：类似地，第三次的搜索树为：至此至此MAX走完走完最好的走步后，最好的走步后，不论不论MIN怎么走，怎么走，都无法挽回败局，都无法挽回败局，因此只好认输了因此只好认输了 博弈中的优化决策博弈中的优化决策•极小极大值法极小极大值法•多人游戏中的最优决策多人游戏中的最优决策 多人游戏中的最优决策多人游戏中的最优决策•许多流行的游戏允许许多流行的游戏允许多于两个多于两个的参加者。
的参加者•如何把极小极大思想推广到多人游戏中？如何把极小极大思想推广到多人游戏中？–在两人的在两人的零和零和游戏中，由于效用值正好相反，所游戏中，由于效用值正好相反，所以二维向量可以简化为一个单一值以二维向量可以简化为一个单一值–每个节点上的每个节点上的单一评估值单一评估值要替换成一个要替换成一个向量向量•例、例、一个有三个人一个有三个人A, B和和C的游戏中，每个节点都与的游戏中，每个节点都与一个向量一个向量
违反盟约会损害社会声誉–游戏者要在游戏者要在毁约得到的直接利益毁约得到的直接利益和和被认为不可信被认为不可信任带来的长期弊端任带来的长期弊端之间寻求平衡之间寻求平衡 本章内容本章内容•5.1 博弈博弈•5.2 博弈中的优化决策博弈中的优化决策•5.3 - 剪枝剪枝•5.4 不完美的实时决策不完美的实时决策•5.5 随机博弈随机博弈•5.6 部分可观察的博弈部分可观察的博弈•5.7 博弈程序发展现状博弈程序发展现状•5.8 其他途径其他途径 - 剪枝的基本思想剪枝的基本思想•在极小极大搜索方法中，由于要生成指定深度以内在极小极大搜索方法中，由于要生成指定深度以内的所有节点，其的所有节点，其节点数将随着搜索深度的增加成指节点数将随着搜索深度的增加成指数增长数增长–这极大地限制了极小极大搜索方法的使用这极大地限制了极小极大搜索方法的使用•能否在搜索深度不变的情况下，利用已有的搜索信能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？息减少生成的节点数呢？ - 剪枝的基本思想剪枝的基本思想•设某博弈问题如下图所示：设某博弈问题如下图所示： - 剪枝的基本思想剪枝的基本思想•α-β搜索过程的基本思想搜索过程的基本思想：把：把博弈树生成博弈树生成和和倒推估值倒推估值结合起来进行，再根据一定的条件判定，有结合起来进行，再根据一定的条件判定，有可能尽早可能尽早修剪掉一些无用的分枝修剪掉一些无用的分枝。
•为了使生成和估值过程紧密结合，采用为了使生成和估值过程紧密结合，采用有界深度优先有界深度优先策略策略进行搜索进行搜索•当生成达到规定深度的节点时，就立即计算其静态估当生成达到规定深度的节点时，就立即计算其静态估值函数，而一旦某个非端节点有条件确定其倒推值时值函数，而一旦某个非端节点有条件确定其倒推值时就立即计算赋值就立即计算赋值 - 剪枝的基本思想剪枝的基本思想•极大值层的下界值称为极大值层的下界值称为α•极小值层的上界值称为极小值层的上界值称为β α-β搜索搜索过程的剪枝规则过程的剪枝规则•α剪枝：剪枝：若任一极小值层节点的若任一极小值层节点的β值小于或等于它任一先辈极值小于或等于它任一先辈极大值层节点的大值层节点的α值，即值，即α（先辈层）（先辈层）≥β（后继层）（后继层），则可，则可中止中止该极小值层中这个该极小值层中这个MIN节点以下的搜索过程这个节点以下的搜索过程这个MIN节点节点最终的倒推值就确定为这个最终的倒推值就确定为这个β值•β剪枝：剪枝：若任一极大值层节点的若任一极大值层节点的α值大于或等于它任一先辈极值大于或等于它任一先辈极小值层节点的小值层节点的β值，即值，即α（后继层）（后继层）≥β（先辈层）（先辈层），则可以，则可以中中止止该极大值层中这个该极大值层中这个MAX节点以下的搜索过程。
这个节点以下的搜索过程这个MAX节节点的最终倒推值就确定为这个点的最终倒推值就确定为这个α值 •根据这些剪枝规则，很容易给出根据这些剪枝规则，很容易给出α-β算法描述，显然剪枝后选算法描述，显然剪枝后选得的最好优先走步，其结果得的最好优先走步，其结果与不剪枝的与不剪枝的MINIMAX方法所得完方法所得完全相同全相同，因而，因而α-β过程具有较高的效率过程具有较高的效率 α-β搜索过程的博弈树搜索过程的博弈树 α-β剪枝举例剪枝举例•约定：约定：–在搜索过程中，节点的生成次序是从上到下，从在搜索过程中，节点的生成次序是从上到下，从左到右进行的左到右进行的–图中带圈的数字，表示节点的计算次序在叙述图中带圈的数字，表示节点的计算次序在叙述时，为了表达上的方便，该序号也同时表示节点时，为了表达上的方便，该序号也同时表示节点–当一个节点有两个以上的序号时，不同的序号，当一个节点有两个以上的序号时，不同的序号，表示的是同一个节点在不同次序下计算的结果表示的是同一个节点在不同次序下计算的结果 α-β搜索过程的博弈树搜索过程的博弈树α-β剪枝举例剪枝举例 - 搜索过程搜索过程•在进行在进行α-β剪枝时，应注意以下几个问题：剪枝时，应注意以下几个问题：1.比较都是在比较都是在极小节点极小节点和和极大节点极大节点间进行的；极大间进行的；极大节点和极大节点的比较，或者极小节点和极小节节点和极大节点的比较，或者极小节点和极小节点间的比较是无意义的。
点间的比较是无意义的2.在比较时注意是与在比较时注意是与“先辈层先辈层”节点比较，不只是节点比较，不只是与父辈节点比较当然，这里的与父辈节点比较当然，这里的“先辈层先辈层”节点，节点，指的是那些已经有了值的节点指的是那些已经有了值的节点3.只有一个节点的值只有一个节点的值“固定固定”以后，其值才能够向以后，其值才能够向其父节点传递其父节点传递 - 搜索过程搜索过程•在进行在进行α-β剪枝时，应注意以下几个问题：剪枝时，应注意以下几个问题：4.α-β剪枝方法搜索得到的最佳走步与极小极大方剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是法得到的结果是一致一致的，的，α-β剪枝并没有因为提剪枝并没有因为提高效率，而降低得到最佳走步的可能性高效率，而降低得到最佳走步的可能性5.在实际搜索时，并在实际搜索时，并不是不是先生成指定深度的搜索图先生成指定深度的搜索图，再在搜索图上进行剪枝再在搜索图上进行剪枝•如果这样，就失去了如果这样，就失去了α-β剪枝方法的意义剪枝方法的意义•在实际程序实现时，首先规定一个搜索深度，然后按在实际程序实现时，首先规定一个搜索深度，然后按照类似于照类似于深度优先搜索深度优先搜索的方式，生成节点。
在节点的的方式，生成节点在节点的生成过程中，如果在某一个节点处发生了剪枝，则该生成过程中，如果在某一个节点处发生了剪枝，则该节点其余未生成的节点就不再生成了节点其余未生成的节点就不再生成了 剪枝的效率问题剪枝的效率问题 •若以若以最理想的情况最理想的情况进行搜索，即对进行搜索，即对MIN节点先扩展最低估值节点先扩展最低估值的节点（若从左向右顺序进行，则设节点估计值从左向右递的节点（若从左向右顺序进行，则设节点估计值从左向右递增排序），增排序），MAX先扩展最高估值的节点（设估计值从左向右先扩展最高估值的节点（设估计值从左向右递减排序），则当搜索树深度为递减排序），则当搜索树深度为D，分枝因数为，分枝因数为B时，时，Ø若不使用若不使用α-β剪枝技术，搜索树的端节点数为：剪枝技术，搜索树的端节点数为：Ø若使用若使用α-β剪枝技术，剪枝技术，可以证明理想条件下生成的可以证明理想条件下生成的端节点数最少，有端节点数最少，有 剪枝的效率问题剪枝的效率问题 •比较后得出比较后得出最佳最佳α-β搜索技术搜索技术所生成深度为所生成深度为D处的端处的端节点数约等于不用节点数约等于不用α-β搜索技术所生成搜索技术所生成深度为深度为D／／2处处的端节点数的端节点数。
–这就是说，在一般条件下使用这就是说，在一般条件下使用α-β搜索技术，在同搜索技术，在同样的资源限制下，可以向前考虑更多的走步数，这样的资源限制下，可以向前考虑更多的走步数，这样选取当前的最好优先走步，将带来更大的取胜优样选取当前的最好优先走步，将带来更大的取胜优势 其他改进方法其他改进方法 •使用使用α-β剪枝技术，当不满足剪枝条件（即剪枝技术，当不满足剪枝条件（即α不大于不大于等于等于β ）时，）时，若若β值比值比α值大不了多少或极相近值大不了多少或极相近，这，这时也可以进行剪枝时也可以进行剪枝–以便有条件把搜索集中到会带来更大效果的其他以便有条件把搜索集中到会带来更大效果的其他路径上，这就是中止对效益不大的一些子树的搜路径上，这就是中止对效益不大的一些子树的搜索，以提高搜索效率索，以提高搜索效率 •不严格限制搜索的深度，当到达深度限制时，如出不严格限制搜索的深度，当到达深度限制时，如出现现博弈格局有可能发生较大变化时博弈格局有可能发生较大变化时（如出现兑子格（如出现兑子格局），则应多搜索几层，使格局进入较稳定状态后局），则应多搜索几层，使格局进入较稳定状态后再中止，这样可使倒推值计算的结果比较合理，避再中止，这样可使倒推值计算的结果比较合理，避免考虑不充分产生的影响，这是等候状态平稳后中免考虑不充分产生的影响，这是等候状态平稳后中止搜索的方法。
止搜索的方法 其他改进方法其他改进方法 •当算法给出所选的走步后，不马上停止搜索，而是当算法给出所选的走步后，不马上停止搜索，而是在原先估计可能的路径上再往前搜索几步在原先估计可能的路径上再往前搜索几步，再次检，再次检验会不会出现意外，这是一种增添验会不会出现意外，这是一种增添辅助搜索辅助搜索的方法 •对某些博弈的对某些博弈的开局阶段开局阶段和和残局阶段残局阶段，往往总结有一，往往总结有一些固定的对弈模式些固定的对弈模式–因此，可以利用这些知识编好走步表，以便在开因此，可以利用这些知识编好走步表，以便在开局和结局时使用局和结局时使用查表法查表法只是在进入中盘阶段后，只是在进入中盘阶段后，再调用其他有效的搜索算法，来选择最优的走步再调用其他有效的搜索算法，来选择最优的走步 其他改进方法其他改进方法•以上这些方法还以上这些方法还不能不能全面反映人们弈棋过程实际所全面反映人们弈棋过程实际所使用的一切推理技术，也未涉及棋局的表示和启发使用的一切推理技术，也未涉及棋局的表示和启发函数问题函数问题–高明的棋手对棋局的表示有高明的棋手对棋局的表示有独特的模式独特的模式•博弈过程中，若在一个短时期内博弈过程中，若在一个短时期内短兵相接短兵相接，进攻和，进攻和防御的战术变化剧烈，这些情况如何在搜索策略中防御的战术变化剧烈，这些情况如何在搜索策略中加以考虑？加以考虑？•基于极小极大过程的一些方法都基于极小极大过程的一些方法都设想对手走的总是设想对手走的总是最优走步最优走步，即我方总应考虑最坏的情况。
实际上，，即我方总应考虑最坏的情况实际上，再好的选手也会有失误，如何利用失误加强攻势，再好的选手也会有失误，如何利用失误加强攻势，也值得考虑也值得考虑•总之要真正解决具体的博弈搜索技术，有许多更深总之要真正解决具体的博弈搜索技术，有许多更深入的问题需要作进一步的研究和探讨入的问题需要作进一步的研究和探讨 本章内容本章内容•5.1 博弈博弈•5.2 博弈中的优化决策博弈中的优化决策•5.3 - 剪枝剪枝•5.4 不完美的实时决策不完美的实时决策•5.5 随机博弈随机博弈•5.6 部分可观察的博弈部分可观察的博弈•5.7 博弈程序发展现状博弈程序发展现状•5.8 其他途径其他途径 不完整的实时决策不完整的实时决策•MINIMAX或或 – 剪枝算法剪枝算法–理想情况：理想情况：算法一直搜索，直到至少一部分空间算法一直搜索，直到至少一部分空间到达终止状态，从而对端节点做出准确评价到达终止状态，从而对端节点做出准确评价–这样的搜索不现实这样的搜索不现实•实用方法：实用方法：–用可以估计棋局效用的用可以估计棋局效用的启发式评价函数启发式评价函数评价评价非终非终止节点止节点–用可以决策什么时候运用用可以决策什么时候运用评价函数评价函数的的截断测试截断测试取取代终止测试。
代终止测试 评价函数评价函数•评价函数的设计：评价函数的设计：①①应该以和应该以和真正的效用函数真正的效用函数同样的方式对同样的方式对终止状态终止状态进行排序进行排序•效用函数效用函数（又称目标函数或者收益函数）：对终止状（又称目标函数或者收益函数）：对终止状态给出一个数值例如，在国际象棋中，结果是赢、态给出一个数值例如，在国际象棋中，结果是赢、输或平局，分别赋予＋输或平局，分别赋予＋1，－，－1或或0②②评价函数的评价函数的计算计算不能花费太多的时间！不能花费太多的时间！③③对于非对于非终止状态终止状态，评价函数应该和取胜的实际机，评价函数应该和取胜的实际机会密切相关会密切相关 评价函数评价函数•在计算能力有限情况下，评价函数能做到最好的就在计算能力有限情况下，评价函数能做到最好的就是是猜测最后的结果猜测最后的结果–例如，国际象棋并例如，国际象棋并不是几率游戏不是几率游戏，而且也确切知，而且也确切知道当前状态；但计算能力有限，从而导致结果必道当前状态；但计算能力有限，从而导致结果必然是不确定的然是不确定的•大多数评价函数的工作方式是大多数评价函数的工作方式是计算状态的不同特征计算状态的不同特征。
–例如，国际象棋中兵的数目、象的数目、马的数例如，国际象棋中兵的数目、象的数目、马的数目等等–这些特征一起定义了状态的各种这些特征一起定义了状态的各种类别类别或者或者等价类等价类–但因但因类别太多类别太多而几乎不可能去估计取胜概率而几乎不可能去估计取胜概率 评价函数评价函数•大多数评价函数计算大多数评价函数计算每个特征单独的数值贡献每个特征单独的数值贡献，然，然后把它们结合起来找到一个总值后把它们结合起来找到一个总值–加权线性评价函数加权线性评价函数每个每个wi是一个权值，是一个权值，fi是棋局的某个特征是棋局的某个特征 评价函数评价函数•例如，例如，国际象棋的入门书中给出各个棋子的国际象棋的入门书中给出各个棋子的估计子力价值估计子力价值–兵值兵值1分；分；–马、象值马、象值3分；分；–车值车值5分；分；–后值后值9分–其它特征例如，其它特征例如，“好的兵阵好的兵阵”和和“王的安全性王的安全性”可能值可能值半个兵•把这项特征值简单相加就得到了一个对棋局的估计把这项特征值简单相加就得到了一个对棋局的估计•经验表明，如果其它都一样，则经验表明，如果其它都一样，则–在领先在领先超过超过1分分的可靠子力优势下很可能取得胜利；的可靠子力优势下很可能取得胜利；–3分分的优势几乎足以肯定取胜。
的优势几乎足以肯定取胜 评价函数评价函数（（a）黑棋有）黑棋有1个马、个马、2个兵的优势，能够取胜个兵的优势，能够取胜b）黑棋会被白棋吃掉皇后，从而失败黑棋会被白棋吃掉皇后，从而失败 评价函数评价函数•加权线性评价函数的假设：加权线性评价函数的假设：每个特征的贡献独立于其每个特征的贡献独立于其它特征的值它特征的值–假设太强！假设太强！–例如，象赋予例如，象赋予3分忽略了象在分忽略了象在残局残局中能够发挥更大中能够发挥更大作用的事实作用的事实•当前国际象棋和其它游戏的程序也采用当前国际象棋和其它游戏的程序也采用非线性的特征非线性的特征组合组合 评价函数评价函数•注意：注意：特征和权值并不是国际象棋规则的一部分特征和权值并不是国际象棋规则的一部分–它们只是人类下棋的经验总结它们只是人类下棋的经验总结•在很难归纳这样的经验规律的游戏中，怎么办？在很难归纳这样的经验规律的游戏中，怎么办？–评价函数的权值可以通过评价函数的权值可以通过机器学习机器学习来估计 截断搜索截断搜索•最直接的控制搜索次数的方法：最直接的控制搜索次数的方法：设置一个固定的深设置一个固定的深度限制度限制•更鲁棒的方法：使用更鲁棒的方法：使用迭代深入搜索迭代深入搜索。
–具体实现：具体实现：不断加大深度优先限制首先为不断加大深度优先限制首先为0，接，接着为着为1，然后为，然后为2，依此类推依此类推–当时间用完时，程序就返回目前已完成的最深的当时间用完时，程序就返回目前已完成的最深的搜索所选择的招数搜索所选择的招数 截断搜索截断搜索•由于评价函数的近似性，这些方法可能导致错误由于评价函数的近似性，这些方法可能导致错误–需要更为复杂的需要更为复杂的截断测试截断测试•评价函数应该只用于那些评价函数应该只用于那些静止的棋局静止的棋局–静止的棋局：静止的棋局：评价值在很近的未来不会出现大的评价值在很近的未来不会出现大的摇摆变化棋局摇摆变化棋局–例如，在国际象棋中，有很好的吃招的棋局对于例如，在国际象棋中，有很好的吃招的棋局对于只统计子力的评价函数来说就不能算时静止的只统计子力的评价函数来说就不能算时静止的•非静止的棋局非静止的棋局可以进一步扩展直到静止的棋局，这可以进一步扩展直到静止的棋局，这种额外的搜索称为种额外的搜索称为静止搜索静止搜索–有时候只考虑某些类型的招数，诸如吃子，能够有时候只考虑某些类型的招数，诸如吃子，能够快速地解决棋局的不确定性快速地解决棋局的不确定性。
单一扩展和前向剪枝单一扩展和前向剪枝•单一扩展：单一扩展：搜索在给定的棋局中搜索在给定的棋局中一步一步明显好于其它明显好于其它招数的行棋招数的行棋–对对“一步明显好于其它招数的行棋一步明显好于其它招数的行棋”进行超过一进行超过一般深度限制的搜索般深度限制的搜索–目的：目的：避免地平线效应且不增加太多搜索代价避免地平线效应且不增加太多搜索代价•前向剪枝：前向剪枝：在某个结点上不需要进一步搜索而直接在某个结点上不需要进一步搜索而直接剪枝–有危险！只在某些特殊的情况下使用才是安全的有危险！只在某些特殊的情况下使用才是安全的 不完整的实时决策不完整的实时决策•假设已经实现：假设已经实现：–国际象棋的评价函数国际象棋的评价函数–使用静止搜索的合理截断测试使用静止搜索的合理截断测试–一个很大的调换表（存储以前见过的棋局的哈希表一般被一个很大的调换表（存储以前见过的棋局的哈希表一般被称做称做调换表调换表））•若在若在“最新的最新的PC”上可每秒生成和评价约一百万个节点，则上可每秒生成和评价约一百万个节点，则允许我们在标准的时间控制下（每步棋允许我们在标准的时间控制下（每步棋3分钟）对每步棋可搜分钟）对每步棋可搜索约索约2亿个节点。
亿个节点–国际象棋的分支因子平均为国际象棋的分支因子平均为35，，355约为约为5亿–如果使用极大极小搜索，只能向前预测如果使用极大极小搜索，只能向前预测5层层，很容易被平，很容易被平均水平的人类棋手欺骗均水平的人类棋手欺骗–如果使用如果使用alpha-beta搜索，可以预测大约搜索，可以预测大约10层层，接近专业，接近专业棋手水平棋手水平。
