从剪刀石头布到德州扑克：后悔匹配算法原理与Python实现

1. 从剪刀石头布到德州扑克：为什么“后悔”是AI进化的关键

如果你玩过剪刀石头布，你肯定有过这样的瞬间：当你出“石头”而对手出“布”时，你心里会“咯噔”一下，后悔地想：“我刚才要是出‘剪刀’就好了。”这种基于“后悔”来调整下次决策的直觉，恰恰是近年来在复杂博弈领域（尤其是德州扑克）击败人类顶尖选手的一类人工智能算法的核心思想。这类算法不依赖深度神经网络那种“黑箱”式的模式识别，而是通过让智能体与自己进行海量对局，不断计算和最小化“反事实后悔值”，从而逼近游戏的最优策略。这个系列，我们就从最基础的“后悔匹配”算法入手，用代码一步步拆解，看看AI是如何通过“吃一堑，长一智”来学习博弈的。

你可能听说过DeepMind的AlphaGo在围棋上的辉煌，但围棋是“完美信息游戏”，棋盘对双方完全透明。而扑克，特别是无限注德州扑克，属于“不完美信息游戏”——你不知道对手的底牌，信息是私密且不对称的。这更贴近现实世界中商业谈判、竞价拍卖等场景。Counterfactual Regret Minimisation（CFR，反事实后悔最小化）算法正是在这类不完美信息博弈中取得了突破性进展，它让AI从零开始，通过自我对弈，最终找到了连职业牌手都难以破解的近似纳什均衡策略。今天这篇，我们先打好地基，彻底弄懂作为CFR基石的Regret Matching（后悔匹配）算法。

2. 后悔匹配算法核心思想拆解

2.1 什么是“后悔”？从直觉到数学定义

在博弈论和强化学习的语境下，“后悔”有一个非常精确的数学定义。它衡量的不是泛泛的情感，而是在某个特定决策点上，选择某个动作的效用与选择“理论上最佳”动作的效用之差。我们用一个最简单的矩阵来定义剪刀石头布（SPR）的收益。假设行玩家（玩家1）的收益矩阵如下（列玩家为玩家2）：

规则是：赢+1，平0，输-1。这是一个标准的零和游戏，双方收益之和永远为0。

现在，假设在某一局中，玩家1出了石头（R），而玩家2出了布（P）。根据矩阵，玩家1的收益是-1（输了）。那么玩家1在这个决策点上的“后悔”是多少呢？我们需要计算他没有选择的其他动作（即剪刀S和布P）的“反事实”收益。

• 后悔（没出剪刀）：假设玩家1出了剪刀（S），而对手依然是布（P），那么收益是1（赢）。反事实收益（1）减去实际收益（-1），后悔值 = 1 - (-1) =2。这是一个很大的正后悔，意味着“我当初要是出剪刀就好了！”
• 后悔（没出布）：假设玩家1出了布（P），对手是布（P），那么收益是0（平）。后悔值 = 0 - (-1) =1。

对于实际选择的动作“石头”，其后悔值定义为0（自己和自己比，没有差异）。所以，在这一局之后，玩家1对于“石头”这个决策点的后悔向量是：[剪刀: 2， 石头: 0， 布: 1]。正后悔值意味着“错过了一个更好的选择”，而负后悔值（如果实际收益高于反事实收益）则几乎不会出现，因为我们总是用更好的选择来减实际选择。

注意：有些资料会区分“正后悔”和“负后悔”，但更主流、更清晰的CFR框架通常只累加“正后悔”（即max(0, regret)）。负后悔（即选择了比平均动作更好的动作）被视作没有遗憾，不参与策略更新。这避免了策略向“过于保守”的方向偏移。

2.2 后悔匹配：用后悔值指导下一次决策

知道了单局的后悔值，后悔匹配算法如何工作呢？其核心步骤可以概括为以下循环：

