前言

本文属于搬运内容，原作者：Dorian Lazar （Salute！）

因为最近开始玩Kaggle的象棋竞赛，刚好就了解一下这样的传统算法，基础打牢，为了更好的向上攀岩！

简介

让我们假设你和朋友一起玩一个游戏。衡量“你在游戏中的表现好坏”的标准是一个数字分数，当你比朋友更接近“赢得游戏”时，分数增加；而当朋友比你更接近“赢得游戏”时，分数减少。在这种情况下，你可以将自己看作是试图最大化分数，而将你的朋友看作是试图最小化分数。

我们可以设计一个算法，能够在这种游戏中做出良好的决策并获胜。我们可以通过以下方式来建模上述情况：我们将有两个实体（函数）互相调用；一个试图最大化分数，另一个试图最小化分数。基本上，这两个函数将模拟两个玩家。

这个算法也是一个很好的AI例子，但它并不是机器学习（ML）。有些人会混淆认为AI等同于ML；实际上，ML是AI的一个子集。有些AI技术并不涉及机器学习。极小化算法（Minimax）就是这样一个算法，它使计算机表现得很智能，但它并没有学习任何东西。尽管如此，它在许多游戏中仍然非常有效。

极小化算法（Minimax Algorithm）

如果我们把游戏看作是这两个玩家Max和Min交替进行，那么我们可以将游戏表示为一个决策树。让我们来看一个非常简单的例子：

每个树中的节点（除了终端节点）表示在游戏中此时应该做出的决策。我们决定采取哪个行动。在这个例子中，我们只有两种选择，但通常，我们可以有任意数量的选择，而这个数量可能会根据游戏状态在不同节点之间变化。

顶部节点（深度为0的节点）表示游戏的当前状态。在这里，我们需要决定游戏的下一步行动。在这个位置，Max是先手玩家，因为他是希望最大化分数的玩家。Max并不是仅仅根据他从当前状态可以到达的下一个游戏状态来做决定，而是这样思考：

“我做了其中一个动作后，我的对手Min会怎么做？”

于是，Max会问Min：“如果我选择左边，你会做什么？”然后再问：“如果我选择右边，你会做什么？”

当Max找出Min会做什么后，他会选择那个能够给他带来最大分数的分支。

但是等等，Min又会怎么做呢？他会如何做出决策来最小化分数？

他将采取和Max一样的策略。Min会调用Max，问Max如果自己选择某个动作，Max会怎么做。

然后Min会选择与Max最大化分数的选择相反的那个动作，即最小化分数。

这个过程就这样继续……每个玩家都会调用对方，不断递归地构建一个大的决策树，直到他们到达终端状态。

最终状态是什么？

终端状态应该是游戏结束的状态，但通常这种做法计算开销很大；让算法探索所有可能的动作直到游戏结束可能需要非常长的时间。因此，我们设定一个最大深度。当游戏结束或达到最大深度时，游戏状态将被视为终端状态。

在上述示例中，终端状态是底部的节点（深度为2）。

最终会发什么？

无论哪个玩家到达终端状态，无论是Max还是Min，都无法再应用之前的策略：调用另一个玩家来帮助做决策。

现在，在终端节点，我们需要计算每个终端状态的游戏得分。

在某些游戏中，这可能并不那么明显，但至少我们需要根据游戏的状态估计分数。

在我们上面的例子中，终端状态的得分是底部的那些数字：1、2、3和4。

Max玩家在这一最后级别上要做的唯一事情就是将这些分数返回给之前级别的Min玩家。

继续描述树的生成过程

在终端状态完成后，我们的决策树将如下所示：

Min玩家将做出的选择用箭头标出。分数从深度2的节点向深度1的节点传播（这是Min玩家的层级）。

接下来，了解了深度1上的决策后，我们让Max玩家在深度0（最顶部的节点）做出决定：

这意味着，在当前游戏状态下，最优的行动是通过顶部节点的右边缘进行的，并且我们将获得至少3分的得分。

我说“至少”是因为这个算法假设Max和Min总是做出最佳选择。但实际上，如果我们的对手比Min更弱，我们可能会得到更好的得分。

如何清晰地表达这个算法？

这是一份虚拟代码：

上述的树形图与虚拟代码只是为了直观描述算法。计算机并不需要显式地构建这样的树。我们只需要两个函数：maximize和minimize，它们会互相调用。

下面是一个描述上述算法的草图：

def maximize(state, depth):
    if depth == 0 or game_over(state):
        return (None, eval(state))  # 返回当前状态的估计分数
    best_move = None
    best_score = -infinity
    for move in possible_moves(state):
        new_state = make_move(state, move)
        _, score = minimize(new_state, depth - 1)
        if score > best_score:
            best_move = new_state
            best_score = score
    return best_move, best_score

def minimize(state, depth):
    if depth == 0 or game_over(state):
        return (None, eval(state))  # 返回当前状态的估计分数
    best_move = None
    best_score = infinity
    for move in possible_moves(state):
        new_state = make_move(state, move)
        _, score = maximize(new_state, depth - 1)
        if score < best_score:
            best_move = new_state
            best_score = score
    return best_move, best_score

def decision(state, depth):
    move, _ = maximize(state, depth)
    return move

def eval(state):
    # 估算当前状态的分数
    return state.score

在这个代码片段中：

• maximize()函数返回一个元组，第一个位置是最大化分数的下一状态，第二个位置是根据该状态估计的得分。

• minimize()函数也返回一个类似的元组。

• decision()函数接收当前游戏状态作为输入，返回为了最大化分数应该选择的状态。

• eval()函数估算给定状态的分数。

Minimax算法的α-β剪枝

