机器之心编辑部

AI 打斗地主，除了信息不完备，还要学会合作与竞争。

众所周知，AI 在围棋上的实力是人类所不能及的。
不过斗地主还不一定。
在 2017 年 AlphaGo 3 比 0 降服中国棋手，被付与职业九段之后，柯洁决定参加斗地主比赛，并得到了冠军。
在当时的赛后采访中，柯洁表示，「很欢快，希望往后再多拿一些冠军，无论什么样的冠军都想拿！
」

但是好景不长，在这种随机性更高的游戏上， AI 紧随而至。

近日，快手 AI 平台部的研究者用非常大略的方法在斗地主游戏中取得了打破，几天内就降服了所有已知的斗地主打牌机器人，并达到了人类玩家水平。
而且，复现这个研究只须要一个普通的四卡 GPU 做事器。

随着斗地主 AI 的不断进化，人（Ke）类（Jie）的斗地主冠军宝座不知还能否保住。

人工智能在很多棋牌类游戏中取得了很大的成功，例如阿尔法狗（围棋）、冷扑大师（德州扑克）、Suphx（麻将）。
但斗地主却因其极大的状态空间、丰富的隐含信息、繁芜的牌型和并存的互助与竞技，一贯以来被认为是一个极具寻衅的领域。

近日，快手 AI 平台部在斗地主上取得了打破，提出了首个从零开始的斗地主人工智能系统——斗零（DouZero）。

比较有趣的是，该系统所利用的算法极其大略却非常有效。
团队创新性地将传统的蒙特卡罗方法（即我们初高中教材中常说的「用频率估计概率」）与深度学习相结合，并提出了动作编码机制来搪塞斗地主繁芜的牌型组合。

该算法在不借助任何人类知识的情形下，通过自我博弈学习，在几天内降服了所有已知的斗地主打牌机器人，并达到了人类玩家水平。
干系论文已被国际机器学习顶级会议 ICML 2021 吸收，论文代码也已开源。
同时，论文作者开放了在线演示平台供研究者和斗地主爱好者体验。

论文链接：https://arxiv.org/abs/2106.06135GitHub 链接：https://github.com/kwai/DouZero在线演示：（电脑打开效果更佳；如果访问太慢，可从 GitHub 高***并离线安装：https://github.com/datamllab/rlcard-showdown）

在线演示支持中文和英文。
利用者可以选择明牌 / 暗牌，并可以调节 AI 出牌速率。
在明牌模式下，用户可以看到 AI 预测出的最好的三个牌型和估量胜率。

让 AI 玩斗地主难在哪儿？

一贯以来，斗地主都被视为一个极具寻衅性的领域。
首先，与许多扑克游戏和麻将一样，斗地主属于非完美信息游戏（玩家不能看到其他玩家的手牌），且包含很多「运气」身分。
因此，斗地主有非常繁芜的博弈树，以及非常大的状态空间（每个状态代表一种可能碰着的情形）。
除此之外，相较于德州扑克和麻将，斗地主还有两个独特的寻衅：

互助与竞争并存：无论是德州扑克还是麻将，玩家之间都是竞争关系。
然而，在斗地主中，两个农人玩家要相互合营对抗地主。
虽然过去有论文研究过游戏中的互助关系 [1]，但是同时考虑互助和竞争仍旧是一个很大的寻衅。
弘大而繁芜的牌型：斗地主有繁芜的牌型构造，例如单张、对子、三带一、顺子、炸弹等等。

它们的组合衍生出了 27,472 种牌型 [2]：

在强化学习里，这些牌型被称为动作空间。
作为比拟，这里列举出了常见强化学习环境及棋牌类游戏的动作空间大小：

虽然无限注德州扑克本身有与斗地主有相同数量级的动作空间，但是其动作空间很随意马虎通过抽象的办法缩小，即把类似的动作合并成一个。
例如，加注 100 和加注 101 没有很大的差异，可以合并成一个。
然而，斗地主中一个动作中的每张牌都很主要，且很难进行抽象。
例如，三带一中带的单张可以是任意手牌。
选错一次（比如拆掉了一个顺子）就很可能导致输掉整局游戏。

险些所有的强化学习论文都只考虑了很小动作集的情形，例如最常用的环境雅达利只有十几个动作。
有部分论文考虑了较大动作集的环境，但一样平常也只有几百个。
斗地主却有上万个可能的动作，并且不同状态有不同的合法动作子集，这无疑给设计强化学习算法带来了很大寻衅。
之前的研究表明，常用的强化学习算法，如 DQN 和 A3C，在斗地主上仅仅略微好于随机策略[2][3]。

「斗零」是怎么斗地主的？

比较有趣的是，斗零的核心算法极其大略。
斗零的设计受启示于蒙特卡罗方法（Monte-Carlo Methods）[4]。
详细来说，算法的目标是学习一个代价网路。
网络的输入是当前状态和一个动作，输出是在当前状态做这个动作的期望收益（比如胜率）。
大略来说，代价网络在每一步打算出哪种牌型赢的概率最大，然后选择最有可能赢的牌型。
蒙特卡罗方法不断重复以下步骤来优化代价网络：

