CFR

概述

反事實遺憾最小化（CFR）是一種用於求解兩人零和遊戲中納許均衡的演算法。由Hart和Mas-Colell提出，後來由Zinkevich等人引入博弈論撲克研究。CFR是AI撲克中的里程碑，也是Libratus和Pluribus等頂尖撲克AI的核心技術之一。

核心原理

CFR疊代計算每個決策節點的「反事實遺憾」——玩家若選擇替代行動而非實際行動所能獲得的額外收益。演算法根據累積的遺憾值調整後續策略，逐步收斂至納許均衡。具體過程包括：

• 遍歷遊戲樹中的所有資訊集。
• 計算每個行動的反事實價值（假設玩家以當前策略到達該資訊集）。
• 更新累積遺憾值並據此生成新策略（通常使用遺憾匹配）。

在德州撲克中的應用

德州撲克是典型的不完美資訊遊戲，狀態空間巨大。CFR及其改進版本（如CFR+、Deep CFR）通過抽象技術（如狀態聚類、行動分組）降低計算複雜性，然後大規模平行計算訓練。例如，Libratus使用改進的CFR演算法在無限注德州撲克中擊敗頂尖人類玩家。

特點

• 理論保證：在零和遊戲中，CFR保證平均策略收斂至納許均衡。
• 無需先驗知識：從均勻隨機策略開始，自動學習最優策略。
• 計算成本高：在無限注德州撲克中遍歷完整遊戲樹不可行，需要抽象和抽樣。

侷限

CFR主要適用於兩人零和遊戲。在多玩家遊戲中，理論上不收斂，但修改（如添加前向搜索的反事實遺憾最小化）可在實踐中獲得良好效果。