2022/04/29 15:22

腾讯AI Lab作者

ICLR 2022｜让绝艺上桌打麻将，腾讯AI Lab全新策略优化算法战胜人类冠军

「绝艺」又有了新成果：在1v1麻将（二人雀神）测试中战胜职业冠军选手。

对于 AI 领域的研究者和从业者来说，腾讯 AI Lab 研发的围棋 AI「绝艺」的名字并不陌生。自 2016 年面世后，它已四次夺得世界顶级赛事冠军，包括 UEC 杯、AI 龙星战、腾讯世界人工智能围棋大赛、世界智能围棋公开赛等，并自 2018 年起无偿担任中国国家围棋队训练专用 AI。

在围棋以外，腾讯 AI Lab 绝艺团队持续深入研究大规模二人零和博弈问题，从完美信息游戏（围棋）逐步拓展至非完美信息游戏（例如麻将）。

4 月 25 日，腾讯 AI Lab 宣布棋牌类 AI「绝艺」取得新突破，在 1v1 麻将（二人雀神）测试中战胜职业冠军选手。团队在大规模强化学习算法框架下提出了一个新的策略优化算法 Actor-Critic Hedge (ACH)，部分解决了大规模深度强化学习自博弈收敛不到纳什均衡最优解的问题。该算法及对应二人麻将 benchmark 已通过论文开源，并被机器学习顶会 ICLR 2022 收录。

论文链接：https://openreview.net/pdf?id=DTXZqTNV5nW

非完美信息博弈广泛存在于日常生活的方方面面，如智慧交通、网络安全、金融分析等。腾讯 AI Lab 以麻将 AI 为切入点研究非完美信息博弈，其目标不仅限于打造世界级的国粹麻将 AI，更多的在于探索非完美信息博弈在游戏领域，以及其他广阔的社会生活领域的实际应用价值。

研究背景

棋牌游戏一直以来都是 AI 技术的优质试验场，例如，在围棋上就诞生了 AlphaGo、绝艺等标杆性的 AI。相比于围棋这类「完美信息」游戏，德州扑克，桥牌，麻将这类 “非完美信息” 游戏存在着大量的隐藏信息，例如，玩家无法直接知道对手的手牌，这给游戏带来了更高的不确定性，对 AI 的博弈能力提出更高要求。

具体而言，在完美信息游戏中，始终存在确定性的最优解，即任何状态下都存在一个固定的最优动作。然而在非完美信息游戏中，最优策略往往是随机化的。例如，在二人石头 - 剪刀 - 布游戏中，最优策略（纳什均衡策略）不在是某一个固定的动作，而是关于每个动作的一个概率分布：等概率出石头，剪刀，和布。

二人石头 - 剪刀 - 布

近年来，反事实遗憾值最小化算法（CFR）在德州扑克游戏 AI 上取得了一些列突破性进展，例如 DeepStack（2017 Science 杂志），Libratus（冷扑大师，2017 Science 杂志），和 Pluribus（2019 Science 杂志）。CFR 具有收敛到纳什均衡解的理论保证。然而，由于 CFR 是一种基于表格的算法，并且需要对游戏树做全遍历，CFR 在德州扑克游戏上的应用需要大量的领域知识来对游戏树做剪枝。虽然后续有一些工作尝试将深度学习和 CFR 做结合，但目前还没有看到 CFR 在其他大规模非完美信息游戏上的成功应用。

另一方面，由于深度强化学习高效的可扩展性，深度强化学习结合自博弈广泛用于大规模非完美信息游戏中求解高强度 AI，例如星际 2，Dota2，和王者荣耀。

然而，基于深度强化学习的大部分 AI 的鲁棒性有待提高，集中表现为 AI 容易被针对，最坏情况下的性能没有保证。这些问题的根本原因在于深度强化学习结合自博弈缺乏收敛到纳什均衡解的理论保证。例如下图所示，在一个简单的二人石头 - 剪刀 - 布游戏中，自博弈 Proximal Policy Optimization 无法收敛到（红线为收敛过程）纳什均衡解（蓝点）。

