近年来,人工智能领域取得了令人惊叹的进展。在图像处理和语音识别等领域取得重大突破的同时,人工智能在各种游戏中战胜人类的成就也引起了广泛关注。尤其是2016年AlphaGo击败韩国围棋大师李世石,标志着AI在围棋领域首次超越人类,成为继1997年深蓝战胜国际象棋大师卡斯帕罗夫之后,AI发展史上又一个里程碑时刻。

与此同时,来自美国、加拿大、捷克和芬兰的一群研究人员正在致力于解决另一个游戏:无限注德州扑克。经过多年努力,他们终于在扑克AI领域取得重大突破。本文将详细介绍扑克AI的核心技术 - 对抗性遗憾最小化(Counterfactual Regret Minimization, CFR),以及基于该技术的几个著名扑克AI系统。

Cepheus:首个解决限注德州扑克的AI

2015年,Oskari Tammelin、Neil Burch、Michael Johanson和Michael Bowling等人开发出名为Cepheus的计算机程序,这是首个能够解决限注德州扑克的AI。他们发表了两篇具有里程碑意义的论文:《解决限注德州扑克》和《限注德州扑克已被解决》。

虽然论文标题宣称"解决"了扑克,但从严格意义上讲,Cepheus是对扑克的"本质解决"。这意味着研究人员能够得到一个近似的Nash均衡策略,在人类一生的时间范围内,该策略与理论上的最优策略是无法区分的。在双人零和博弈中,如果不知道对手的具体策略,采用Nash均衡策略是任何玩家能做的最好选择。

Cepheus采用了快速版本的对抗性遗憾最小化算法,离线预计算出Nash均衡策略。研究人员高效地计算并存储了所有可能游戏情况下的最优应对策略,这些策略以数以TB计的向量形式存储,每个向量代表特定游戏情况下各种可能行动的概率分布。

虽然这种方法看起来不如AlphaGo的深度神经网络那么"性感",但计算Nash均衡策略的算法在某种程度上与AlphaGo/AlphaZero使用的算法类似。两种解决方案的共同点是通过自我对弈来学习。Cepheus的核心算法 - 对抗性遗憾最小化(CFR) - 正是本文的主要研究对象。

DeepStack:基于神经网络的无限注德州扑克AI

大约两年后,另一个成功的扑克AI系统 DeepStack 问世。它能够在无限注德州扑克中击败人类选手。DeepStack的核心是基于神经网络辅助的持续重解(continual re-solving)技术。

重解是一种子博弈求解技术。子博弈是指以当前决策点为根节点的博弈树。从高层次来看,子博弈求解意味着将子博弈与父节点分离,单独求解。换句话说,重解是一种在给定决策点重构剩余博弈策略的技术。

DeepStack创造者使用了持续重解技术,在整个博弈过程中只维护两个向量。这两个向量足以持续重构当前子博弈中近似Nash均衡的策略。

为了克服持续重解带来的计算复杂性问题,DeepStack引入了深度神经网络。这个复杂性问题源于需要在博弈过程中的每个决策点重新计算对抗性价值向量。直接使用对抗性遗憾最小化(CFR)求解器在实践中是不可行的。DeepStack通过限制CFR求解器的深度和广度来解决这个问题(这在某种程度上类似于AlphaGo的价值网络和策略网络)。广度限制通过动作抽象实现(只允许弃牌、跟注、2或3倍加注和全下等有限动作),而深度限制则通过在计算对抗性价值的一定深度使用价值函数(由深度神经网络估计)来实现。

为了评估DeepStack的性能,研究人员在国际扑克联合会的帮助下选择了来自17个国家的33名职业选手,每人进行3000手牌。比赛通过在线界面进行。DeepStack平均每100手牌赢得49个大盲注(492 mbb/g)。除了一名结果不具统计显著性的选手外,DeepStack战胜了所有对手。

这是机器首次能够在无限注德州扑克中与人类匹敌。DeepStack的一些对局视频可以在其YouTube频道上观看,包括河牌中击中顺子后全下对抗人类同花的精彩操作,以及转牌圈的(某种程度上的)诈唬迫使人类弃牌等精彩瞬间。

Libratus:来自卡内基梅隆大学的强大对手

2017年1月,扑克AI领域又迎来一个重要突破。由卡内基梅隆大学的Tuomas W. Sandholm及其同事开发的无限注德州扑克AI系统Libratus击败了由4名职业选手组成的团队:Jason Les、Dong Kim、Daniel McCauley和Jimmy Chou。这场名为"头脑对决AI"的比赛在匹兹堡的一家赌场举行,持续20天,总共进行了约12万手牌。参赛选手被认为比DeepStack的对手更强。20万美元的奖金池按照表现比例分配给4名选手。Libratus以平均每100手赢147个大盲注的优势战胜了所有选手。

