斗地主想躺赢？深度强化学习来帮你

极光扫描

​摘要：尽管很多深度强化学习方法在围棋等完全信息博弈问题中已经实现了近似最优解，但是当应用场景扩展到一些不完全信息博弈问题时，这些深度强化学习方法的表现却差强人意。而作为国民现象级游戏的斗地主，由于策略复杂，并且存在多玩家对战和配合的规则，造就了游戏中的不同玩家之间的信息不对称，加大了深度强化学习在这类不完全信息博弈游戏中的应用难度，使得应用深度强化学习进行此类问题的研究中显得更加充满趣味和挑战。本文就将以斗地主为例，探讨深度强化学习在不完全信息博弈中的应用。



图表 1    “和你合作真是太愉快了”意味着提示队友出炸，但目前还没有斗地主AI对“黑话”进行关注

<hr/>I.机器博弈介绍

机器博弈是近年来深度强化学习应用的热门课题，可以归结为完全信息博弈和不完全信息博弈。完全信息博弈指的每一参与者都拥有所有其他参与者的特征、策略及得益函数等方面的准确信息的博弈；而如果参与者中存在信息不对称的情况，就是不完全信息博弈。
具体而言，以斗地主为例，从任一玩家的角度来看，所获得的信息都是自己的牌面和已经打出的牌，但每个人对游戏整体态势的把握却是不一样的。例如：某玩家手中没有A牌，那么对于该玩家而言，另两名玩家手中的A牌数量和花色都是未知的；但是倘若某玩家手中有四张A牌（即俗称的A炸），那么他可以明确判断出另两名玩家是没有A牌的。而完全信息博弈则不同，以围棋、象棋为例，对弈双方对棋局的把握全凭棋盘上的局势，不存在信息不对称，从理论上讲，对弈双方可以站在完全对等的角度，模拟出棋局接下来所有可能的发展。
很多深度强化学习算法在完全信息博弈的游戏中收获了显著的应用成效，但在斗地主这类不完全信息博弈问题的应用中，却收效甚微。本文将重点介绍目前斗地主游戏中的最强AI——DouZero，通过沿袭DeltaDou的思路，结合深度神经网络，并搭配蒙特卡洛方法，成功斩获“斗地主之王”的称号。
<hr/>II.研究背景

要解决不完全信息博弈，有两种思路：一种是不断接近纳什均衡，找到博弈的平衡点，此种思路的代表是CFR算法；另一种思路是收益函数最大化，通过构建合理的收益函数，从最优化角度寻找策略解集，这种思路的代表是DQN、A3C算法。
a).纳什均衡
a.1.引入
纳什均衡，又称为非合作博弈均衡，是博弈论中的一个重要术语。在一场博弈中，如果任意一位参与者在其他所有参与者的策略确定的情况下，其选择的策略是最优的，那么这个策略组合就被定义为纳什平衡。
以经典的囚徒困境为例，图表2中展示了两名罪犯Alan和Ben选择承认或缄默时面对的刑期：当他们都拒不开口时，两个人都会判一年监禁；如果一方认罪，那么指认的一方就可以作为污点证人立即释放，但选择缄默的人却会判处15年监禁；而如果双方都认罪，两人都将面临十年刑期。
从理性人的假设考虑，在双方无法沟通的情况下，Alan和Ben基于各自的利益理性思考，都会选择指认。在这种情况下，无论哪一方单独作出改变，都不会使得双方都受益，这种情况就是纳什均衡。从上帝视角来看，其实两个人选择信任对方并且都保持缄默，才是对所有人最好的策略。但由于非合作博弈中沟通的缺失，往往只会追求纳什均衡，而非最优结果。



图表 2    囚徒困境

a.2.纳什均衡在游戏中的应用——CFR
因此，zinkevich（2008）就提出了使用虚拟遗憾最小化算法CFR（Counterfactual Regret Minimization），来获得近似的纳什均衡，这种算法也确实在德州扑克中取得了不错的效果。
但是正如前文所言，纳什均衡一般应用于解决非合作博弈问题，不支持沟通或者合作，每位玩家都从各自的角度理性思考进行决策和操作。而在斗地主游戏中，两名“农民队友”之间可以通过互相配合的方式，共同赢得胜利；此外，相比于德州扑克，斗地主的信息集合空间更大，动作可能性更多（图表3），而且不容易被抽象。出于以上种种限制，CFR算法在斗地主游戏中并未取得显著成效。



