浅谈德州扑克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等。

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

利己还是利他

昨天在书店看书，看到一本《沃顿商学院最受欢迎思维课》，以为是讲思维的，翻开一看，却是讲如何选择。作者是哈佛商学院最年轻的终身教授，将人分为三种：获利型，也就是利己主义者；付出型，也就是利他主义者；互利型，更精明的人。然后通过大量成功案例说明，利他主义者从长期看更容易成功。

书中讲了几个案例，其中印象最深的是林肯。他就是坚定的利他主义者，想问题不是从自己的利益出发，而是社会价值最大化。好几次他参选，他努力抨击他认为不合适的候选人，却在领先情况下让给他认为比自己更适合的人。这样赢得了对手的广泛尊敬，最后当选总统--这些曾经的对手都成为他坚定的支持者。

利己主义者看上去短期获利，但长期以往，大家就不愿意和他深交。就比如请吃饭，中国人还是不习惯AA，如果一个人老是想着别人请，自己占便宜，肯定越来越不受欢迎。要知道吃饭是次要的，相互交流，增进感情才是核心。

而一个精明的互利主义者看上去很完美，同时照顾到自己和他人的利益。但如果你总是在利益间平衡，做事情都要求回报，也很容易被看清。他人对你也会衡量利益。

这里正好想到一个心理学的词汇：延迟满足。曾经有一个实验，给几个小孩一些糖，并告诉他们，可以选择立即吃或者等到研究人员回来再吃，如果等那么会获得额外的奖励。实验持续了很多次，有很多孩子选择了立即吃，也有一些孩子抵制了诱惑，坚持等到研究人员回来。然后多年后的跟踪调查，这些能够抵制诱惑的小孩更容易成功。

利他主义并不要求马上获得与付出匹配的利益，甚至并不在意回报。但世事就是这么奇妙，所谓“有心栽花花不发，无心插柳柳成荫”。很多不经意间的付出，会获得不一样的认可，扩展你的有效人脉，而这些人脉会在某个时刻帮到你。

以我为例，有一个对我影响很大的事就是加入支付宝。但这个的起因，却恰恰是我不要求回报的行为：参与开源软件的翻译。当时我毕业几年，做java开发，spring和hibernate都出来没多久。我出于对技术的热爱和对开源软件的支持，加入社区参与opendoc行动——就是拿出业余时间将这些开源软件的文档翻译成中文，只有署名权，没有一分钱稿费。但通过这个我更深刻理解了技术，并认识了一些朋友。然后正好一个朋友在支付宝，他推荐了我去面试，然后我通过了。这就是主观利他却不经意间给自己带来巨大价值的例证。

说了价值我们再从人性角度看利他主义的基础。这里有一个朋友推荐的视频：【TED】让利他精神成为你的准则。其实利他思维就根植在我们的内心。父母对小孩的付出都是无私的不要求回报的，而并不是所谓的“养儿防老”。他们只要看到小孩快乐成长就会有着由衷的欣慰和满足。很多时候我们看到陌生人处于危难，也会奋不顾身去救助，而不是考虑回报。恻隐之心，人皆有之。人性本善。

所以秉承利他主义，你将会得到长期的回报和心灵深处的满足。何乐而不为？

那么该如何应用这个原则呢？我简单总结4点：

1.积极参与公益活动，尽自己的能力帮助一些陌生人。比如我一直参与慈济的“日行一善”活动，进一步落地就是一天捐一元，每月初一次，钱虽然不多，但溪流汇成大海，相信也能帮到一些需要的人。

2.多帮助他人，顺手给别人介绍人脉和资源，不用自己特别累，但价值很大。比如我在技术圈和hr圈资源较多，对流量也很熟悉，可以帮大家推广和变现。

3.和人交朋友不要带着价值尺度去衡量，真诚对待每一个人，因为爱好相聚。我就较擅长各种球类运动，也会玩玩德扑，大家可以找我玩。

4.对下属更考虑ta们的发展和感受，让其有成长，大家在一起快乐的工作。同时营造利他的氛围，鼓励相互帮助和分享。

对世界报以善意，世界也会以善意回你！