![[Paper] 麻将AI Suphx](data:image/svg+xml;utf8,<svg xmlns='http://www.w3.org/2000/svg'></svg>)
[Paper] 麻将AI Suphx
这篇文章主要介绍微软亚洲研究院的麻将AI Suphx的思路与细节，汇总了论文信息、直播答疑信息、博客等材料中的信息并进行重新排列。文章主要分为四个部分，第一部分介绍麻将AI中存在的三个主要挑战，接着第二部分介绍文章针对这些问题引入的三个新的模块，并在第三部分结合到整个训练流程中，最后第四个部分介绍不同模块的离线评估效果以及Suphx在线测试效果与亮点。
1. Challenges
首先第一部分描述麻将AI中存在的挑战，文章中将它陈述为三个部分。
1.1 Complicated Scoring Rules
第一个挑战是得分规则计算相对其他游戏要复杂。在竞技麻将中，通常是进行若干回合，基于这些回合的累计分数，得到整个对局的排名，最终基于排名去调整玩家的分段。所以它的复杂性来自两方面：
首先是来自单回合内，这也就是常规的RL中的sparse reward的挑战，在每回合可能有上百个action，但是只有对局结束才会返回一个score，reward传播慢，从而导致学习慢。
其次则是来自不同回合之间的，由于agent学习的最终目标是保证在多个回合之后排名领先，单回合的获胜并不代表最终分数就高。文章中举的一个例子是如果玩家在最后一局的时候出于第一名，为了防止在最后一局被第二名超过，它可能会策略性地选择输掉最后一局，让第三/第四名获胜。这种能力是常规RL的设置中所无法学习到的，虽然说RL中能学习到某些为了大局而作出一些小牺牲，但是这些都是在一个回合之内的行为。而在不同回合之间，游戏都是重新开始的，它们是不存在关联的，就没法做出类似上面例子中的关联性行为。所以克服这个难题的关键点就在于如何将最终的rank拆分到每个回合中，根据之前对局的信息，知道现在这个回合对于最终结果的影响。
在论文中，引入了global reward prediction，通过人类高手进行监督学习得到每个对局的重要性，一并解决上述的两个问题。
1.2 Imperfect Information
第二个挑战则是来自输入信息。相对围棋等完全信息的游戏，麻将中能看到的信息只有自己的手牌以及台上被丢出的牌，对手的牌和牌墙上的牌都是看不到的，而据论文所说，麻将的隐含信息相对德扑要大得多，这也侧面证明了它的学习难度更大。
过去的DRL的成功应用中也有不少关于imperfect information的处理。在OpenAI的Dota Five使用了传统DRL的对于partial information的处理，利用RNN来提取过去observation中包含的当前不可知的信息。DeepMind的Capture the flag中，对RNN进行一定的变化，引入了Fast&Slow RNN，在不同间隔上同时对信息进行提取。而在Alphastar中一方面也使用了RNN来提取时序信息并利用FiLM的结构，将提取的时序信息嵌入ResNet的每个block中，另一方面也借鉴了近年multi-agent RL中centralized training & decentralized execution模式，在训练value function时候同时引入敌我双方的特征对critic进行训练，辅助policy的学习，而在决策时不需要用到critic，所以摆脱了对敌方特征的依赖。
在Suphx论文中，则是引入了Oracle Guiding的概念，在训练过程中，对于模型的输入从完全信息缓慢降低到可见信息，这个从某个角度来讲就是curriculum learning的一个过程，通过控制信息量的角度将任务难度缓慢提高，希望尽可能保留在信息多时候学习到的能力。
1.3 Complex playing rules
第三个挑战则是游戏规则的复杂性带来的。这个点的提出主要是对标围棋和德扑。一方面是麻将本身容易出现打断整个牌局顺序的行为，另一方面imperfect information也使得模型更难预测何时会打断，所以导致构建game tree变得比较困难，即使能够建起来也会比较庞大，而文章也提到critic的训练比较困难，类似AlphaZero中利用critic作为MCTS expansion阶段的value也很难做到，从而MCTS/CFR这两个在围棋和德扑中发挥重大作用的方法难以在麻将中应用。
文章中写这个挑战主要是为了引出下面的policy adaption，但是由于在线计算的速度要求，天凤平台对战的AI并没有用上policy adaption，也达到了大家现在了解到的效果。
2. Novel Techniques
这个部分就正式介绍解决上面提到的三个挑战对应的三个方法，在evaluation部分会介绍这些方法带来的提升。
2.1 Global Reward Prediction
引入的第一个模块是global reward prediction，它针对的是上面提到的竞技麻将中的复杂计分规则的问题。从某种意义上看，它其实就是一个Inverse Reinforcement Learning的过程：从人类数据中学习reward。这里我们直接看reward predictor的结构图：
这个模块的主要思路就是用GRU去建模一局中前若干个回合对整局的贡献。例如对第k轮，就输入从0到k回合的对局信息到GRU中，输出前k回合的累计reward \Phi\left(x^{k}\right) 。而要得到第k回合的reward，它就是相邻两个回合的predict value的差值： \Phi\left(x^{k}\right)-\Phi\left(x^{k-1}\right) ，用于表征当前这回合对整个流程的贡献。
这个网络的训练就是直接利用人类数据进行监督学习。它的输入是当前回合的分数，庄家，连庄的轮数，立直（听牌）的点数，输出则是最终整局的分数，训练数据则是来自人类顶尖高手的对局。在这里并没有输入任何跟当前回合对战的具体牌面与对战信息，而仅仅是一些会影响到最终分数的指标。这个阶段是希望能够学习到人类顶尖高手在回合层面的战略判断。
在监督学习阶段将模型训练至收敛之后，在强化学习计算就利用它作为reward来指导agent的学习。在采集到数据之后，将上面提到的对局信息输入GRU中，对相邻回合做差，就可以得到当前回合的reward，再将它作为其中每个state-action pair的reward，用于强化学习算法优化agent。
2.2 Oracle Guiding
第二个模块则是针对Imperfect information做的优化。在前面也有提到在multi-agent以及alphastar中都有作弊式地利用一些无法获取到的信息辅助agent学习。这里则是利用perfect information来给agent的训练做curriculum learning，这也就是oracle所表达的含义。
还是先一句话概括一下oracle guiding的做法：从perfect information开始训练，按概率随机屏蔽部分不可见的信息，在训练过程不断提高屏蔽的概率，最终完全屏蔽作弊信息。
具体可以看下面这个公式：
\mathcal{L}(\theta)=\underset{s, a \sim \pi_{\theta^{\prime}}}{\mathrm{E}}\left[\frac{\pi_{\theta}\left(a |\left[x_{n}(s), \delta_{t} x_{o}(s)\right]\right)}{\pi_{\theta^{\prime}}\left(a |\left[x_{n}(s), \delta_{t} x_{o}(s)\right]\right)} A^{\pi_{\theta}}\left(\left[x_{n}(s), \delta_{t} x_{o}(s)\right], a\right)\right] \\
目前需要关注的只是它的输入信息，也就是这个部分 \left[x_{n}(s), \delta_{t} x_{o}(s)\right] ， 其中前半部分表示对战时的能获取的信息，后半部分表示作弊获取到的信息。它的核心点在 \delta_{t} 这个dropout matrix，里面的每一项都是一个Bernoulli分布 P\left(\delta_{t}(i, j)=1\right)=\gamma_{t} ，经过矩阵乘法就表示某一个部分作弊信息是否需要在网络中mask掉，随着训练这个概率从1到0衰减，到最后所有作弊信息都会被mask掉。
最终作弊信息被mask掉之后，就回到了正常的强化学习训练过程了，在这里文章提到了两个小trick：第一个是在继续训练的时候将学习率陡降到原学习率的1/10，个人感觉这个主要是因为样本质量下降了，需要防止单步训练对原模型影响太大。第二个则是引入reject sampling，将训练中质量太差的样本丢弃掉，提高训练效果。（具体这个importrance sampling weight在3.4中会有讲解）
基于dropout的curriculum learning相对直接mask信息的方式的高明之处在于它可能每轮都mask不同的信息，这其实就相当于学习进度往前推进了，但是仍然在不时复习过去的知识，所以它更容易保留过程学习的技能，这从直观上看也是符合直觉的。
2.3 Policy Adaptation
第三个模块是针对运行时进行的优化，前面提到由于规则复杂，构建game tree比较困难，导致一些search-based的方法难以应用，而由于麻将的初始牌面对于整局的打法是影响很大的，虽然agent能够学习到应对不同的初始牌面，但是如果能在获得这个麻将初始牌面的时候针对性的做一些优化，效果必然会更好了。这里提出了Parametric Monte-Carlo Policy Adaption就是沿着这个思路来做优化的。
同样一句话概括一下policy adaptation的做法：在每回合获得初始牌面后，随机生成若干局对手牌面与墙牌，agent基于这些牌面进行self-play得到训练数据，进行一个小的强化学习训练，对policy进行微调。
具体而言可以分成三个步骤：
- Simulation：随机生成若干局对手牌面与墙牌，运行self-play，得到K回合的trajectory。
- Adaptation：按照正常的RL训练流程对网络参数进行更新。
- Inference：基于finetuned过的policy与对手对战。
需要留意的是，这里在不同回合中，策略都会回归到同一个原策略，也就是每回合adaptation并不会对其他回合有影响。在文章中提到simulation的对局数量不需要太大，不过在evaluation阶段是对一个初始牌面进行了10W次对局的simulation，所以看来要出现好效果需要的对局还是稍微多了点。可能也是因为这个原因，线上对战的时候并没有用上policy adaptation。
3. Learning Algorithm
上面讲完了文章的三个创新点，这节会介绍整体的训练流程，并将这三个点结合到训练流程中，下面这个是总体的结构：
3.1 Decision Flow
首先先直观地介绍一下决策流程，由于涉及到比较多麻将术语，这里选用官方介绍中的中文流程图，便于大家理解整个过程：
这整个流程图其实就是两个部分内容，一个部分是客观事实，也就是场上发生了什么事件，当前可做的决策。另外一部分是主观决策，也就是基于能做的决策类型去做出判断。
从是否打断打牌顺序的角度可以将决策流程分为左右两部分，左边一部分是到当前玩家摸牌，所以可以执行的动作是要么直接胡牌，要么可以加杠/暗杠，要么就直接立直，如果都不选就从牌堆中选择一张牌来丢出。而右边一部分则是不轮到当前玩家执行动作，这时候做的就是一些可以打破游戏顺序的操作：胡牌/吃/碰/杠，在这些行为中选择模型输出概率最大的。
所以距离整个系统正常运作就只差上面提到的六个模型了，在这节的剩下几个部分会介绍这六个模型的结构，输入和训练方法。
3.2 Features & Models
这个部分介绍决策流程中的六种模型的结构以及它们的输入特征。
对于上面的六个决策模型，可以拆分为两类模型。一类是仅仅决策是否的模型，胡/立直/吃/碰/杠都是归为这类。另外一类则是输出选择哪张牌，在这里就是丢牌模型：如果不选择胡/杠/立直，就会从34种牌中选择一种来当前持有的来输出。所以网络结构也就可以分为以下两类：
两类的结构也基本差不多，传入输入特征，经过50个block的resnet，再经过简单的网络处理得到输出。对于多分类在经过resnet之后则使用1*1的卷积进行降维，而二分类最后则是直接过fc得到output。
讲完网络之后就是给网络输入什么，这里对特征做了两部分的处理，分别是observable information和look-ahead features，这里的look-ahead features还是蛮有的特征设计痕迹的。需要注意的是，这里的特征是以牌为单位的，所以最后的输入是D*34的，也就是每张牌都有D维。
首先是observable information，对于我的手牌，所有人已经打出去的牌，宝牌是哪些等信息，都会单独进行编码，编码方式如下图，这里的四个channels是表示当前编码的信息中有多少个，例如这里我的手牌中有三个红中，那么红中就有三个channel是1。而对于上面提到的不同类型信息都会进行一次这样的编码，然后将他们堆叠。
其次是look-ahead feature，它表示摸回一张牌并丢出某张牌之后的胜率以及得分情况的估计。文章使用了DFS来寻找可能的获胜情况，为了简化计算，在搜索过程忽略对手们的行为情况（文章没有仔细描述这个过程）。
此外，对于吃/碰/杠三个模型，输入的信息里同样包含了让哪张牌吃/碰/杠的信息，因为有些情况，例如吃是可能存在多个选择的，这时候就要分别进行前向确定选择哪个的概率大。
3.3 Supervised Learning
这部分和下一部分会介绍如何基于上面的特征对这几个网络结构进行学习。整体的学习步骤还是分成两个阶段：监督学习与强化学习。
监督学习的部分就比较直接了，论文从人类高手的对战中抽取出大量的数据进行训练，最终的训练效果对比过去有类似做法的文章精度都要高，训练数据量也在表中，其中验证集的数据是10K，测试集的数据是50K。仅仅通过监督学习得到的模型也能获得不错的效果。（这里只提到了五个模型，胡牌模型没有列入其中）
3.4 Reinforcement Learning
接下来就来到重头戏，如何基于监督学习的模型进行进一步的强化学习（在最终模型中，仅仅对discard model进行了进一步的强化学习训练）。
由于算法的选择与系统架构往往是相适应的，所以先介绍这里的分布式训练系统，总体上看是基本配置：分布式采样，数据存储在replay buffer中，采样进行策略更新：
其次是算法选择，这里选择的是带importance sampling的policy gradient算法，不太了解到同学可以简单搜索一下：
\mathcal{L}(\theta)=\underset{s, a \sim \pi_{\theta^{\prime}}}{\mathrm{E}}\left[\frac{\pi_{\theta}(a | s)}{\pi_{\theta^{\prime}}(a | s)} A^{\pi_{\theta}}(s, a)\right] \\
在这里的advantage并没有引入critic作为baseline，而是直接用一批数据的reward的均值作为baseline，reward来源于global reward predictor的输出值。为了鼓励exploration，在目标函数中添加了entropy项：
\nabla_{\theta} J\left(\pi_{\theta}\right)=\underset{s, a \sim \pi_{\theta^{\prime}}}{\mathrm{E}}\left[\frac{\pi_{\theta}(s, a)}{\pi_{\theta^{\prime}}(s, a)} \nabla_{\theta} \log \pi_{\theta}(a | s) A^{\pi_{\theta}}(s, a)\right]+\alpha \nabla_{\theta} H\left(\pi_{\theta}\right) \\
接着这里引入了动态调整的entropy系数：根据经验设置一个entropy的标准值，如果当前entropy小于这个值，那么系数加大，如果当前entropy大于这个值，那么系数减少：
\alpha \leftarrow \alpha+\beta\left(H_{\text {target }}-\bar{H}\left(\pi_{\theta}\right)\right) \\
而上面提到的reject sampling就是用在这个replay buffer中，由于分布不匹配对policy gradient影响比较大，所以这里将分布差异太大的数据直接丢掉，这里仍然是人工设置的一个未知的阈值。
自此Suphx的方法部分就介绍完毕了，下面会简单讲一下效果评估。
4. Evaluation
在文章评估部分，主要有两个比较包含信息量的点：SL和RL的各个组件的离线评估效果，SL最终模型在线上的得分。需要注意的是：下面的两个Evaluation体系的绝对分数有一定参考性，但是无法对比。
4.1 Offline Evaluation
首先是添加的各个组件的效果，在离线评估系统中存在五个模型，它们分别是：
- SL：仅仅通过监督学习得到的模型。
- SL-weak：一个训练未完成的SL模型，效果略差于SL。
- RL-basic：在SL模型的基础上，对discard model训练了1500W局，这里的reward使用了回合的score。
- RL-1：在RL-basic基础上加了global reward predictor用于计算回合reward。
- RL-2：在RL-1的基础上在加上了oracle guiding。
评估中，生成了100W场初始牌面，其余四个模型都以三个SL-weak作为对手在这些牌面上交战，最终得到稳定的分数。效果自然符合预期。
这里值得留意的一点是RL-2在这里的分数是8.3，而SL分数是7.67左右，在后面在线评估中，训练2500W轮的RL-2得分是8.74，人类顶尖选手是7.46，所以看到这里还是蛮好奇SL模型在线上评估中分数是否能大于7.46。
另外，文章还对比了有无policy adaptation的效果差异，这这里对于每个初始牌面生成了10W个对局进行policy adaptation，也就是说在当前初始牌面下采样了10W场对局进行进一步训练，对战没有经过这10W场对局的自己。在同样的初始牌面生成另外的10W对局于没有进行adaption的RL-2进行对战。在上百场对局后，胜率差不多66%。文章中挑选了一个例子，说明经过adaption后行为略有差异，特别在最后两回合中，如果发现在adaptation过程中很容易第四名，就就会打得比较激进，希望依靠这个活的更多score，避免第四名。（感觉举例说明有点不够有说服力，而且按照前面所讲，这个行为应该也会被global reward predictor引导出来）
4.2 Online Evaluation
最后一部分就是在线评估了，首先是总体效果，相比人类顶尖选手和之前的一些AI的分数，总的数据是超过了平台上99.99%的玩家。
另外，文章经过统计也发现Suphx点胡和排最后的概率都比较小，前者说明它更容易赢，少排第四不容易输太多，分段比较稳定：
5. Comments
这篇论文看过来最重要的点还是imitation learning的重要性，在大型任务上，利用人类数据做监督学习预训练是目前提高训练效率的最好选择。在Suphx中，仅仅监督学习在offline evaluation系统中已经可以达到7.67的效果了。目前来看用监督学习达到的最惊艳的结果还是AlphaStar的效果，一方面是监督学习已经达到星际钻石选手水平，另一方面它引入了Z统计量，给监督学习训练出来的模型提供了具有多风格的可能性。关于Z的使用，AlphaStar已经在星际这个大场景中验证过了，感觉它会是给Agent提供训练多样性提高self-play的robust的有效途径。
总体而言，整篇文章从思路上看比较顺畅，但是感觉细节和实验部分都做得不太够，包括备注里提到的H-target，advantage计算，以及各种超参数的值都没有提及。另外，实验感觉相对Dota Five和AlphasStar都要单薄许多，可能是因为比较耗算力，以及对战平台的限制，ablation study没法做得比较全面。Suphx现在也还在尝试一下新的点，希望后续能看到更多精彩的内容。
最后的备注：上面一些细节主要来源于直播中的提问，包括H_target的设置，advantage的计算，reward是否整回合都一样，学习率降低到1/10是否是突变。
预告一下，下篇论文阅读会写DeepMind最近发的agent57。
