跳到主要内容

详解Minimax算法与α-β剪枝

· 阅读需 9 分钟

在局面确定的双人对弈里，常采用博弈树搜索。我方追求更大的赢面，而对方会设法降低我方的赢面。由于局面确定，因此可以对赢面进行评估。我方往较大赢面的方向走，同时考虑对方的走法。由于对方的走法不确定，就假设对方会选择最大程度降低我方赢面的方向走，我方应规避那些对方可以大幅降低我方赢面的走法。

Minimax算法​

称我方为MAX，对方为MIN，图示如下：

例如，对于如下的局势，假设从左往右搜索，根节点的数值为我方赢面（倒推值）：

我方应选择中间的路线。因为，如果选择左边的路线，最差的赢面是3；如果选择中间的路线，最差的赢面是15；如果选择右边的路线，最差的赢面是1。虽然选择右边的路线可能有22的赢面，但对方也可能使我方只有1的赢面，假设对方会选择使得我方赢面最小的方向走，那么经过权衡，显然选择中间的路线更为稳妥。

实际上，在看右边的路线时，当发现赢面可能为1就不必再去看赢面为12、20、22的分支了，因为已经可以确定右边的路线不是最好的。这个过程就是剪枝，可以避免不必要的计算。

α−β\alpha-\beta 剪枝​

例如，对于如下的局势，假设从左往右搜索：

若已知某节点的所有子节点的倒推值，则可以算出该节点的倒推值：对于MAX节点，取最大倒推值；对于MIN节点，取最小倒推值。

若已知某节点的部分子节点的倒推值，虽然不能算出该节点的倒推值，但可以算出该节点的倒推值的取值范围。同时，利用该节点的倒推值的取值范围，在搜素其子节点时，如果已经确定没有更好的走法，就不必再搜索剩余的子节点了。

记 vv 为节点的倒推值，且 α≤v≤β\alpha \leq v \leq \beta，即 α\alpha 为最大下界， β\beta 为最小上界。当 α≥β\alpha \geq \beta 时，该节点剩余的分支就不必继续搜索了（也就是可以进行剪枝了）。注意，当 α=β\alpha = \beta 时，也可以剪枝，这是因为不会有更好的结果了，但可能有更差的结果。

初始化时，令 α=−∞\alpha = -\infty ，β=+∞\beta = +\infty ，也就是 −∞≤v≤+∞-\infty \leq v \leq +\infty。到节点A时，由于左子节点的倒推值为3，而节点A是MIN节点，试图找倒推值小的走法，于是将 β\beta 值修改为3，这是因为3小于当前的 β\beta 值（β=+∞\beta = +\infty）。然后节点A的右子节点的倒推值为17，此时不修改节点A的 β\beta 值，这是因为17大于当前的 β\beta 值（β=3\beta = 3）。之后，节点A的所有子节点搜索完毕，即可计算出节点A的倒推值为3。

节点A是节点B的子节点，计算出节点A的倒推值后，可以更新节点B的倒推值范围（也就是 α\alpha 和 β\beta 值）。由于节点B是MAX节点，试图找倒推值大的走法，于是将 α\alpha 值修改为3，这是因为3大于当前的 α\alpha值（α=−∞\alpha = -\infty）。之后搜索节点B的右子节点C，并将节点B的 α\alpha 和 β\beta 值传递给节点C。

对于节点C，由于左子节点的倒推值为2，而节点C是MIN节点，于是将 β\beta值修改为2。此时 α≥β\alpha \geq \beta，故节点C的剩余子节点就不必搜索了，因为可以确定，通过节点C并没有更好的走法。然后，节点C是MIN节点，将节点C的倒推值设为 β\beta ，也就是2。由于节点B的所有子节点搜索完毕，即可计算出节点B的倒推值为3。

计算出节点B的倒推值后，节点B是节点D的一个子节点，故可以更新节点D的倒推值范围。由于节点D是MIN节点，于是将 β\beta 值修改为3。然后节点D将 α\alpha 和 β\beta 值传递给节点E，节点E又传递给节点F。对于节点F，它只有一个倒推值为15的子节点，由于15大于当前的 β\beta 值，而节点F为MIN节点，所以不更新其 β\beta 值，然后可以计算出节点F的倒推值为15。

计算出节点F的倒推值后，节点F是节点E的一个子节点，故可以更新节点E的倒推值范围。节点E是MAX节点，更新 α\alpha，此时 α≥β\alpha \geq \beta，故可以剪去节点E的余下分支。然后，节点E是MAX节点，将节点E的倒推值设为 α\alpha ，也就是15。此时，节点D的所有子节点搜索完毕，即可计算出节点D的倒推值为3。

计算出节点D的倒推值后，节点D是节点H的一个子节点，故可以更新节点H的倒推值范围。节点H是MAX节点，更新 α\alpha。然后，按搜索顺序，将节点H的 α\alpha 和 β\beta 值依次传递给节点I、J、K。对于节点K，其左子节点的倒推值为2，而节点K是MIN节点，更新 β\beta，此时 α≥β\alpha \geq \beta，故可以剪去节点K的余下分支。然后，将节点K的倒推值设为2。

计算出节点K的倒推值后，节点K是节点J的一个子节点，故可以更新节点J的倒推值范围。节点J是MAX节点，更新 α\alpha，但是，由于节点K的倒推值小于 α\alpha，所以节点J的 α\alpha 值维持3保持不变。然后，将节点J的α\alpha 和 β\beta 值传递给节点L。由于节点L是MIN节点，更新 β=3\beta = 3，此时 α≥β\alpha \geq \beta，故可以剪去节点L的余下分支，由于节点L没有余下分支，所以此处并没有实际剪枝。然后，将节点L的倒推值设为3。

此时，节点J的搜索子节点搜索完毕，计算出节点J的倒推值为3。由于节点J是节点I的子节点，故可以更新节点I的倒推值范围。节点I是MIN节点，更新 β=3\beta = 3，此时，α≥β\alpha \geq \beta，故可以剪去节点I的余下分支。然后，将节点I的倒推值设为3。

参考链接​