2021/12/16 15:05

中科院自动化所博弈学习研究组作者

达到人类专业玩家水平，中科院自动化所研发轻量型德州扑克AI程序AlphaHoldem

中科院自动化所兴军亮研究员领导的博弈学习研究组提出了一种高水平轻量化的两人无限注德州扑克 AI 程序——AlphaHoldem。其决策速度较 DeepStack 速度提升超 1000 倍，与高水平德州扑克选手对抗的结果表明其已经达到了人类专业玩家水平，相关工作已被 AAAI 2022 接收。

从人工智能学科诞生伊始，智能博弈研究就是人工智能技术发展创新的沃土，并且一直都是衡量人工智能发展水平的重要评价准则 [1][2][3][4]。2016 年，AlphaGo[2] 以 4:1 的成绩战胜围棋世界冠军李世石，这一事件被认为是智能博弈技术发展的一个重要里程碑。不同于完美信息的围棋博弈，现实世界博弈的一个显著特点是由于信息不完备性造成的对手不确定。以德州扑克为代表的大规模不完美信息博弈问题很好地集中了这一难题，是进一步深入研究智能博弈理论与技术的极佳平台。近年来，国际上围绕德州扑克这一大规模不完美信息博弈问题的优化求解取得了长足进步，来自加拿大阿尔伯特大学和美国卡内基梅隆大学的研究者设计的 AI 程序 DeepStack[3]和 Libratus[4]先后在两人无限注德州扑克中均战胜了人类专业选手，随后卡内基梅隆大学设计的 AI 程序 Pluribus[5]又在六人无限注德州扑克中战胜了人类专业选手。

上述具有里程碑意义的德州扑克 AI 都依赖一种迭代式的反事实遗憾最小化（Counterfactual Regret Minimization，CFR）[6]算法。该算法在训练过程中不仅需要耗费大量的计算资源，同时需要很多德州扑克游戏的领域知识。近日，中国科学院自动化研究所兴军亮研究员领导的博弈学习研究组在德州扑克 AI 方面取得了重要进展，提出了一种高水平轻量化的两人无限注德州扑克 AI 程序 AlphaHoldem。AlphaHoldem 整体上采用一种精心设计的伪孪生网络架构，并将一种改进的深度强化学习算法与一种新型的自博弈学习算法相结合，在不借助任何领域知识的情况下，直接从牌面信息端到端地学习候选动作进行决策。AlphaHoldem 使用了 1 台包含 8 块 GPU 卡的服务器，经过三天的自博弈学习后，战胜了 Slumbot[7]和 DeepStack[3]。在每次决策时，AlphaHoldem 仅需不到 3 毫秒，比 DeepStack 速度提升超过了 1000 倍。同时，AlphaHoldem 与四位高水平德州扑克选手对抗 1 万局的结果表明其已经达到了人类专业玩家水平。

背景介绍

德州扑克是国际上最为流行的扑克游戏，由于最早起源于 20 世纪初美国德克萨斯州而得名。德州扑克的规则是使用去掉王牌的一副扑克牌，共 52 张牌，至少 2 人参与，至多 22 人，一般参与人数为两人和十人之间。游戏开始时，首先为每个玩家发两张私有牌作为各自的 “底牌”，随后将五张公共牌依次按三张、一张、一张朝上发出。在发完两张私有牌、三张共有牌、第四张公共牌、第五张公共牌后玩家都可以多次无限制押注，这四轮押注分别称为“翻牌前”、“翻牌”、“转牌”、“河牌”。图 1 展示了一场德州扑克游戏的完整流程示意。经过四轮押注之后，若仍不能分出胜负，游戏进入“摊牌” 阶段，所有玩家亮出各自底牌并与公共牌组合成五张牌，成牌最大者获胜。图 2 给出了德州扑克不同组合的牌型解释和大小。

图 1：两人无限注德州扑克一次游戏过程示意

