Games -- Trees, Minimax, Pruning

进入新的一章, 我们从单智能体环境（智能体与一个被动的世界互动）进入到多智能体的对抗性搜索 (Adversarial Search) 环境中。在这里，环境中存在其他智能体（对手），它们会主动采取行动来阻挠我方目标的实现。

当存在一个理性对手时，一个智能体不能再简单地寻找一条通往目标的路径。它必须假设对手也会采取最优的行动来对抗自己。因此，智能体的策略必须是：在所有可能的对手回应中，选择那个能保证自己获得“最坏情况下的最好结果”的行动。

对抗搜索与博弈树 (Adversarial Search & Game Trees)

对抗搜索问题通常被形式化为博弈 (Games)。这些博弈是零和 (zero-sum) 的，意味着一个玩家的收益就是另一个玩家的损失。

思考这类游戏最简单的方式是将其定义为单个变量值，其中一方或智能体试图最大化，而另一方或智能体试图最小化，从而形成直接竞争。在《吃豆人》中，这个变量是你的得分，你试图通过快速高效地吃豆子来最大化得分，而鬼魂则试图通过首先吃掉你来最小化得分。许多常见的家用游戏也属于这类游戏：如Checkers(跳棋), Chess(国际象棋), Go(围棋)等.

与返回全面计划的常规搜索不同，对抗性搜索返回一个策略或政策，它仅根据我们的智能体及其对手的某种配置推荐最佳可能的移动。

而博弈树 (Game Tree), 就是表示博弈的一种形象方式。其具有以下几个组成部分: - 节点 (Nodes)：代表博弈中的状态 (states)。

• 边 (Edges)：代表玩家可以采取的行动 (moves)。

• 叶节点 (Terminal Nodes)：代表博弈结束的状态，每个叶节点都有一个效用值 (utility value)，表示该结局对第一个玩家（通常称为MAX）的好坏程度。

Minimax 算法

Minimax 是在对抗博弈中找到最优策略的基础算法, 该算法基于一个激励性的假设运行，即我们面对的对手会采取最优行为，并且始终执行对我们最不利的移动。

同时, 它的名字完美地概括了其核心逻辑：最大化 (Maximize) 自己在对手最小化 (Minimize) 自己收益后的得分。

玩家角色：

• MAX 玩家：试图最大化最终的效用值。

• MIN 玩家：试图最小化MAX玩家的最终效用值。

算法流程（自底向上递归） ：

• 生成博弈树：从当前状态开始，一直向下探索到博弈结束的终端状态。

• 计算终端节点的效用：根据游戏规则，为每个终端状态（叶节点）分配一个效用值。

• 递归回溯：从叶节点开始，逐层向上计算每个非终端节点的Minimax值。

  • 对于 MIN 节点：该节点的Minimax值是其所有子节点中的最小值。

  • 对于 MAX 节点：该节点的Minimax值是其所有子节点中的最大值。

• 做出决策：在根节点，MAX玩家选择那个通往具有最高Minimax值的子节点的行动。

在实现中，minimax 的行为与深度优先搜索类似，计算节点的值的顺序与 DFS 相同，从最左边的终端节点开始，依次向右迭代。更精确地说，它对游戏树进行后序遍历。

Minimax算法可以为任何有限的、确定性的、完全信息下的双人零和博弈找到最优的行动策略。但它的缺点是必须遍历整个博弈树，时间复杂度为 O(b^m)，在像国际象棋这样复杂的博弈中是不可行的。

Alpha-Beta 剪枝 (Alpha-Beta Pruning)

Alpha-Beta剪枝是Minimax算法的一个极其重要的优化，它可以在不影响最终决策的情况下，剪掉博弈树中大量不必要的分支。

其核心思想是, 在搜索过程中，如果一个分支的探索结果已经被证明不可能比当前已找到的最佳选择更好，那么就没有必要再继续探索这个分支了。

两个关键变量：

• α (Alpha)：在从根节点到当前节点的路径上，MAX玩家目前能确保获得的最低分数。

• β (Beta)：在从根节点到当前节点的路径上，MIN玩家目前能确保获得的最高分数（即MAX玩家能获得分数的上限）。

剪枝规则 ：

• Alpha 剪枝 (在MIN节点)：如果一个MIN节点的某个子节点的值 v 小于或等于当前路径上的 α 值，那么这个MIN节点就可以被剪枝了。

  • 因为我们知道MAX玩家在MIN的同一层其他兄弟上已经有了一个至少能得到 α 的选择。而当前这个MIN节点保证了MAX玩家最多只能得到 v（因为MIN会选择最小的）。既然 v ≤ α，MAX玩家就绝不会选择走向这个MIN节点的路径。因此，该MIN节点的其他子节点无需再探索。