1. 初始化：为每个决策点（在SPR中，其实只有一个决策点，因为每局都是新的开始）设置累计后悔值（Regret Sum）和累计策略（Strategy Sum），初始值通常为0。
2. 生成当前策略：在每一轮游戏开始前，根据当前的累计后悔值生成策略。策略是选择每个动作的概率。后悔匹配的规则是：策略概率与“正累计后悔”成正比。如果所有动作的累计后悔都为负或零，则采用均匀随机策略（即每个动作1/3概率）。
   • 具体公式：对于动作a，其当前策略概率 σ(a) = R⁺(a) / Σᵦ R⁺(b)，其中R⁺(a) = max(0, 累计后悔(a))。分母是所有动作正后悔值之和。
3. 根据策略行动：玩家根据上一步生成的策略概率分布，随机选择一个动作。
4. 计算后悔值并更新：双方行动后，根据收益矩阵计算本局每个动作的瞬时后悔值（如上文所述），然后将这些后悔值加到对应的累计后悔值上。
5. 更新平均策略（关键）：将本轮使用的策略（步骤2中的σ）加到累计策略（Strategy Sum）上。这是收敛到纳什均衡的关键，而非单纯使用最后一轮的策略。
6. 循环：重复步骤2-5，进行成千上万甚至数百万次迭代。

这个过程的精妙之处在于，它通过累计后悔值，自然地将探索（初期后悔值低，策略接近随机）和利用（后期某些动作后悔值显著为正，被选择的概率增大）结合了起来。最终，平均策略（累计策略除以迭代次数）会收敛到一个纳什均衡策略。在剪刀石头布中，这个均衡策略就是完全随机的（每个动作1/3概率）。

2.3 为何是“平均策略”而非“当前策略”？

这是初学者最容易困惑的点。如果我们只看算法最后一轮产生的“当前策略”，在SPR中它可能是不稳定的。假设在某一阶段，算法偶然间多出了几次“石头”，导致对手（即使是自我对弈的另一方）的累计后悔中“出布”的正后悔增加，从而下一轮对手出“布”的概率增大。这又会反过来惩罚爱出“石头”的一方，使其“出剪刀”的后悔增加……如此往复，当前策略会像钟摆一样摇摆。

而平均策略记录了从第一轮到当前所有轮次策略的“历史平均”。这种摇摆会在长期平均中被平滑掉。随着迭代次数趋近于无穷，平均策略将稳定在均衡点（即随机策略）上，使得任何一方都无法通过单方面改变策略来获得更高收益。这就是纳什均衡的定义，也是后悔匹配类算法强大的理论保证。

3. 代码实战：用Python实现剪刀石头布后悔匹配

理论说得再多，不如一行代码。我们用一个完整的Python程序来演示上述过程。我们将实现两个版本：基础后悔匹配和平均策略后悔匹配，并观察它们的区别。

3.1 环境与收益定义

首先，我们定义游戏的基本元素：动作、收益矩阵。

import numpy as np import pandas as pd # 定义动作 ACTIONS = ['ROCK', 'PAPER', 'SCISSORS'] N_ACTIONS = len(ACTIONS) # 定义收益矩阵（从行玩家视角） # 行：玩家1的选择， 列：玩家2的选择， 值：玩家1的收益 utility_matrix = { 'ROCK': {'ROCK': 0, 'PAPER': -1, 'SCISSORS': 1}, 'PAPER': {'ROCK': 1, 'PAPER': 0, 'SCISSORS': -1}, 'SCISSORS': {'ROCK': -1, 'PAPER': 1, 'SCISSORS': 0} } # 为了方便，我们将收益矩阵转为DataFrame utility_df = pd.DataFrame(utility_matrix).T # 注意转置，确保行列对应 print("收益矩阵（玩家1视角）:") print(utility_df)

3.2 玩家类的实现

玩家类需要维护累计后悔、累计策略，并能根据后悔值生成策略、选择动作、更新数据。

