第 II 部分 · 问题求解
第 5 章 对抗搜索与博弈
Chapter 5 · Adversarial Search and Games
本章导读
多智能体零和场景下，对手会针对性反制你的最优策略。以博弈树为核心，从 Minimax、α-β 剪枝到蒙特卡洛树搜索，讲解时限与随机性下的近似最优决策。
学习要点
- 博弈的形式化：带 MIN 对手的搜索问题，MAX / MIN 节点交替；多人博弈的扩展。
- Minimax 算法与最优对策；含随机因素（骰子）时的期望 minimax。
- α-β 剪枝：结果完全等价的大幅加速，剪枝效率取决于动作排序的好坏。
- 实时决策：深度受限搜索 + 评价函数（特征线性组合）、截断测试与前瞻。
- 蒙特卡洛树搜索：选择 / 扩展 / 模拟 / 回传四步循环，AlphaGo 战胜人类的基石。
核心概念
| 术语 | English | 一句话解释 |
|---|---|---|
| 博弈树 | Game Tree | 双方交替行动形成的与 / 或树 |
| Minimax | Minimax | 最小化对手最大收益的递归决策准则 |
| α-β 剪枝 | Alpha-Beta Pruning | 利用上下界省略不影响决策的分支 |
| 评价函数 | Evaluation Function | 对非叶局面效用的启发式估计 |
| 截断搜索 | Cutoff Test | 时限约束下限制深度的搜索 |
| 期望节点 | Chance Node | 引入随机性的期望值层 |
| 蒙特卡洛树搜索 | MCTS | 随机模拟驱动非对称扩展的搜索框架 |
| UCT | Upper Confidence Bound for Trees | MCTS 中平衡探索与利用的选择公式 |
| 完全信息博弈 | Perfect Information | 双方对状态完全透明（如国际象棋） |
配套代码（aima-python）
aima-python 是官方维护的开源算法库（MIT 协议），建议每学完一章就跑一遍对应模块的示例。