Libratus主要采用了三种方法的组合:

使用蒙特卡洛对抗性遗憾最小化计算的蓝图策略

蓝图策略是对游戏抽象(为减小游戏规模而对动作和牌面进行聚类)预先计算的策略,作为系统其他组件的参考。前两轮的蓝图设计为密集型(即动作抽象包含更多不同的下注大小)。Libratus在游戏开始时按照蓝图策略行动,然后在博弈树更深处的决策点切换到嵌套子博弈求解。

嵌套子博弈求解

给定蓝图策略和游戏中的某个决策点,Libratus创造者应用了新颖的子博弈求解技术 - 嵌套子博弈求解。子博弈求解技术为剩余博弈重构策略,实践中通常优于蓝图参考策略。这项技术的细节在NIPS 2017最佳论文中有详细描述。

比赛期间的自我改进

比赛期间记录对手的行动(下注大小),每天结束后扩展蓝图策略。将频繁出现且与当前动作抽象相距较远的下注(可能最容易利用Libratus的弱点)在比赛日之间的夜晚添加到蓝图中。

2017年12月,嵌套子博弈求解论文的作者Tuomas Sandholm和Noam Brown在Reddit的r/machinelearning上进行了一次AMA(Ask Me Anything)活动。其中有一个问题是关于DeepStack和Libratus的比较。

所有这些扑克程序都以某种形式的对抗性遗憾最小化(CFR)作为核心组件。Cepheus使用了CFR的快速变体离线预计算Nash均衡,DeepStack使用了基于神经网络辅助的类CFR算法进行子博弈求解,而Libratus则使用蒙特卡洛对抗性遗憾最小化计算蓝图策略(即游戏抽象的Nash均衡)。

博弈论基础

博弈论是一个数学领域,为建模和推理交互情况提供了有用的工具。这些被称为"博弈"的交互情况可能具有非常不同的性质,取决于许多因素,如参与者数量、效用结构、行动顺序等。基于这些特征,我们可以将博弈分类。一旦对博弈进行分类,我们就可以使用适用于该类型博弈的已知通用定理进行推理。在本文中,我们将重点关注无限注德州扑克。让我们首先了解博弈论如何对这种扑克进行分类,以便后续使用适当的工具。

无限注德州扑克是什么类型的博弈?

无限注德州扑克是一个双人零和有限博弈,具有不完全信息和随机因素。让我们逐一解析这些特征:

双人:因为有两名玩家参与有限博弈:意味着可能的行动历史数量是有限的。在扑克中,这个数字虽然巨大但确实是有限的。零和:所有收益(玩家的得失)加起来等于零。这适用于扑克。除非出现平局没有玩家获胜,否则一个玩家获得的底池就是另一个玩家损失的等价金额(不考虑抽成)。不完全信息:玩家无法准确知道游戏的确切状态 - 存在玩家不知道的隐藏信息。在扑克中,这个隐藏信息是对手的手牌。存在随机因素:游戏中存在玩家无法控制的随机元素 - 在扑克中,这些是连续的随机下注轮或初始发牌。

这些特征将决定我们有权使用哪些定理/模型来理解CFR。

在无限注德州扑克中拥有策略意味着什么?

简单来说,策略描述了在每一种可能情况下如何行动。它是整个游戏中的行动指南,一个你可以查阅行动的查找表。

在像扑克这样的游戏中,通过策略选择的行动不能完全确定。随机化是必要的 - 如果玩家不这样做,他们的下注模式将很快被学习和利用。在博弈论中,决策点的随机化通过概率实现。

行为策略是决策点上动作的概率分布集合。它完整描述了在所有游戏情况下如何行动(因此称为行为策略)。在单次游戏中,具体行动是从与决策点相关的概率分布中抽取的。

另一方面,策略组合是所有参与游戏的玩家的策略集合。在我们的无限注德州扑克场景中,策略组合由两个策略组成(每个玩家一个)。

给定一个策略组合,我们就可以模拟玩家之间的扑克对局。单次游戏过程将是一系列从玩家策略给出的概率分布中抽取的行动(加上庄家作为随机因素的行动)。一旦游戏结束,玩家获得他们的效用(或收益)。

由于我们处于概率框架中,我们可以考虑玩家的期望效用。每个策略组合直接指示了两名玩家的期望效用(期望收益)。这意味着我们可以通过期望效用来评估策略和策略组合。

