《人工智能》全套PPT第3章 智能搜索

1、第三章智能搜索3.1搜索概论3.2盲目搜索3.3启发式搜索3.4博弈树搜索of311习题3.1 搜索概论第三章 智能搜索of312 科学发展观要求建立人与自然和谐的社会，经济全球化、信息网络化、智能社会化成为当前发展的特征。探索人类智慧的道路，从思维科学走向社会智能科学，是时代的要求，体现了人文与科技的交融。在人工智能领域，所需求解的问题大多都具备结构不良或非结构化性质。这类问题通常并不存在“一马平川”式的求解方案。人们发现，很多问题的求解，其实可以通过试探性的搜索来获得。1搜索的定义3.1 搜索概论第三章 智能搜索of313 求解问题的第一步，就是把问题描述清楚，也就是目标的表示，它涉及到一

2、种知识表示策略状态空间表示法。第二步就是搜索策略。这里的“搜索”是指，智能系统尝试性地找到目标解的动作序列。 搜索问题可分解为两个关键的子问题：（1）搜索什么；（2）在哪里搜索。前者是指搜索的解，即目标为何。后者是指搜索空间。搜索空间就是由一系列状态构成。那什么是状态呢？下面我们来讨论这个基础问题。1搜索的定义3.1 搜索概论第三章 智能搜索of3142状态空间表示3.1 搜索概论第三章 智能搜索of315 定义2：状态空间（State Space）：某个问题的全部可能状态或关系集合。2状态空间表示 还是拿下棋来举例，它的状态空间，就是指它的每一个合法棋局的全体集合。很显然，由于状态空间可能非

3、常巨大，所以在搜索之前，通常并不会一次性地把所有状态都生成出来，而是渐进式地扩展，“目标”状态就是在每次新展开的状态中搜索。 3.1 搜索概论第三章 智能搜索of316 定义2：状态空间（State Space）：某个问题的全部可能状态或关系集合。2状态空间表示 和普通搜索算法不同的是，对于人工智能系统而言，在问题求解之前，搜索空间是未知的。通常是“走一步、看一步”，“摸着石头过河”。因此，搜索通常分为两个阶段：1）状态空间的生成阶段。2）对该状态空间中寻找目标解的阶段。对于博弈类游戏，上述特征尤其明显。我们通常无需把每一个棋局都考虑一边，而是在对方落子后，方才考虑我方可能走的每一步有利的棋局

4、。3.1 搜索概论第三章 智能搜索of317 定义3：操作算子（Operator）：使问题从一种状态变迁到另外一种状态的操作规则或函数。2状态空间表示 操作算子可以是某个动作（如下棋的走步），也可以数学运算符、逻辑运算符等。3.1 搜索概论第三章 智能搜索of3181定义状态空间。根据问题的特性，给出相应的状态空间，包括初始状态、目标状态和状态的一般表示形式。2确定操作算子集合：能够作用于一个状态后，迁移到另外一个状态。3确定一组搜索策略，使得能够从初始状态出发，沿着某条路径出发，达到目标路径。 有了上面概念上的铺垫，下面我们可以给出基于状态空间法的搜索算法基本流程：2状态空间表示3.1 搜索

5、概论第三章 智能搜索of319 这样一来，问题求解的求解过程可归纳为：应用合法的规则和控制策略，取遍历或搜索状态空间，直至找到从初始状态到目标状态的某个路径。在这个过程中，要涉及两类函数： （1）目标检测函数：用来确定某个状态是不是目标状态。 （2）路径代价函数：对每条路径赋予一定的权重，看走那条路最划算（代价最小）。2状态空间表示3.1 搜索概论第三章 智能搜索of3110下面我们列举一个案例来说明知识的状态空间表示法。【例3.1】八数码问题的状态空间表示法。 在一个九宫格里面放入8个数字，数字只能上下左右移动，并且只能移动到空白处。通过若干此移动后，能把图3-1中左图数字移动成右图数字。2

