博弈树的搜索算法(二)
本帖最后由 Stubborn 于 2022-4-24 10:10 编辑AlphaBeta剪枝算法
AlphaBeta剪枝算法是对MaxMin算法方法的优化，它们产生的结果是完全相同的，它们的思想也是一样的，但是AlphaBeta剪枝算法多了一个核心思想：如果你已经有一个不太坏的选择了，那么当你要作别的选择，并知道它不会更好时，你没有必要确切地知道它有多坏。只要你能证明它不比最好的选择更好，你就可以完全抛弃它。
如果你不能理解上面的话，那么尝试理解下面的小游戏：
你的死敌面前有两个口袋，他和你打赌赌输了，因此他必须从中给你一样东西，而挑选规则却非常奇怪：
[*]两个口袋里都有几件物品，你能取其中的一件
[*]你来挑这件物品所在的口袋，而他来挑这个口袋里的物品。
[*]你一次只能找一只口袋，在找口袋时一次只能从里面摸出一样东西。
很明显，你选中一个口袋，你的死敌势必会从口袋挑最差的给你。当你挑选完成其中一个口袋，你发现，这个口袋价值最差的物品是20元现金，那么你现在已经有了一个不太坏的选择。当你再去翻找另外一个口袋，突然发现这个口袋里面有一条臭鱼，你觉得这个臭鱼比20元现金价值要差，那么你还会浪费时间继续翻找这个口袋里面的剩下物品吗？
Python代码
def AlphaBetaAlgorithm(int: depth, flag,MaxValue, MinValue)：
#定义递归出口,到达既定深度，或者是游戏结束状态，返回当前游戏状态的评分
if (depth || GameOver)：
return EvaluationFunction(Gs)
# 测试所有合法的着点
for Move in GeneratorMoves:
# 执行着点
MakeNextMove()
# 交换身份，继续，
score = AlphaBetaAlgorithm(depth-1, falg, alpha, beta)
# 撤销着点
UnMakeNextMove()
# 如果当前是Max走步落子
if flag is Max:
MaxValue = max(score, MaxValue)
# 在口袋挑物品，发现臭鱼，这个口袋不再搜索。
if MaxValue >= MinValue:
return MinValue
else:
MinValue = min(socre, MinValue)
if flag is Max:
return MaxValue
else:
return MinValue
无条件支持楼主ing......
页:
[1]