博弈树剪枝算法例题,通俗解释剪枝算法

阅读本章之前,请参阅上一篇文章《Minimax算法及实例分析》

因为Minimax算法存在计算复杂性的大问题。 所需搜索的节点数随最大深度呈指数函数增长,算法的效果往往与深度相关,因此算法的效果受到很大限制。

alpha-beta剪枝是对Minimax的补充和改进。 通过采用alphabeta剪枝,无需构建和搜索最大深度d内的所有节点。 在构建过程中,如果当前结构再往下移动也找不到更好的解,则停止该结构以下的搜索,即剪枝。

阿尔法-贝塔基于如下朴素的思想:始终记住当前已知的最佳选择,从当前结构进行搜索时,如果找不到比已知的最佳解更好的解,则停止对其结构分支的搜索剪枝),追溯到父节点继续搜索。

alpha-beta算法可看作变种的极大极小,基本方法是从根节点以深度优先的方式构造结构树,在构造每个节点时读取该节点的alpha和beta两个值。 阿尔法表示搜索当前节点时已知的最佳选择的下界,贝塔表示从该节点搜索下界的最坏结果的上界。 因为假设对方将情况导向最坏的结局之一,所以如果贝塔小于阿尔法,则表示从中无论最终结局是哪一个,其上限价值都将低于已知的最优解,也就是说,从这里开始向下找不到更好的解

上面的示例还介绍了alpha-beta剪枝算法的工作原理。 从根节点开始,详细说明使用alpha-beta的每个步骤。

根节点的alpha和beta分别被初始化为,和。 深度优先搜索的第一个子节点不是叶节点,所以阿尔法和贝塔是从父节点继承的,分别为,搜索的第三层次的第一个子节点与上述相同。 搜索第四个层次,到达叶的节点,利用评价函数得到的该节点的评价值为1。

1.8em; text-align:center”>

此叶节点的父节点为max节点,因此更新其alpha值为1,表示此节点取值的下界为1。

再看另外一个子节点,值为20,大于当前alpha值,因此将alpha值更新为20。此时第三层最左节点所有子树搜索完毕,作为max节点,更新其真实值为当前alpha值:20。

由于其父节点(第二层最左节点)为min节点,因此更新其父节点beta值为20,表示这个节点取值最多为20。

搜索第二层最左节点的第二个孩子及其子树,按上述逻辑,得到值为50(注意第二层最左节点的beta值要传递给孩子)。由于50大于20,不更新min节点的beta值。

搜索第二层最左节点的第三个孩子。当看完第一个叶子节点后,发现第三个孩子的alpha=beta,此时表示这个节点下不会再有更好解,于是剪枝。

继续搜索B分支,当搜索完B分支的第一个孩子后,发现此时B分支的alpha为20,beta为10。这表示B分支节点的最大取值不会超过10,而我们已经在A分支取到20,此时满足alpha大于等于beta的剪枝条件,因此将B剪枝。并将B分支的节点值设为10,注意,这个10不一定是这个节点的真实值,而只是上线,B节点的真实值可能是5,可能是1,可能是任何小于10的值。但是已经无所谓了,反正我们知道这个分支不会好过A分支,因此可以放弃了。

在C分支搜索时遇到了与B分支相同的情况。因此讲C分支剪枝。

此时搜索全部完毕,而我们也得到了这一步的策略:应该走A分支。

可以看到相比普通Minimax要搜索18个叶子节点相比,这里只搜索了9个。采用Alpha-beta剪枝,可以在相同时间内加大Minimax的搜索深度,因此可以获得更好的效果。并且Alpha-beta的解和普通Minimax的解是一致的。

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注