对抗性搜索与博弈

对抗性搜索是研究竞争环境中决策制定的学科，其中智能体必须在博弈树中选择行动，以对抗试图实现相反结果的对手。

Definition

对抗性搜索通过探索博弈树来计算玩家的行动，其中玩家轮流行动，并使用最小最大原理（每个玩家都假设对手会采取最优行动来优化自身）以及剪枝和启发式评估来处理大型博弈树。

Scope

本主题涵盖双人、零和、完全信息博弈中的搜索：包括最小最大决策规则、允许最小最大算法跳过明显不相关分支的Alpha-Beta剪枝、针对过大而无法精确求解的博弈的评估函数和深度受限搜索，以及针对分支因子非常大的博弈的蒙特卡洛树搜索。它探讨了博弈树的建模方式以及计算限制如何强制进行启发式截断。它不包括多智能体激励的一般博弈论均衡分析，该内容在多智能体系统下进行处理。

Core questions

• 最小最大规则如何确定对抗最优对手的最优行动？
• Alpha-Beta剪枝如何在不影响最小最大值的情况下消除分支？
• 在大型博弈中，评估函数如何用于在固定深度处截断搜索？
• 蒙特卡洛树搜索何时优于深度受限的最小最大搜索？

Key concepts

• 博弈树
• 最小最大值
• Alpha-Beta剪枝
• 评估（启发式）函数
• 深度受限搜索和地平线效应
• 零和完全信息博弈
• 蒙特卡洛树搜索
• 走法排序

Key theories

最小最大决策规则

在双人零和博弈中，每个玩家选择能最大化其自身最小保证结果的行动；将这些最大/最小值沿博弈树向上传播，即可在根节点得到最优行动。

Alpha-Beta剪枝

通过跟踪已保证给最大化和最小化玩家的最佳值，Alpha-Beta搜索证明某些子树无法影响最终决策并跳过它们，从而返回精确的最小最大值，并且在最佳情况下，可以在给定时间内将可达深度大致平方。

蒙特卡洛树搜索

当分支因子过大而无法进行穷举性前瞻时，蒙特卡洛树搜索通过随机模拟和平衡探索与利用的选择规则来构建非对称树，这种方法改变了围棋等博弈中的计算机对弈方式。

Clinical relevance

对抗性搜索产生了里程碑式的人工智能系统，从使用Alpha-Beta搜索的国际象棋引擎到基于蒙特卡洛树搜索的围棋程序，同样的技术也为自动化谈判、安全博弈以及任何被建模为优化方之间竞争的场景提供了信息。

History

香农1950年的论文将计算机国际象棋框定为带有评估函数的最小最大搜索，而冯·诺依曼的最小最大定理提供了博弈论基础。Alpha-Beta剪枝在1950年代至1960年代发展起来，并由克努特和摩尔（1975）进行了严格分析。蒙特卡洛树搜索于2000年代正式化，推动了博弈能力的下一次飞跃，尤其是在围棋领域。

Key figures

• Claude E. Shannon
• John von Neumann
• Arthur Samuel
• Donald E. Knuth
• Ronald W. Moore

Seminal works

• shannon1950
• knuth1975
• browne2012

Frequently asked questions

Alpha-Beta剪枝会改变最小最大算法选择的行动吗？

不会。Alpha-Beta剪枝返回的值和行动与完整最小最大算法完全相同；它只是避免探索那些明显无法影响结果的分支。其好处是速度，并且在走法排序良好的情况下，它可以在相同时间内搜索大约两倍的深度。

为什么在围棋等博弈中要使用蒙特卡洛树搜索而不是最小最大搜索？

围棋的分支因子巨大，并且缺乏简单准确的评估函数，因此固定深度的最小最大搜索效率低下。蒙特卡洛树搜索通过多次随机模拟来估计走法质量，并选择性地向有希望的线路增长树，这在这种博弈中具有更好的扩展性。