极小极大搜索算法

2.4　极小极大搜索算法

极小极大是应用于机器博弈、决策理论、统计等领域的决策规则，其目的是尽可能地减少可能发生的损失；同时，尽可能地提高其潜在的收益。极小极大决策规则起源于双人零和博弈理论，既适用于轮流下棋的情况，也适用于同时下棋的情况，并已被扩展应用于具有不确定因素的更复杂博弈项目与通用的决策理论中。

John von Neumann提出了极小极大定理如下：“对于任何一个有限状态的双人零和博弈，存在一个评价值V与适用于博弈双方的一组策略，同时满足以下两个条件：①已知选手B的策略，选手A的最好回报是V；②已知选手A的策略，选手B的最好回报则是-V。”

以第2.3.5节取豆子博弈为例，每个人在拿豆子时，都会选择一个合适的数值x，其中x∈［1，…，m］，来争取在经过两人几轮选择之后，自己最有可能拿到最后一个豆子。比如现在剩下5个豆子，每个人最多拿3个豆子，那么先选择的那个人会发现，如果自己拿1、2、3个豆子，则分别会给对手剩下4、3、2个豆子；如果剩下3个或2个豆子，那么对手就会取胜，如果有4个豆子，那么对手无论拿几个豆子，都会给自己剩下小于等于3个豆子，自己就可以取胜，因而，第1次拿1个豆子是个不错的选择。

在更普遍的意义上，对于双人零和博弈，博弈双方对于己方的盘面都会根据博弈规则选择最优秀的落子，根据零和原则，该策略也等同于选择对对方最恶劣的落子。双方轮流落子的过程就形成了一个最大最小的过程。

极小极大搜索算法就是一个基于以上极小极大过程的递归博弈树搜索算法，通常用于双人博弈，也可扩展应用于多人博弈。在极小极大搜索算法中，博弈树的每个节点都有一个价值，用于表示对于某博弈方该节点所对应盘面的优劣。对于双人零和博弈，假设博弈双方分别是A与B，博弈树内部节点价值的计算中，A方每一步落子的价值是B方所有可能应手价值的最小值。因此，A方是极大方，B方是极小方，本搜索算法被称为极小极大搜索算法。

当博弈较为简单时，博弈树较小而可以被完全展开，博弈树叶子节点的价值可以通过胜负结果来确定。当博弈较为复杂时，博弈树很大而不可能被完全展开，博弈树叶子节点的价值可以通过第2.3节所讨论的静态评估函数来计算。因此，使用静态评估函数可以把极小极大搜索算法应用于展开博弈树的一部分。例如，战胜国际象棋世界冠军Garry Kasparov的“深蓝”计算机就是用了至少12层的搜索，12层搜索以外再使用静态评估函数。极小极大搜索算法如算法2.2和算法2.3所示。

算法2.2　极小算法的伪代码

算法2.3　极大算法的伪代码

极小极大搜索算法可以看作是在一定深度上对博弈树的遍历。通常来说，极小极大搜索算法所遍历节点的数目是所遍历深度的指数次方。对于围棋，每步棋有很多选择，而由于时间和空间的限制，无法使用极小极大搜索算法做深层的搜索。在不影响极小极大搜索算法结果的条件下，极小极大搜索算法的效率可以进一步提高，第2.6节所讨论的α-β减枝算法就是这样一个例子。α-β减枝算法之后，我们将会进一步其他性能的改进方法，虽然某些方法可能会改变搜索的最终结果。