对抗搜索（Adversarial Search）也称为博弈搜索（Game Rearch）

在一个竞争的环境中，智能体（agents）之间通过竞争实现相反的利益，一方最大化这个利益，另一方最小化。

对抗搜索的方法主要有三个： 最小最大搜索（Minmax Search） Alpha-Beta剪枝搜索（Pruning Search） 蒙塔卡洛树搜索（Monte-Caelo Tree Search）

最大最小搜索为对抗搜索中最基本的搜索方法；剪枝搜索是一种对最大最小搜索进行改进的算法，即在搜索过程中可以减去无需搜索的分支节点，且不影响搜索结果。蒙特卡洛树搜索通过采样而非穷举方法来实现搜索。

这里只讲一个最简单的例子说明minmax search的计算过程。

假设根据当前局面我们得到一个下图所示的博弈树：

从上往下，单数层是我方行动，双数层是对方行动，我方行动需要选择对我最有利的行动，即value大的行动，对方行动则是选择使我方最不利的行动，即value小的行动。

我们需要从最底层第四层开始考虑，双数层所以是对方行动。对于node I，会选择值更小的node M，node I的值更新为0。再考虑第三层，单数层是我方行动。node F会选择I，J中值更大的J，更新为5，G会选择K，L中值更大的L，更新为8。依次一层层向上类推，可以得到最终结果为：

性质 完备性（complete）？yes（只要决策树有限） 最优性（optimal）？yes（对手是理性的） 空间复杂度（space）？O(b*m)（深度优先探索） 时间复杂度（time）？O(b^m) m是树的最大深度，在每个节点存在b个有效走法

优点 算法是一种简单有效的对抗手段 在对手也“尽力而为”的前提下，算法可返回最优结果

缺点 如果搜索树极大，则无法在有效时间内返回结果

改善 使用alpha-beta剪枝来减少搜索节点 对节点进行采样，而非逐一搜索（MCTS）

用于Min-Max的剪枝，一些搜索是没有必要的，故此可以剪除（cut-off）那些没有必要搜索,即对搜索进行剪枝（prune)。Alpha-Beta算法是一种有效而常用的剪枝算法.

Alpha-Beta算法是在Min-Max方法基础上的一个改进.它维护一个搜索窗口（search window）:[α, β].

每个节点有两个值，分别是alpha和beta。节点的alpha和beta在搜索过程中：alpha从负无穷逐渐增大，beta从正无穷不断减少。如果一个节点的alpha>beta，那么该节点和它的后继节点可以被剪枝。注意：搜索的顺序一般是从左向右，或者是从右向左，而不是自上而下。

更详细的计算步骤见链接link~~~~~~~~~~~~~~

剪枝本身不影响算法输出结果

节点先后次序会影响剪枝效率

如果节点次序“恰到好处”，alpha-beta剪枝是时间复杂度为O(b^m/2) 而，最大最小搜索时间复杂度为O(b^m)