反事实遗憾最小化

概述

反事实遗憾最小化（Counterfactual Regret Minimization, CFR）是一种用于求解两人零和博弈中纳什均衡的算法，由 Hart 和 Mas-Colell 提出，后由 Zinkevich 等人引入博弈论扑克研究中。CFR 在 AI 扑克领域具有里程碑意义，是许多顶级扑克 AI（如 Libratus、Pluribus）的核心技术之一。

核心原理

CFR 通过迭代过程，在每个决策节点上计算“反事实遗憾”——即如果玩家当时选择了某个备选行动，相比实际行动可能获得的额外收益。算法根据累计遗憾值调整后续迭代中的策略，使得策略逐渐收敛到纳什均衡。具体过程包括：

• 遍历博弈树的所有信息集。
• 计算每个行动的反事实值（假设玩家以当前策略到达该信息集的概率）。
• 更新累加遗憾值，并据此生成新策略（通常采用遗憾匹配）。

在德州扑克中的应用

德州扑克是典型的不完全信息博弈，具有庞大的状态空间。CFR 及其改进版本（如 CFR+、Deep CFR）通过抽象技术（如状态聚类、行动分组）减少计算复杂度，再配合大规模并行计算进行训练。例如，Libratus 采用了改良的 CFR 算法，在无限制德州扑克中击败顶级人类选手。

特点

• 理论保证：在零和博弈中，CFR 保证策略平均收敛到纳什均衡。
• 无需先验知识：从均匀随机策略开始，自动学习最优策略。
• 计算开销大：完整博弈树遍历在无限注德州扑克中不可行，需结合抽象与采样。

局限性

CFR 主要适用于两人零和博弈。多人博弈中收敛性无理论保证，但实践中通过修改（如反事实遗憾最小化加前向搜索）也可在多人情境中取得良好效果。