图表 3    有限注德州扑克和斗地主的信息集大小、动作状态空间大小比较

b).收益函数最大化
b.1引入
解决不完全信息博弈问题的另一种思路是通过构建收益函数，寻找预期收益最大化的解。下文中介绍的DQN (Deep Q-Network)和A3C (Asynchronous Advantage Actor-Critic)算法就属于经典的收益函数最优化求解算法。

• DQN
  在DQN算法中，首先利用深度神经网络来进行价值函数估计，解决在连续状态空间下的最优值求解问题，称为 Q-network；然后基于Q-value指导智能体决策过程，并对Q-network进行训练；最后使用经验回放解决数据冗余、样本相关性和非静态分布的问题。
  
• A3C
  A3C算法则在价值函数的基础之上，结合了策略梯度。使得策略能够基于当前状态调整未来动作的概率，同时价值函数也会基于经验和奖励不断更新。
  

b.2.收益函数最大化在游戏中的应用——DQN、A3C
在一些小游戏，例如Atari中的Space invader（Mnih 2015）中，使用DQN可以取得不错的效果。根据图表4我们可以看到，随着训练回合的不断扩大，绿色的飞船会更加灵活地左右移动，保证在不打到自己堡垒的情况下，射击更远处的外星飞船，从而获得更高的分数。



图表 4    用DQN玩Atari中的Space Invader小游戏，图源：台大李宏毅机器学习

但是DQN在斗地主的应用中同样存在动作空间过大的问题，使用DQN会导致结果估计和机器运算时间过长；而且斗地主的奖励稀疏（sparse reward）问题会导致DQN的收敛速度大大降低。因此DQN也不适用于斗地主游戏。
You（2019）将DQN、A3C，与RHCP（递归拆牌Recursive Hand Cards Partitioning）进行对比，发现DQN、A3C的胜率仅在20%以下（图表5）。
此外，由于A3C算法需要在价值函数优化求解的过程中，不断更新未来动作的概率。而在斗地主游戏中，牌池中剩余的牌和已经打出的牌关系很大，要严格准确概括牌组隐藏的出牌概率难度很大，因此A3C算法在斗地主中的适用性也不高。



图表 5    A3C、DQN与非机器学习算法在斗地主游戏中的胜率比较

<hr/>III.DeltaDou——AI崛起

Jiang（2019）提出的DeltaDou是第一个可以和顶尖真人斗地主玩家媲美的AI。为了解决不完全信息博弈问题，他结合了寻找纳什均衡和长期收益最大化两种思想，提出了虚拟博弈蒙特卡洛搜索树FPMCTS（Fictitious Play MCTS），并使用两种评分机制来评估算法效果。
a)虚拟博弈蒙特卡洛搜索树




图表 6    蒙特卡洛模拟搜索树一次迭代流程

传统蒙特卡洛树搜索MCTS是一种逼近纳什均衡的搜索策略，结合了树的搜索性，使结果收敛；又保持了蒙特卡洛的随机性，使得树的构建能够真实模拟和逼近实际牌局。如图表7所示，MCTS主要分为四个步骤：选择、拓展、仿真和回溯。
首先，从根节点开始，每次都选择一个“最值得搜索的子节点”。一般用上限置信区间算法来选择分数最高的节点（UCT），直到来到一个之前没有走过的走法节点，进入下一步拓展。FPMCTS结合将收益函数最大化的思路，将UCT拓展为P-UCT，得到玩家动作的概率分布。
在拓展阶段，FPMCTS 将节点扩展两级，产生新的决策节点。如图表7所示，对农民D的决策和概率进行测算。此局中，农民D的手牌为LJJ555443，共9张牌，而另一位农民E手中仅剩3张牌。此时农民D的出牌选择为单张3或者一对4。随着蒙特卡洛模拟的次数不断增多，对动作空间的概率测算也更加准确，因此经过200次模拟后，农民D推测下家农民E手里剩下一对A。此时，FPMCTS将农民D的决策从出单张3修正为打出一对4，从而让下家出牌，取得胜利。
接下里进行蒙特卡洛模拟：玩家从之前没有试过的走法开始，快速走到底并记录胜负。最后，将第三步中得到的胜负结果回溯合并到之前的MCTS树结构上。



图表 7 使用FPMCTS的农民上家出牌策略的蒙特卡洛树

b)评价机制ADP、WP

