|
机器之心报道
机器之心编辑部
AI 打斗地主，除了信息不完全，还要学会合作与竞争。
众所周知，AI 在围棋上的实力是人类所不能及的。不过斗地主还不一定。在 2017 年 AlphaGo 3 比 0 打败中国棋手，被授予职业九段之后，柯洁决议参加斗地主比赛，并获得了冠军。在当时的赛后采访中，柯洁表示，「很欢乐，希望当前再多拿一些冠军，无论什么样的冠军都想拿！」
但是好景不长，在这种随机性更高的游戏上， AI 紧随而至。
近日，快手 AI 平台部的研讨者用非常简单的方法在斗地主游戏中获得了打破，几天内就打败了一切已知的斗地主打牌机器人，并达到了人类玩家程度。而且，复现这个研讨只需求一个普通的四卡 GPU 服务器。
随着斗地主 AI 的不断退化，人（Ke）类（Jie）的斗地主冠军宝座不知还能否保住。
人工智能在很多棋牌类游戏中获得了很大的成功，例如阿尔法狗（围棋）、冷扑大师（德州扑克）、Suphx（麻将）。但斗地主却因其极大的形状空间、丰富的隐含信息、复杂的牌型和并存的合作与竞技，不断以来被以为是一个极具应战的范畴。
近日，快手 AI 平台部在斗地主上获得了打破，提出了首个从零末尾的斗地主人工智能系统——斗零（DouZero）。
比较风趣的是，该系统所运用的算法极其简单却非常有效。团队创新性地将传统的蒙特卡罗方法（即我们初高中课本中常说的「用频率估计概率」）与深度学习相结合，并提出了动作编码机制来应付斗地主复杂的牌型组合。
该算法在不借助任何人类知识的状况下，经过自我博弈学习，在几天内打败了一切已知的斗地主打牌机器人，并达到了人类玩家程度。相关论文已被国际机器学习顶级会议 ICML 2021 接收，论文代码也已开源。同时，论文作者开放了在线演示平台供研讨者和斗地主爱好者体验。
- 论文链接：https://arxiv.org/abs/2106.06135
- GitHub 链接：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. | 