6、状态空间表示八数码游戏初始与结果3.1 搜索概论第三章 智能搜索of3111 我们将九宫格中的格子从左到右，从上至下依次编号成1至9个格子，如图3-2所示。2状态空间表示八数码游戏格子编号3.1 搜索概论第三章 智能搜索of3112 则我们的状态空间中的初始状态为：Q1=1,2,3,X,6,4,8,7,5。其中X 代表该位置的数字为空。现在如图3所示，有以下几种操作算子：2状态空间表示f1=数字8移动到X位上。产生对应的状态为：Q2=1,2,3,X,6,4,8,7,5。f2=数字7移动到X位上。产生对应的状态为：Q3=1,2,3,8,6,4,7,X,5。f3=数字1移动到X位上。产生对应的状态

7、为：Q4=X,2,3,8,6,4,1,7,5。f4=数字6移动到X位上。产生对应的状态为：Q5=1,2,3,8,X,4,6,7,5。f5=数字5移动到X位上。产生对应的状态为：Q6=1,2,3,8,6,4,5,7,X。f6=数字6移动到X位上。产生对应的状态为：Q7=1,2,3,8,X,4,6,7,5。3.1 搜索概论第三章 智能搜索of3113则操作算子的集合F=f1，f2，f3，f4,，f5，f6，目标状态Q7=1,2,3,8,X,4,6,7,5。2状态空间表示状态空间表示法示例八：数码游戏第三章智能搜索3.1搜索概论3.2盲目搜索3.3启发式搜索3.4博弈树搜索of3114习题3.2 盲

8、目搜索第三章 智能搜索of3115 盲目搜索（Blind Search）又叫非启发式搜索（Uninformed Search），它只会按预定的搜索策略进行搜索，而不会考虑问题本身的特性而做变通，它唯一能区分的就是，下一个状态是目标状态（即问题的解）还是非目标状态。 因此，盲目搜索一般只适用于求解比较简单的问题。我们将学习的宽度优先搜索和深度优先搜索，属于盲目搜索方法。3.2 盲目搜索第三章 智能搜索of31161宽度优先搜索 宽度优先搜索（Breadth First Search，BFS）又称广度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最

9、短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。 宽度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。3.2 盲目搜索第三章 智能搜索of31171宽度优先搜索宽度优先搜索示例图13.2 盲目搜索第三章 智能搜索of31181宽度优先搜索3.2 盲目搜索第三章 智能搜索of31191宽度优先搜索3.2 盲目搜索第三章 智能搜索of31201宽度优先搜索图3-5 宽度优先搜索示例图23.2 盲目搜索第三章 智能搜索of31212深度优先搜索 深度优先搜索（Depth Firs

10、t Search，DFS）属于图算法的一种。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。3.2 盲目搜索第三章 智能搜索of31222深度优先搜索 深度优先搜索所使用的策略就如其名字一样，只要可能，就在图中尽量的深入。深度优先搜素总是对最近才发现的结点V 的出发边进行探索，直到该结点的所有出发边都被发现为止。一旦结点V 的所有出发边都被发现，搜索则回溯到V 的前驱结点（V 是经过该点才被发现的），来探索该前驱结点的出发边。 该过程一直持续到从源结点可以到达的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作

11、为新的源节点，并重复同样的搜索过程。3.2 盲目搜索第三章 智能搜索of31232深度优先搜索深度优先遍历图的基本思路是，从图中某顶点V 出发： （1）访问顶点V 。 （2）依次从V 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和 v 有路径相通的顶点都被访问。 （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。3.2 盲目搜索第三章 智能搜索of31242深度优先搜索 下面采用一个示例图来说明这个过程。如图3-6所示，示例图是一个无向图，如果我们从A 点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是B

