博弈
博弈的主要特点：
- 超过两个以上玩家可以改变状态
- 不同玩家有不同的利益取向，并以此来改变世界
博弈的特点：
- 完全信息（可完全预测），或者不完全信息（不可完全观测）
- 确定性，或者随机性（存在随机性的元素）
- 一次性博弈，多步博弈，有限步数，无限步数
- 零和博弈，负和博弈，正和博弈
搜索和对抗性搜索的区别：
| 搜索 | 对抗性搜索 | |
|---|---|---|
| 玩家个数 | 单智能体 | 多智能体 |
| 解 | 启发式方法 | 策略 |
| 解的质量 | 最优解 | 近似解 |
| 评价函数 | 到达目标的代价估计 | 评价目前局势的好坏 |
MiniMax
考虑这样的游戏：
- 两个理性玩家，轮流操作
- Max 玩家希望最大化分数，Min 玩家希望最小化部署
策略：在搜索时，如果轮到 Max 玩家，则求后继状态分数的最大值；如果轮到 Min 玩家，则求后继状态分数的最小值。
Alpha-beta 剪枝
思路：如果在搜索的时候，如何已经可以知道不可能会被走到，那么就不需要继续扩展。
对于 Max 节点 $S$：
- 记 $\alpha_s$ 为 $S$ 是被遍历过的子节点的最大值，$\beta_S$ 是当前遍历过的 $S$ 的兄弟的最小值
- 当持续更新 $\alpha_S$ 的时候，发现有 $\alpha_S \ge \beta_S$ 那么就可以停止该结点的搜索，因为该结点不可能造成它的父节点的更新。
对于 Min 节点 $S$：
- 记 $\alpha_s$ 为当前遍历过的 $S$ 的兄弟的最大值，$\beta_S$ 是是被遍历过的子节点的最小值
- 当持续更新 $\alpha_S$ 的时候，发现有 $\alpha_S\ge \beta_S$ 那么就可以停止该结点的搜索，因为该结点不可能造成它的父节点的更新。
Alpha-beta 剪枝的泛化：如果 $m’$ 是 $n$ 的祖先节点，且 $m’$ 是 Max 节点，$n$ 是 Min 节点，$\alpha(m’) \ge \beta(n)$ 则 $n$ 可以停止目前的搜索。
- Alpha 剪枝：若 Max 的 alpha 值大于等于任何祖先的 Min 结点的 beta 值，则进行 alpha 剪枝。
- Beta 剪枝：若 Min 的 beta 值小于等于任何祖先的 Max 节点的 alpha 值，进行 beta 剪枝
经过了剪枝之后，如果节点遍历的顺序是最优的（最优的动作最先遍历），那么使用 alpha-beta 剪枝需要遍历的节点数为 $O(b^{d/2})$.
在真实游戏中，搜索根本无法扩展到叶子结点。需要设计启发式函数来计算非叶子节点的估计值。
- 使得终止节点的排序和原来的效用函数一致
- 计算简便
- 对于非叶子节点，评价函数需要与这个节点实际能获得胜利的概率强相关。