对抗搜索与博弈

对抗搜索和博弈

本笔记主要讨论对抗搜索和博弈，通过本笔记的内容，我们可以掌握解决井字棋、国际象棋、围棋的算法。

MiniMax

MiniMax算法可以解决井字棋等状态空间不够大的双人零和博弈问题。

双人零和博弈就是两个人进行一场游戏，该游戏的结果要么是某一个人获胜、要么是平局，而不存在两个人都获胜的情况。在我的笔记算法>>动态规划中已经解决过Coin Game和井字棋游戏并介绍了Minimax思想。

AIMA将两个参与者分别称为MAX和MIN。这个很好理解，假设我们自己是参与者，那么我们自己就是MAX，对手就是MIN——这个MIN本身是从我们自己的角度来看的，对手为了最大化自己的利益，从而导致我们的利益在对方的轮次被最小化了。

形式化定义

我们将博弈形式化为一个搜索问题，包含以下要素：

• 初始状态 \(s_0\)：棋盘的初始配置以及轮到哪个玩家走棋。
• 玩家函数 \(\text{TO-MOVE}(s)\)：返回在状态 \(s\) 下轮到哪位玩家。
• 动作函数 \(\text{ACTIONS}(s)\)：返回在状态 \(s\) 下合法的走法集合。
• 转移模型 \(\text{RESULT}(s, a)\)：返回执行动作 \(a\) 后的新状态。
• 终止测试 \(\text{IS-TERMINAL}(s)\)：判断游戏是否结束（胜、负或平局）。
• 效用函数 \(\text{UTILITY}(s, p)\)：给终局状态 \(s\) 对玩家 \(p\) 赋一个数值。例如在井字棋中，胜利 = +1，失败 = -1，平局 = 0。

算法思想

MiniMax 算法通过递归地展开整棵博弈树来做出最优决策。核心思想是：

• 当轮到 MAX 走棋时，MAX 选择使效用值最大化的动作。
• 当轮到 MIN 走棋时，MIN 选择使效用值最小化的动作。

算法的伪代码如下：

function MINIMAX-SEARCH(game, state):
    player ← game.TO-MOVE(state)
    value, move ← MAX-VALUE(game, state)
    return move

function MAX-VALUE(game, state):
    if game.IS-TERMINAL(state):
        return game.UTILITY(state, MAX), null
    v ← -∞
    for each a in game.ACTIONS(state):
        v2, a2 ← MIN-VALUE(game, game.RESULT(state, a))
        if v2 > v:
            v, move ← v2, a
    return v, move

function MIN-VALUE(game, state):
    if game.IS-TERMINAL(state):
        return game.UTILITY(state, MAX), null
    v ← +∞
    for each a in game.ACTIONS(state):
        v2, a2 ← MAX-VALUE(game, game.RESULT(state, a))
        if v2 < v:
            v, move ← v2, a
    return v, move

复杂度分析

设博弈树的最大深度为 \(m\)，每个节点的合法动作数（分支因子）为 \(b\)，则：

• 时间复杂度：\(O(b^m)\) —— 需要遍历整棵博弈树。
• 空间复杂度：\(O(bm)\) —— 深度优先搜索只需维护从根到当前节点的路径。

对于井字棋而言，\(b \approx 5\)（平均分支因子），\(m = 9\)（最多9步），状态空间约为 \(9! = 362880\)，完全可以穷举。但对于国际象棋（\(b \approx 35, m \approx 80\)）或围棋（\(b \approx 250, m \approx 150\)），朴素的 MiniMax 是不可行的。

井字棋例子

考虑一个简化的井字棋局面：假设当前轮到 MAX（X）走棋，棋盘上已经有若干棋子。MiniMax 的求解过程如下：

1. 展开博弈树：从当前局面出发，MAX 枚举所有空格作为可能的落子位置。
2. 递归求解：对每个 MAX 的走法，轮到 MIN（O）走棋，MIN 同样枚举所有走法，如此交替递归直到终局。
3. 回传效用值： - 在叶节点（终局状态），用效用函数直接赋值：X 胜 = +1，O 胜 = -1，平局 = 0。 - MIN 层取子节点中的最小值回传。 - MAX 层取子节点中的最大值回传。
4. 选择最优动作：MAX 在根节点选择回传值最大的那个动作。