用代价网络天生一场对局记录下该对局中所有的状态、动作和末了的收益（胜率）将每一对状态和动作作为网络输入，收益作为网络输出，用梯度低落对代价网络进行一次更新

实在，所谓的蒙特卡罗方法便是一种随机仿照，即通过不断的重复实验来估计真实代价。
在初高中教材中，我们学过「用频率估计概率」，这便是范例的蒙特卡罗方法。
以上所述是蒙特卡罗方法在强化学习中的大略运用。
然而，蒙特卡罗方法在强化学习领域中被大多数研究者忽略。
学界普遍认为蒙特卡罗方法存在两个缺陷：1. 蒙特卡罗方法不能处理不完全的状态序列。
2. 蒙特卡罗方法有很大的方差，导致采样效率很低。

然而，作者却惊异地创造蒙特卡罗方法非常适宜斗地主。
首先，斗地主可以很随意马虎产生完全的对局，以是不存在不完全的状态序列。
其次，作者创造蒙特卡罗方法的效率实在并没有很低。
由于蒙特卡罗方法实现起来极其大略，我们可以很随意马虎通过并行化来采集大量的样本以降落方差。
与之相反，很多最前辈的强化学习算法虽然有更好的采样效率，但是算法本身就很繁芜，因此须要很多打算资源。
综合来看，蒙特卡罗方法在斗地主上运行韶光（wall-clock time）并不一定弱于最前辈的方法。
除此之外，作者认为蒙特卡罗方法还有以下优点：

很随意马虎对动作进行编码。
斗地主的动作与动作之前是有内在联系的。
以三带一为例：如果智能体打出 KKK 带 3，并由于带牌带得好得到了褒奖，那么其他的牌型的代价，例如 JJJ 带 3，也能得到一定的提高。
这是由于神经网络对相似的输入会预测出相似的输出。
动作编码对处理斗地主弘大而繁芜的动作空间非常有帮助。
智能体纵然没有见过某个动作，也能通过其他动为难刁难代价作出估计。
不受过度估计（over-estimation）的影响。
最常用的基于代价的强化学习方法是 DQN。
但众所周知，DQN 会受过度估计的影响，即 DQN 会方向于将代价估计得偏高，并且这个问题在动作空间很大时会尤为明显。
不同于 DQN，蒙特卡罗方法直接估计代价，因此不受过度估计影响。
这一点在斗地主弘大的动作空间中非常适用。
蒙特卡罗方法在稀疏褒奖的情形下可能具备一定上风。
在斗地主中，褒奖是稀疏的，玩家须要打完全场游戏才能知道输赢。
DQN 的方法通过下一个状态的代价估计当前状态的代价。
这意味着褒奖须要一点一点地从末了一个状态向前传播，这可能导致 DQN 更慢收敛。
与之相反，蒙特卡罗方法直接预测末了一个状态的褒奖，不受稀疏褒奖的影响。

「斗零」系统如何实现？

斗零系统的实现也并不繁芜，紧张包含三个部分：动作 / 状态编码、神经网络和并行演习。

动作 / 状态编码

如下图所示，斗零将所有的牌型编码成 15x4 的由 0/1 组成的矩阵。
个中每一列代表一种牌，每一行代表对应牌的数量。
例如，对付 4 个 10，第 8 列每一行都是 1；而对付一个 4，第一行只有末了一行是 1。
这种编码办法可适用于斗地主中所有的牌型。

斗零提取了多个这样的矩阵来表示状态，包括当前手牌，其他玩家手牌之和等等。
同时，斗零提取了一些其他 0/1 向量来编码其他玩家手牌的数量、以及当前打出的炸弹数量。
动作可以用同样的办法进行编码。

神经网络

如下图所示，斗零采取一个代价神经网络，其输入是状态和动作，输出是代价。
首先，过去的出牌用 LSTM 神经网络进行编码。
然后 LSTM 的输出以及其他的表征被送入了 6 层全连接网络，末了输出代价。

并行演习

系统演习的紧张瓶颈在于仿照数据的天生，由于每一步出牌都要对神经网络做一次前向传播。
斗零采取多演员（actor）的架构，在单个 GPU 做事器上，用了 45 个演员同时产生数据，终极数据被搜集到一个中心演习器进行演习。
比较有趣的是，斗零并不须要太多的打算资源，仅仅须要一个普通的四卡 GPU 做事器就能达到不错的效果。
这可以让大多数实验室轻松基于作者的代码做更多的考试测验。

实验

为验证斗零系统的有效性，作者做了大量的实验。
这里我们选取部分实验结果。
作者将斗零和多个已有的斗地主 AI 系统进行了比拟，详细包括：