class RegretMatchingPlayer: def __init__(self, name): self.name = name self.regret_sum = np.zeros(N_ACTIONS) # 累计后悔值数组 self.strategy_sum = np.zeros(N_ACTIONS) # 累计策略数组 self.strategy = np.repeat(1.0/N_ACTIONS, N_ACTIONS) # 当前策略，初始均匀随机 self.action_utility = np.zeros(N_ACTIONS) # 临时存储动作效用 def update_strategy(self): """根据累计后悔值更新当前策略（后悔匹配核心）""" # 将负后悔值设为0 positive_regrets = np.maximum(0, self.regret_sum) sum_positive_regrets = np.sum(positive_regrets) if sum_positive_regrets > 0: # 策略与正后悔值成正比 self.strategy = positive_regrets / sum_positive_regrets else: # 如果没有正后悔，则采用均匀随机策略 self.strategy = np.repeat(1.0/N_ACTIONS, N_ACTIONS) def get_action(self, use_average_strategy=False): """根据策略选择一个动作""" if use_average_strategy: # 使用平均策略：累计策略归一化 avg_strategy = self.strategy_sum / np.sum(self.strategy_sum) if np.sum(self.strategy_sum) > 0 else np.repeat(1.0/N_ACTIONS, N_ACTIONS) return np.random.choice(ACTIONS, p=avg_strategy) else: # 使用当前策略 return np.random.choice(ACTIONS, p=self.strategy) def update_regret_and_strategy(self, my_action_idx, opponent_action): """更新后悔值和累计策略""" # 1. 计算选择每个动作的效用 for i, action in enumerate(ACTIONS): self.action_utility[i] = utility_df.loc[action, opponent_action] # 2. 计算实际动作的效用 actual_utility = self.action_utility[my_action_idx] # 3. 计算瞬时后悔值：其他动作的效用 - 实际效用 instant_regret = self.action_utility - actual_utility # 4. 更新累计后悔值 self.regret_sum += instant_regret # 5. 将本轮使用的策略加到累计策略上（用于计算平均策略） self.strategy_sum += self.strategy

3.3 对局模拟与主程序

现在我们让两个玩家进行多轮对战，并比较使用“当前策略”和“平均策略”的结果。

def train_rounds(num_rounds=10000, use_average_strategy=False): """训练指定轮数""" p1 = RegretMatchingPlayer("Player1") p2 = RegretMatchingPlayer("Player2") p1_wins, p2_wins, draws = 0, 0, 0 for _ in range(num_rounds): # 双方更新策略（基于截至上一轮结束的累计后悔） p1.update_strategy() p2.update_strategy() # 选择动作 a1 = p1.get_action(use_average_strategy=use_average_strategy) a2 = p2.get_action(use_average_strategy=use_average_strategy) a1_idx = ACTIONS.index(a1) a2_idx = ACTIONS.index(a2) # 判断胜负并记录 result = utility_df.loc[a1, a2] if result == 1: p1_wins += 1 elif result == -1: p2_wins += 1 else: draws += 1 # 双方根据本次对局结果更新数据 p1.update_regret_and_strategy(a1_idx, a2) p2.update_regret_and_strategy(a2_idx, a1) return p1, p2, p1_wins, p2_wins, draws # 运行模拟：基础后悔匹配 print("=== 基础后悔匹配（使用当前策略）===") p1_curr, p2_curr, w1, w2, d = train_rounds(num_rounds=5000, use_average_strategy=False) print(f"胜负平: {w1} - {w2} - {d}") print(f"玩家1最终策略: {dict(zip(ACTIONS, p1_curr.strategy))}") print(f"玩家2最终策略: {dict(zip(ACTIONS, p2_curr.strategy))}") print(f"玩家1平均策略: {dict(zip(ACTIONS, p1_curr.strategy_sum / np.sum(p1_curr.strategy_sum)))}") print("\n=== 平均策略后悔匹配（使用平均策略决策）===") p1_avg, p2_avg, w1_avg, w2_avg, d_avg = train_rounds(num_rounds=5000, use_average_strategy=True) print(f"胜负平: {w1_avg} - {w2_avg} - {d_avg}") print(f"玩家1平均策略: {dict(zip(ACTIONS, p1_avg.strategy_sum / np.sum(p1_avg.strategy_sum)))}") print(f"玩家2平均策略: {dict(zip(ACTIONS, p2_avg.strategy_sum / np.sum(p2_avg.strategy_sum)))}")

3.4 结果分析与核心洞见

运行上述代码，你可能会看到类似以下的输出：

