CFR

概述

反事实遗憾最小化（CFR）是解决大型不完美信息博弈（尤其是扑克）的领先算法。由 Hart、Mansour 和 Zinkevich（2000）提出，CFR 通过反复与自身博弈并根据遗憾调整策略，来逼近纳什均衡。

CFR 工作原理

CFR 在每次迭代中执行两个关键步骤：

• 计算反事实值：对于每个信息集（博弈树中玩家必须行动的一个节点），CFR 计算每种行动的反事实值——即玩家采取该行动后的预期收益，以对手到达该节点的概率加权。
• 遗憾更新：算法累积未采取行动的遗憾值，计算方式为行动的价值与实际执行策略的价值之差。遗憾值代表玩家通过偏离到该行动所能获得的收益。

正遗憾值越高的行动，在后续迭代中被选中的概率越大。算法使用遗憾匹配（regret matching）根据正遗憾值的比例选择行动的概率分布。

在扑克中的应用

扑克因隐藏手牌和诈唬而成为典型的不完美信息博弈。CFR 在开发超人类扑克 AI 中发挥了关键作用：

• Libratus（2017年）：击败顶级单挑无限注德州扑克玩家。采用名为 CFR+ 的变体，并运用高级抽象技术。
• Pluribus（2019年）：首个在六人无限注德州扑克中击败精英人类玩家的 AI。使用蒙特卡洛 CFR 应对更大的分支因子。

CFR 渐近收敛到纳什均衡，但在实践中需要大量计算和内存。为扩展规模，CFR 通常结合以下技术：

• 抽象：将相似的手牌或牌面结构分组，以减少状态空间。
• 剪枝：剔除低概率行动。
• 采样：蒙特卡洛 CFR 对随机结果进行采样，而非枚举所有可能性。

优势与局限性

• 优势：保证收敛到纳什均衡；无需对手模型（与剥削性策略不同）；成功应用于大型博弈。
• 局限性：计算成本高；需要精心调整抽象级别；无法利用特定对手弱点；主要用于离线预计算而非实时对局。

与GTO的关系

CFR 是推导扑克中博弈论最优（GTO）策略的主要工具。许多现代 GTO 求解器都使用 CFR 或其衍生算法。然而，纯 GTO 打法在面对弱对手时可能并非最优，因此人类玩家通常会将基于 CFR 的解决方案与剥削性调整相结合。

结论

CFR 彻底改变了扑克人工智能和博弈论。虽然它本身并非扑克术语，但却是现代扑克分析的基石。理解其原理有助于玩家领悟求解器如何推导出平衡策略。