最小最大算法的伪代码

Question

我希望获得MinMax算法的伪代码。 我需要编写两个函数，def maxAgent（gameState，depth）和minAgent。 有没有人有正确且易于理解的伪代码。

- Shilpa

---

游戏树是否已完全构建，还是存在未被探索的节点？minmax算法可以分阶段完成（可能确定胜者或返回“未决定”），也可以在游戏树完整构建后完成，此时将找到一个明确的胜者。 - mdma

树已完全构建。它返回最佳得分。 - Shilpa

Answer 1

MinMax算法旨在最大化玩家A的得分并最小化玩家B的得分。给定一个节点，您可以通过对后继节点的得分取最大值（对于A）或最小值（对于B）来找到最佳游戏的最终结果。

假设叶子节点已经分配了获胜者（A为1，B为-1），而所有其他节点的得分均为0。然后，您可以使用类似以下内容的方法计算A的最终获胜结果：

  getMaxScore(node) {
    score = node.score;
    for each child node 
       score = max(score, getMaxScore(node))  
    next

    return score;
  }

这是基础算法。只要分数变成1，你就可以立即终止评估，那么A就胜利了。

对于B的算法getMinScore也是一样的，只需要使用min函数，并且如果进行短路运算，寻找-1。

- mdma

---

什么？minmax并不是为了最大化A的最大结果或A的预期结果，也不是为了最小化B的预期结果（在B随机玩、B理性玩或任何其他规则下，B都不知道A的行动）。它告诉A如何玩以使B的最大结果最小化，如果B知道A的选择，则可以实现该结果。它被写成min_{a \in A} max_{b \in B} c(a,b)，其中a是玩家A的移动，b是玩家B的移动，c是成本函数。 - Ben Voigt

@Ben，你说的是正确的，但是你误解了我的意思。我在谈论字面上的/实现的细节 - 如果A获胜得分为1，B获胜得分为-1，则A的函数应该从0开始最大化得分。（提示，我没有说结果 - 我说的是“分数”，这是一项实施细节。） - mdma

Answer 2

两个玩家A和B轮流进行游戏。

给定一个评估棋盘局面P的计分函数f。f(P)越大对于A就越好，对于B就越差（即f(P)是在不考虑进一步预测的情况下评估P对于A有多“好”的估价）。

考虑一个棋盘局面P。

如果P是叶节点（即P是一个获胜的位置或者我们已经向前看了想要看的层数），那么我们返回f(P)作为此节点的得分。

否则，P不是一个叶节点，而是有子节点C1, ..., Cn，我们递归地计算其孩子的得分，得到S1, ..., Sn。

如果A在P处下棋，则P的得分为max{S1, ..., Sn}，因为A将始终努力使自己的优势最大化。

如果B在P处下棋，则P的得分为min{S1, ..., Sn}，因为B将始终努力使A的优势最小化。

这应该足以转化成代码。

完成后，请参阅alpha-beta剪枝，它可以（大幅）减少您需要执行的搜索量。Alpha-beta剪枝的基本思想是：如果A推断出B可以玩出让A最大优势为M的策略，那么考虑任何得分大于M的子树都是没有意义的，因为B永远不会允许A有这个选项！

- Rafe