最小最大算法的伪代码

Question

我想获得最小最大算法的伪代码。我必须创建 2 个函数，def maxAgent(gameState, height) 和 minAgent。有没有人有正确且简单的伪代码。

Answer 1

两个玩家 A 和 B 轮流玩。

我们给出了一个评分函数 f，用于评估给定的棋盘位置 P。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 这个选择！

Answer 2

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 。