图 2：德州扑克不同牌型大小说明和比较

德州扑克不仅是最流行的扑克类游戏，而且也为研究智能博弈基础理论和方法提供了一个绝佳试验和测试平台。首先，德州扑克博弈的问题复杂度很大，两人无限注德州扑克的决策空间复杂度超过 10 的 161 次方[3]；其次，德州扑克博弈过程属于典型的回合制动态博弈过程，游戏参与者每一步决策都依赖于上一步的决策结果，同时对后面的决策步骤产生影响；另外，德州扑克博弈属于典型的不完美信息博弈，博弈过程中玩家各自底牌信息不公开使得每个玩家信息都不完备，玩家在每一步决策时都要充分考虑对手的各种可能情况，这就涉及到对手行为与心理建模、欺诈与反欺诈等诸多问题。此外，由于德州扑克游戏规则又非常简单且边界确定，特别适合作为一个虚拟实验环境对博弈的相关基础理论方法和核心技术算法进行深入探究。

目前主流德州扑克 AI 背后的核心思想是利用反事实遗憾最小化（Counterfactual Regret Minimization, CFR）算法 [6] 逼近纳什均衡策略。具体来说，首先利用抽象（Abstraction）技术 [3][7] 压缩德扑的状态和动作空间，从而减小博弈树的规模，然后在缩减过的博弈树上进行 CFR 算法迭代。这些方法严重依赖于人类专家知识进行博弈树抽象，并且 CFR 算法需要对博弈树的状态结点进行不断地采样遍历和迭代优化，即使经过模型缩减后仍需要耗费大量的计算和存储资源。例如，DeepStack 使用了 153 万的 CPU 时以及 1.3 万的 GPU 时训练最终 AI，在对局阶段需要一个 GPU 进行 1000 次 CFR 的迭代过程，平均每个动作的计算需耗时 3 秒。Libratus 消耗了大于 300 万的 CPU 时生成初始策略，每次决策需要搜索 4 秒以上。这样大量的计算和存储资源的消耗严重阻碍了德扑 AI 的进一步研究和发展；同时，CFR 框架很难直接拓展到多人德扑环境中，增加玩家数量将导致博弈树规模呈指数增长。另外，博弈树抽象不仅需要大量的领域知识而且会不可避免地丢失一些对决策起到至关作用的信息。

表 1：不同算法的训练测试资源对比

方法介绍

不同于已有的基于 CFR 算法的德州扑克 AI，中国科学院自动化研究所博弈学习研究组基于端到端的深度强化学习算法研发了一款高水平轻量型的德州扑克 AI 程序 AlphaHoldem，其整体架构如图 4 所示。AlphaHoldem 采用 Actor-Critic 学习框架[8]，其输入是卡牌和动作的编码，然后通过伪孪生卷积网络（结构相同参数不共享）提取特征，接下来通过两个全连接层得到状态的高层特征，最终输出动作概率和价值估计。AlphaHoldem 的成功得益于其采用了一种高效的状态编码来完整地描述当前及历史状态信息、一种基于 Trinal-Clip PPO 损失的深度强化学习算法来大幅提高训练过程的稳定性和收敛速度、以及一种新型的 Best-K 自博弈方式来有效地缓解德扑博弈中存在的策略克制问题。

图 4：端到端学习德州扑克 AI 学习框架

高效的全状态空间编码：已有德州扑克 AI 受限于 CFR 算法的处理能力，均需要对牌面状态和动作信息进行压缩，压缩的好坏完全取决于对德扑领域知识的掌握程度，而且不可避免地造成信息的损失。AlphaHoldem 对整个状态空间进行高效编码，不利用德扑领域知识进行信息压缩。对于卡牌信息，将其编码成包含多个通道的张量，用来表示私有牌、公共牌等信息。对于动作信息，AlphaHoldem 同样将其编码为多通道张量，用来表示各玩家当前及历史的动作信息。AlphaHoldem 的多维张量状态表示方法不仅完整地编码了当前及历史的状态信息，而且非常适合作为卷积神经网络的输入进行特征的学习。

