algorithm - minmax 算法的伪代码

Question

我想获得 minmax 算法的伪代码。我必须创建 2 个函数，def maxAgent(gameState, depth) 和 minAgent。是否有任何机构拥有正确且简单的伪代码。

score 2 · Accepted Answer

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。

score 2 · Accepted Answer

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 pruning，它应该（大大）减少你需要做的搜索量。Alpha-beta 剪枝基于这样一种想法，即如果 A 推断 B 可以强制 A 的最大优势为 M，那么考虑任何得分大于 M 的子树是没有意义的，因为 B 永远不会允许 A 那个选项！

2 回答 2