1.5 对抗搜索
在一些搜索问题中，有多个智能体进行博弈或竞争，即智能体的目标相互冲突，这时就需要对抗搜索。在对抗搜索中，一个智能体需要在其他智能体同样通过搜索寻找各自最优解的同时寻找自己的最优策略。击败国际象棋冠军卡斯帕罗夫的“深蓝”所使用的Alpha-Beta剪枝搜索和击败世界围棋冠军的AlphaGo所使用的蒙特卡洛树搜索都属于对抗搜索。
在本节中，主要考虑在两个智能体的零和博弈问题下的搜索。在此类博弈中，双方收益的和为零，即必有一方获胜或双方打平。围棋、国际象棋以及猜拳游戏都是典型的零和博弈问题。因为双方收益之和为零，那么我们可以只用一个收益函数，其中一个智能体最大化收益，而另一个智能体最小化收益，一个零和博弈可以通过博弈树来定义。博弈树由初始状态s0、动作集合A和收益函数U（p）组成，其中每个节点表示博弈的一个状态，而每一条边则表示不同玩家的一次行动。树的叶节点表示博弈的结束，而收益函数U（p）则表示在每一个叶节点p确定双方获胜或打平的情况。
博弈树包含两个玩家MIN和MAX，每个玩家轮流执行动作，其中玩家MAX希望最大化收益函数，而玩家MIN希望最小化收益函数。以井字棋游戏为例来展现博弈树。井字棋是一种在3×3格子上进行的连珠游戏，由分别代表○和×的两个游戏者轮流在格子里留下标记（一般来说先手者为×），任意三个标记形成一条直线，则为获胜。其（部分）博弈树如图1.13所示。
图1.13 井字游戏的（部分）博弈树
下面将简要介绍两种常见的对抗式搜索方法：极小极大搜索（MiniMax search）和Alpha-Beta剪枝搜索。
1.5.1 极小极大搜索
极小极大搜索是博弈树搜索的一种基本方法。其基本思想是使用一个收益评估函数v（p）对给定的中间节点p进行评估，并通过搜索找到使收益评估函数最大（或最小）的动作。
给定一棵博弈树，最优策略可以通过检查每个节点的极小值或极大值来确定。这是因为在任意状态，MAX玩家会倾向于移动到所有选择中收益极大的状态，而MIN玩家倾向于移动到所有选择中极小的状态。因此我们可以通过如下公式递归确定每个节点玩家的最优策略及收益：
其中U（p）是终止节点的收益函数，p'是在p节点执行动作a后到达的下一个节点。因此，我们可以使用递归的算法来计算最优的策略。
具体来说，给定当前的格局，算法首先给出MAX玩家的所有可能走法，再进一步给出MIN玩家的所有可能走法，由此进行若干步，得到一棵子博弈树，并在叶节点计算收益评估函数的值；最后由底返回至上计算，在MIN玩家处取下一步收益估值的最小值，在MAX玩家处取下一步收益估值的最大值，最终计算出使得MAX玩家在最坏情况下能最大化收益的动作。
下面考虑两步棋的情况来说明，此时博弈树如图1.14所示。图中叶子节点的数字或由收益评估函数v（p）计算得到，或由结束状态的收益函数给出，其他节点则使用倒推的方法估值。例如，Y是MAX玩家决策的节点，其估值应取A，B，C中最大者。A，B，C是MIN玩家决策的节点，其估值应分别取其子节点收益评估函数值最小者。由此，可以计算出MIN玩家在A，B，C三个节点的最优动作分别对应收益为5，1，2的动作；而MAX玩家在Y节点最优的动作是A；最终的平衡策略是MAX玩家采取A动作，而MIN玩家采取对应收益为5的动作。使用极小极大搜索算法在博弈树中递归求解时，两位玩家分别交替使用使收益极小和极大的动作，故称为极小极大搜索。
图1.14 两步棋游戏的博弈树
极小极大搜索算法的伪代码如下，算法中的极小极大搜索函数即为前述公式中的递归函数：
算法5：极小极大搜索（节点p，是否为极大方）
图1.14的博弈树中极小极大搜索的具体步骤如下。假设初始节点p=Y，该节点为MAX玩家。
（1）首先搜索左边的A节点，为MIN玩家，再进一步搜索两个终止节点；MIN玩家从返回的收益中选择最小的一个，得到节点的最优策略收益为v=5。
（2）进而搜索Y节点可能到达的第二种情况，即B节点，为MIN玩家，其同样从两种中止节点中选择最小的一个，得到节点的最优策略收益为v=1。
（3）然后搜索Y节点可能到达的第三种情况，即C节点，为MIN玩家，同样得到节点的最优策略收益为v=2。
（4）最后回到Y节点，为MAX玩家，在所有可能的收益中取最大值，得到Y节点最优策略的收益为v=5。
1.5.2 Alpha-Beta剪枝搜索
Alpha-Beta剪枝搜索通过避免不必要的节点搜索来提高算法的运行效率，是对极小极大搜索算法的优化。Alpha-Beta剪枝搜索的基本思想是，如果在当前节点已知对手存在一个策略能使自己获得的收益少于之前某个节点能够获得的收益，则己方玩家一定不会选择当前节点，故无需继续搜索当前节点的剩余子节点，因此称为“剪枝”。Alpha-Beta剪枝搜索引入了Alpha与Beta两个变量，其中Alpha表示到目前为止的路径上发现的MAX玩家当前的最优值，Beta则表示到目前为止的路径上发现的MIN玩家当前的最优值。如果在某一个节点有Alpha≥Beta，则说明该玩家当前的最优策略（Beta）劣于之前已有的最优策略（Alpha）。故无需搜索当前节点的剩余子节点，因此可以进行剪枝。
Alpha-Beta剪枝搜索的伪代码如下：
算法6：Alpha-Beta剪枝搜索（节点p，alpha，beta，是否为极大方）
我们仍然用图1.14中的两步棋游戏具体说明Alpha-Beta剪枝搜索的执行过程。初始化时，设alpha=-inf（负无穷），beta=inf（正无穷）。
Alpha-Beta剪枝搜索的具体步骤如下：
（1）从根节点Y开始递归搜索，同样首先搜索左侧节点A，此时alpha=-inf，beta=inf，所以alpha<beta，故继续搜索；最终到达最左侧子节点。因为该子节点是终止节点，返回收益v=5；
（2）返回到A节点，并更新其beta=min（inf，5）值为5。此时alpha=-inf，beta=5，所以alpha<beta，继续搜索节点A的子节点。因为其下个子节点也是终止节点，所以返回收益v=6；
（3）返回到A节点；因为6>beta=5，故A节点的beta值无改动；继续返回Y节点更新其alpha=max（-inf，5）值为5。此时alpha=5，beta=inf，所以alpha<beta，继续搜索Y节点的B子节点的子节点；因为其第一个子节点是终止节点，所以返回收益v=2。
（4）返回更新B节点的beta=min（inf，2）值为2，此时alpha=5，beta=2，所以alpha>beta，说明MAX玩家选择B节点的最优策略值不大于beta=2，而同时MAX玩家可以通过选择其他节点（此时为A）来获得至少alpha=5的收益，因此MAX玩家必不选择B节点，故无需继续搜索B节点的其他子节点，可剪枝。
（5）返回更新Y节点的alpha=max（5，2），此时由于5>2，故无需更新；此时alpha=5，beta=inf，alpha<beta，继续搜索C节点及其子节点。因为其第一个子节点是终止节点，所以返回收益v=3。
（6）返回更新C节点的beta=min（inf，3）值为3，此时alpha=5，beta=3，因而alpha>beta，故同样无需继续搜索C节点的其他子节点，可剪枝。并返回到Y，完成全部搜索。
通过上面的例子可以看出，基于零和博弈中最优策略的性质，Alpha-Beta剪枝搜索通过避免不必要的节点搜索，提高了算法的效率。