问minmax算法的伪代码

EN

两个玩家，A和B，轮流玩。

我们给出了一个评分函数f，它评估给定的棋盘位置P。f(P)的值越大，A越好，B越差(即，f(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这样做！

minmax算法尝试最大化玩家A的分数，最小化玩家B的分数。给定一个节点，您可以通过取后续节点的分数的max (对于A)或min (对于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。