人工智能(一):最小-最大算法

先说minimax算法主要用在什么样的游戏里:1。零和博弈:是指一方的胜利代表另一方的失败，例如象棋、五子棋等。2.完美信息:玩家知道前面所有的步骤。国际象棋是完全信息，因为棋手交替落地，前面的步骤可以在棋盘上体现出来，而石头剪刀布不是。这类游戏通常可以看作是一个树形图，列出了每一种可能性。比如下面这个井字游戏，Max代表自己，Min代表对手。

这时候我们需要给每个结果一个分数，就是这里的效用。这个分数是从我自己(也就是Max)的角度评价的。比如上图，我赢了+1，输了-1，平了0。所以，我想最大化这个分数，我的对手想最小化这个分数。(在游戏中，这个分数叫做静态值。)在这里，井字游戏是一个比较简单的游戏，所以可以列出所有可能的结果。然而，大多数游戏不太可能列出所有结果。按照计算机运算量，我们可能只能往前推7、8步，所以这个时候分数不仅仅是-1、1、0这么简单，而且会有专门的算法根据当前的结果给出不同的分数。

这时候我们需要给每个结果一个分数，这就是这里的效用。这个分数是从我自己(也就是Max)的角度评价的。比如上图，我赢了+1，输了-1，平了0。所以，我想最大化这个分数，我的对手想最小化这个分数。(在游戏中，这个分数叫做静态值。)在这里，井字游戏是一个比较简单的游戏，所以可以列出所有可能的结果。然而，大多数游戏不太可能列出所有结果。按照计算机运算量，我们可能只能往前推7、8步，所以这个时候分数不仅仅是-1、1、0这么简单，而且会有专门的算法根据当前的结果给出不同的分数。假设我们像下面这个游戏，我是第一个玩家。我应该如何使用最小最大算法选择第一步？

这时候我们就从结果入手，这是第四步。图中标注的第四步是我的对手做的，所以他要做的就是把这个分数最小化，这样对手就可以根据结果推导出下面的选项。

从后往前继续看步骤3。当我们知道了对手的选择，我们就可以根据对手的结果推导出自己的选择。我们要做的就是把这个分数最大化，如图。

重复这一步，最终可以找到第一步的最佳选择，如图。

重复这一步，最终可以找到第一步的最优选择，如上图所示，这就是Minimax算法。

然后，电脑给出第一个分数

当给出这个分数时，我们站在步骤1。无论另一个分支的编号是多少，步骤1的左框中的编号都不会超过2。因为第二步是我的对手做的，他希望分数越小越好，仅此而已。

这时电脑计算出另一个分支的分数，是7。知道对方得分是7后，就知道步骤1的左框得分是2。这时，我们向前看一步(步骤0)。步骤0的分数大于等于2，因为我想最大化分数。画

现在，再次计算右分支的分数，得到1。同样，如果我们站在第1步，右边方框中的数字不会超过1，如图所示。

在这种情况下，即使不算最后一个数，我仍然可以知道第0步的结果是2，因为已知第1步的右框的值不会超过1。所以我们可以直接知道结果，也就是，

我们可以看到，使用剪枝算法，我们不仅得到了相同的结果，而且减少了计算量。在实际应用中，加上剪枝算法，计算机大约需要计算2*n (x/2)个结果。如果n是分支数，x是步数。相比之前只用minimax算法的n x，效率提升了不少。这意味着，如果在国际象棋比赛中使用极大极小算法，计算机可以向前评估7步，使用剪枝算法，计算机可以向前评估14步。IBM开发的国际象棋超级计算机深蓝使用了minimax和剪枝算法，两次击败世界象棋冠军。