二、对抗搜索（Adversarial Search）(博弈搜索 Game Search)
所谓对抗搜索，即在一个竞争环境中，智能体（agents）之间通过竞争实现相反的利益，一方最大化这个利益，另一方最小化这个利益。
本文主要讨论在确定的、全局可观察的、竞争对手轮流行动、零和游戏（zero-sum）下的对抗搜索。
例如，两人对决游戏（MAX and MIN,MAX先走）可如下形式化描述，从而将其转换为对抗搜索问题。
下面我们通过Tic-Tac-Toe游戏来理解一下对抗搜索。
游戏规则：
- MAX先行，可在初始状态的9个空格中任意放一个X
- MAX希望游戏终局得分高、MIX希望游戏终局得分低
- 所形成游戏树的叶子结点有9！=362880，国际象棋的叶子节点数为10^40
我们的目标是，选择一个最优策略保证MAX选手的利益最大化。
1、minimax算法
给定一个游戏搜索树，minimax算法通过每个节点的minimax值来决定最优策略。MAX希望最大化minimax值，而MIN则相反
例如：
- 如果搜索树是有限的，则minimax算法是完备的。
- 如果对手也采取对抗策略，则minimax算法是最优的。
- 时间复杂度：O(b^m)
- 空间复杂度：O(b x m)
m是游戏树的最大深度，在每个节点存在b个有效走法。
如果搜索树极大，则minimax算法无法在有效时间内返回结果。因此我们又引入alpha-beta pruning算法来减少搜索节点。同时对节点进行采样、而非逐一搜索（i.e.,MCTS）
2.alpha-beta pruning算法
该算法是minimax算法的优化，剪去了不影响最终结果的分支，使得搜索路径变少。
剪枝过程：
- Alpha值为可能解法的最大上界
- Beta值为可能解法的最小下界
- 如果节点N是可能解法路径中的一个节点，则其产生的收益一定满足如下条件：
Alpha值 <= reward(N) <= Beta值（其中reward（N）是节点N产生的收益）
每个节点有两个值，分别是Alpha值和Beta值，节点的Alpha值和Beata值在搜索过程中不断变化。其中，Alpha值从负无穷大逐渐增加，Beta值从正无穷大逐渐减少如果一个节点的Alpha值（MAX当前得到的最大收益）大于Beta值（MIN给对手的最小收益），则该节点的后续节点可剪枝。
- 剪枝本身不影响算法输出结果
- 节点的先后次序会影响剪枝效率
- 如果节点次序“恰到好处”，Alpha-Beta剪枝的时间复杂度为O(b^ m/2),最小最大搜索的时间复杂度为O(b^m)
本文借鉴于mooc 吴飞老师 人工智能-模型与算法