Trinal-Clip PPO 强化学习：由于信息不完美及不同对手的各种 “诈唬” 欺骗行为，使得德州扑克成为一种结果具有很强随机性的游戏，这导致常见的强化学习算法（如 PPO[9]等）训练过程很不稳定且难以收敛。AlphaHoldem 提出了一种新型的 Trinal-Clip PPO 损失用于改进深度强化学习过程的稳定性，通过引入 3 个截断参数解决了 PPO 算法在优势函数小于零时损失值方差过大的问题以及 “全压” 等动作造成的价值函数难估计的问题。整体上来说，Trinal-clip PPO 损失有效缓解了德扑博弈的强随机性造成的策略训练不稳定问题，使 AlphaHoldem 训练得又快又好。

Best-K 自博弈训练方法：德扑游戏不同策略之间存在复杂的克制关系，这使得 Naive 自博弈方法 [10] 或是 AlphaGo 采用的 Best-Win 自博弈方法 [3] 很难在德扑游戏中收敛。然而使用 AlphaStar 的群体博弈 PBT[11]，神经虚拟自博弈 NFSP[12]等方法来训练德扑 AI 会消耗比传统 CFR 算法更多的计算资源。为了有效地平衡训练效率和模型性能，AlphaHoldem 采用了一种新型的 Best-K 自博弈方法。该方法通过在训练过程中测试历史模型的性能，挑选出 K 个最好的模型与现在最新的模型对打，不断通过强化学习提升自身性能。

性能测试

AlphaHoldem 到底能达到什么水平呢？

我们将 AlphaHoldem 与当前的高水平德扑 AI 进行了比较，发现 AlphaHoldem 都有明显优势。经过 10 万局的对抗，AlphaHoldem 平均赢 Slumbot[7]（2018 年世界计算机扑克大赛 ACPC 冠军，现在还在进化）111.56 mbb / 局（每 1000 手牌赢多少个大盲注），赢 DeepStack（课题组使用 120 GPU 卡训练 3 周复现的版本）16.91 mbb / 局。同时，它可以达到人类专业玩家水平，通过和 4 位专业玩家对抗 1 万局，AlphaHoldem 平均赢专业玩家 10.27 mbb / 局。另外，AlphaHoldem 在一台包含 1 个 AMD 2.00GHz CPU（64 个核心）、8 个 NVIDIA TITAN V GPU 的服务器上仅训练三天，在一个 CPU 核心下每次决策仅需 4 毫秒，做到了真正的又快又好。

AlphaHoldem 接下来会接入到课题组自研的人机对抗平台 OpenHoldem[13]（http://holdem.ia.ac.cn/）中供研究者开放测试（图 5）。OpenHoldem 是学术界第一个开放的大规模不完美信息博弈研究平台，包含了多维度评测指标、高性能基准 AI 以及公开的在线测试环境。平台支持人人对抗、机机对抗以及人机对抗等多种模式、支持 AI 分布式并行对抗、支持动态测试请求响应及资源分配、支持多用户并发访问和跨终端统一登录。平台目前已经吸引了来自高校、研究所、互联网企业等 200 余家单位的近 500 名注册用户，并受到了国内多家权威机构和主流媒体的转发报道。

图 5：OpenHoldem 在线不完美信息博弈对抗平台首页

后续计划

AlphaHoldem 采用了端到端强化学习的框架，大大降低了现有德扑 AI 所需的领域知识以及计算存储资源消耗，并达到了人类专业选手的水平。该框架是一个通用的端到端学习框架，我们已经在多人无限注德扑上验证了该框架的适用性，目前正在提升多人模型训练过程的学习性能。我们还准备将 AlphaHoldem 背后的技术应用到更多不完美信息博弈问题中，比如麻将、斗地主、桥牌等，同时也计划进行多人博弈策略空间的均衡结构分析等研究内容。