DeltaDou [5] 是首个达到人类玩家水平的 AI。
算法紧张基于贝叶斯推理和蒙特卡罗树搜索，但缺陷是须要依赖很多人类履历，并且演习韶光非常长。
纵然在用规则初始化的情形下，也须要演习长达两个月。
CQN [3] 是一个基于牌型分解和 DQN 的一种方法。
虽然牌型分解被证明有一定效果，但是该方法依然不能打败大略规则。
SL （supervised learning，监督学习）是基于内部搜集的顶级玩家的对战数据，用同样的神经网络构造演习出来的模型。
除此之外，作者尽可能搜集了所有已知的规则模型，包括 RHCP、RHCP-v2、RLCard 中的规则模型[2]，以及一个随机出牌策略。

斗地主中玩家分为地主和农人两个阵营。
作者利用了两个评估指标来比较算法之间的性能：

WP (Winning Percentage) 代表了地主或农人阵营的胜率。
算法 A 对算法 B 的 WP 指标大于 0.5 代表算法 A 强于算法 B。
ADP(Average Difference in Points)表示地主或农人的得分情形。
每有一个炸弹 ADP 都会翻倍。
算法 A 对算法 B 的 ADP 指标大于 0 代表算法 A 强于算法 B。

实验 1：与已知斗地主 AI 系统的比拟

作者比较胜率（WP）和分值（ADP）。
如下表所示，斗零（DouZero）在两项指标上都明显好于已知方法。
值得一提的是，由于斗地主本身有很大的「运气」身分，高几个百分点的胜率就代表很大的提高了。

实验 2：在 Botzone 平台上的比拟

Botzone（https://www.botzone.org.cn/）是由北京大学 AI 实验室开拓的在线对战平台，支持多种游戏的在线评测，并举办过多场棋牌类 AI 比赛。
作者将斗零上传到了斗地主对战的系统。
Botzone 计分结果表明，斗零在 344 个对战机器人中脱颖而出，在 2020 年 10 月 30 日排名第一。

实验 3：斗零的演习效率

作者用 DeltaDou 和 SL 作为对手，丈量斗零的演习效率。
所有的实验都在一个做事器上进行，该做事器包括 4 个 1080Ti GPU 和 48 核处理器。
如下图所示，斗零在两天内超过了 SL，在 10 天内超过了 DeltaDou。

实验 4：与人类数据的比较

斗零究竟学出了什么样的策略呢？作者将人类数据作为测试数据，打算不同阶段的模型在人类数据上的准确率，如下图所示。
我们可以创造两个有趣的征象。
首先，斗零在前五天的演习中准确率不断提高。
这表明斗零通过自我博弈的办法学到了类似于人类的出牌办法。
其次，在五天往后，准确率反而低落，这解释斗零可能学到了一些超出人类知识的出牌办法。

实验 5：案例剖析

上文提到，斗地主游戏中两个农人须要合营才能降服地主。
作者为此做了一个案例剖析，如下图所示。
图中下方农人出一个小牌就能帮助右方农人得胜。
图中显示了预测出的最优的三个牌型和预测的代价。
我们可以看到预测结果基本符合预期。
下方农人「认为」出 3 有非常高的得胜概率，而出 4 或 5 的预期代价会明显变低，由于右方农人的手牌很有可能是 4。
结果表明斗零确实学到了一定的互助策略。

总结

斗零的成功表明大略的蒙特卡罗算法经由一些加强（神经网络和动作编码）就可以在繁芜的斗地主环境上有着非常好的效果。
作者希望这个结果能启示未来强化学习的研究，特殊是在稀疏褒奖、繁芜动作空间的任务中。
蒙特卡罗算法在强化学习领域一贯不受重视，作者也希望斗零的成功能启示其他研究者对蒙特卡罗方法做更深入的研究，更好地理解在什么情形下蒙特卡罗方法适用，什么情形下不适用。

为推动后续研究，作者开源了斗地主的仿照环境和所有的演习代码。
值得一提的是，斗零可以在普通的做事器上演习，并不须要云打算的支持。
作者同时开源了在线演示平台和剖析平台，以帮助研究者和斗地主爱好者更好地理解和剖析 AI 的出牌行为。
鉴于当前的算法极其大略，作者认为未来还有很大的改进空间，比如引入履历回放机制来提高效率、显性建模农人之间的互助关系等等。
作者也希望未来能将斗零的技能运用到其他扑克游戏以及更加繁芜的问题中。

研发团队先容：这项事情是由 Texas A&M University 的 DATA 实验室和快手 AI 平台部的游戏 AI 团队互助而成。
DATA 实验室紧张从事数据挖掘和机器学习算法等方面的研究，以更好地从大规模、网络化、动态和稀疏数据中创造可操作的模式。
快手游戏 AI 团队，紧张依托在最前辈的机器学习技能，致力于做事游戏研发，推广，运营等各个环节。

参考文献：

[1] Lerer, Adam, et al. "Improving policies via search in cooperative partially observable games." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 05. 2020.

[2] Zha, Daochen, et al. "RLCard: A Platform for Reinforcement Learning in Card Games." IJCAI. 2020.

[3] You, Yang, et al. "Combinational Q-Learning for Dou Di Zhu." arXiv preprint arXiv:1901.08925 (2019).

[4] Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.

[5] Jiang, Qiqi, et al. "DeltaDou: Expert-level Doudizhu AI through Self-play." IJCAI. 2019.