浅谈德州扑克AI核心算法:CFR

自2017年AlphaGo战胜世界围棋冠军柯洁后，人工智能技术进入公众视野。棋牌类AI随之在人工智能领域掀起热潮。然而，在AlphaGo之前，人们就已经开始挑战棋牌类AI，从简单的跳棋、五子棋到复杂的中国象棋、国际象棋，再到围棋和德州扑克，数十年来取得了丰硕成果。德州扑克作为不完全信息博弈，不仅要应对复杂的决策，还要应对对手的虚张声势、故意示弱等策略，其博弈树无论是广度还是深度都非常庞大，一直是科学家们想要攻克的高山。在AlphaGo战胜柯洁的同一年，德扑AI DeepStack和Libratus先后在“一对一无限注德州扑克”中击败了职业扑克玩家，实现了不完全信息博弈的突破，而它们所采用的核心算法就是Counterfactual Regret Minimization(CFR)。

1. Regret Matching

CFR算法的前身是regret matching算法，在此算法中，智能体的动作是随机选择的，其概率分布与positive regret成正比，positive regret表示一个人因为过去没有选择该行动而受到的相对损失程度。

1.1算法原理

石头剪子布是最为简单的零和博弈游戏，是典型的正则式博弈，其payoff table如下：

图1·石头剪刀布收益图

Regret matching算法流程在本例中为：

a)首次迭代，player1和player2都以[公式]概率随机选择动作，假设player1选择布，player2选择剪刀。

b)以player1视角，首次博弈结果收益为：[公式]。

c)根据结果收益计算后悔值，[公式]

d)进行归一化处理更新player1的行动策略：[公式]。

e)根据更新后的策略选择动作进行多次博弈，直至达到纳什平衡

f)返回平均策略

核心代码如下（具体代码戳这儿）：

1）获得策略方法：1.清除遗憾值小于零的策略并重置策略为0；2.正则化策略，保证策略总和为13.在某种情况下，策略的遗憾值总和为0，此时重置策略为初始策略。

2）训练方法：1.玩选择策略进行博弈，根据博弈结果计算动作效益；2.根据动作效益计算后悔值。

实验结果：

1)当固定对手策略为{0.4, 0.3, 0.3}时

图2·固定对手策略，玩家策略

2)当玩家和对手都采用Regret Matching更新策略时

图3·玩家和对手策略

2. Counterfactual Regret Minimization

石头剪子布是典型的“一次性”博弈，玩家做出动作即得到结果。而生活中显然许多的博弈属于序列化博弈，博弈由一系列的动作组成，上一步的动作可能会导致下一步的动作选择变更，最终的动作组合形成博弈结果。这种序列游戏我们不再使用payoff table表示，而是使用博弈树的形式。博弈树由多种状态组成，边表示从一个状态到另一个状态的转换。状态可以是机会节点或决策节点。机会节点的功能是分配一个机会事件的结果，因此每个边代表该机会事件的一个可能结果以及事件发生的概率。在决策节点上，边代表行动和后续状态，这些状态是玩家采取这些行动的结果。

同样地，对CFR算法中的符号进行若干定义：

算法流程：

2.2实例

库恩扑克(Kunh’s pocker)是最简单的限注扑克游戏，由两名玩家进行游戏博弈，牌值只有1，2和3三种情况。每轮每位玩家各持一张手牌，根据各自判断来决定加定额赌注过牌(P）还是加注(B)。具体游戏规则如下：

图4·库恩扑克规则

以玩家α视角构建库恩扑克博弈树：

图5·先手玩家博弈树

CFR算法流程在本例中为：

a)初始策略为随机策略，假设玩家α抽到的牌值为：3

b)第一轮迭代时，节点选择动作P的虚拟收益计算方法为：[公式]。结合博弈树求解得到：[公式]、[公式]、[公式]、[公式]；[公式]、[公式] [公式] [公式]。同理，计算节点选择动作B的虚拟收益为：[公式]

c)利用虚拟收益更新后悔值：[公式]

d)利用后悔值更新策略：[公式]，[公式]

e)归一化策略：[公式]，[公式]

f)多次迭代，直至达到纳什平衡

核心代码实现：

实验结果：

图6·库恩扑克，玩家和对手策略

3.引申

CFR算法出现时就已经能够解决德州扑克，但面对52张底牌、加注、过牌、河牌等复杂多变的情况使得德扑的博弈树无论是深度还是广度都十分的庞大，对计算资源和储存资源上的开销过于巨大，使得仅仅靠CFR算法攻克德扑十分困难。而CFR后续的研究者们都在费尽心力优化CFR算法的效率，致力于提高计算速度和压缩存储空间。在此，笔者简单介绍几种CFR变种算法，仅做了解。

3.1 CFR+：