12、 也可以是C ，D ），则我们可能得到如下的一个访问过程：AB E（没有路了！回溯到 A ) C F H G D（没有路，最终回溯到A ，A 也没有未访问的相邻节点，本次搜索结束）。深度优先搜索示例图第三章智能搜索3.1搜索概论3.2盲目搜索3.3启发式搜索3.4博弈树搜索of3125习题3.3 启发式搜索第三章 智能搜索of31261启发式搜索策略 启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。3.3 启发式搜索第

13、三章 智能搜索of31271启发式搜索策略 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。 如果能够利用搜索过程所得到的问题自身的一些特征信息来指导搜索过程，则可以缩小搜索范围，提高搜索效率。像这样利用问题自身特征信息来引导搜索过程的方法成为启发式方法。 启发式策略可以通过指导搜索向最有希望的方向前进，降低了复杂性。通过删除某些状态及其延伸，启发式算法可以消除组合爆炸，并得到令人能接受的解(通常并不一定是最优解)。3.3 启发式搜索第三章 智能搜索of31281启发式搜索策略 然而，启发式策

14、略是极易出错的。在解决问题的过程中启发仅仅是下一步将要采取措施的一个猜想，常常根据经验和直觉来判断。由于启发式搜索只有有限的信息(比如当前状态的描述)，要想预测进一步搜索过程中状态空间的具体行为则很难。一个启发式搜索可能得到一个次优解，也可能一无所获。这是启发式搜索固有的局限性。这种局限性不可能由所谓更好的启发式策略或更有效的搜索算法来消除。 一般说来，启发信息越强，扩展的无用节点就越少。引入强的启发信息，有可能大大降低搜索工作量，但不能保证找到最小耗散值的解路径(最佳路径)。因此，在实际应用中，最好能引入降低搜索工作量的启发信息而不牺牲找到最佳路径的保证。3.3 启发式搜索第三章 智能搜索o

15、f31291启发式搜索策略以下为一个启发式搜索的八数码游戏例子： 如图3-7所示，在一个九宫格里面放入8个数字，数字只能上下左右移动，并且只能移动到空白处。通过若干次这样的移动后，把左图数字位置移动成右图数字位置。八数码游戏初始与结果3.3 启发式搜索第三章 智能搜索of31301启发式搜索策略 解决此问题的启发策略：每次移动的时候，正确位置数码的个数要大于交换前正确位置数码个数。正确位置数码的个数是指每个数码的位置与最终格局的对比，如果位置相同，则说明此数码在正确位置。图3-8中红色字体标识的数码为正确位置数码，由此我们可以发现下图中左边初始图案正确位置的数码个数为4个。八数码游戏寻找正确位

16、置数码个数3.3 启发式搜索第三章 智能搜索of31311启发式搜索策略 由下图3-9所示可得，正确位置数码个数大于等于4的只有左下方的格局，那么下一步选择的就是左下方的格局。八数码游戏3.3 启发式搜索第三章 智能搜索of31321启发式搜索策略再次调用次算法如下图3-10所示：这样一步一步地进行，最终即可得到最终格局。八数码游戏3.3 启发式搜索第三章 智能搜索of31332有序搜索 有序搜索（Ordered Search）又称之为最佳优先搜索（Best First Search），是一种启发式搜索算法，我们也可以将它看作广度优先搜索算法的一种改进；最佳优先搜索算法在广度优先搜索的基础上，

17、用启发估价函数对将要被遍历到的点进行估价，然后选择代价小的进行遍历，直到找到目标节点或者遍历完所有的点，算法结束。3.3 启发式搜索第三章 智能搜索of31342有序搜索 要实现最佳优先搜索我们必须使用一个优先队列（Priority Queue）来实现，通常采用一个open 优先队列和一个closed 集open 优先队列用来储存还没有遍历将要遍历的节点，而closed 集用来储存已经被遍历过的节点。我们用下面图3-11作为一个示例图来描述最佳优先搜索过程。最佳优先搜索示例图3.3 启发式搜索第三章 智能搜索of31352有序搜索最佳优先搜索的过程如图3-12所示，可以被描述为：搜索出的路径为

