http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html https://www.cnblogs.com/pangxiaodong/archive/2011/05/26/2058864.html

  Minimax算法（亦称 MinMax or MM）又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法。

  Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。而开始的时候总和为0。很多棋类游戏可以采取此算法，例如井字棋（tic-tac-toe）。

  以上是来自WIKI百科的解释，其实说的通俗一点，就是有两个人下棋，先手希望下一步的局面是自己胜算最大的局面，而后手则希望下一步的局面是先手胜算最小的局面（因为先手输，后手就会赢）。

  那么，如何来判断当前的局面的胜算到底怎么样呢？我们可以设置一个估价函数，按照某种方案来计算当前局面的优劣程度。

  （建议先跳过以下内容）

  然后在这种想法的前提下，就是高能的博弈过程。如果只向后看一步（也就是直接计算下一步的估价值）的话，那情况就是：先手预测了自己走完这一步的所有可能的局面，然后选择了所有走法中局面看起来最好的（估价函数的结果最好的）走法。之后，后手也预测了自己走完这一步的所有可能的局面，然后也选择了所有走法中局面看起来最好的（估价函数的结果最好的）走法。如此循环往复，直到最后游戏结束。（GG，即Good Game）

  如果这两个棋手比较优秀，可以往后看两步（也就是只直接计算往后数两步的估价值），那么，情况就是这样的：先手预测了自己走完这一步的所有可能局面，并同时预测了对手的所有应对方案（也就是对手会选择让下一步局面估价函数最小的走法，所以先手这一步应该选择，让后手不管走么走估价函数都尽量大的走法），综合这些信息，选择了一个最优的局面，后手也是如此。也就是我猜到了我这么走，你会怎么走，所以我选择这么走的高端玩法。

  当然，也可以往后看三步（也就是只直接计算往后数三步的估价值），那么，情况就是这样的：先手预测了自己走完这一步的所有可能局面，并同时预测了对手的所有应对方案，还同时又想到了自己在面对对手的每种应对方案时的所有可能走法，从中选择一个最优秀的，后手也是如此。也就是，我猜到了我这么走，你会那么走，然后我会这么走，所以我选择这么走的更高端玩法。

  （跳到这儿就可以了）

  不知道大家是不是懵逼了，其实看不懂也没关系，上面的大家可以当成废话（那你写这么多干嘛？MDZZ），下面我们就要上图啦，结合图示，一下子就可以明白怎么回事了。

  我们用正方形来代表先手（选择估价最大的局面），圆形来代表后手（选择估价最小的局面）。只有叶子节点才可以直接计算估价值。

  则我们假设棋局的博弈树如下(往后看4步)，那么先手应该如何选择呢：

  首先，先手应该计算后手在第四步的时候应该会选择价值为多大的局面（即从所有子节点中选择最小的），如下图（红色字体）：

  然后先手在计算自己在第三步时应该如何选择（即从所有子节点中选择最大的），如下图（红色字体）：

  然后先手在计算后手在第三步时应该如何选择（即从所有子节点中选择最小的），如下图（红色字体）：

  最后先手就可以决定下一步应该怎么走了（即从所有子节点中选择最大的），如下图（红色字体）：

  所以，如果先后手都进行最有决策的话，棋局的走向则下图所示（红线）：

  (当然，如果后手不是进行最优决策的话，棋局的走向就不一定是这样的了，先手也可以尝试走有风险，但是收益更高的局面，这就不在我们的讨论范围之内了)

  可以看到，如果按照MinMax算法来进行决策的话，需要的计算量是随着向后看的步数的增加而呈指数级增长的。但是，这些状态中其实是包含很多不必要的状态的，所以我们可以进行剪枝。

