用井字游戏理解 Minimax 算法-蒲公英云

Minimax 算法是博弈论中使用的一种回溯算法，用于在假设您的对手也在采取最佳行动的情况下确定最佳行动。Minimax算法的使用是一种不涉及机器学习的人工智能形式。本文解释了 Minimax 算法，并探讨了如何使用它来确定井字游戏中的下一步。

MiniMax 算法工作的条件

每个玩家采取交替动作
每个玩家都在发挥最佳状态以赢得胜利
游戏是战略性的，不依赖任何机会元素

最大化和最小化

为了将极小极大算法应用于游戏，一名玩家被指定为最大化玩家，另一名玩家被指定为最小化玩家。最大化玩家玩游戏以尝试获得最高分，而最小化玩家玩游戏以获得最低可能分数。在游戏的每一点，都可以评估棋盘以确定当前得分。如果最终得分为正结果，则最大化玩家获胜，如果得分为负结果，则最小化玩家获胜，如果结果为零，则游戏为平局。

最大化玩家评估最佳行动，以了解他们的对手也会做出他们可以做出的最佳行动。下一步是通过创建一个树结构并评估在最大化和最小化玩家之间交替的每个可能的移动并计算最终结果的分数来决定的。评估像国际象棋这样的游戏中的每一个动作很复杂，并且计算量可能非常昂贵，但是在像井字游戏这样的游戏中，可以评估每一个动作。

在一次移动中，最大化玩家将始终选择产生最大分数的路径。

最大化选择得分最高的移动

最小化玩家将始终选择产生最低分数的路径。

最小化选择得分最小的移动

具有四个级别的示例二叉树

游戏将有多个可供玩家使用的动作，并且在游戏结束之前可能还有多个回合。例如，在国际象棋中，估计一个玩家每回合可以有大约 35 步可用。在井字游戏中，第一个玩家有 9 个可用的动作，而第二个玩家在 9 个开局动作中的每一个都有 8 个可能的动作。

让我们假设一个游戏，其中每个玩家只有两个动作可用，并给出代表 4 个动作后棋盘评估的随机数集。在每个级别，玩家必须在两条可能的路径之间进行选择。假设这是最大化玩家回合。Minimax 算法将对所有路径执行深度优先遍历，以评估最佳移动。

游戏中只有两个动作可用的示例结果

最大化玩家将在 -60 和 12 之间选择 12，并将在 17 和 3 之间选择 17。然后，最小化玩家将在 12 和 17 之间选择 12。

左侧路径解析为 12 分

左侧路径解析为 11 分

所以最大化玩家选择的最佳路径是左路径。

最大化玩家的最佳选择是左侧路径

将 Minimax 应用于井字游戏

为了在井字游戏中使用 Minimax 确定最佳移动，我们指定一名玩家为最大化玩家，另一名玩家为最小化玩家。

假设X是最大化玩家，O是最小化玩家。最简单的评分策略之一是为包含 3 个X标记 [ X Wins ]的行指定加 1值，为包含 3 个O标记 [ O Wins ] 的行指定 -1 值，当比赛是平局。可以通过遵循每个可能的移动路径来评估当前玩家的下一步移动。每个玩家都可以预测他们的对手会同样做出他们最好的举动。玩家X正在寻找 1 的分数，而玩家O正在寻找 -1 的分数。

这有点像

“我知道你会怎么做”
“你知道我知道你会做什么”
“我知道你知道我知道你会做什么”
等等…

以 X 作为最大化玩家的 tic tac toe 的 Minimax 得分

最大化玩家的下一步动作示例

给定下面的示例棋盘，极小极大算法可用于确定玩家X（最大化玩家）的最佳移动。

给定一个带有 X 移动的 tic tac toe board 示例

X有三个可用的方格来放置令牌。这些中的第一个和第三个结果是+1的分数， X立即获胜并结束游戏。第二个结果是游戏继续并切换到玩家O的回合。玩家O有两种选择，一种是O三连胜，得分为-1。玩家O将始终选择最小选项，因此它会向上滚动到-1层。所以X的下一步是在+1 和-1和+1之间进行选择将被选中。当有两个价值相等的选项时，可以选择第一个。

这个过程解释了为什么 Minimax 是一种回溯算法。采取每一个可能的举动来确定这是否是获胜的举动，然后回溯并放弃非获胜的举动。

从井字游戏开始就可以遵循相同的过程，但由于有 9 个初始选项，每个选项有 8 秒选项，为此绘制图表将具有挑战性。

井字游戏中 X 玩家的选项

Minimax 算法的伪代码

我将在下一篇文章中实现 Swift 中的 minimax 算法，让玩家可以对着电脑玩井字游戏。这是算法的伪代码。对于可以设置深度以限制递归次数的更复杂的游戏，这可能会有所不同，但对于井字游戏，这不是必需的。

function minimax_recursive(node, isMaximising)
{
    If game is over
        return board score
    If isMaximising
        bestValue = negInfinity
        For each valid move on the board
            value = minimax_recursive(node, false)
            bestValue = max(value, bestValue)
        return bestValue
    Else // Minimising
        bestValue = posInfinity
        For each valid move on the board
            value = minimax_recursive(node, true)
            bestValue = min(value, bestValue)
        return bestValue
}