例如在某个局面下，MAX 有三个可选位置 A、B、C。经过完整的递归展开后，A 回传值为 0（平局），B 回传值为 +1（MAX 必胜），C 回传值为 -1（MIN 必胜）。MAX 选择 B。

MiniMax 的最优性

在双方都最优博弈的前提下，MiniMax 保证找到纳什均衡策略。对于井字棋，MiniMax 可以证明：在双方都最优的情况下，结果一定是平局。

---

Alpha-Beta 剪枝

对于国际象棋等状态空间巨大而不能使用朴素的 Minimax 方法的情况，我们使用 Alpha-Beta 剪枝。Alpha-Beta 剪枝的核心思想是：如果我们已经知道某个分支不可能比当前已知的最优选择更好，就没必要继续探索它。

剪枝原理

Alpha-Beta 剪枝维护两个值：

• \(\alpha\)（Alpha）：当前搜索路径上，MAX 已经保证能获得的最低收益（MAX 的下界）。初始值为 \(-\infty\)。
• \(\beta\)（Beta）：当前搜索路径上，MIN 已经保证能获得的最高收益（MIN 的上界，从 MAX 视角看是上界）。初始值为 \(+\infty\)。

剪枝条件：

• 在 MIN 节点中，如果当前节点的值 \(v \leq \alpha\)，则发生 \(\alpha\) 剪枝 —— MAX 不会选择进入这个分支，因为 MAX 在祖先节点已经有更好的选择。
• 在 MAX 节点中，如果当前节点的值 \(v \geq \beta\)，则发生 \(\beta\) 剪枝 —— MIN 不会选择进入这个分支，因为 MIN 在祖先节点已经有更好的选择。

简而言之：一旦 \(\alpha \geq \beta\)，就可以剪枝。

伪代码

function ALPHA-BETA-SEARCH(game, state):
    player ← game.TO-MOVE(state)
    value, move ← MAX-VALUE(game, state, -∞, +∞)
    return move

function MAX-VALUE(game, state, α, β):
    if game.IS-TERMINAL(state):
        return game.UTILITY(state, MAX), null
    v ← -∞
    for each a in game.ACTIONS(state):
        v2, a2 ← MIN-VALUE(game, game.RESULT(state, a), α, β)
        if v2 > v:
            v, move ← v2, a
            α ← max(α, v)
        if v ≥ β:
            return v, move    // β 剪枝
    return v, move

function MIN-VALUE(game, state, α, β):
    if game.IS-TERMINAL(state):
        return game.UTILITY(state, MAX), null
    v ← +∞
    for each a in game.ACTIONS(state):
        v2, a2 ← MAX-VALUE(game, game.RESULT(state, a), α, β)
        if v2 < v:
            v, move ← v2, a
            β ← min(β, v)
        if v ≤ α:
            return v, move    // α 剪枝
    return v, move

复杂度与走法排序

Alpha-Beta 剪枝的效率高度依赖于走法排序（Move Ordering）：

• 最坏情况：走法排序极差，没有任何剪枝发生，退化为普通 MiniMax，时间复杂度为 \(O(b^m)\)。
• 最优情况：走法排序完美（总是先搜索最优走法），时间复杂度降低到 \(O(b^{m/2})\)。这意味着在相同时间内，Alpha-Beta 可以搜索两倍深度的博弈树。

走法排序启发式

实践中常用的排序策略包括：

• 迭代加深（Iterative Deepening）：先做浅层搜索，用上一轮搜索的结果指导下一轮的走法排序。
• 杀手启发式（Killer Heuristic）：优先尝试在兄弟节点中产生过剪枝的走法。
• 历史启发式（History Heuristic）：根据走法在整棵搜索树中的历史表现排序。
• 置换表（Transposition Table）：用哈希表记录已评估过的局面，避免重复搜索。

