博弈树的搜索算法(二)

Stubborn

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

tiger20100907

无条件支持楼主ing......