图中的剪枝过程被称为什么剪枝

图中的剪枝过程被称为Alpha剪枝。

Alpha-beta剪枝是一种搜索算法，用以减少极小化极大算法（Minimax算法）搜索树的节点数。这是一种对抗性搜索算法，主要应用于机器游玩的二人游戏（如井字棋、象棋、围棋）。当算法评估出某策略的后续走法比之前策略的还差时，就会停止计算该策略的后续发展。该算法和极小化极大算法所得结论相同，但剪去了不影响最终决定的分枝。

alpha-beta算法原理：

alpha-beta剪枝算法是基于极大极小搜索算法的。极大极小搜索策略是考虑双方对弈若干步之后，从可能的步中选一步相对好的走法来走，在有限的搜索范围内进行求解，可以理解为规定一个有限的搜索深度。

为此要定义一个静态估计函数f，以便对棋局的势态做出优劣的估计，这个函数可根据棋局的优劣势态的特征来定义。这里规定，MAX代表程序方，MIN代表对手方，P代表一个棋局（即一个状态）。有利于MAX的势态，f(p)取正值，有利于MIN的势态，f(p)去负值，势态均衡，f(p)取零。

极大极小过程，以及阿尔法-贝塔剪纸。极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的α-β剪枝搜索方法，就是从这一方法发展而来的。

首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜。假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。会下棋的读者都知道，在只看一步的情况下最好的棋，从全局来说不一定就好，还可能很不好。因此为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋。

想一想人是如何下棋的呢？人实际上采用的是一种试探性的方法。首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的回应......这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。初学者可能只能看一、两个轮次，而高手则可以看几个，甚至十几个轮次。

极小极大搜索方法，模拟的就是人的这样一种思维过程。当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。

在图3.5所示的例子中，假定搜索深度为2，D～J是7个叶节点，在它们下边括号中的数字是这些节点的评价函数值（假定可以计算得到）。A、B、C是三个极小节点，它们分别取各自子节点最小值为自己的值，得到三个节点的值分别为-6、-2和-4。s是极大节点，从A、B、C三个节点的值中取最大值，得到-2。由于-2来自于节点B，所以搜索的结果是应选择B作为我方的走步。对于我方来说，-2并不是一个好的结果，但却是在对方不犯错误的情况下，对我方最有利的结果。因为从图中可以看出，如果选择A为我方的走步，如果对方回应D的话，我方可以得到评价值9，固然对我方有利。但是如果对方是一个高手的话，他一定回选择E，而不是D。在这种情况下，我方只能得到-6，结果岂不是更差。因此，极小极大过程是一种假定对手每次回应都正确的情况下，如何从中找出对我方最有利的走步的搜索方法。

值得注意的是，不管设定的搜索深度是多少层，经过一次搜索以后，只决定了我方一步棋的走法。等到对方回应一步棋之后，需要在新的棋局下重新进行搜索，来决定下一步棋如何走。极小极大搜索策略是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在有限的搜索深度范围内进行求解。为此要定义一个静态估计函数f，以便对棋局的势态（节点）作出优劣估值，这个函数可根据势态优劣特征来定义（主要用于对端节点的"价值"进行度量）。一般规定有利于MAX的势态，f（p）取正值，有利于MIN的势态，f（p）取负值，势均力敌的势态，f（p）取0值。若f（p）＝＋∞，则表示MAX赢，若f（p）＝－∞，则表示MIN赢。下面的讨论规定：顶节点深度d＝0，MAX代表程序方，MIN代表对手方，MAX先走。

图3.5是一个表示考虑两步棋的例子，图中端节点给出的数字是用静态函数f（p）计算得到，其他节点不用f（p）估计，因为不够精确，而应用倒推的办法取值。例如A、B、C是MIN走步的节点，MAX应考虑最坏的情况，故其估值应分别取其子节点f（p）估值中最小者，而s是MAX走步的节点，可考虑最好的情况，故估值应取A、B、C值中的最大者。这样求得f（s）＝－2，依此确定了相对较优的走步应是走向B，因为从B出发，对手不可能产生比f（s）＝－2更差的效果。实际上可根据资源条件，考虑更多层次的搜索过程，从而可得到更准确的倒推值，供MAX选取更正确的走步。当用端节点的静态估计函数f（p）求倒推值时，两位选手应采取不同的策略，从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。

beta剪枝是相对于极大极小节点而言。

算法原理:

alpha-beta剪枝算法是基于极大极小搜索算法的。极大极小搜索策略是考虑双方对弈若干步之后，从可能的步中选一步相对好的走法来走，在有限的搜索范围内进行求解，可以理解为规定一个有限的搜索深度。

为此要定义一个静态估计函数f，以便对棋局的势态做出优劣的估计，这个函数可根据棋局的优劣势态的特征来定义。这里规定，MAX代表程序方，MIN代表对手方，P代表一个棋局（即一个状态）。有利于MAX的势态，f(p)取正值，有利于MIN的势态，f(p)去负值，势态均衡，f(p)取零。

定义极大层的下界为alpha，极小层的上界为beta，alpha-beta剪枝规则描述如下：

（1）alpha剪枝。若任一极小值层结点的beta值不大于它任一前驱极大值层结点的alpha值，即alpha(前驱层) >= beta(后继层)，则可终止该极小值层中这个MIN结点以下的搜索过程。这个MIN结点最终的倒推值就确定为这个beta值。

（2）beta剪枝。若任一极大值层结点的alpha值不小于它任一前驱极小值层结点的beta值，即alpha(后继层) >= beta(前驱层)，则可以终止该极大值层中这个MAX结点以下的搜索过程，这个MAX结点最终倒推值就确定为这个alpha值。

---