博弈学习研究组介绍

博弈学习研究组是中科院自动化所下属科研团队，是中科院人工智能创新研究院的骨干研究力量。课题组负责人为兴军亮研究员。课题组现有正式员工 9 人，博士研究生 7 人，硕士研究生 9 人，形成了一支以青年科研骨干为主体的高水平、高素质的科研队伍。

研究组以计算机博弈为研究切入点，通过将最新的机器学习技术引入到经典博弈理论和模型之中，同时借鉴运筹学、最优化、算法设计等学科的研究方法和算法，形成具有鲜明交叉特点的技术研究体系；通过使用经典博弈理论对博弈过程进行建模，然后利用最新机器学习技术对模型的参数进行学习更新，从而实现对复杂人机博弈问题的可建模性、可计算性和可解释性的结合。

课题组从 2018 年底开始研究以德州扑克为代表的大规模不完美信息博弈问题，在 2020 年公开了学界首个大规模不完美信息博弈对抗平台 OpenHoldem，集成了高性能基准 AI、多维度评测协议、在线对抗评估等完整功能，支持人机、机机、人人、人机混合等对抗模式。相关研发工作的主要完成人员包括兴军亮研究员，李凯副研究员，博士生赵恩民、徐航、李金秋，硕士生闫仁业、吴哲等。

相关论文信息

Enmin Zhao#, Renye Yan#, Jinqiu Li, Kai Li, Junliang Xing*.

High-Performance Artificial Intelligence for Heads-Up No-Limit Poker via End-to-End Reinforcement Learning. In AAAI 2022.

Kai Li, Hang Xu, Enmin Zhao, Zhe Wu, Junliang Xing*.

OpenHoldem: An Open Toolkit for Large-Scale Imperfect-Information Game Research. ArXiv preprint arXiv:2012.06168, 2020.

参考文献

[1] Murray C, Joseph H, and Feng-hsiung H. Deep Blue. Artificial Intelligence, 2002, 134(1):57-83.

[2] Silver D, Huang A, Maddison C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484-489.

[3] Moravčík M, Schmid M, Burch N, et al. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker[J]. Science, 2017, 356(6337): 508-513.

[4] Brown N, Sandholm T. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals[J]. Science, 2018, 359(6374): 418-424.

[5] Brown N, Sandholm T. Superhuman AI for multiplayer poker[J]. Science, 2019, 365(6456): 885-890.

[6] Zinkevich M, Johanson M, Bowling M, et al. Regret minimization in games with incomplete information[J]. Advances in neural information processing systems, 2007, 20: 1729-1736.

[7] Jackson E G. Slumbot NL: Solving large games with counterfactual regret minimization using sampling and distributed processing[C]. Workshops at the Twenty-Seventh AAAI Conference on Artificial Intelligence. 2013.

[8] Konda V R, Tsitsiklis J N. Actor-critic algorithms[C]. Advances in neural information processing systems. 2000: 1008-1014.

[9] Schulman J, Wolski F, Dhariwal P, et al. Proximal policy optimization algorithms[J]. ArXiv preprint arXiv:1707.06347, 2017.

[10] Silver D, Hubert T, Schrittwieser J, et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play[J]. Science, 2018, 362(6419): 1140-1144.

[11] Vinyals O, Babuschkin I, Czarnecki W M, et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning[J]. Nature, 2019, 575(7782): 350-354.

[12] Heinrich J, Lanctot M, Silver D. Fictitious self-play in extensive-form games[C]. International conference on machine learning. PMLR, 2015: 805-813.

[13] Li K, Xu H, Zhang M, et al. OpenHoldem: An Open Toolkit for Large-Scale Imperfect-Information Game Research[J]. ArXiv preprint arXiv:2012.06168, 2020.

理论游戏AI德州扑克中科院自动化研究所

相关数据

纳什均衡技术