随着深度的增加，我们的玩家将变得更强。但如果我们为算法设置较大的深度，它可能会需要很长时间。因此，我们应该选择一个最大深度，它仍然符合我们的时间需求。我们能否让这个算法更快，从而可以使用更大的深度值，同时遵守时间约束？

为了解决这个问题，我们可以使用**α-β剪枝（Alpha-Beta Pruning）**来优化Minimax算法。α-β剪枝通过剪去一些不必要的分支来减少计算量，从而提高算法的效率。基本思想是在搜索树中进行剪枝时，如果已经发现某个分支的最优解比当前节点的最优解差，就不再继续搜索这个分支。这样可以大大减少计算量，尤其在搜索较大深度时。

让我们看以下这个例子：

为了决定顶部节点的行动，我们是否需要评估树中的所有节点？

α-β剪枝是一种可以用来改进Minimax算法的策略，通过忽略树中一些我们提前知道不会帮助我们做出最优决策的分支。α-β剪枝的名字来自于该算法中使用的两个参数：α和β。

那么，这个方法是如何工作的呢？

每次我们确定一个节点的得分时，我们也会将它向上传播到树中的父节点，并用它来设置父节点结果的上下界。

例如，在我们的树中，如果我们从左到右开始评估节点，在确定最左侧终端节点（其得分为4）后，我们就知道父节点的结果不会大于4。因为父节点是一个Min节点，而如果我们已经有了4，父节点就无法选择比这个更大的值。

但在这一点上，这个信息并没有太大帮助。我们继续进行，并看看会发生什么。我们评估下一个终端节点，发现父节点的值为3，而顶部节点的值不会小于3。这一信息将会有帮助。

如果我们继续评估节点，我们会发现终端节点的得分为2，这意味着它的父节点应该 ≤ 2。

现在，我们是否还需要评估最后一个节点？不需要。我们已经知道，如果顶部节点选择左分支，它至少能得到3分。而从右分支，我们无法获得超过2分的结果。因此，从此时起，我们可以忽略右分支。

在这个小示例中，跳过一个终端节点看起来并没有带来太大的改进。但在一个更大的树中，这样的节点可能会包含一个非常大的子树。并且请注意，在这里我们只跳过了一个兄弟节点，因为这是那个分支中唯一剩下的节点。如果还有更多剩余节点，我们会跳过它们。例如，如果右分支有终端节点2、1和0，那么在评估完2之后，我们就可以跳过1和0。

另外，跳过的节点数将取决于终端节点的顺序。你可能注意到，在这个例子中，我将得分从1、2、3、4反转为4、3、2、1。这不是随便的选择。当得分按升序排列时，那是最坏的情况，在这种情况下不会进行任何剪枝。但在实际中，出现这种最坏的顺序的几率很小。平均而言，α-β剪枝使得Minimax算法在相同的时间内可以深入探索几乎两倍的树深度。

如何表达剪枝优化后的算法：

Alpha是所有（直接或间接）父级Max节点中的最大下界，而Beta是所有（直接或间接）父级Min节点中的最小上界。在maximize函数中，在遍历子节点时，我们将alpha值更新为迄今为止找到的最大得分，如果这个最大得分大于beta，我们就知道有某个父级Min节点不会选择当前分支，因此停止探索剩余的子节点。minimize函数中的情况也类似。

决策函数中的正负无穷（首次调用maximize时）意味着我们从没有任何得分限制的状态开始算法。

因此，minimax算法是一个相对简单的算法，适用于简单的游戏（低分支因子）。它也是一个不涉及机器学习的AI的好例子。

以下是Python伪代码：

def maximize(state, alpha, beta):
    if is_terminal(state):
        return evaluate(state), None

    max_score = -infinity
    best_move = None

    for child in get_children(state):
        score, _ = minimize(child, alpha, beta)
        if score > max_score:
            max_score = score
            best_move = child

        # Update the alpha value
        alpha = max(alpha, max_score)

        # If alpha is greater than or equal to beta, prune the remaining branches
        if alpha >= beta:
            break

    return max_score, best_move


def minimize(state, alpha, beta):
    if is_terminal(state):
        return evaluate(state), None

    min_score = infinity
    best_move = None

    for child in get_children(state):
        score, _ = maximize(child, alpha, beta)
        if score < min_score:
            min_score = score
            best_move = child

        # Update the beta value
        beta = min(beta, min_score)

        # If alpha is greater than or equal to beta, prune the remaining branches
        if alpha >= beta:
            break

    return min_score, best_move


def evaluate(state):
    # Define how to evaluate the game state
    pass


def is_terminal(state):
    # Define a terminal state condition
    pass


def get_children(state):
    # Define how to generate child states from the current state
    pass

解释：

• Alpha和Beta：alpha是所有Max节点的最大下界，beta是所有Min节点的最小上界。

• maximize函数：它尝试从当前状态出发，通过遍历所有子节点来最大化得分，并且在遍历过程中，更新alpha值。如果alpha超过了beta，我们就停止继续探索当前节点的其他子节点，因为父级Min节点将不会选择该分支。

• minimize函数：它类似于maximize，但目标是最小化得分，并且在遍历过程中更新beta值。

• is_terminal：用于判断当前状态是否为终止状态（例如，游戏是否结束）。

• evaluate：用于评估当前状态的得分。每个游戏的评估方式不同，可以根据具体的游戏规则来实现。

• get_children：用于生成当前状态的所有可能子状态。

剪枝：

• 在每次计算Max节点的得分时，如果发现alpha值大于等于beta，就可以停止计算其他子节点，因为可以确定父节点（Min节点）不会选择当前分支，从而避免了不必要的计算。

希望你在本次阅读中有所收获！

原文链接