评估函数与截断搜索

在实际应用中（如国际象棋引擎），由于无法搜索到终局，我们通常在某个深度 \(d\) 处截断搜索，并用一个评估函数（Evaluation Function） \(\text{EVAL}(s)\) 来估计非终局状态的效用值。好的评估函数应满足：

1. 终局状态的评估与真实效用一致。
2. 计算速度快。
3. 与实际胜率强相关。

国际象棋中经典的评估函数基于棋子价值：兵 = 1，马/象 = 3，车 = 5，后 = 9，再加上位置、控制力、王的安全性等修正项。

---

蒙特卡洛树搜索

对于围棋这样的超过宇宙原子数的状态空间的游戏，即使有 Alpha-Beta 剪枝和精心设计的评估函数也远远不够。我们使用蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）。

MCTS 的核心思想截然不同：不需要评估函数，而是通过大量随机模拟（rollout/playout）来统计估计每个走法的胜率。

四个阶段

MCTS 的每一轮迭代包含四个阶段：

1. 选择（Selection）

从根节点开始，根据树策略（Tree Policy），沿着已经展开的树向下选择子节点，直到到达一个叶节点（尚有未展开子节点的节点）。选择策略需要在利用（Exploitation）和探索（Exploration）之间取得平衡。

2. 扩展（Expansion）

在选定的叶节点处，将一个或多个尚未展开的子节点加入树中。

3. 模拟（Simulation / Rollout）

从新扩展的节点出发，执行一次随机模拟直到游戏结束。在朴素 MCTS 中，模拟阶段的走法完全随机选取（或使用简单的启发式策略）。

4. 回传（Backpropagation）

将模拟结果（胜/负/平）沿路径向上回传，更新路径上每个节点的访问次数 \(N\) 和累计胜场 \(Q\)。

这四个阶段不断重复，直到达到计算预算（时间或迭代次数限制），然后选择根节点下访问次数最多的子节点作为最终走法。

UCB1 公式

选择阶段最常用的策略是 UCT（Upper Confidence Bounds for Trees），基于 UCB1 公式：

\[ \text{UCB1}(v_i) = \frac{Q(v_i)}{N(v_i)} + C \cdot \sqrt{\frac{\ln N(v)}{N(v_i)}} \]

其中：

• \(Q(v_i)\)：子节点 \(v_i\) 的累计收益（胜场数或得分总和）。
• \(N(v_i)\)：子节点 \(v_i\) 的访问次数。
• \(N(v)\)：父节点 \(v\) 的访问次数。
• \(C\)：探索常数，控制利用与探索的权衡。\(C = \sqrt{2}\) 是理论最优值，实践中常需调整。

公式的第一项 \(\frac{Q(v_i)}{N(v_i)}\) 是利用项，倾向于选择历史胜率高的节点；第二项 \(C \cdot \sqrt{\frac{\ln N(v)}{N(v_i)}}\) 是探索项，倾向于选择访问次数少的节点。

UCB1 的理论保证

UCB1 可以证明，随着迭代次数趋于无穷，MCTS 的策略会收敛到 MiniMax 最优策略。这意味着给定足够的计算资源，MCTS 可以解决任何有限的完全信息博弈。

MCTS 与围棋

围棋的状态空间约为 \(10^{170}\)（合法局面约 \(2 \times 10^{170}\)），远超国际象棋的 \(10^{47}\)。围棋之所以特别难，有以下原因：

1. 分支因子极大：\(b \approx 250\)，而国际象棋只有约 35。
2. 评估函数极难设计：围棋的局面评估远比国际象棋复杂，很难用简单的规则量化。
3. 对局很长：平均约 150 手，每一手都有巨大的选择空间。

MCTS 在围棋上的成功源于它不需要评估函数。早期的围棋程序（如 MoGo、Crazy Stone、Fuego）基于朴素 MCTS，通过在 rollout 策略中加入一些围棋领域知识（如常见棋形、征子判断），在 \(9 \times 9\) 小棋盘上达到了业余高段水平，但在 \(19 \times 19\) 标准棋盘上仍然只有业余低段水平。