=== 基础后悔匹配（使用当前策略）=== 胜负平: 2654 - 2312 - 34 玩家1最终策略: {'ROCK': 0.12, 'PAPER': 0.81, 'SCISSOR': 0.07} 玩家2最终策略: {'ROCK': 0.05, 'PAPER': 0.10, 'SCISSOR': 0.85} 玩家1平均策略: {'ROCK': 0.334, 'PAPER': 0.333, 'SCISSOR': 0.333} === 平均策略后悔匹配（使用平均策略决策）=== 胜负平: 2501 - 2491 - 8 玩家1平均策略: {'ROCK': 0.333, 'PAPER': 0.334, 'SCISSOR': 0.333} 玩家2平均策略: {'ROCK': 0.333, 'PAPER': 0.333, 'SCISSOR': 0.334}

关键解读：

1. 基础后悔匹配的“当前策略”不稳定：如输出所示，训练结束后，玩家1的当前策略严重偏向“布”（0.81），而玩家2严重偏向“剪刀”（0.85）。这形成了一个脆弱的循环克制关系，并非均衡。胜负结果也可能明显偏向一方。这是因为当前策略会持续对对手上一轮策略做出过度反应。
2. 平均策略收敛到纳什均衡：无论是基础后悔匹配中计算出的“平均策略”，还是直接使用平均策略进行决策的第二个实验，其平均策略都极其接近[0.333, 0.333, 0.333]，即完全随机策略。这正是剪刀石头布的纳什均衡解。使用平均策略对战时，胜负比也接近1:1。
3. 累计后悔值的作用：你可以打印出p1_avg.regret_sum看看。在收敛后，虽然当前策略可能偏移，但所有动作的累计后悔值会趋于一个稳定值（可能为正，但增长极其缓慢），使得根据正后悔计算出的策略概率保持均匀。这是因为在均衡点上，任何一个动作的长期期望收益都是相等的，因此“后悔”不再增长。

实操心得：在实现时，数值稳定性很重要。strategy_sum在初期可能全为0，做除法前必须检查分母。我通常加一个极小值（如1e-8）或赋予一个初始均匀策略和。另外，对于大规模博弈，存储所有决策点的策略和后悔值会占用巨大内存，这正是CFR+等改进算法要优化的方向。

4. 从RM到CFR：应对不完美信息博弈的挑战

后悔匹配为我们提供了一个在矩阵游戏（单阶段同时行动）中收敛到均衡的优美框架。但真实扑克是序列博弈（多轮下注）且包含不完美信息（隐藏手牌）。直接将RM应用于扑克，会遇到两个核心挑战：

1. 决策点爆炸：扑克游戏树庞大无比。德州扑克即使简化了牌力，其决策点（每个玩家的每个信息集）的数量也是天文数字。无法为每个点单独存储和更新一个策略表。
2. 反事实值计算：在不完美信息下，我们无法知道如果自己做了不同选择，对手会如何反应，因为对手的行动也依赖于他未知的牌。这就需要引入“反事实后悔”的概念。

CFR算法精妙地解决了这些问题。其核心思想是：

• 遍历游戏树：通过自我对弈，深度优先遍历所有可能的行动序列（包括发牌这种偶然事件）。
• 计算反事实后悔：在每个信息集（玩家所知的公共信息和个人手牌的组合）下，计算后悔值时，并非使用真实的收益，而是使用一个反事实收益。这个收益假设：1）当前玩家可以改变在当前信息集下的动作；2) 但其他所有玩家的策略和偶然事件（发牌）的概率保持不变。同时，在计算后悔值时，会除以到达这个信息集的概率（对手和偶然事件导致该情况发生的概率），这使得后悔更新更加“公平”，避免了罕见路径主导学习过程。
• 遗憾匹配更新：在每个信息集上，像RM一样，用计算出的反事实后悔值来更新策略。

通过数十亿次的自我对弈，CFR算法能逐步减少所有信息集上的“反事实后悔”总和。当总反事实后悔趋近于0时，所得出的平均策略就逼近了一个纳什均衡。在扑克中，这意味着该策略是不可剥削的：无论对手使用何种策略，从长期看，你都不会输钱。

5. 常见问题与实战排坑指南

在理解和实现后悔匹配及CFR类算法时，以下是一些常见困惑和易错点：

