我想知道如何使用 negamax 算法。我正在尝试用 C# 为游戏 mancala 编写代理。当给定游戏节点时，该算法会为您提供一个数字。
假设我的 AI 玩家想要移动。negamax 函数返回一个数字。所以它告诉我从那一刻起最好的移动得分是多少。我怎样才能使用这个号码？
如果轮到玩家 A，我尝试做出他可能的动作并检查每个动作的负最大值。但是，如果我先移动然后检查 negamax，那么当 negamax 运行时（假设我们仍然只有 1 级深），它将评估移动，然后下一步必须是玩家 B 的。
我对此感到非常困惑。当我看到 negamax 伪代码（例如在维基百科页面上）时，它说要尝试该玩家的动作。如果我这样做，它将返回最高分数，而不会告诉我哪个动作得到了那个分数。
应该如何使用 negamax？
这是一个有趣的。
这一切都是关于探索可能移动树中的每个节点。如果您使用 alpha-beta 修剪，您可以通过“修剪”（而不是评估）树的某些分支来使算法更有效。我将假设您没有使用修剪，而是要查看完整的树。
如果 Mancala 是一款非常简单的游戏，例如井字游戏，则无需“评估函数”即可实现算法。在井字游戏中，如果您玩出所有可能的动作，您将获得胜利、失败或平局。您将在那里实现一个负最大算法，而不考虑游戏的中间状态（即最后一步之前的任何移动），因为可能的移动数量非常有限，并且 AI 引擎将能够轻松计算所有一直到最后的可能性。
另一方面，在国际象棋中，“评估函数”（EF，以下简称）是必不可少的，因为这个星球上没有任何硬件可以计算出所有可能的国际象棋移动序列直到游戏结束。因此，大多数国际象棋 AI 会深入 12-14 层，然后评估结果位置，为后分配 8 分，为车分配 5 分，为主教或马分配 3 分，为棋子分配 1 分，然后为控制方格（控制中心方格更多点），国王安全等。
对于 Mancala，据我所知，它可能已经足够复杂以至于需要一个评估函数，但也许该评估函数会很简单，例如仍然拥有的种子数量，还为在一个先进的职位。（我查阅了 Wiki Mancala，看起来有很多可能的变体——我不确定你正在使用哪一个。）
因此，需要针对特定深度（即，使用所有可能的玩法直到游戏结束）并使用简单的 EF 来实现负最大算法。让我们假设您将实施看起来 5 步深度的 AI。negamax 的好处是它是完全对称的和零和的。换句话说，如果位置对 AI 的评估为 5，它对人类玩家的评估为 -5。如果人类玩家评估为 13，那么 AI 评估为 -13。这就是讨论的“单一数字”。考虑到这一切，人工智能算法看起来像这样（同样，没有修剪）：
1) 检查每个可能的 AI 动作
2）对于这些动作中的每一个，检查每个可能的对手反应
3) 对于每一个可能的反应，检查每一个可能的 AI 动作
4) 对于每一个可能的 AI 动作，检查每个可能的对手反应
5) 最后，针对每一个可能的对手反应，检查每一个可能的 AI 动作
现在我们已经达到了深度 5，并且您已经构建了具有 5 个级别的树，并且可能有数千或数百万个树的叶子（底层节点）。您以这样的方式编写代码，即每个节点都引用其父节点，并引用其所有子节点，以便您可以轻松地遍历树，从父节点到子节点然后返回。
一旦你正确设置了树，现在是时候实现 negamax 算法了，如下所示（让我们假设更高的分数对 AI 玩家更好）：
6) 对于每4级对手的反应，找出所有AI子动作中评价最高的，并修剪所有其他子动作。您正在确定您的 AI 从现在开始的第 5 步，以响应每个可能的从现在开始的第 4 次对手的反应。因此，现在每个 4 级响应都有一个假定的 5 级响应。现在您将您对第 5 级孩子所做的评估分数分配给第 4 级父级。这就是说，如果你达到了第 4 级对手的移动，人工智能将做出这个特定的第 5 级移动，并且棋盘将评估该分数。
7）接下来，您评估每个 3 级 AI 动作，并为每个动作在所有第 4 级对手动作中找到最低评价，修剪所有其他孩子，并分配第 4 级分数（来自最高的第 5 级）级节点）到第 3 级。您正在执行与第 6 步相同的操作，除了使用 LOWEST child score（b/c 这是 AI 移动而不是对手移动）。
8) 对第 2 级执行与第 6 步相同的操作，在所有 3rd-from-now 移动中找到最高评价，并将最高评价分配给第 2 级节点。
9) 对第 1 级执行与第 7 步相同的操作，在所有 2nd-from-now 移动中找到 LOWEST 评估，并将这些最低评估分配给 1st 级节点。
10) 查看所有 1 级节点，您的 AI 应该播放得分最高的节点。
显然，您不会将深度硬编码为 5，而是将其设为一个参数，并且您将使用递归（如 Wiki 中的内容）来完成此操作。要选择深度，请查看运行所需的时间，并将 n 设置为仍允许快速 AI 响应的最高深度。一旦你在这里建立了基础，你可以稍后添加修剪策略，这将通过不评估显然不是正确移动的整个树分支来实现更大的深度，但这是我为你布置的完整的、基本的 negamax。
祝你好运，编程应该很有趣！
Onemancat 给出了非常详尽的解释 - +1。
对你的问题的简短回答是 negamax 返回特定位置的分数，所以你要做的是在第一层玩每一个动作，为每个结果位置调用 negamax 来评估它，然后选择得分最高的动作作为结果。