纳什平衡，又称为非合作赛局博弈，是在非合作博弈状况下的一个概念解，在博弈论中有重要地位，以约翰·纳什命名。如果某情况下无一参与者可以通过独自行动而增加收益，则此策略组合被称为纳什均衡点。

来源：维基百科

深度强化学习技术

强化学习（Reinforcement Learning）是主体（agent）通过与周围环境的交互来进行学习。强化学习主体（RL agent）每采取一次动作（action）就会得到一个相应的数值奖励（numerical reward），这个奖励表示此次动作的好坏。通过与环境的交互，综合考虑过去的经验（exploitation）和未知的探索（exploration），强化学习主体通过试错的方式（trial and error）学会如何采取下一步的动作，而无需人类显性地告诉它该采取哪个动作。强化学习主体的目标是学习通过执行一系列的动作来最大化累积的奖励（accumulated reward）。一般来说，真实世界中的强化学习问题包括巨大的状态空间（state spaces）和动作空间（action spaces），传统的强化学习方法会受限于维数灾难（curse of dimensionality）。借助于深度学习中的神经网络，强化学习主体可以直接从原始输入数据（如游戏图像）中提取和学习特征知识，然后根据提取出的特征信息再利用传统的强化学习算法（如TD Learning，SARSA，Q-Learnin）学习控制策略（如游戏策略），而无需人工提取或启发式学习特征。这种结合了深度学习的强化学习方法称为深度强化学习。

来源：Scholarpedia

机器学习技术

机器学习是人工智能的一个分支，是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论，机器学习与推断统计学联系尤为密切，也被称为统计学习理论。算法设计方面，机器学习理论关注可以实现的，行之有效的学习算法。

来源：Mitchell, T. (1997). Machine Learning. McGraw Hill.

人工智能技术

在学术研究领域，人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体（intelligent agent）

来源：Russell, S., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach.

基准技术

一种简单的模型或启发法，用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

来源：Google ML Glossary

参数技术

在数学和统计学裡，参数（英语：parameter）是使用通用变量来建立函数和变量之间关系（当这种关系很难用方程来阐述时）的一个数量。

来源：维基百科

收敛技术

在数学，计算机科学和逻辑学中，收敛指的是不同的变换序列在有限的时间内达到一个结论（变换终止），并且得出的结论是独立于达到它的路径（他们是融合的）。通俗来说，收敛通常是指在训练期间达到的一种状态，即经过一定次数的迭代之后，训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说，如果采用当前数据进行额外的训练将无法改进模型，模型即达到收敛状态。在深度学习中，损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变，暂时形成收敛的假象。

来源：Wikipedia Google ML glossary

运筹学技术

运筹学，是一门应用数学学科，利用统计学和数学模型等方法，去寻找复杂问题中的最佳或近似最佳的解答。运筹学经常用于解决现实生活中的复杂问题，特别是改善或优化现有系统的效率。研究运筹学的基础知识包括矩阵论和离散数学，在应用方面多与仓储、物流等领域相关。因此运筹学与应用数学、工业工程专业密切相关。

来源：维基百科

博弈树技术

游戏树（game tree）是指组合博弈理论中用来表达一个赛局中各种后续可能性的树，一个完整的游戏树（complete game tree）会有一个起始节点，代表赛局中某一个情形，接着下一层的子节点是原来父节点赛局下一步的各种可能性，依照这规则扩展直到赛局结束。游戏树相同于扩展形式的博弈理论中的树。游戏树中形成的叶节点代表各种游戏结束的可能情形，例如井字游戏会有26,830个叶节点。

来源：维基百科

张量技术

