详解Minimax算法与α-β剪枝

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

Minimax算法

称我方为MAX,对方为MIN,图示如下:

例如,对于如下的局势,假设从左往右搜索,根节点的数值为我方赢面(倒推值):

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

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

$\alpha-\beta$ 剪枝

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

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

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

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

初始化时,令 $\alpha = -\infty$ ,$\beta = +\infty$ ,也就是 $-\infty \leq v \leq +\infty$。到节点A时,由于左子节点的倒推值为3,而节点A是MIN节点,试图找倒推值小的走法,于是将 $\beta$ 值修改为3,这是因为3小于当前的 $\beta$ 值($\beta = +\infty$)。然后节点A的右子节点的倒推值为17,此时不修改节点A的 $\beta$ 值,这是因为17大于当前的 $\beta$ 值($\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节点,更新 $\beta = 3$,此时 $\alpha \geq \beta$,故可以剪去节点L的余下分支,由于节点L没有余下分支,所以此处并没有实际剪枝。然后,将节点L的倒推值设为3。

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

参考链接

AI

上一篇 Linux下实用图片批处理脚本
下一篇 memset的一个坑

添加新评论

*
*