Suphx论文阅读笔记
Published:
Suphx，国内玩家一般称之为苏菲，是目前日麻最强AI。 其论文于3月30日发布于arXiv，我是在@爱可可-爱生活老师的微博上看到的。 本文是论文阅读笔记，其实差不多是简单翻译了一下。 视频在B站。
1. 引言
首先给出几个词语：
- Round：局
- Game：半庄
- Riichi：立直
- Chow：吃
- Pong：碰
- Kong：杠
1.1 日麻AI面对的三大挑战
- 记分规则复杂。 我们以半庄结束时尽量上分为目的，因此不能单纯地以一局的胜负作为反馈信号。 从这个角度来讲日麻比象棋围棋都复杂。
- 信息不完全可见。 象棋围棋等游戏中所有信息都是对双方可见的，而日麻牌山和其他家的手牌是不可见的，隐藏的状态是天文数字，这使得我们很难把奖励和可见的信息联系起来。
- 游戏过程不确定。 象棋围棋等游戏中玩家的决策顺序很直白，双方轮流走棋。 而麻将中四名玩家的操作顺序可以被吃碰杠打断，这使得棋类游戏中的蒙特卡洛树搜索(Monte-Carlo tree search)和德州扑克中的反事实反悔最小化(counterfactual regret minimization)算法均不适用于麻将。
1.2 苏菲的解决方案
- 全局奖励预测。 训练一个模型基于当前场况预测整个半庄的奖励。 同时设计了look-ahead特征用于编码不同役种做成的可能性和期望收益，来帮助agent做出判断。
- 先知指导。 引入一个先知模型，这个模型是信息完全的，也就是可以看到牌山和所有家的手牌，那么模型训练从先知玩家开始，逐步丢掉实际游戏中不可见的信息来逼近正常的玩家。 在先知玩家指导下训练远快于从一开始就只利用正常玩家可见的信息进行训练。
- 参数化蒙特卡洛策略适应(parametric Monte-Carlo policy adaptation, pMCPA)。 利用游戏中可见的新信息将一个offline训练好的策略逐渐调整到适合当前游戏。
2 苏菲概述
2.1 苏菲的决策流程
苏菲包含五个模型，分别负责决策切牌、立直、吃、碰和杠。 苏菲使用一条简单的规则来决定是否见逃：如果是四确和就见逃，否则能和一定和。 决策树方面，首先分两种情况：自家摸牌和他家切牌。 在自家摸牌时，杠模型首先判断是否要进行暗杠或者加杠。 如果杠了，则分为两种情况，暗杠之后重新进入自家摸牌阶段进行决策，加杠的话如果没有他家抢杠则重新进入自家摸牌阶段进行决策。 天凤是没有国士抢暗杠的规则的，不过我想即使有也不太需要考虑，概率太低了。 同时也没有考虑四杠散了的情况。 如果不杠，就由立直模型进行决策是否要立直。 这里是很有趣的，我们都知道苏菲的留立很玄学。 不论立不立接下来都交由切牌模型决定切哪张牌。 这一段我的理解是切牌模型显然是知道哪些牌能切出去，因为如果要立直的话就不是哪张都可以切了。 在他家切牌时，首先当然是检查是否荣和，如果不和就由吃碰杠三个模型决策是否吃碰杠。 这三个模型是同步给出决策的，如果有多个操作被决定执行的话则会选择其中置信度最高的一个来执行。
那么苏菲的决策流程图如图所示。
2.2 特征和模型结构
基本的特征形式是34维向量，一个向量作为一个通道。 我们知道日麻的麻将牌是一到九万，一到九条，一到九饼，东西南北白发中，一共是三九二十七加七，34种。 特征向量里的每个维度正是对应一种牌。 而手牌用二值的34乘4的二维张量表示。 每种牌各四张，所以这个34乘4的张量里的每个元素实际上相当于一张牌，如果在手里就是1，不在手里就是0。 Look-ahead特征也就是说往后算几步，这是各种棋牌游戏的基本操作。 日麻里有34种雀头和89种面子，三七二十一种顺子，34种刻子，34种杠子，所以说显然是不可能遍历所有可能性。 苏菲在这里的简化策略有两点：首先做深度优先搜索找到可能能做出的役种；其次不管他家怎么打，只考虑自己的进张和切牌，我的理解是通俗来讲就是全攻。 在这两个简化的基础上，每次苏菲可以得到一百多个look-ahead特征，每个特征是一个34维向量。 这里作者举了一个例子，一个特征可以表示切掉某张牌后推进到一个12000点的两向听。 其他特征比如牌河宝牌也以34维向量为基本单位，分类特征通过多个通道表示，每个通道为全1或者全0，整数特征被分到多个桶里进行编码然后每个桶同样通过全1或者全0通道表示。 基本的模型是卷积神经网络。 那么模型结构如下图所示。
可以看到切牌和立直使用了838个特征而吃碰杠是958个，也就是他家打出的牌会占用120个通道。 但是具体这将近一千个通道都是编码什么我还是不知道，希望知道的朋友可以在评论区交流一下。 值得强调的一点是苏菲的模型里没有任何池化层，因为张量中的每个元素都是有明确语义的，这和图像是不同的。
3 学习算法
学习算法分三步：第一步是监督学习，通过天凤上的高端对局牌谱训练切牌、立直、吃、碰、杠五个模型；第二步是自我对局，基本的算法是policy gradient策略梯度，同时引入了针对日麻的全局奖励和先知指导，也就是解决方案的前两点；第三步就是天凤实战，在实战过程中会利用得到的信息继续在线优化策略，也就是解决方案的第三点。
3.1 熵正则化的分布式强化学习
使用了重要性采样来解决异步分布式训练导致的staleness of trajectories（属实不会翻译）。 这里面重要性采样等于是给advantage乘以一个系数，这个系数，也就重要性权重，是新策略given状态s采取行动a的条件概率除以旧策略的概率，损失函数是这个加权advantage的期望。 作者发现训练过程对策略的熵是非常敏感的，如果熵太小就会迅速收敛并且自我对局就不能改善模型了，如果熵太大训练就不稳定而且方差很大。 所以要给损失函数加上一项熵，其系数则是受前一段时间的平均熵和目标熵的差值调制。 如果前一段时间的平均熵比目标熵大则系数会减小，如果前一段时间的平均熵比目标熵小则系数会增大，相当于一个简单的负反馈。 分布式系统如图所示，有很多个自我对局，其中每个自我对局包括一个基于CPU的麻将模拟器，和相应的基于GPU的推理引擎。 策略更新和路径生成是解耦的，策略更新是由参数服务器负责的，模拟器会把对局进程推送到参数服务器的缓冲区，然后推理引擎每隔约1000个mini-batches抓取一下最新的策略。
3.2 全局奖励预测
作者首先指出仅使用一局的打点或者整个半庄的得分来作为奖励都是不行的。 这个很显然：只用一个半庄的得分作为奖励就没办法区分每一局的游戏情况；只用每一局的打点作为奖励就不能根据场况做出电报或者弃和之类的操作。
作者引入了一个RNN来预测全局奖励，两层GRU接两层全连接层，可以看到一个半庄中的各局构成了一个序列，作为RNN的输入。 序列中的每个元素包含的信息包括这一局的打点、累计点数、庄家位置、庄家连庄数和场上的立直棒数。 我的理解是庄家位置其实是表示现在距离完场还有多远，比如说轮到北起家坐庄那我们就知道现在是南四或者东四，当然实际上东四和南四的差别是非常大的，但是在作者的描述里好像没有做区分，不知道大家怎么理解这里。 那么连庄数和立直棒数量其实就是看一下场供有多少，场供比较多的情况下就会倾向于速攻抢棒嘛。 模型的输出就是最后整个半庄的得分，整个模型是在学习的第一阶段通过天凤牌谱来做监督学习，训好了以后用在第二第三阶段。
3.3 先知指导
麻将对AI来说很难本质原因就是可见信息太少隐藏信息太多。 在这种情况下，硬搞强化学习不是不行，但是会慢得离谱儿，所以要引入先知指导。 先知玩家和正常玩家相比多得到的信息就是他家的手牌和牌山，也就是可以看到所有信息。 在这种情况下先知玩家是很容易训练到一个很强的水平的，那么一个朴素的知识蒸馏的办法就是让正常玩家去拟合先知玩家的决策，然而实际情况是正常玩家基本拟合不动先知。 所以作者只能让先知逐渐降低他的灵视，把先知才能看到的他家手牌和牌山这两部分特征乘以一个二值dropout矩阵，其中元素是服从伯努利分布的，分布的参数在训练过程中逐渐由1下降到0。 下降到0以后就变成正常玩家了，这时候接着训练，但是学习率降到之前的十分之一，并且判断重要性权重的值，如果超过预设的阈值的话就拒绝这个样本。 如果不采取这两项措施的话训练就会拉胯。
3.4 参数化蒙特卡洛策略适应
麻将和棋类以及MOBA游戏很不同的一点是起手。 棋类和MOBA游戏每次起手是一样的，但是麻将的话起手随机性非常大，好的时候可以天地和，烂的时候只能w弃和。 所以策略是需要根据当前情况更新的。更新的办法是这样：
- 模拟。 开局的时候就随机猜K种不同的牌山和他家手牌然后根据offline模型打这K局牌。
- 适应。 用这K局牌的结果更新梯度，精调offline模型。
- 推断。 实际开打之后用这个精调过的模型。
作者表示K不用太大，尽管如此，这波操作也是人类不能做到的。 这个精调有丶meta-learning内味。 我老板就是搞元增强学习的所以对这个很亲切。
4 离线评估
4.1 监督学习
实验结果可以看到切牌准确率是76.7%，这个是一个34分类问题可以说还蛮准的，而其他模型都是做二分类，吃碰杠都可以做到90%以上的准确率，而立直稍微低一些，这也是大家觉得苏菲的留立很神秘的原因吧，因为训的时候拟合人类玩家拟合得不是很好，在人类看来就很神秘。
4.2 增强学习
这边列出来了五种AI：
- SL就是只做了第一阶段的监督学习
- SL-weak监督学习都没完全做完
- RL-basic只用熵正则化的分布式强化学习训了切牌模型，其他四个模型还是SL水平
- RL-1比RL-basic多了全局奖励预测
- RL-2比RL-1又多了先知指导
测试的时候用另外四种AI分别和三个SL-weak打一百万个半庄，在20块Tesla K80上打了两天。 算安定段位的时候随机取八十万个半庄来算，算一千次避免偶然性。 训的时候每个AI用了一百五十万个半庄，四块Titan XP做参数服务器四十块Tesla K80做自我对局，训了两天。
从结果来说即使只用监督学习也能升凤，加上强化学习可以到8段多。
这边作者举了个例子，南四大TOP，RL-basic还想攻而RL-1和RL-2防了。 这个其实蛮怪的，因为RL-basic也是八段水平，这个牌我觉得最多五段就知道该防了吧，下家明显染万子你切一张万子最后还听万子，和率又低铳率又高。 不过可能审稿人不打日麻，不会觉得这个怪。
4.3 在线策略更新评估
开局苏菲做如下操作：
- 数据生成。 采样十万个可能的对局，把自己复制三份自己和自己打十万局。
- 策略适应。 根据自己和自己打的十万局来精调策略。
- 测试适应后的策略。 精调后再打一万局测试一下。
作者直言这个很费时间所以他们也只评估了几百次，结果是精调后对精调前的胜率是66%。 作者举了一个例子就是精调后AI学会了做风险更大的牌跳满避四，让我想起了CRT第四轮Nelly的经典见逃三逆一。
5 在线评估
很不幸，我们都知道角田不让苏菲打凤桌。 尽管如此苏菲还是打到了十段，5760战安定8.74段（可见是波上十段的）。 然后作者和其他两个AI对比，不用说也知道是被苏菲吊打，还和一些十段人类玩家做了对比，但是因为一般人类十段都在凤桌所以这个对比没什么用。 苏菲的铳率和吃四率都蛮低的，铳率10.06%吃四率18.7%，总的来说就是防守很强。
6 结论和讨论
作者总结了几点：
- 首先我们其实应该把运气的成分考虑进去，比如说好调吃一比恶调吃一简单，但最后得到的分数一样，这不够周全。
- 其次我们可以同步训练先知玩家和正常玩家然后做知识蒸馏，作者进行了尝试，效果不错。
- 最后就是现在苏菲的精调只在开局进行一次，如果可以在局中不断精调效果可以更好，也不需要模拟那么多局。
最后的三个附录分别是日麻规则、天凤段位积分规则和安定段位算法，大家玩日麻的都懂，不必再赘述。