为什么是纳什均衡?

我们的主要算法 CFR 产生一种称为纳什均衡的策略组合的近似。

纳什均衡是一种策略组合(所有参与玩家的策略集),使得没有单个玩家有动机偏离。它代表了玩家之间的平衡点,在这一点上,没有玩家通过改变自己的策略获得额外收益。我们说两个玩家都在玩纳什均衡策略组合,如果在另一个玩家保持原策略不变的情况下,改变一个玩家的策略不会带来任何额外价值(就效用而言) - 两个玩家都在对彼此使用最佳应对策略。

关于纳什均衡,会产生几个问题。首先,扑克中是否存在纳什均衡?如果存在,是只有一个还是多个?CFR将计算哪一个?我们能保证找到最佳的纳什均衡吗?

关于纳什均衡存在性的第一个问题可以通过纳什存在性定理来解答,该定理指出对于有限博弈(包括扑克),保证存在纳什均衡。

另一个重要的定理是极小极大定理,它证明对于双人零和有限博弈,存在一个均衡中两个玩家都能获得的最佳单一可能效用,称为游戏的价值。

因此,扑克中所有纳什均衡的值都是相等的 - 它们产生相同的期望效用。

更进一步,它们是可互换的:你可以用任何纳什均衡中的任何策略替换另一个纳什均衡中的相应策略,结果仍然是纳什均衡。这意味着CFR可以找到任何纳什均衡,而不必担心找到"最佳"的那个。

对抗性遗憾最小化(CFR)算法

现在我们已经了解了博弈论的基础知识,让我们深入研究对抗性遗憾最小化(CFR)算法。CFR是一种迭代算法,用于在扑克等大规模不完全信息博弈中计算近似纳什均衡。

CFR的核心思想

CFR的核心思想是通过最小化每个决策点的"遗憾"来逐步改进策略。遗憾是指在知道对手策略的情况下,选择最佳行动而不是当前策略所指定行动所能获得的额外效用。

算法的工作原理如下:

初始化每个玩家的策略为均匀随机策略。

重复以下步骤多次迭代:

a. 对每个玩家:

计算当前策略组合下每个决策点的对抗性价值(counterfactual value)。更新每个决策点的累积遗憾。根据累积遗憾更新策略。

b. 更新平均策略。

返回平均策略作为近似纳什均衡。

对抗性价值

对抗性价值是CFR算法中的一个关键概念。它代表了在给定决策点选择特定行动的期望价值,假设我们已经到达了该决策点。这个"假设"部分很重要,因为在不完全信息博弈中,并非所有决策点都能被等概率地到达。

对抗性价值的计算涉及到遍历整个博弈树,同时考虑到达每个节点的概率。这个计算过程是递归的,从博弈树的叶子节点开始,逐层向上传播价值。

遗憾更新

在每次迭代中,CFR会计算每个决策点的即时遗憾,并将其累加到累积遗憾中。即时遗憾是指在当前迭代中,选择最佳行动而不是当前策略所指定行动所能获得的额外对抗性价值。

累积遗憾用于更新策略。具体来说,新的策略是通过将累积遗憾正规化(即将其转换为概率分布)得到的。这确保了算法会逐渐倾向于选择长期表现良好的行动。

平均策略

CFR的一个关键特性是它返回的是平均策略,而不是最终迭代的策略。平均策略是在所有迭代中使用的策略的加权平均。这个平均策略被证明会收敛到纳什均衡。

CFR的理论保证

CFR算法有强大的理论保证。可以证明,随着迭代次数的增加,平均策略会收敛到纳什均衡。具体来说,收敛速度与迭代次数的平方根成反比。这意味着要将近似误差减半,需要将迭代次数增加四倍。

CFR的变体

自CFR算法提出以来,研究人员开发了许多变体来提高其效率。一些重要的变体包括:

CFR+: 这是一种改进的CFR变体,它使用更积极的遗憾更新规则和策略更新规则。CFR+通常比原始CFR收敛得更快。

蒙特卡洛CFR (MCCFR): 这种变体使用采样来减少每次迭代的计算量。而不是遍历整个博弈树,MCCFR只探索树的一小部分,但仍保持收敛保证。

深度限制的CFR: 这种方法将CFR与深度限制搜索相结合,允许在更大的博弈中应用CFR。

折扣CFR: 这种变体通过对早期迭代的结果应用折扣来加速收敛。

CFR在扑克AI中的应用

现在让我们回顾一下CFR在前面提到的三个主要扑克AI系统中的应用。

Cepheus中的CFR