Jiang（2019）提出的两种评分机制分别为ADP（Average Difference in Points）和WP（Winning Percentage），通过两种算法对战的结果评估算法优劣。ADP计算的是对战得分差异，获胜得1分，失败丢1分，若对战中出现炸弹则分数加倍，最终得到ADP分数若为正，表示该算法应用下得到的策略效果优于对比算法的策略效果。而WP（Winning Percentage）计算的则是获胜次数占比，结果大于50%表示该算法胜于另一种对比算法。
相比于RHCP递归拆牌法，无论是从ADP还是WP来看，DeltaDou都表有着更优异的表现。但是和人类玩家相比，DeltaDou的表现还是略显逊色。这是因为在DeltaDou的决策中，废牌（例如三带一中的单张就属于废牌）十分重要，但却不容易被抽象化，选择不当甚至会破坏其他单张牌型（如顺子等牌型），最终导致输掉比赛。



图表 8    DeltaDou与其他算法效果比较

此外，DeltaDou计算成本也很高，即使在开始时用监督回归来进行训练，也需要两个多月的时间来完成。而DouZero的出现，则改变了深度强化学习在斗地主中应用效果不佳的局面。
<hr/>IV.DouZero——斗地主之王

Zha（2021）在汲取之前的经验之后，提出DouZero。所谓zero，即不需要任何领域知识或基础动态知识，从零开始通过自我对局来学习。因为其出色的表现，DouZero成为目前斗地主领域效果最好的深度强化学习AI。
DouZero继承了DeltaDou的部分思想，使用蒙特卡洛法进行随机模拟，找出使收益函数最大化的动作；在此基础上构建深度神经网络，对动作进行编译，寻找隐藏的出牌策略。这就是DouZero使用的DMC（Deep Monte-Carlo）法。
a)蒙特卡洛模拟法

蒙特卡洛模拟法（MC）直接从完整的状态序列来估计状态的真实价值，并认为某状态的价值等于在多个状态序列中以该状态计算得到的收益均值（Suton& Barto 2018）。
蒙特卡洛模拟方法在Douzero中的具体应用步骤如下：
第一步，生成一个策略回合π，并使用 ε-贪心策略（epsilon-greedy），使收益函数每次都收敛到局部最优解；



图表 9    ε-贪心策略

第二步，对于每个出现在回合中的状态s，动作a，都使用用均方误差(MSE)更新收益函数Q(s, a)。在这一步，DouZero不再使用MC法的收益函数Q，而将其替换为深度神经网络。
第三步，对于回合中的每个状态s，取使得期望收益最大的动作a，并计算对应的π(s)。
使用蒙特卡洛的优势在于：通过模拟直接逼近真实状态空间，使得估计不易受偏差值的影响；收敛速度与解空间的维数无关，能够同时计算多个方案与多个未知量；并且这种思想清晰直白，结构简单，易于实现。
b)深度神经网络




图表 10 DouZero的深度神经网络

深度神经网络在Douzero中的应用的特殊之处在于：结合牌局状态和出牌动作，形成深度神经网络的输入层（图表10左侧）；使用LSTM模型处理历史出牌矩阵；使用MLP（Multilayer Perceptron）（图表10右侧）来更新价值函数。

• 输入层：
  

DouZero使用的神经网络输入层，既包含了当前的牌局状态（state），也涵盖了出牌人的动作（action）。
（1）牌局状态
首先，DouZero将牌局状态编译成15*4的牌组矩阵（如图11），每列代表手牌数字，依次向上标记该数字手牌出现的记录。以3为例，在手牌中出现2次，则在3对应列（第一列）依次向上标记两个1，代表数字3在手牌中出现2次。



图表 11    牌组矩阵示意图

之后将该全牌组矩阵展平为60列的一维向量。因为小鬼和大鬼只有两个，所以删去6个空值，转换成一个长度为54的手牌矩阵。接下来，使用相同的编码步骤构建另外两名玩家的手牌矩阵，记录玩家们的手牌状态。利用类似的方法可以分别构建54维的最近出牌矩阵，54维的农民一及农民二的手牌矩阵；使用两个17维的one-hot编码向量代表两位农民的剩余牌数，以及一个15维的one-hot编码向量反映炸弹留存状况。
并且回溯之前5个回合的历史出牌，将每一个回合（即三次出牌）的出牌矩阵展开并拼接形成162（54*3）维向量，5个回合的历史出牌按行拼接，形成5*162维的历史出牌矩阵。在这一步骤中，由于使用每行记录一整个回合的出牌记录，即一回合中3名玩家分别的出牌记录，形成了163维的长序列向量，因此使用LSTM模型处理历史出牌矩阵，从而解决长序列训练过程中的梯度消失和梯度爆炸问题。相比普通的神经网络，LSTM模型在长序列中有着更好的表现。
（2）出牌动作
用类似的方法也可以构建出当前出牌动作的54维矩阵，最终动作矩阵和状态矩阵共同构成深度强化学习的输入层。