方法简介

腾讯 AI Lab 的研究结合经典反事实遗憾值最小化算法 CFR 的思想，在大规模强化学习算法框架下提出了一个新的策略优化算法 Actor-Critic Hedge (ACH)。该算法一方面具备深度强化学习方法的可扩展性，一方面在某些条件下具备收敛到纳什均衡解的理论保证。

具体来说，我们修改传统深度强化学习策略网络的损失函数：从最大化累计奖励到拟合累计采样 advantage：

累计采样 advantage 与 CFR 中的累计遗憾值存在一定的等价关系。另外，可以证明，相比过去基于采样 regret 的方法，采样 advantage 有更小的 variance：

更小的 variance 在基于神经网络的方法中意味着更稳定的效果。

ACH 具体算法流程如下：

在该工作中，我们引入了一类新的 CFR 算法：Weighted CFR。Weighted CFR 有如下定义：

算法 ACH 可以看作是一类基于神经网络的 Weighted CFR 算法的一个高效实现。我们证明了 Weighted CFR 的算法收敛性，进而近似证明了 ACH 的算法收敛性：

另外，针对 1v1 麻将的具体神经网络设计如下：

实验结果

在对比主流方法的基础上，该算法的优越性在 1v1 麻将（战胜职业冠军）和 1v1 德州扑克上均得到了验证。

二人麻将：「二人雀神」

1v1 麻将（二人雀神）测试中，「绝艺」与世界冠军职业选手对战 1000 回合，平均赢番 0.82（标准差 0.96，单边 t 检验的 p value 为 0.19）

1v1 麻将环境，主流算法性能对比

1v1 简单德扑环境，各种经典反事实遗憾值最小化算法扩展的对比

理论麻将非完美信息博弈绝艺

相关数据

纳什均衡技术

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

来源：维基百科

深度学习技术

深度学习（deep learning）是机器学习的分支，是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。深度学习是机器学习中一种基于对数据进行表征学习的算法，至今已有数种深度学习框架，如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

来源：LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. nature, 521(7553), 436.

深度强化学习技术

强化学习（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.

剪枝技术

剪枝顾名思义，就是删去一些不重要的节点，来减小计算或搜索的复杂度。剪枝在很多算法中都有很好的应用，如：决策树，神经网络，搜索算法,数据库的设计等。在决策树和神经网络中，剪枝可以有效缓解过拟合问题并减小计算复杂度；在搜索算法中，可以减小搜索范围，提高搜索效率。

来源：Wikipedia

概率分布技术

概率分布（probability distribution）或简称分布，是概率论的一个概念。广义地，它指称随机变量的概率性质－－当我们说概率空间中的两个随机变量具有同样的分布（或同分布）时，我们是无法用概率来区别它们的。

来源：维基百科

收敛技术

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

来源：Wikipedia Google ML glossary

损失函数技术

在数学优化，统计学，计量经济学，决策理论，机器学习和计算神经科学等领域，损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

来源：Wikipedia

神经网络技术

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

策略网络技术

在强化学习中，策略网络指一组相对稳定的关系，这些关系具有非等级和相互依赖的性质，将各个行为者（actor）联系起来。

来源：igi-global

完美信息博弈技术

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

来源：Wikipedia

强化学习技术

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

来源：机器之心

腾讯机构

腾讯，1998年11月诞生于中国深圳，是一家以互联网为基础的科技与文化公司。我们的使命是“通过互联网服务提升人类生活品质”。腾讯秉承着 “一切以用户价值为依归”的经营理念，为亿万网民提供优质的互联网综合服务。腾讯的战略目标是“连接一切”，我们长期致力于社交平台与数字内容两大核心业务：一方面通过微信与QQ等社交平台，实现人与人、服务及设备的智慧连接；另一方面为数以亿计的用户提供优质的新闻、视频、游戏、音乐、文学、动漫、影业等数字内容产品及相关服务。我们还积极推动金融科技的发展，通过普及移动支付等技术能力，为智慧交通、智慧零售、智慧城市等领域提供有力支持。

http://www.tencent.com/