18、：A-H-G-D-E，整条路径的代价和为16。最佳优先搜索示例图详细过程3.3 启发式搜索第三章 智能搜索of31362有序搜索 （1）将根节点放入优先队列 open 中。 （2）从优先队列中取出优先级最高的节点X 。 （3）根据节点X 生成子节点Y ： X 的子节点Y 不在 open 队列或者 closed 中，由估价函数计算出估价值，放入open 队列中。 X 的子节点Y 在open 队列中，且估价值优于open 队列中的子节点Y ，将 open 队列中的子节点Y 的估价值替换成新的估价值并按优先值排序。 X 的子节点Y 在closed 集中，且估价值优于closed 集中的子节点Y ，将

19、 closed 集中的子节点Y 移除，并将子节点Y 加入open 优先队列。 （4）将节点X 放入closed 集中。 （5）重复过程2,3,4直到目标节点找到，或者open 为空，程序结束。3.3 启发式搜索第三章 智能搜索of31373通用图搜索算法 在图算法中经常要执行遍历每个顶点和每条边的操作，即图搜索。许多图算法都以图搜索为基础，如2-着色问题、连通性计算基于深度优先搜寻（DFS），而无权最短路径则基于广度优先搜索（BFS）。 基于搜索的算法还包括计算最小生成树的Prim算法以及计算最短路径的Dijkstra算法。其中我们在前面章节已经介绍过广度优先搜索以及深度优先搜索，本小节着重介

20、绍Prim算法和Dijkstra算法。3.3 启发式搜索第三章 智能搜索of31383通用图搜索算法 普里姆（Prim）算法，图论中的一种算法，可在加权连通图里搜索最小生成树，即由此算法搜索到的边子集所构成的树中，不但包括了连通图中的所有顶点（Vertex），且使得树中所有的边的权值之和亦为最小值。 Prim算法基于贪心算法设计，该算法从一个顶点出发，选择这个顶点发出的边中权重最小的一条加入最小生成树中，随后从当前的树中的所有顶点发出的边中选出权重最小的一条加入树中，以此类推，直到所有顶点都在树中，算法结束。算法可以按如下具体描述：3.3 启发式搜索第三章 智能搜索of31393通用图搜索算法

21、3.3 启发式搜索第三章 智能搜索of31403通用图搜索算法 下面举一个例子来说明，图3-13是一个无向图，假设我们从顶点a 出发使用Prim算法计算最小生成树，其算法运行过程如下。Prim算法示例图3.3 启发式搜索第三章 智能搜索of31413通用图搜索算法 从顶点a发出的边有，和，其中权重最小的边为，于是我们将边加入到最小生成树中，此时最小生成树包括图3-14中的阴影边和灰色顶点。Prim算法示例图3.3 启发式搜索第三章 智能搜索of31423通用图搜索算法 接下来我们继续从当前最小生成树中的顶点发出的所有边中寻找权重最小的一条，即边，中的边，于是我们将边加入到树中，如下图3-15所

22、示。 Prim算法示例图3.3 启发式搜索第三章 智能搜索of31433通用图搜索算法 继续上述步骤，从顶点a、f、d 发出的边中选出权重最小的一条，即边，并将它加入到树中，如下图3-16所示。Prim算法示例图3.3 启发式搜索第三章 智能搜索of31443通用图搜索算法重复上述步骤，最后得到图的最小生成树如下图3-17所示。Prim算法示例图3.3 启发式搜索第三章 智能搜索of31453通用图搜索算法 迪杰斯特拉（Dijkstra）算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉

23、算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra算法采用的是一种贪心的策略，声明一个数组Dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T 。初始时，原点s 的路径权重被赋为0(Dis s =0)。若对于顶点s 存在能直接到达的边(s , m)，则把Dis m 设置为w (s , m)，同时把所有其他（s 不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T 只有顶点s 。3.3 启发式搜索第三章 智能搜索of31463通用图搜索算法 从Dis 数组选择最小值，则该值就是源点s 到该值对应的顶点的最短路径，并且把该点加入到T 中，