如图, 当探索完左侧节点3之后, MAX根节点已经至少得到了3, 而中间的MIN节点此时最好情况也是2, 因此MAX根本不需要考虑这个节点的其余子节点

• Beta 剪枝 (在MAX节点)：如果一个MAX节点的某个子节点的值 v 大于或等于当前路径上的 β 值，那么这个MAX节点就可以被剪枝了。

  • 因为我们知道MIN玩家在更高层已经有了一个能把MAX玩家的得分限制在 β 以下的选择。而当前这个MAX节点至少能得到 v。既然 v ≥ β，MIN玩家就绝不会让游戏走到这个MAX节点的路径上来。因此，该MAX节点的其他子节点无需再探索。

需要注意的是, 剪枝的效率高度依赖于行动的顺序。如果总是先探索最好的行动，Alpha-Beta剪枝可以将需要探索的节点数从 O(b^m) 减少到大约 O(b^m/2)，这相当于将可搜索的深度加倍，是一个巨大的提升。

评估函数 (Evaluation Functions)

为什么需要评估函数？—— 现实的妥协

Minimax 和 Alpha-Beta 剪枝算法在理论上是完美的，它们能为任何有限的、确定性的博弈找到最优解。但这里有一个巨大的现实障碍：计算资源的限制。

对于像国际象棋（分支因子约35，深度可达80层）或围棋这样的复杂博弈，其完整的博弈树比宇宙中的原子还要多。即使是最高效的 Alpha-Beta 剪枝算法，也无法在有限的时间内（比如比赛规定的几分钟内）搜索到游戏的终局。

既然我们无法“看到”游戏的结局，我们就必须在某个点停止搜索，并对当前的局面进行“估算”。这个“估算”就是通过评估函数来完成的。

简单来说，评估函数是我们在无法进行完美、完整的逻辑推演时，所采用的一种基于经验和特征的、不完美的“直觉”判断。

定义

评估函数是一个启发式函数，它接收一个非终端的游戏状态（例如，一个中盘的棋局）作为输入，并输出一个数值，这个数值估计了该状态对 MAX 玩家的最终效用值。

它将一个非终端节点“伪装”成一个终端节点。当 Alpha-Beta 搜索达到预设的深度限制 (depth limit) 时，它就不再继续向下扩展，而是调用评估函数来为这个“叶”节点打分。这个分数随后会被用于 Minimax 的回溯计算中。

与启发式 h(n) 的区别：

• 在A*搜索中，启发式 h(n) 估计的是从当前状态到目标的剩余成本。

• 在博弈中，评估函数估计的是从当前状态开始，如果双方都下得很好，最终整个游戏的结局对MAX玩家的效用。

如何设计评估函数？

一个好的评估函数需要能够快速而准确地判断局势的优劣。这通常通过以下步骤实现：

1. 提取特征 (Features)：

• 首先，我们需要从游戏状态中提取出一系列能够反映局势优劣的关键特征。

• 国际象棋示例：

  • 棋子自身优势 (Material Advantage)：这是最基础的特征。通常会给每个棋子赋一个分值（例如，兵=1，马=3，象=3，车=5，后=9），然后计算双方棋子分值的差。

  • 棋子位置和机动性 (Piece Position & Mobility)：一个位于中心位置的马比在角落里的马更有价值。一个能够移动到很多位置的棋子比被困住的棋子更有价值。

  • 兵形结构 (Pawn Structure)：是否存在孤兵、叠兵等弱点。

2. 加权线性函数 (Weighted Linear Function)：

• 常见的做法是将这些特征组合成一个加权线性函数，来计算总的评估值。

• EVAL(s) = w₁f₁(s) + w₂f₂(s) + ... + wₙfₙ(s)

  • s：当前的游戏状态。

  • fᵢ(s)：第 i 个特征在状态 s 下的数值（例如，f₁ 可能是白方棋子总分减去黑方棋子总分）。

  • wᵢ：第 i 个特征的权重。这个权重反映了该特征在决定胜负中的重要性。例如，王的安全性的权重可能比兵形结构的权重要高。

这些特征和权重的选择，是深层领域知识的体现。在国际象棋中，它们来自于数百年人类大师对弈经验的总结。在现代AI中，这些权重也可以通过机器学习的方法，让程序通过分析大量的棋局数据（甚至是自我对弈）来自动学习和优化。