AlphaGo：MCTS + 深度强化学习

AlphaGo（DeepMind, 2016）在 MCTS 的核心框架上做了关键改进：

• 策略网络（Policy Network）：用深度卷积神经网络替代随机 rollout，引导 MCTS 的选择和扩展阶段，大幅缩小搜索宽度。
• 价值网络（Value Network）：用深度网络直接评估局面的胜率，替代 rollout 到终局的需要，大幅减少搜索深度。
• 强化学习自我博弈：通过自我对弈不断提升策略网络和价值网络的质量。

AlphaGo 的后续版本 AlphaGo Zero 完全去掉了人类棋谱数据，仅通过自我博弈从零开始学习，在 72 小时内超越了所有前代版本。AlphaZero 进一步将这一框架推广到国际象棋和将棋，在所有三种棋类中都超越了最强的专用引擎。

从搜索到学习

AlphaGo 的成功展示了一个重要范式：搜索（MCTS）+ 学习（深度强化学习）的结合可以解决传统方法无法企及的问题。这一思想在大语言模型时代被继承——例如 OpenAI 的 o1 模型通过搜索+学习的方式提升推理能力。

---

期望极小极大搜索（Expectiminimax）

现实中许多博弈包含随机因素，如西洋双陆棋中的掷骰子。Expectiminimax 在 MiniMax 的基础上引入了机会节点（Chance Node）。

博弈树中有三种节点类型：

• MAX 节点：选择使价值最大化的动作
• MIN 节点：选择使价值最小化的动作
• Chance 节点：对所有可能的随机结果取期望值

\[ \text{EXPECTIMINIMAX}(s) = \begin{cases} \text{UTILITY}(s) & \text{if IS-TERMINAL}(s) \\ \max_a \text{EXPECTIMINIMAX}(\text{RESULT}(s, a)) & \text{if TO-MOVE}(s) = \text{MAX} \\ \min_a \text{EXPECTIMINIMAX}(\text{RESULT}(s, a)) & \text{if TO-MOVE}(s) = \text{MIN} \\ \sum_r P(r) \cdot \text{EXPECTIMINIMAX}(\text{RESULT}(s, r)) & \text{if } s \text{ 是机会节点} \end{cases} \]

复杂度：若随机结果有 \(n\) 种可能，则分支因子变为 \(b \times n\)，时间复杂度为 \(O((bn)^m)\)。

Alpha-Beta 剪枝的限制

在 Expectiminimax 树中，Alpha-Beta 剪枝不能直接使用，因为机会节点的值是加权平均，无法简单地用上下界剪掉。需要使用改进的 Star1/Star2 剪枝 算法，利用效用函数的值域进行有限剪枝。

---

不完美信息博弈

上述所有算法都假设完美信息——所有玩家都能看到完整的游戏状态。但许多现实博弈是不完美信息（Imperfect Information） 的，如扑克、桥牌。

信息集（Information Set）

在不完美信息博弈中，玩家无法区分某些状态。处于同一信息集中的所有状态，对该玩家来说是不可分辨的。

\[ \text{信息集 } I_i = \{s \in S : s \text{ 对玩家 } i \text{ 不可分辨}\} \]

求解方法

1. 确定化搜索（Determinization）

最简单的方法：将不完美信息博弈转化为多个完美信息博弈，然后分别求解并取平均。

• 从当前信息集中随机采样多个可能的完整状态
• 对每个完整状态使用普通 Alpha-Beta 或 MCTS 求解
• 投票或平均各解的推荐动作

确定化的缺陷

确定化忽略了信息不对称的战略价值。例如在扑克中，确定化不会建议虚张声势（bluffing），因为在每个确定化的世界中，对手都"知道"你的牌。这被称为 Strategy Fusion 问题。

2. 反事实遗憾最小化（CFR, Counterfactual Regret Minimization）

CFR 是目前求解大规模不完美信息博弈最成功的方法：

