上节提到强化学习算法解决的井字棋游戏并不适合用Minimax算法解决，理由是Minimax假设游戏双方都不会犯错，这种情况比较特殊。

1.Minimax算法

别称：Minmax算法（MM）算法，极小化极大算法，为了找出失败的最大可能性中的最小值的算法。

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

在对弈过程中，为了实现自己获胜概率最大化，在尽可能多的预测对手后面行动的情况下走出使自己接下来赢面估价最大的行动。

先手与后手的目的一样，行动指南也都是以最大化自己估价而最小化对手估价。

在这里以正方形代表先手（选择估价最大的局面），圆形代表后手（选择估价最小的局面）。只有叶子节点才可以直接计算估价值。则我们假设棋局的博弈树如下（预测后面的四步），每步策略？

该游戏中所有策略的集合可以由一棵巨大的根树来表示，树中的每个顶点都对应于棋盘的一个布局（configuration）。所谓“棋盘的一个布局”，是在游戏过程中通过标记棋盘上的小方格得到的。其中数字表示达到此种布局先手可以获得的分数。

以井字棋为例，令叶子顶点对应于游戏的最终状态，将其标记为1或0，分别对应于游戏者A获胜或失败；对于游戏者B而言，数值的含义是相反的。

对于下图(a)的局面而言，A只有一个选择，且之后将获胜，因此可以将树中对应于下图(a)的顶点也标记为1——表示A将获胜。

之后简单分析一下下图(b)就会发现无论B怎样选择，最终他都将失利，而由A获得胜利，因此可以将树中对应于下图(b)的顶点也标记为1——表示此时无论B如何行棋，A都一定获胜。

对于下图(c)而言，B怎样选择，他都可以获胜，因此可以将树中对应于下图(c)的顶点也标记为0——表示B一定可以获胜。但是对于下图(d)，如果游戏者B做出了正确选择（左下角），那么他将获胜，而如果他做出了错误选择（右上角），那么他将失利。为了分析博弈树，将假定任何一名游戏者都不会犯错误。在这种假定下，可以将树中对应于下图(d)的顶点也标记为0——表示存在着游戏者B的获胜策略。

如果将分别以下图(b)~(d)为根的子树展开的话（见下图(e)），会发现对应于轮到B行棋的奇数层顶点根据其孩子顶点的标号对自己进行标号的行为和逻辑运算“与”一致，因此可以用∧表示。 

回到此问题，分数表示当前布局是使先手可以获得的最好结果。

图1. 先手计算的第五步

首先，先手应该计算后手在第四步的时候应该会选择价值为多大的局面（即从所有子节点中选择最小的），如下图（红色字体）：所有子节点代表了第五步所有可能的情况，为了使先手得分最低，后手会在第四步从自己所有走步可能中选择使第五步估价最差的一步；

图2. 第四步中后手的选择

然后先手在计算自己在第三步时应该如何选择（即从所有后手子节点中选择最大的），如下图（红色字体）：先手考虑到后手第四步的选择，则会在第三步选择使自己得分最高的情况；

图3. 第三步中先手的选择

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

图4 后手在第二步的选择

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

图5. 先手的第一步选择

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

图6 最终的策略路线

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

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

2 剪枝

名称来自于计算过程传递的两个边界，根据边界限制不必要的可能的解决方案集。其中，表示目前所有可能解中最大下界，是目前所有可能解中最小上界。

因此，如果搜索树上的一个节点被考虑作为最优解路上的节点（或者说是这个节点被认为是有必要进行搜索的节点），那么它一定满足以下条件（N是当前节点的估价值）：

在求解过程中会逐渐逼近。如果对于某一个节点，出现了的情况，那么此节点必不会产生最优解，也就不必继续扩展（或生成子节点），从而完成剪枝。

以上图的情况进行说明：

（1）从根节点开始向下搜索，到第四步，红色序号代表顺序。

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

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

继续搜索，至叶子节点：

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

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

然后，我们发现15并不能更新当前节点的β值，所以令当前节点权值为15，并返回其权值，尝试更新其父节点(Max节点)的α 值。因为其父节点的α < 15，所以我们令α = 15 。此时，该节点α = 15 , β = 3 ，α > β ，则说明其子节点并不包含最优解，不需要在进行搜索。所以返回其节点权值给父节点（Min节点），尝试对父节点的β值进行更新。父节点的β < 15 ，则不需要进行更新。同时可确定父节点的权值为3。

继续返回权值给父节点，尝试更新父节点的α ，发现父节点α < 3 ，则令α = 3，并继续向下搜索直至叶子节点。注意新生成的子节点的 α 、 β  值继承自父节点。

从叶子节点返回权值给父节点（Min节点），并尝试更新其父节点的β值，因为父节点β > 2，所以，令β = 2，此时有α > β，说明其子节点并不包含最优解，不需要再进行搜索。所以返回其节点权值给父节点（Max节点），尝试对父节点的α值进行更新。因为父节点α > 2 ，无需进行更新，继续搜索其子节点至叶子节点。

从叶子节点返回权值给父节点（Min节点），并尝试更新其父节点的β值，因为父节点β > 3 ，所以，令β = 3 ，同时确认父节点权值为3。继续返回权值给父节点，并尝试更新其父节点的α 值，因为父节点α = 3，所以无需进行更新，同时确定该节点权值为3。

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

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

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