Cepheus使用了CFR的一个快速变体来预计算限注德州扑克的近似纳什均衡策略。具体来说,它使用了CFR+算法,这是一种改进的CFR变体,通常比原始CFR收敛得更快。

Cepheus的主要挑战是处理限注德州扑克巨大的博弈树(约

1

0

14

10^{14}

1014个决策点)。为了解决这个问题,研究人员使用了几种技术:

抽象化: 将相似的牌面和决策点聚类,以减少博弈树的大小。并行化: 在大规模集群上并行运行CFR算法。压缩: 使用特殊的压缩技术来减少存储策略所需的内存。

通过这些技术,Cepheus能够在合理的时间内计算出高质量的近似纳什均衡策略。

DeepStack中的CFR

DeepStack采用了一种不同的方法。它不是预计算整个博弈的策略,而是在游戏过程中动态地解决子博弈。这种方法被称为"持续重解"。

DeepStack使用了一种类似CFR的算法来解决子博弈,但引入了深度神经网络来估计子博弈树深处的值。这允许DeepStack在合理的时间内解决更大的子博弈。

具体来说,DeepStack的算法包括以下步骤:

使用CFR预计算前两轮(翻牌前和翻牌)的策略蓝图。在游戏过程中,对于每个决策点:

a. 构建一个局部子博弈树。

b. 使用深度神经网络估计树叶节点的值。

c. 使用类CFR算法解决这个子博弈。

通过这种方法,DeepStack能够在无限注德州扑克中实现接近人类专业水平的表现。

Libratus中的CFR

Libratus采用了一种混合方法,结合了预计算和实时计算。它使用了三个主要组件:

蓝图策略: 使用蒙特卡洛CFR (MCCFR)预计算整个博弈的抽象版本的策略。

嵌套子博弈求解: 在游戏过程中,Libratus使用一种新颖的子博弈求解技术,称为嵌套子博弈求解。这种技术允许Libratus在考虑整个博弈上下文的同时,高效地求解局部子博弈。

自我改进: Libratus能够在比赛过程中不断改进其策略,特别是针对对手频繁使用的非标准下注大小。

Libratus的CFR应用主要体现在计算蓝图策略和解决子博弈这两个方面。通过结合这些技术,Libratus能够在无限注德州扑克中达到超人的表现水平。

CFR的局限性和未来发展

尽管CFR在扑克AI中取得了巨大成功,但它仍然存在一些局限性:

计算复杂性: 对于非常大的博弈,CFR的计算要求仍然很高,即使使用抽象化和采样技术。

多人博弈: 虽然CFR可以扩展到多人博弈,但在这种情况下的收敛保证较弱,实际性能也可能下降。

通用性: CFR主要设计用于求解不完全信息的零和博弈。对于非零和博弈或完全信息博弈,可能存在更有效的算法。

未来的研究方向可能包括:

改进CFR的计算效率,使其能够处理更大规模的博弈。

开发更好的抽象化和采样技术,以在不显著降低策略质量的情况下减少计算复杂性。

将CFR与深度学习和强化学习技术进一步结合,可能产生更强大和更通用的算法。

探索CFR在其他领域的应用,如经济学、军事策略或自动谈判系统。

结论

对抗性遗憾最小化(CFR)算法是现代扑克AI系统的核心技术之一。通过迭代地最小化每个决策点的遗憾,CFR能够计算出近似纳什均衡策略,使AI在复杂的不完全信息博弈中达到超人的表现水平。

从Cepheus到DeepStack再到Libratus,我们看到了CFR算法的不断演进和改进。这些系统不仅展示了CFR在扑克中的强大能力,也为我们理解和解决其他复杂决策问题提供了宝贵的见解。

随着研究的继续,我们可以期待看到CFR及其变体在更广泛的领域中的应用,以及与其他先进AI技术的结合。这些发展将进一步推动我们对复杂决策过程的理解,并可能在游戏之外的实际问题中找到重要应用。

参考文献

Bowling, M., Burch, N., Johanson, M., & Tammelin, O. (2015). Heads-up limit hold’em poker is solved. Science, 347(6218), 145-149.

Brown, N., & Sandholm, T. (2017). Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374), 418-424.

Moravčík, M., Schmid, M., Burch, N., Lisý, V., Morrill, D., Bard, N., … & Bowling, M. (2017). DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337), 508-513.

Zinkevich, M., Johanson, M., Bowling, M., & Piccione, C. (2008). Regret minimization in games with incomplete information. Advances in neural information processing systems, 20.

Brown, N., & Sandholm, T. (2019). Superhuman AI for multiplayer poker. Science, 365(6456), 885-890.