注：真实的搜索顺序并不一定是一层一层的进行的

   Alpha-beta( α − β \alpha - \beta α−β)剪枝的名称来自计算过程中传递的两个边界，这些边界基于已经看到的搜索树部分来限制可能的解决方案集。 其中，Alpha( α \alpha α)表示目前所有可能解中的最大下界，Beta( β \beta β)表示目前所有可能解中的最小上界。

  因此，如果搜索树上的一个节点被考虑作为最优解的路上的节点（或者说是这个节点被认为是有必要进行搜索的节点），那么它一定满足以下条件（ N N N是当前节点的估价值）： α ≤ N ≤ β \alpha \leq N \leq \beta α≤N≤β   在我们进行求解的过程中， α \alpha α和 β \beta β会逐渐逼近。如果对于某一个节点，出现了 α > β \alpha > \beta α>β的情况，那么，说明这个点一定不会产生最优解了，所以，我们就不再对其进行扩展（也就是不再生成子节点），这样就完成了对博弈树的剪枝。

  可能这个过程描述起来还是有一些抽象，那么，我们就用图像（依旧是往后看4步）来还原模拟一下这个过程：

  首先，我们开始从根节点向下进行搜索，直到进行了四步为止（废话，不到4步没有值呀），红色的序号代表顺序。

  当我们搜索到了第一个叶子节点的时候，我们发现它的权值是3，并且它的父节点是Min节点，又因为父节点的最小上界 β > 3 \beta > 3 β>3，所以我们更新父节点，令 β = 3 \beta = 3 β=3。（因为父节点要取最小值，这个最小值不会比3更大，所以我们更新其上界）然后继续向下搜索。

  因为17比3大，所以这个节点我们可以无视掉（没啥用啊）。我们已经搜索完了当前这个Min节点的所有孩子，所以我们返回它的节点值给它的父节点（Max节点），尝试更新父节点的 α \alpha α值。（因为这是一个Max节点，他的孩子的估价值和 α 、 β \alpha、\beta α、β值已经确定了，所以父节点取值范围的下界也需要被更新），此处更新父节点，令 α = 3 \alpha = 3 α=3。然后继续进行搜索，注意新生成的子节点的 α 、 β \alpha、\beta α、β 值继承自父节点。

  继续搜索，至叶子节点：

  我们发现它的权值是2，并且它的父节点是Min节点，又因为父节点的最小上界 β > 2 \beta > 2 β>2，所以我们更新父节点，令 β = 2 \beta = 2 β=2。（因为父节点要取最小值，这个最小值不会比2更大，所以我们更新其上界）。然后此时我们发现父节点出现了 α > β \alpha > \beta α>β的情况，说明最优解不可能从这个节点的子节点中产生，所以我们不再继续搜索它的其他子节点。（这就是 β \beta β剪枝）并继续返回其节点值，尝试更新父节点。因为父节点的 α = 3 > 2 \alpha = 3 > 2 α=3>2，所以更新失败。

  然后我们已经搜索完了当前这个Max节点的所有子节点，所以我们返回它的节点值，并尝试更新他的父节点的 β \beta β 值。因为父节点的 β > 3 \beta > 3 β>3，所以我们令$\beta = 3 $。并继续向下搜索至叶子节点，注意新生成的子节点的 α 、 β \alpha、\beta α、β 值继承自父节点。

  然后，我们发现15并不能更新当前节点的 β \beta β值，所以令当前节点权值为15，并返回其权值，尝试更新其父节点(Max节点)的 α \alpha α值。因为其父节点的 α < 15 \alpha < 15 α β \alpha > \beta α>β，则说明其子节点并不包含最优解，不需要在进行搜索。所以返回其节点权值给父节点（Min节点），尝试对父节点的 β \beta β值进行更新。父节点的 β < 15 \beta < 15 β 2 β>2，所以，令 β = 2 \beta = 2 β=2，此时有 α > β \alpha > \beta α>β，说明其子节点并不包含最优解，不需要再进行搜索。所以返回其节点权值给父节点（Max节点），尝试对父节点的 α \alpha α值进行更新。因为父节点 α > 2 \alpha > 2 α>2，无需进行更新，继续搜索其子节点至叶子节点。

  从叶子节点返回权值给父节点（Min节点），并尝试更新其父节点的 β \beta β值，因为父节点 β > 3 \beta > 3 β>3，所以，令 β = 3 \beta = 3 β=3，同时确认父节点权值为3。

  继续返回权值给父节点，并尝试更新其父节点的 α \alpha α值，因为父节点 α = 3 \alpha = 3 α=3，所以无需进行更新，同时确定该节点权值为3。

  因为该节点的所有子节点全部搜索完毕，所以返回该点权值给父节点，并尝试更新其父节点的 β \beta β值，因为父节点 β > 3 \beta > 3 β>3，所以，令 β = 3 \beta = 3 β=3，同时确认父节点权值为3。因为此时有 α = β = 3 \alpha = \beta = 3 α=β=3，所以无需再搜索其子节点，直接返回权值给根节点，并尝试更新根节点的 α \alpha α值，因为根节点 α = 3 \alpha = 3 α=3，所以无需进行更新。

  根节点的所有子节点搜索完毕，则得出最优解为3。

  可以对比一下不加剪枝与加了剪枝之后的搜索过程，可以发现Alpha-Beta剪枝对算法的性能有了很大的提升。

伪代码如下：

MinMax算法：

Alpha-Beta剪枝：