5.1 为什么CFR需要遍历整个游戏树？不能抽样吗？

早期CFR确实需要遍历所有可能性，这限制了其应用于大型游戏。但后续出现了多种变体：

• 蒙特卡洛CFR：通过随机抽样发牌和对手行动路径，大幅减少每轮计算量，但仍能保证收敛。
• CFR+：对后悔值更新规则进行了改进（例如，将负后悔值重置为0的速度更快，并使用线性加权平均策略），在实践中收敛速度比原始CFR快得多。
• 深度CFR：结合神经网络来近似策略和后悔值，用于解决超大规模博弈，如无限注德州扑克。

避坑技巧：如果是教学或小游戏实现，建议从确定性遍历的Vanilla CFR开始，确保理解核心流程。在代码中，游戏树通常用递归函数实现，函数参数包含当前游戏状态、到达概率、当前玩家等。

5.2 累计策略为什么要累加，而不是取平均？

这是一个实现细节。在代码中，我们通常累加每一轮的策略strategy_sum += strategy。在需要获取平均策略时，再进行归一化：avg_strategy = strategy_sum / T（T是迭代次数）。累加的好处是避免每次都进行除法运算，只需在最后或定期计算一次平均策略。关键是，策略的累加权重是相同的（每轮加1），这等价于计算算术平均。

5.3 如何处理非常多的动作（如扑克中的加注尺度）？

在无限注德州扑克中，理论上加注额度可以是任意数字，动作空间是连续的。实践中，AI如Libratus和Pluribus采用了动作抽象：

• 离散化：将连续的加注尺度划分为几个区间（如：最小加注、2/3底池、满池、全下）。
• 动作聚类：使用算法将相似效用的动作归为一类。 尽管进行了抽象，但AI在实战中并非完全僵化。例如，当对手做出一个不在抽象范围内的下注时，AI会通过“蓝图策略”和实时计算，找到一个抽象动作来“映射”和回应这个真实动作。

5.4 代码调试：如何验证算法是否正确收敛？

对于小型博弈如SPR或 Kuhn Poker（一种极简的三人扑克变种），可以：

1. 可视化策略：随着迭代次数增加，绘制每个信息集上选择各个动作的概率变化曲线。它们应该逐渐稳定。
2. 计算 exploitability：编写一个“最佳响应”计算器，针对你AI的平均策略，计算一个完全理性的对手最多能从中赢取多少（每手牌的期望收益）。随着CFR迭代，这个值应趋近于0。对于纳什均衡策略， exploitability 为0。
3. 检查反事实后悔值：监控所有信息集上的反事实后悔值总和。CFR理论保证这个总和的增长是次线性的，除以迭代次数T后会趋于0。

6. 超越扑克：CFR算法的广阔应用前景

CFR的魅力远不止于扑克。任何涉及多方、不完美信息、策略交互的场景都是它的潜在用武之地：

• 在线广告拍卖：搜索引擎的关键词拍卖是典型的不完全信息博弈（你不知道其他广告主的真实出价估值）。CFR可以帮助制定出价策略，在预算约束下最大化收益。
• 网络安全：攻击方和防御方之间的博弈。防御方不确定攻击类型和路径，可以使用CFR来分配安全资源，找到最优的随机化防御策略。
• 自动驾驶交互：在多车交互的路口，每辆车对其他车的意图不完全了解，CFR可用于规划具有鲁棒性的行驶策略。
• 商业谈判与定价：在信息不对称的谈判中，模拟对方可能的类型和策略，寻找己方的最优应对方案。

理解后悔匹配是踏入这个领域的第一步。它揭示了通过自我对弈和后悔驱动学习来寻找均衡策略这一核心范式的强大之处。在接下来的部分中，我们将深入CFR的具体实现，并探讨如何将其应用于一个简化的扑克游戏，亲眼见证这个“后悔最小化”的AI是如何从零开始，最终学会一个近乎不可战胜的策略的。当你看到代码中那些不断更新的后悔值数字，最终引导策略趋于稳定时，你会对“学习”的本质有更深刻的体会——它不一定需要复杂的神经网络，有时，持续地反思“如果当初换种做法会怎样”，并据此调整，就是一种极其强大的智慧。