图表 12    地主牌组的矩阵和向量大小

• MLP：
  

将动作和状态合并之后，使用层数为6的多层感知机MLP（Multilayer Perceptron）来生成动作价值函数Q的值。（图表13）



图表 13   多层感知机，图源：twitter

除了全局神经网络以外，DouZero还分别对三个玩家分别构建角色网络，分别学习地主和两个农民的动作与状态。并且通过共享缓冲区，使得全局神经网络和角色网络之间实现连结和定期通信。
c)DouZero在斗地主应用中的表现

根据图表14可以看出，从与其他算法竞争的结果来看，DMC的表现极为出色。首先，DouZero打败了所有基于规则的策略（RHCP、CQL）和监督式学习（SL），这证明了在斗地主中采用强化深度学习的有效性。



图表 14    DouZero与其他算法对弈结果



图表 15    左图：DouZero与Deltadou、SL对比；右图：DouZero 在 344 款斗地主机器人中排名第一，截至 2020年10月30日评分为 1625.11

其次，Douzero还打败了之前的Deltadou，双方对战中，Douzero的获胜次数占比达到58.6%，成为最强斗地主AI（图表14，15）。
在执行时间上，DeltaDou也相当出色（图表16）。这是因为DMC由于DouZero 基于蒙特卡洛模拟直接进行采样和模拟，可以轻松每秒同时生成数千个样本，以缓解高方差带来的收敛过慢的问题，从而加速训练。这样，DMC虽然使用了复杂的神经架构，但也能每秒生成更多数据。而且由于DMC算法其不受回合长度限制，无需大量数据来模拟收益，因此训练速度很快，DouZero三天就能超过DeltaDou，十天就能基本完成训练。（图表17）



图表 16    每步平均执行时间



图表 17    WP、ADP两种评价机制下DouZero的训练时间，黑色虚线是DeltaDou的基准线

DouZero不仅使用矩阵解决了动作编译复杂的问题，也用DMC算法帮助解决了奖励稀疏导致的收敛过慢问题，并且还使得机器可以从0开始，通过模拟自我对局，就可以完成很好的学习。当然作者也提出，DouZero还有很多可以改进的空间，可以帮助DouZero在真人对战中进一步提升胜率和运算效率。例如，作者提出之后可以用ResNet等卷积神经网络CNN网络来代替LSTM，进一步减少训练时间，解决长序列训练过程中的种种问题；在强化学习中可以尝试Off-Policy学习，将目标策略和行为策略分开以提高训练效率；以及关注黑话的使用，尝试模拟农民的合作等等。
<hr/>V.结论

DeltaDou是首个达到人类玩家水平的 AI，算法主要基于贝叶斯推理和蒙特卡洛树搜索，但缺点是需要依赖很多人类经验，并且训练时间非常长。而DouZero则将深度神经网络和传统强化学习蒙特卡洛法结合，不仅表现出色，训练时间也大幅缩短，还无需有知识背景。DouZero的出现，启发了后人对深度强化学习在不完全信息博弈的游戏中的应用相关思考，也让我们惊叹于机器学习的魅力，期待在未来获得更加广泛的应用。
<hr/>参考文献

[1] Martin Zinkevich. Regret Minimization in Games with Incomplete Information.2008
[2] Yang You. Combinational Q-Learning for Dou Di Zhu.2019
[3] Volodymyr Mnih. Human-level control through deep reinforcement learning.2015
[4] Qiqi Jiang. DeltaDou: Expert-level Doudizhu AI through Self-play.2019
[5] Daochen Zha. DouZero: Mastering DouDizhu with Self-Play DeepReinforcement Learning.2021
[6] Suton, Barto. Reinforcement Learning:An Introduction.2018

市场有风险，投资需谨慎。以上陈述仅作为对于历史事件的回顾，不代表对未来的观点，同时不作为任何投资建议。

深海迷航

专业抢沙发的！哈哈