对抗搜索
在竞争环境中，两个或两个以上的智能体具有互相冲突的目标，这引出了对抗搜索问题。通常对博弈的研究专注于如国际象棋、围棋和扑克之类的项目，而不是处理真实世界中的混乱冲突。这些项目的简化特性是一个优势：博弈状态很容易表示，智能体通常仅能执行少数几个动作，而且动作的效果由明确的规则定义。对于体育比赛，描述更加复杂，可能动作的范围更大，而且定义动作合法性的规则也不够明确。
人工智能领域中最常研究的博弈（例如国际象棋和围棋）是博弈论学者所称的确定性、双人、轮流、完美信息的零和博弈。“完美信息”是“完全可观测”的同义词，“零和”意味着对一方有利的东西将对另一方同等程度有害：不存在“双赢”结果。在博弈论中，通常用移动作为“动作”的同义词，用局面作为“状态”的同义词。
通常将两个参与者分别称为$max$和$min$，$max$先移动，然后两个参与者轮流移动，直到博弈结束。博弈结束时，获胜者得分，而失败者受到惩罚。可以使用以下元素对博弈进行形式化定义。
1、$S_0$：初始状态，指定博弈开始时如何设置。
2、$To$-$Move(s)$：在状态$s$下，轮到其移动的参与者。
3、$Actions(s)$：在状态$s$下，全体合法移动的集合。
4、$Result(s, a)$：转移模型，定义状态$s$下执行动作$a$所产生的结果状态。
5、$Is$-$Terminal(s)$：终止测试，博弈结束时返回真，否则返回假。博弈结束时的状态称为终止状态。
6、$Utility(s, p)$：效用函数（也称为目标函数或收益函数），定义博弈结束时终止状态$s$下参与者$p$得到的最终的数值收益。
在对抗搜索中将完整的博弈树定义为搜索树，它会记录每个一直到终止状态的移动序列。如果状态空间本身是无界的，或者博弈规则允许局面可以无限次重复，那么博弈树可能是无限的，由于节点数过大博弈树被认为是一个在物理世界中无法实现的理论结构。
极小化极大搜索
给定博弈树，可以通过计算树中每个状态的极小化极大值确定最优策略，记为$Minimax(s)$。某一状态的极小化极大值是指，假设从该状态到博弈结束两个参与者都以最优策略行动，到达的终止状态对于$max$的效用值。终止状态的极小化极大值就是它的效用值。在非终止状态下，轮到$max$移动时，$max$倾向于移动到极小化极大值最大的状态，而$min$倾向于移动到极小化极大值最小的状态。所以有：
$$
Minimax\left( s \right) =\begin{cases}
Utility\left( s,Max \right)& Is\ Terminal\left( s \right)\\
\underset{a\in Actions\left( s \right)}{max}Minimax\left( \text{Re}sult\left( s,a \right) \right)& To\ Move\left( s \right) =Max\\
\underset{a\in Actions\left( s \right)}{min}Minimax\left( \text{Re}sult\left( s,a \right) \right)& To\,\,Move\left( s \right) =Min\\
\end{cases}
$$
极小化极大算法对博弈树进行完整的深度优先探索。如果树的最大深度为$m$，并且在每个点都有$b$种合法移动，那么极小化极大算法的时间复杂度为$O(b^m)$。对于一次生成所有动作的算法，空间复杂度为$O(bm)$，对于一次只生成一个动作的算法，空间复杂度为$O(m)$。指数级的复杂度使得$Minimax$无法应用于复杂博弈。
博弈的状态数关于树的深度是指数量级的。没有一种算法可以完全消除指数项，但有时可以将它减半，即通过剪枝消除对结果没有影响的树的大部分，从而不需要检查所有状态就能计算出正确的极小化极大决策。这种技术称为$\alpha $-$\beta $剪枝（alpha-beta pruning）。
$\alpha $-$\beta $剪枝得名于$Max-Value(state, \alpha , \beta )$中的两个额外参数，它们分别是路径上任何位置的倒推值的下界和上界：
$\alpha $：到目前为止，路径上发现的$max$的任一选择点中最佳（即最大值）选择的值。也就是说，$\alpha =$“至少”。
$\beta $：到目前为止，路径上发现的$min$的任一选择点中最佳（即最小值）选择的值。也就是说，$\beta =$“至多”。
$\alpha $-$\beta $搜索不断更新$\alpha $和$\beta $的值，并且一旦当前节点的值比此时的$\alpha $（对于$max$）或$\beta $（对于$min$）值更差，就剪掉该节点的剩余分支（即终止递归调用）。
$\alpha $-$\beta $剪枝的有效性很大程度上依赖于状态的检查顺序，这表明应该先检查有可能是最佳选择的后继节点。如果能够完美地实现这一点，$\alpha $-$\beta $搜索算法只需要检查$O(b^{m/2})$个节点就能选出最佳移动，而极小化极大算法需要$O(b^m)$。这意味着有效分支因子从$b$变为了$\sqrt{b}$，换句话说，在相同时间内，拥有完美移动顺序的$\alpha $-$\beta $剪枝可以求解的树的深度大约是极小化极大算法的两倍。
如果移动顺序随机，对于适当大小的$b$，需要检查的节点总数约为$O(b^{3m/4})$。显然无法实现完美移动顺序，但通常可以选择一个接近接近完美的简单的排序函数，能让检查的节点数减少到不超过最好情况的大约 2 倍。
在以往情况的搜索中，通往重复状态的冗余路径会导致搜索代价呈指数级增长，而维护一个先前到达状态的表可以解决这个问题。在博弈树搜索中，重复状态的产生是由于换位——移动序列的不同排列最终导致相同的局面，这个问题可以通过换位表解决，它将缓存状态的启发式值。换位表非常有效，在相同时间内能到达的搜索深度将扩大一倍。
即使采用剪枝和精巧的移动顺序，极小化极大算法也不适用于国际象棋和围棋这样的游戏，因为在可用时间内仍然有太多状态需要探索。克劳德·香农意识到这一问题，并提出了两种策略。A 型策略考虑搜索树中某一深度的所有可能的移动，然后使用启发式评价函数估计该深度下状态的效用值。它探索了树的宽但浅的部分。B 型策略舍弃了那些看起来就很差的移动，“尽可能”走那些更有可能的路线。它探索了树的深但窄的部分。
启发式$\alpha $-$\beta $树搜索
为了充分利用有限的计算时间，可以提前截断搜索，并对状态应用启发式评价函数，从而有效地将非终止节点转变为终止节点。换句话说，用$Eval$函数代替$Utility$函数，$Eval$对状态效用值进行估计。用截断测试代替终止测试，对于终止状态，截断测试必定返回真，但是它可以根据搜索深度和当前状态的任意属性自由决定何时终止搜索。这样得到搜索深度$d$处状态$s$的启发式极小化极大值的计算公式$H$-$Minimax(s, d)$：
$$
H~Minimax\left( s,d \right) =\begin{cases}
Eval\left( s,Max \right)& Is\,\,Cutoff\left( s \right)\\
\underset{a\in Actions\left( s \right)}{max}H~Minimax\left( \text{Re}sult\left( s,a \right) ,d+1 \right)& To\,\,Move\left( s \right) =Max\\
\underset{a\in Actions\left( s \right)}{min}H~Minimax\left( \text{Re}sult\left( s,a \right) ,d+1 \right)& To\,\,Move\left( s \right) =Min\\
\end{cases}
$$
启发式评价函数$Eval(s, p)$向参与者$p$返回状态$s$的期望效用的估计值。对于终止状态，一定是$Eval(s, p) = Utility(s, p)$，而对于非终止状态，估计值必须介于输和赢之间：$Utility(loss, p)\le Eval(s, p) \le Utility(win, p)$。除了满足这些需求之外，一个好的评价函数首先，计算时间不能太长！其次，评价函数应与实际的获胜机会密切相关。
控制搜索量最直接的方法是设置一个固定的深度限制，这样的话，对所有大于固定深度$d$的$depth$（以及所有终止状态），$Is$-$Cutoff(state, depth)$都返回$true$。深度$d$的选择取决于分配时间内所选择的移动。更稳健的方法是使用迭代加深。当时间耗尽时，程序将返回最深的已完成搜索所选择的移动。如果在每一轮迭代加深中，都维护换位表中的条目，那么作为奖励，后续轮次的速度将加快，我们可以使用评估值改进移动顺序。
由于评价函数只是一种近似，这些简单方法可能导致误差。评价函数只能应用于静态局面，也就是说，在这些
局面中不存在会使评估值大幅度摇摆变化的待定移动（例如吃掉皇后）。对于非静态局面，$Is$-$Cutoff$将返回$false$，并继续搜索直到到达静态局面。这种额外的静态搜索有时会被进一步限制为只考虑特定类型的移动（例如吃子），它能快速消除当前局面的不确定性。
视野效应则更难消除。它是指程序面临一个将给我方造成严重损失而且基本无法避免的对方移动，但可以使用拖延战术暂时避开。缓解视野效应的一种策略是允许单步延伸，该策略是说，即使搜索本应在此状态截断，但是，如果在给定局面中有比其他所有移动都“明显更好”的一种移动，就允许算法继续沿着这个移动延伸搜索。这会使树变得更深，但由于单步延伸通常很少，这一策略并不会增加很多节点，在实践中，它已被证明是有效的。
$\alpha $-$\beta $剪枝将剪掉对最终评估没有影响的树的分支，但前向剪枝将剪掉那些看上去很糟糕但也可能实际很好的移动。因此，这一策略以出错风险增大的代价节省了计算时间。用香农的话说，这是$B$型策略。显然，大多数人类棋手都会这么做，仅考虑每个局面的几步移动。前向剪枝的实现包括：
1、束搜索：在每一层，只考虑一“束”n 个最佳移动（根据评价函数），而不是所有可能的移动。遗憾的是，这种方法相当危险，因为无法保证最佳移动不被剪枝。
2、$ProbCut$概率截断算法：$\alpha $-$\beta $搜索的前向剪枝版本，它使用从先前经验中获得的统计数据来减少最佳移动被剪除的概率。$\alpha $-$\beta $搜索将剪除所有可证明位于当前$(\alpha $,$\beta )$窗口之外的节点。$ProbCut$算法则剪除有可能位于窗口之外的节点。它通过执行浅层搜索计算某个节点的倒推值$v$，然后利用过去的经验估计树中深度为$d$的节点的值$v$位于$(\alpha $,$\beta )$范围之外的可能性。布罗将这种技术应用到了他的黑白棋程序$Logistello$，发现即使常规版本的黑白棋程序拥有两倍的可用时间，$ProbCut$版本依然以 64%的获胜率击败了常规版本。
3、后期移动缩减技术：假设移动顺序已经调整好，因此在可能的移动的列表中后期才出现的移动不太可能是好的移动。这一技术没有将后期的移动完全删除，只是减少了搜索这些移动的深度，从而节省了时间。如果缩减后的搜索返回的值高于当前值，则可以重新运行全深度搜索。
对一个国际象棋程序来说，开局就考虑一个包含 10 亿个博弈状态的树似乎有些过犹不及：漫长的搜索得出的结论仅仅是移动兵。一个世纪以来，许多国际象棋书籍都介绍了如何下好开局和残局。因此，许多游戏程序使用也可以使用查表而非搜索来处理开局和残局。
对于开局，计算机主要依靠人类的专业知识。可以从书中复制人类专家关于如何打好每个开局的最佳建议并将其输入表中供计算机使用。此外，计算机还可以从以前玩过的游戏的数据库中收集统计数据，以判断哪种开局最容易取胜。最开始的几步可能的局面很少，大多数局面都能存储在表中。通常，移动 10～15 步后，我们会到达一个很少见到的局面，程序必须从查表切换到搜索。
在游戏接近结束时，可能的局面又变少，因此更容易查表。这是计算机的专长：计算机对残局的分析能力远远超过了人类。另外，计算机可以通过生成一种策略完全解决残局问题，这一策略是从每种可能状态到该状态下最佳移动的映射。这样计算机就可以在这个表中查到正确移动从而完美完成棋局。
这个表由逆向极小化极大搜索构建：首先考虑在棋盘上放置 KBNK 的所有方法。有些局面是白方获胜，将它们标为“赢”。然后反转国际象棋规则，做逆向移动。无论黑方的应对是什么，白方的任何一步最终位于“赢”局面的移动，都标为“赢”。继续上述搜索，直到所有可能局面都被解析为赢、输或平局，这样就得到了一个包含所有 KBNK 残局的准确无误的查询表。这种做法不仅适用于 KBNK 残局，也适用于所有棋子数不超过 7 的残局，这样的表格包含 400 万亿个状态。棋子数为 8 的表则包含 40 000 万亿个状态。
