beta剪枝是相对于什么结点而言

Question

如题所述

Answer 1

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值。