24、完成一个顶点。 然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在Dis 中的值。 之后，从Dis 中找出最小值，重复上述动作，直到T 中包含了图的所有顶点。3.3 启发式搜索第三章 智能搜索of31473通用图搜索算法Dijkstra算法示例图3.3 启发式搜索第三章 智能搜索of31483通用图搜索算法首先第一步，先声明一个Dis 数组，该数组初始化的值为如图3-19所示：Dijkstra算法示例图Dis 数组3.3 启发式搜索第三章 智能搜索of31493通用图搜索算法Dijkstra算法示例图Dis

25、 数组3.3 启发式搜索第三章 智能搜索of31503通用图搜索算法Dijkstra算法示例图Dis 数组3.3 启发式搜索第三章 智能搜索of31513通用图搜索算法Dijkstra算法示例图Dis 数组3.3 启发式搜索第三章 智能搜索of31523通用图搜索算法Dijkstra算法示例图Dis 数组3.3 启发式搜索第三章 智能搜索of31533通用图搜索算法Dijkstra算法示例图结果起点终点最短路径长度无105030603.3 启发式搜索第三章 智能搜索of31544A* 算法3.3 启发式搜索第三章 智能搜索of31554A* 算法3.3 启发式搜索第三章 智能搜索of31564

26、A* 算法 如下就A*算法与深度优先搜索算法和广度优先搜索算法进行比较： 深度优先搜索会朝一个方向进发，直到遇到边界或者障碍物，才回溯。一般在实现的时候，我们采用递归的方式来进行，也可以采用模拟压栈的方式来实现。3.3 启发式搜索第三章 智能搜索of31574A* 算法 如图3-24，S 代表起点，E 代表终点。我们如果按照右、下、左、上这样的扩展顺序的话，算法就会一直往右扩张，直到走到地图的右边界，发现没找到目标点，然后再回溯。深度优先搜索方式3.3 启发式搜索第三章 智能搜索of31584A* 算法 这个算法的好处就是实现简单，不过也存在两个明显的问题：1、路径可能不是最优解；2、寻路时间

27、比较长。 图3-25展示了广度优先算法的方式，广度优先搜索像是地震波，从起点向外辐射，直到找到目标点。我们在实现的时候，一般采用队列来实现。广度优先搜索方式3.3 启发式搜索第三章 智能搜索of31594A* 算法 广度优先算法的优点是实现简单，同时保证算法能够找到一条最优的路径。但是也存在不足之处就是算法消耗的时间比较大，遍历的点会很多。那么这里我们就可以思考一个问题：为什么广度优先算法能找到最优路径，但是却很耗时呢？ 广度优先搜索之所以能找到最优的路径，原因就是每一次扩展的点，都是距离出发点最近、步骤最少的。如此这样递推，当扩展到目标点的时候，也是距离出发点最近的。这样的路径自然形成了最短

28、的路线。 正是由于广度优先搜索是一层层的扩展，让它可以保证了算法能找到一条最优的路线的可能性，但是却同时也因此消耗了更多的时间和计算能力去走了绝大多的无效步骤。3.3 启发式搜索第三章 智能搜索of31604A* 算法 从另一个角度看，广度优先搜索算法只关注了当前扩展点和出发点之间的关系，而忽略了当前点和我们的目标点的之间的关系，也就是一种缺乏指引搜索，较为盲目的搜索方式。情况如图3-26所示时：存在两种搜索方式时3.3 启发式搜索第三章 智能搜索of31614A* 算法3.3 启发式搜索第三章 智能搜索of31624A* 算法SM的距离+ME的距离3.3 启发式搜索第三章 智能搜索of316

