我想了解如何使用负极大算法。我正在尝试用C#编写一个曼卡拉游戏的智能体。这个算法在给定一个游戏节点时会返回一个单一的数字。

假设我的AI玩家想要进行一次移动。负极大函数返回一个单一的数字。所以它告诉我从那个点开始最佳移动的分数是多少。我如何使用这个一个数字呢？

如果是玩家A的回合，我尝试了他的所有可能的移动，并检查每个移动的负极大值。然而，如果我先进行移动然后再检查负极大值，那么当负极大值在运行时（假设我们仍然只深入一层），它会评估这个移动，然后下一个移动将必须是玩家B的。

我对此感到非常困惑。当我看到维基百科上的负极大伪代码时，它说要尝试那个玩家的移动。如果我这样做，它会返回最高分数，但不会告诉我哪个移动获得了那个分数。

负极大算法应该如何使用呢？

回答：

这是一个有趣的问题。

这完全是关于探索可能移动树中的每个节点。如果你使用alpha-beta剪枝，你可以通过“剪枝”（不评估）树的一些分支来提高算法的效率。我将假设你不使用剪枝，并且会查看整个树。

如果曼卡拉是一个非常简单的游戏，比如井字游戏，你可以实现算法而不需要“评估函数”。在井字游戏中，如果你玩出所有可能的移动，你会得到胜利、失败或平局。在那里，你会实现一个负极大算法，而不需要考虑游戏的中间状态（即，最后一步之前的任何移动），因为可能的移动非常有限，AI引擎可以轻松地计算出所有可能性直到游戏结束。

另一方面，在国际象棋中，“评估函数”（以下简称EF）是必不可少的，因为这个星球上的任何硬件都无法计算出每一种可能的国际象棋移动序列直到游戏结束。因此，大多数国际象棋AI会深入12-14层，然后评估结果位置，分配8分给王后，5分给车，3分给象或马，1分给兵，然后为控制的格子（对中心格子的控制给更多分）、国王的安全性等分配额外的分数。

就曼卡拉而言，据我所知，它可能足够复杂，需要一个评估函数，但这个评估函数可能很简单，比如仍拥有的种子数量，还可以为处于高级位置的种子加分。（我查看了曼卡拉的维基，看起来有许多可能的变体——我不确定你在使用哪个。）

因此，负极大算法需要为一定的深度实现（即，不是使用所有可能的玩法直到游戏结束），并且使用一个简单的EF。假设你会实现AI深入5步。负极大的一个好处是它完全对称且零和；换句话说，如果位置对AI评估为5，对人类玩家则评估为-5。如果对人类玩家评估为13，对AI则评估为-13。这就是讨论的“单一数字”。考虑到所有这些，AI算法看起来会像这样（再次，没有剪枝）：

1) 检查每个可能的AI移动

2) 对于每个移动，检查每个可能的对手回应

3) 对于每个可能的回应，检查每个可能的AI移动

4) 对于每个可能的AI移动，检查每个可能的对手回应

5) 最后，对于每个可能的对手回应，检查每个可能的AI移动

现在我们已经达到了深度5，你已经构建了一个有5个层次的树，可能有成千上万或数百万个叶子（树的底层节点）。你以这样的方式编写代码，每个节点都有对其父节点的引用，以及对所有子节点的引用，这样你可以轻松地遍历树，从父节点到子节点然后返回。

一旦你正确设置了树，现在是时候实现负极大算法了，如下所示（假设较高的分数对AI玩家更好）：

6) 对于每个第四级对手回应，在所有AI子移动中找到最高评估，并剪掉所有其他子节点。你正在确定你的AI在每个可能的第四级对手回应中将进行的第五级移动。因此，现在每个第四级回应都有一个确定的第五级回应。现在你将第五级子节点的评估分数分配给第四级父节点。这意味着如果你到达那个第四级对手移动，AI将进行这个特定的第五级移动，棋盘将评估为那个分数。

7) 接下来，你评估每个第三级AI移动，对于每个移动，找到所有第四级对手移动中最低的评估，剪掉所有其他子节点，并将第四级分数（来自最高的第五级节点）分配给第三级。你在做与步骤6相同的事情，除了使用最低的子节点分数（因为这是AI移动而不是对手移动）。

8) 对第二级执行与步骤6相同的事情，找到所有第三级移动中最高的评估，并将这些最高评估分配给第二级节点。

9) 对第一级执行与步骤7相同的事情，找到所有第二级移动中最低的评估，并将这些最低评估分配给第一级节点。

10) 查看所有第一级节点，你的AI应该选择分数最高的那个进行移动。

显然，你不会将深度硬编码为5，而是将其设置为一个参数，你将使用递归（如维基中所示）来实现这一点。要选择一个深度，看看运行需要多长时间，并将n设置为仍能保证AI快速响应的最高深度。一旦你在这里建立了基础，你可以稍后添加剪枝策略，这将通过不评估显然不是正确移动的整个树分支来实现更大的深度，但这就是我为你列出的完整的、基本的负极大算法。

祝你好运，这应该是一个有趣的编程项目！