张量是一个可用来表示在一些矢量、标量和其他张量之间的线性关系的多线性函数，这些线性关系的基本例子有内积、外积、线性映射以及笛卡儿积。其坐标在维空间内，有个分量的一种量，其中每个分量都是坐标的函数，而在坐标变换时，这些分量也依照某些规则作线性变换。称为该张量的秩或阶（与矩阵的秩和阶均无关系）。在数学里，张量是一种几何实体，或者说广义上的“数量”。张量概念包括标量、矢量和线性算子。张量可以用坐标系统来表达，记作标量的数组，但它是定义为“不依赖于参照系的选择的”。张量在物理和工程学中很重要。例如在扩散张量成像中，表达器官对于水的在各个方向的微分透性的张量可以用来产生大脑的扫描图。工程上最重要的例子可能就是应力张量和应变张量了，它们都是二阶张量，对于一般线性材料他们之间的关系由一个四阶弹性张量来决定。

来源：维基百科

卷积神经网络技术

卷积神经网路（Convolutional Neural Network, CNN）是一种前馈神经网络，它的人工神经元可以响应一部分覆盖范围内的周围单元，对于大型图像处理有出色表现。卷积神经网路由一个或多个卷积层和顶端的全连通层（对应经典的神经网路）组成，同时也包括关联权重和池化层（pooling layer）。这一结构使得卷积神经网路能够利用输入数据的二维结构。与其他深度学习结构相比，卷积神经网路在图像和语音识别方面能够给出更好的结果。这一模型也可以使用反向传播算法进行训练。相比较其他深度、前馈神经网路，卷积神经网路需要考量的参数更少，使之成为一种颇具吸引力的深度学习结构。卷积网络是一种专门用于处理具有已知的、网格状拓扑的数据的神经网络。例如时间序列数据，它可以被认为是以一定时间间隔采样的一维网格，又如图像数据，其可以被认为是二维像素网格。

来源：Goodfellow, I.; Bengio Y.; Courville A. (2016). Deep Learning. MIT Press.维基百科

完美信息博弈技术

在经济学中，完全的信息是完美竞争的特征。随着市场信息的完善，所有消费者和生产者都被假定在对自由市场体系进行理论化和财务政策效应时，对产品的价格，效用，质量和生产方法有完整的认识。

来源：Wikipedia

强化学习技术

强化学习是一种试错方法，其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划（Dynamic Programming）。流行的强化学习方法包括自适应动态规划（ADP）、时间差分（TD）学习、状态-动作-回报-状态-动作（SARSA）算法、Q 学习、深度强化学习（DQN）；其应用包括下棋类游戏、机器人控制和工作调度等。

来源：机器之心

AlphaStar技术

AlphaStar是2019年1月DeepMind推出的打星际争霸2的AI系统。在1月的首次亮相中，DeepMind播放的比赛视频显示AlphaStar击败了两名人类职业选手TOL与MaNa，引起了业内极大的关注。DeepMind 官方博客介绍，AlphaStar 的行为是由一种深度神经网络生成的，该网络从原数据界面（单位列表与它们的特性）接收输入数据，输出构成游戏内行为的指令序列。具体来说，该神经网络使用了一个 transformer 作为躯干，结合了一个深度 LSTM 核、一个带有 pointer 网络的自动回归策略 head 以及一个中心价值基线。

来源：机器之心官网 DeepMind博客

AMD机构

超威半导体（中国）有限公司专门为计算机、通信和消费电子行业设计和制造各种创新的微处理器（CPU、GPU、主板芯片组、电视卡芯片等)，以及提供闪存和低功率处理器解决方案，公司成立于1969年。AMD致力为技术用户——从企业、政府机构到个人消费者——提供基于标准的、以客户为中心的解决方案。

https://www.amd.com/zh-hans

Infor机构

Infor是一家跨国企业软件公司，总部设在美国纽约市。Infor专注于通过云计算作为服务交付给组织的业务应用。最初专注于从财务系统和企业资源规划(ERP)到供应链和客户关系管理的软件， Infor在2010年开始专注于工业利基市场的软件，以及用户友好的软件设计。Infor通过Amazon Web Services和各种开源软件平台部署云应用。

www.infor.com