与CFR算法不同的是，CFR+算法对累计平均策略做折减，对迭代的策略进行平均时，给近期迭代的策略赋予更高的权重；直观上，越到后期，策略表现越好，因此在都策略做平均时，给近期策略更高的权重更有助于收敛。

在CFR+算法中，counterfactual utility被定义为以下形式：

[公式]

在的基础上，CFR+算法定义了一个[公式]，此时CFR+算法中的[公式]为一个累加值，而CFR算法定义[公式]的为平均值，因此CFR+算法中的regret计算方式为：

[公式]

另外，在CFR+算法中，最后输出的平均策略为一下形式：

[公式]

3.2 MCCFR：

MCCFR（Monte Carlo Counterfactual Regret Minimization)是蒙特卡洛算法和CFR算法的结合，其核心在于：在避免每轮迭代整棵博弈树的同时，依然能够保证[公式]的期望值保持不变。将叶子节点分割为不同的[公式]，且保证覆盖所有的叶子结点。

定义[公式]是在当前迭代中选择[公式]的概率：[公式]。

定义[公式]表示在当前迭代中采样到叶子节点的概率：[公式]

那么在选择[公式]迭代时，得到的采样虚拟值为：[公式]

通过一定的概率选择不同的block，得到一个基于采样的CFR算法。

3.3结语

除了上述介绍的两个算法外，CFR算法的优化数不胜数，有提高计算速度的Discount-CFR、Warm Start、Total RBP，也有压缩存储空间的CFR-D、Continue-Resolving、Safe and Nested Subgame Solving等。

机器博弈是人工智能领域的重要研究方向。非完备信息博弈是机器博弈的子领域。非完备信息博弈中存在隐藏信息和信息不对称的特点，和完备信息博弈相比，非完备信息博弈更加贴近现实生活中。例如，竞标、拍卖、股票交易等现实问题中都存在隐藏信息和信息不对称。因此，研究非完备信息博弈问题更有现实意义。德州扑克博弈包含了隐藏信息、信息不对称和随机事件等重要特性，它是典型的非完备信息博弈。对其的研究具有非常重大的意义，感兴趣的读者可深入了解。

德州扑克中,qq遇到allin如何处理

德州扑克中，QQ作为第三强起手牌，其牌力不容小觑。但是，翻牌后，QQ的处境变得复杂。面对任意一手随机牌，QQ的原始胜率约80%，仅低于AA的85%，但翻牌后，QQ很容易翻车。翻牌后的两大难点在于：一是翻牌出现A或K的情况，二是底池中有多人时，QQ的优势消失。

玩QQ的难点主要集中在翻牌后的处理上。QQ最害怕遇到翻牌中有A或K的情况，以及底池中人多时。对于翻牌有A或K的情况，QQ有41%的可能遇到，这使得QQ的胜率变得不确定。玩家需要判断对手手中可能有的A或K，并据此调整打法。底池中有多人时，QQ的优势不再明显，新手玩家容易陷入误区，要么过于谨慎，要么过于激进，结果往往是碰到不利局面。

要应对翻牌后的难点，关键在于翻牌前的策略。避免给自己挖坑，保持激进打法是关键。根据统计，如果QQ是盈利第三高的手牌，说明玩家的紧凶打法掌握得不错。因此，玩QQ的第一要务就是凶狠。下面是具体策略：

1.翻牌前的玩法：始终加注或反加进池，避免溜入底池。当面对不同情况，如有人加注开池，反加通常更为有利。在特定位置，根据对手行动调整加注量，如按钮位或大盲位，根据对手的加注量确定反加金额。

2.面对3bet和4bet：如果翻牌前已加注，遇到对手3bet，根据对手类型决定是否弃牌、跟注或4bet。在确定对手范围后做出决策，特别是对手是紧手时，应考虑其可能持有AK等牌。

3.面对多人底池：在多人底池中，QQ的价值大大降低。此时，需要更加谨慎，但依然要尝试拿价值。在全低牌面时，尝试下注，但注意对手的范围和可能的行动。

4.翻牌有A或K时：面对这种情况，不要盲目放弃，尝试下注拿价值，尤其是针对转牌和河牌。在多人底池中，需要更加小心，留心对手的可能牌型和行动。

5.策略调整：在锦标赛中，根据码量调整策略，当盲注级别升高，盲注和前注达到码量的10%时，加注和反加可能更为有利。在低级别游戏中，转牌和河牌的加注往往意味着对手持有坚果牌。

综上所述，玩QQ时需综合考虑位置、筹码量和对手情况，灵活调整策略。翻牌前的积极加注、翻牌后的谨慎下注，以及根据具体牌面和对手反应调整打法，是关键。在实践中不断学习和调整，才能在德扑游戏中取得更好的成绩。祝您在扑克桌上好运连连！