• 遗憾（Regret）：衡量"如果当时换一个动作，我能多赢多少"
• 反事实遗憾：考虑对手的策略后，每个动作的遗憾值

\[ R_i^T(I, a) = \sum_{t=1}^T \left[ v_i(\sigma_I^{I \to a}, t) - v_i(\sigma, t) \right] \]

• 策略更新：用 Regret Matching 将正遗憾归一化为下一轮的混合策略
• 收敛保证：平均策略收敛到纳什均衡

CFR 的成功案例：

• Libratus（CMU, 2017）：在无限注德州扑克（Heads-Up No-Limit Texas Hold'em）中击败了顶级人类职业选手，决策点数量达 \(10^{161}\)
• Pluribus（CMU & Facebook, 2019）：将不完美信息博弈扩展到六人对局

3. 信息集MCTS（IS-MCTS）

将 MCTS 扩展到不完美信息博弈：

• 在每次迭代开始时，从当前信息集中采样一个确定状态
• 在搜索树中，按信息集而非具体状态合并节点
• 平衡了确定化和精确求解之间的trade-off

---

多人博弈

当参与者超过两人时，问题发生本质变化：不再是零和博弈，因此 MiniMax 不直接适用。

多人极大极大搜索

将效用函数从标量扩展为向量 \(\mathbf{V}(s) = (V_1(s), V_2(s), \ldots, V_n(s))\)，每个玩家 \(i\) 在自己的轮次选择使 \(V_i\) 最大化的动作。

联盟与背叛

在多人博弈中，玩家可能形成临时联盟——两个弱者联合对抗强者。这使得博弈分析远比两人情况复杂：

• 合作博弈论：研究稳定联盟的形成条件
• 核心（Core）：没有任何子联盟有动机偏离的分配方案
• Shapley值：公平分配联盟收益的方法

---

现代博弈AI总览

博弈类型	代表性游戏	核心算法	里程碑
完美信息·确定性	井字棋	MiniMax	完全可解
完美信息·确定性	国际象棋	Alpha-Beta + 评估函数	Deep Blue (1997)
完美信息·确定性	围棋	MCTS + 深度RL	AlphaGo (2016)
完美信息·随机性	西洋双陆棋	Expectiminimax + TD学习	TD-Gammon (1992)
不完美信息	德州扑克	CFR + 抽象	Libratus (2017)
不完美信息·多人	六人扑克	CFR + 深度搜索	Pluribus (2019)
合作	花火（Hanabi）	Theory of Mind + 搜索	开放问题
多人·大规模	星际争霸II	多智能体RL	AlphaStar (2019)
多人·大规模	Dota 2	PPO + 自我博弈	OpenAI Five (2019)

---

博弈搜索的前沿方向

1. LLM 推理中的搜索

大语言模型时代的推理能力提升越来越依赖搜索：

• Best-of-N 采样：生成 \(N\) 个回答，用验证器选最优——本质是蒙特卡洛采样
• Tree of Thoughts (ToT)：将推理过程组织为树结构，使用 BFS/DFS 搜索最优推理路径
• 过程奖励模型（PRM）：在推理的每一步进行评分，而非仅评估最终答案——类似于 MCTS 中的价值网络
• OpenAI o1/o3 模型：在"思考时间（test-time compute）"中进行搜索，用更多计算换取更好的推理结果

这一方向被称为推理时扩展（inference-time scaling），其核心哲学与 MCTS 一脉相承：用搜索弥补模型能力的不足。

2. 多智能体博弈与自我博弈

• Population-Based Training（PBT）：维护一个策略种群，通过相互博弈进化
• League Training：AlphaStar 使用联赛式训练，策略在不同对手中迭代进化
• Neural Fictitious Self-Play（NFSP）：结合 RL 和监督学习逼近纳什均衡

3. 人类-AI 协作博弈

• 合作AI：Hanabi 等需要心智理论（Theory of Mind）的合作博弈仍是开放挑战
• 人机混合团队：如何在人类与AI各有优势的场景中协同决策
• 可解释博弈策略：让AI的博弈策略对人类可理解，促进信任

---

评论