29、34A* 算法第三章智能搜索3.1搜索概论3.2盲目搜索3.3启发式搜索3.4博弈树搜索of3164习题3.4 博弈树搜索第三章 智能搜索of31651博弈的定义 博弈本意是：下棋。引申义是：在一定条件下，遵守一定的规则，一个或几个拥有绝对理性思维的人或团队，从各自允许选择的行为或策略进行选择并加以实施，并从中各自取得相应结果或收益的过程。有时候也用作动词，特指对选择的行为或策略加以实施的过程。3.4 博弈树搜索第三章 智能搜索of31661博弈的定义一个完整的博弈应当包括五个方面的内容： 1. 博弈的参加者，即博弈过程中独立决策、独立承担后果的个人和组织。 2. 博弈信息，即博弈者所掌握的对

30、选择策略有帮助的情报资料。 3. 博弈方可选择的全部行为或策略的集合。 4. 博弈的次序，即博弈参加者做出策略选择的先后。 5. 博弈方的收益，即各博弈方做出决策选择后的所得和所失。3.4 博弈树搜索第三章 智能搜索of31671博弈的定义 博弈树是一种与/或树的一种，为了方便博弈树的研究，我们使用一种简单的博弈作为研究的对象。具体的说这样的博弈具有如下的特点： （1）对垒的A，B 双方轮流采取行动(这就比同时采取行动在分析上方便的许多)，博弈的结果只有三种情况：A 方胜，B 方败；A 方败，B 方胜；双方战成平局。 （2）在对垒过程中，任何一方都了解当前的格局及过去的历史。 （3）任何一方在

31、采取行动前都要根据当前的实际情况，进行得失分析，选取对自己最为有利而对对方最为不利的对策,不存在“碰运气”的偶然因素。即双方都是十分理智地决定自己的行动。3.4 博弈树搜索第三章 智能搜索of31681博弈的定义 在博弈过程中，任何一方都希望自己取得胜利。因此,在某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在A 方的立场上，则可供A 方选择的若干行动方案之间是“或”关系，因为主动权操在A 方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由A 方决定。但是，若B 方也有若干个可供选择的行动方案，则对A 方来说这些行动方案

32、之间是“与”关系，因为这时主动权操在B 方手里，这些可供选择的行动方案中地任何一个都可能被B 方选中，A 方必须考虑到对自己最不利的情况发生。 若把上述博弈过程用图表示出来，得到的是一棵“与/或”树。这里要特别指出，该“与/或”树是始终站在某一方（例如A 方）的立场上得出的，决不可一会儿站在这一方的立场上,一会儿又站在另一方的立场上。3.4 博弈树搜索第三章 智能搜索of31692极小极大分析法 极大极小过程是考虑双方对弈若干步之后，从可能的走法中选一步相对好的走法来走，即在有限的搜索深度范围内进行求解。 为此我们需要定义一个局面估价函数：我们给每个局面（State）规定一个估价函数值f ，评

33、价它对于己方的有利程度。胜利的局面的估价函数值为+，而失败的局面的估价函数值为。3.4 博弈树搜索第三章 智能搜索of31702极小极大分析法 Max局面：假设这个局面轮到己方走，有多种决策可以选择，其中每种决策都会形成一种子局面（Sub-State）。由于决策权在我们手中，当然是选择估价函数值f最大的子局面，因此该局面的估价函数值等于其子局面f的最大值，把这样的局面称为Max局面。 Min局面：假设这个局面轮到对方走，它也有多种决策可以选择，其中每种决策都形成一种子局面（Sub-State）。但由于决策权在对方手中，在最坏的情况下，对方当然是选择估价函数值f最小的子局面，因此该局面的估价函数

