引言
反事实后悔最小化（Counterfactual Regret Minimization, CFR）是求解不完全信息博弈纳什均衡的经典算法。本文先用最小博弈 Kuhn Poker 给出完整 CFR 实现，再给出在德州扑克中的工程化落地思路（抽象与对手建模）。
1. CFR 核心思想
- 信息集（Information Set）：在不完全信息下，玩家对状态的可观测等价类
- 策略：在每个信息集上对可行动作的概率分布 σ(I)
- 后悔值：选择动作 a 与平均策略相比的损失
- CFR 迭代：累计正后悔值 R⁺(I,a)，按比例归一化得到新策略（Regret Matching）
2. Kuhn Poker 简介
- 牌：3 张（J, Q, K），每人一张，先手/后手
- 行动：过/跟/加注（精简为 bet/pass + call）
- 结算：摊牌比大小或对手弃牌
3. Python 实现（Kuhn Poker CFR）
import random
from collections import defaultdict
CARDS = ['J', 'Q', 'K']
class KuhnCFR:
def __init__(self):
self.regret_sum = defaultdict(lambda: [0.0, 0.0]) # 每信息集两动作: [pass, bet]
self.strategy_sum = defaultdict(lambda: [0.0, 0.0])
def get_strategy(self, info_set):
regrets = self.regret_sum[info_set]
# Regret-Matching
positive = [max(r, 0.0) for r in regrets]
normalizer = sum(positive)
if normalizer > 0:
strategy = [r/normalizer for r in positive]
else:
strategy = [0.5, 0.5]
# 累加平均策略
for i in range(2):
self.strategy_sum[info_set][i] += strategy[i]
return strategy
def get_average_strategy(self, info_set):
s = self.strategy_sum[info_set]
total = sum(s)
if total > 0:
return [x/total for x in s]
return [0.5, 0.5]
def cfr(self, cards, history, p0, p1):
plays = len(history)
player = plays % 2
opponent = 1 - player
# 终止判断
if len(history) >= 2:
terminal_pass = history[-1] == 'p'
double_bet = history[-2:] == 'bb'
if terminal_pass:
# p 或 bp
if history == 'pp':
return 1 if cards[player] > cards[opponent] else -1
else:
return 1
elif double_bet:
return 2 if cards[player] > cards[opponent] else -2
# 信息集：牌 + 历史
info_set = cards[player] + history
strategy = self.get_strategy(info_set)
# 递归对手价值
if player == 0:
v_pass = -self.cfr(cards, history + 'p', p0*strategy[0], p1)
v_bet = -self.cfr(cards, history + 'b', p0*strategy[1], p1)
else:
v_pass = -self.cfr(cards, history + 'p', p0, p1*strategy[0])
v_bet = -self.cfr(cards, history + 'b', p0, p1*strategy[1])
v = strategy[0]*v_pass + strategy[1]*v_bet
# 反事实后悔
regrets = [v_pass - v, v_bet - v]
if player == 0:
reach = p1
else:
reach = p0
self.regret_sum[info_set][0] += reach * regrets[0]
self.regret_sum[info_set][1] += reach * regrets[1]
return v
def train(self, iterations=100000):
util = 0.0
deck = CARDS[:]
for _ in range(iterations):
random.shuffle(deck)
util += self.cfr(deck[:2], '', 1.0, 1.0)
print(f"Average game value for Player 0: {util/iterations:.4f}")
# 输出平均策略
strat = {I: self.get_average_strategy(I) for I in self.strategy_sum}
return strat
if __name__ == '__main__':
solver = KuhnCFR()
avg_strategy = solver.train(50000)
for I in sorted(avg_strategy.keys()):
s = avg_strategy[I]
print(I, { 'pass': round(s[0],3), 'bet': round(s[1],3) })
运行后，你将得到接近文献中的纳什近似策略。例如持 K 倾向下注、持 J 更倾向过牌等。
4. 扩展到德州扑克的工程实践
CFR 在完整德州扑克上需要“抽象”以压缩庞大状态空间：
- 信息集抽象：按公共牌纹理、权益（hand strength/board texture）、行动序列分桶
- 行动抽象：将下注空间离散为固定档位（如 0.33pot/0.66pot/pot）
- 公共牌抽样：Public Chance Sampling 或外部抽样（External Sampling CFR）
- 策略表示：表格策略或函数逼近（NFSP/CFR+/Deep CFR 结合神经网络）
- 加速：多进程自对弈，增量保存平均策略，CFR+ 使用正则化与截断加速收敛
实践建议：
- 先在 Leduc Poker（小型公共牌博弈）上验证抽象与 CFR+ 实现
- 逐步接入德扑回合（翻前/翻牌/转牌/河牌）与行动抽象
- 评估用 exploitability 或与固定对手对战胜率衡量
5. 结语
本文提供了可运行的 CFR 基础实现与向德州扑克落地的工程路线。下一步可引入 CFR+、外部抽样、函数逼近策略网络，实现规模化训练与对战。
💬 交流与讨论
⚠️ 尚未完成 Giscus 配置。请在
_config.yml中设置repo_id与category_id后重新部署，即可启用升级后的评论系统。配置完成后，评论区将自动支持 Markdown 代码高亮与 LaTeX 数学公式渲染，访客回复会同步到 GitHub Discussions，并具备通知功能。