$\alpha-\beta$ 剪枝算法

The minimax algorithm is a way of finding an optimal move in a two player game. Alpha-beta pruning is a way of finding the optimal minimax solution while avoiding searching subtrees of moves which won’t be selected. In the search tree for a two-player game, there are two kinds of nodes, nodes representing your moves and nodes representing your opponent’s moves. Nodes representing your moves are generally drawn as squares (or possibly upward pointing triangles):

博弈的基本概念

零和博弈 有残缺信息的, 确定性的, 轮流的(回合的), 两个参与者的博弈

有残缺信息 单方都能够查问本场游戏的残缺历史记录

零和 单方的 效用值 在游戏完结时的代数和为0.

效用值 utival 是游戏完结时用于表征较量输赢的变量, 如围棋中黑方 utival = 1, 白方 utival = -1, 可示意黑方获胜. 在博弈树上, 若根节点为 MAX 节点, 则叶节点上的值即为 MAX 方的效用值.

极小极大算法

极大值搜寻 对于以后场面(父节点), 计算所有可能的落子点的场面得分, 选取其中得分最大者(最大子节点), 作为落子点.

极小极大搜寻 设我方为 MAX 方, 对方为 MIN 方, utival 为效用值. 假如单方都同样地足够理智. MAX 方的指标是使效用值 utival 最大化, 而 MIN 方的指标是使 utival 最小化, 两方轮流落子.

当初咱们从下到上倒着思考. 思考顶点为 MAX , 深度为 n, 从上到下各层顺次为 MAX1, MIN2, MAX3, MIN4, …, MIN_n 的博弈树. 这棵树 MIN_n 层之下全为终局叶节点.

思考 MIN_n 层结点 Ni , Ni 的子节点全为终局 (叶) 节点. 此时是 MIN 方的最初一步, 因而其肯定会抉择效用值最小的叶节点来落子, 因而在零和博弈的状况下结点 Ni 的下一步是确定的. 也就是说, MIN_n 层的全副结点的下一步都是可确定的. 咱们将结点 Ni 的极小极大值 minimax 保留在 Ni 上. 同理, 对于 MAX_(n-1) 层的节点 Mi, 下一步也是确定的. 对其所有子节点取最大值, 即为 Mi 的 minimax 值, 保留在 Mi 上. 顺次类推, 直到计算出根节点 MAX1 的 minimax 值.

极小极大算法应用了简略的递归算法, 计算根节点的每个后继结点的极大极小值. 算法自上而下始终后退到树的叶节点, 而后将极小极大值逐层回传. 将极小极大值回传的过程中, 记录落子地位, 也就是记录子节点的索引. 最初, 咱们失去了根节点处的落子策略.

python 实现

class Tree:
    def __init__(self, val, childs=None, maxormin='max'):
        self.val = val
        self.childs = childs  # list
        self.maxormin = maxormin


    def is_leaf(self):  # 以后结点是否是叶节点
        return self.childs is None

    def Max(self):  # 返回子节点的最大值
        return max([child.val for child in self.childs])

    def argmax(self):  # 返回子节点最大值地位的索引
        return [child.val for child in self.childs].index(self.Max())

    def Min(self):  # 返回子节点的最大值
        return min([child.val for child in self.childs])

    def argmin(self):  # 返回子节点最大值地位的索引
        return [child.val for child in self.childs].index(self.Min())

    def minimax(self):
        inf = 999999999
        choices = dict()  # 记录每步的抉择, choises[tree] = index
        arg= -1  # 寄存最大值或最小值的索引
        def max_value(tree=self):
            if tree.is_leaf():
                return tree.val
            nonlocal arg
            v = -inf
            for i, child in enumerate(tree.childs):
                minval = min_value(child)
                if minval > v:
                    v = max(v, minval)
                    arg = i
            choices[tree] = arg
            # print(v, choices)

            return v

        def min_value(tree=self):
            if tree.is_leaf():
                return tree.val
            nonlocal arg
            v = inf
            for i, child in enumerate(tree.childs):
                maxval = max_value(child)
                if maxval < v:
                    v = min(v, maxval)
                    arg = i
            choices[tree] = arg
            # print(v, list(choices.keys())[0].childs, self)
            return v

        if self.maxormin == 'max':
            return max_value(), choices[self]
        else:
            return min_value(), choices[self]


B = Tree(0, [Tree(3), Tree(12), Tree(8)], 'min')
C = Tree(0, [Tree(4), Tree(4), Tree(6)], 'min')
D = Tree(0, [Tree(14), Tree(5), Tree(2)], 'min')
A = Tree(0, [B, C, D], 'max')
E = Tree(0, [A, Tree(1)], 'min')

print(E.minimax())

未完待续

参考资料

1. <<CS 161 Recitation Notes – Minimax with Alpha Beta Pruning>>

   http://web.cs.ucla.edu/~rosen…

2. 【课程】数据结构与算法 Python 版 - 北京大学 - 陈斌 -19- 棋类的决策树搜寻

   https://www.bilibili.com/vide…

3. 博弈树 alpha-beta 剪枝搜寻的五子棋 AI

   https://www.jianshu.com/p/837…