34、值等于其子局面f值的最小值，把这样的局面称为Min局面。3.4 博弈树搜索第三章 智能搜索of31712极小极大分析法终结局面：胜负已分（假设没有和局）极小极大分析法示例图3.4 博弈树搜索第三章 智能搜索of31722极小极大分析法3.4 博弈树搜索第三章 智能搜索of31732极小极大分析法 但是，实际问题中的所有局面所产生的博弈树一般都是非常庞大，非常庞大的多叉树，并不能依靠暴力搜索来寻找最佳解法。因此需要用到一些剪枝手段，常用的比较初级的有-剪枝技术。3.4 博弈树搜索第三章 智能搜索of31743-剪枝技术 -剪枝算法是一个搜索算法旨在减少在其搜索树中，被极大极小算法评估的节点数。这

35、是一个常用人机游戏对抗的搜索算法。它的基本思想是根据上一层已经得到的当前最优结果，决定目前的搜索是否要继续下去。 -剪枝算法是对Minimax方法的优化，它们产生的结果是完全相同的，只不过运行效率不一样。3.4 博弈树搜索第三章 智能搜索of31753-剪枝技术这种方法的前提假设与Minimax也是一样的： 1）双方都按自己认为的最佳着法行棋。 2）对给定的盘面用一个分值来评估，这个评估值永远是从一方（搜索程序）来评价的，红方有利时给一个正数，黑方有利时给一个负数。（如果红方有利时返回正数，当轮到黑方走棋时，评估值又转换到黑方的观点，如果认为黑方有利，也返回正数，这种评估方法都不适合于常规的算

36、法描述）。 3）从我们的搜索程序（通常把它称为Max）看来，分值大的数表示对己方有利，而对于对方Min来说，它会选择分值小的着法。3.4 博弈树搜索第三章 智能搜索of31763-剪枝技术 -剪枝技术只能用递归来实现。这个思想是在搜索中传递两个值，第一个值是，即搜索到的最好值，任何比它更小的值就没用了，因为策略就是知道的值，任何小于或等于的值的合理着法都不会对整个局面的获胜率有更高的提高。 第二个值是，即对于对手来说最坏的值。这是对手所能承受的最坏的结果，因为我们知道在对手看来，他总是会找到一个对策不比更坏的。如果搜索过程中返回或比更好的值，那就够好的了，走棋的一方就没有机会使用这种策略。3.

37、4 博弈树搜索第三章 智能搜索of31773-剪枝技术 在搜索着法时，每个搜索过的着法都返回跟和有关的值，它们之间的关系非常重要，或许意味着搜索可以停止并返回。 如果某个着法的结果小于或等于，那么它就是很差的着法，因此可以抛弃。因为我前面说过，在这个策略中，局面对走棋的一方来说是以为评价的。3.4 博弈树搜索第三章 智能搜索of31783-剪枝技术 如果某个着法的结果大于或等于 ，那么整个节点就作废了，因为对手不希望走到这个局面，而它有别的着法可以避免到达这个局面。因此如果我们找到的评价大于或等于 ，就证明了这个结点是不会发生的，因此剩下的合理着法没有必要再搜索。 如果某个着法的结果大于但小于

38、，那么这个着法就是走棋一方可以考虑走的，除非以后有所变化。因此会不断增加以反映新的情况。有时候可能一个合理着法也不超过 ，这在实战中是经常发生的，此时这种局面是不予考虑的，为了避免这样的局面，我们必须在博弈树的上一个层局面中选择另外一个着法。3.4 博弈树搜索第三章 智能搜索of31793-剪枝技术 下图3-29中第四层的4的值为4比其父节点的值5要小，所以将其剩余的枝剪去。AlphaBeta剪枝示例图3.4 博弈树搜索第三章 智能搜索of31804蒙特卡洛树搜索 蒙特卡洛树搜索（Monte Carlo Tree Search）并不是一种模拟人的算法。而是通过随机的对游戏进行推演来逐渐建立一棵不对称的搜索树的过程。可以看成是某种意义上的强化学习，当然这一点学界还有一些争议。 我们经常会听到“蒙特卡洛树搜索”这个概念，事实上，蒙