人人都能看懂的麻将 AI -- Suphx

吹就一个字

由微软亚洲研究院开发的麻将 AI 系统 Suphx 成为首个在国际知名专业麻将平台“天凤”上荣升十段的 AI 系统，这是目前 AI 系统在麻将领域取得的最好成绩，其实力超越该平台公开房间顶级人类选手的平均水平。下面一起来看看 Suphx 是如何把麻将打好的。
1 任务介绍

在玩家自己的摸牌回合，可以执行丢牌、立值、杠。
在其他玩家打牌的回合，玩家可以执行吃、碰、杠。
Suphx 中是否胡牌使用了固定的规则，而下列操作通过网络进行学习：

操作	具体内容
丢牌	决定手牌丢哪张
立值	只能胡固定的牌，加1番
吃	决定用哪些手牌吃
碰	决定是否碰
杠	决定是否杠

2 任务挑战

麻将任务的挑战主要体现在如下三个方面：
2.1 复杂的积分规则

第一是多局得分策略，一次麻将游戏（Game）分为多局（Round），最终的排名取决于多局得分之和。因此每局得分需要有所策略，例如最后一局时，第一名担心被第二名超过，就会战略性输给第三名、第四名，来保住自己的第一名位置。
第二是单局的得分平衡，每一局游戏的得分取决于胡牌的结果，例如清一色得分较多，但是胡牌概率小，小屁胡得分少，但是胡牌概率大。这需要玩家来平衡胡牌的大小和胡牌的概率。
2.2 隐含信息多

围棋和象棋是完全博弈游戏，每个玩家可以看到游戏的所有信息，而麻将是不完全信息博弈。除了玩家自己的手牌和已打的手牌可见外，对手的手牌、墙面玩家都是无法看到的。将所有不可见的牌型进行排列组合，有 10 的 48 次方之复杂。因此玩家选择打哪张牌是非常困难的，因为这个和对手手牌及墙面有很大相关。
另外一局会有几百回合操作，例如出牌、碰牌、吃牌等等，但是一局只有一个奖励，导致将每一个操作与最终的奖励结合起来是非常困难的。
2.3 复杂的出牌规则

麻将中有吃牌、碰牌、杠牌、打牌等操作，每个操作发出都有可能打乱摸牌顺序。因此很难像围棋那样遍历出所有的未来操作组合，形成游戏树。
3 Suphx 介绍

Suphx 为了解决上面三个问题，提出了三个方法：

• 复杂的积分规则：通过 Global Reward Prediction 和 look-ahead features 学习单局的得分和多局的得分策略
  
• 隐含信息多：Oracle Guiding 提供作弊信息，来保证玩家学习从简到难
  
• 复杂的出牌规则：Policy Adaption 根据手牌牌面学习自适应策略
  

3.1 输入格式

Suphx 选择使用图片类似的数据格式进行表征，图片是 CWH 三维度信息，分别代表通道数、宽度、高度。麻将的格式整合为 Dx34x1，分别代表通道数量（每一个通道是一个特征）、牌面种类、每个特征用一行表示。
手工特征包括如下几种：

• 牌型特征：每一种牌型特征用 34x4 编码，34 代表麻将有 34 类手牌，4 代表每种手牌最多有 4 张
  
  
  
  • 自己的手牌
    
  • 其他玩家的可见牌
    
  • 宝牌：3个通道来表示三种赤宝牌
    
  • 所有打出的牌
    
  
  
• 类别特征：34x1 维向量中用 0 或者 1 来表征
  
  
  
  • 当前轮数
    
  • 庄家是谁
    
  • 庄家连续数量
    
  • 听牌数量
    
  
  
• 整数特征：34 x 1，如果特征最大值大于 34，则进行 bucket 的离散分散
  
  
  
  • 各个玩家的累计分数
    
  • 剩余可摸牌数
    
  
  
• 打牌历史序列
  
• look-ahead 特征：
  
  
  
  • 进行深搜计算打出某张牌在摸n张牌后能获得某分数的概率
    
  • 简化：忽略对手的手牌和行为，只考虑玩家自己摸牌和丢牌的行为
    
  
  

3.2 模型第一步：学习基础操作 -- 监督学习

上述的输入特征整合为类似图像的输入，对于需要学习的吃、碰、杠、立值、丢牌操作，每个操作对应一个模型，Suphx 通过处理图像的两种神经网络进行学习：

• 吃、碰、杠的输出是2维，代表操作或者不操作。
  
• 丢牌或者胡牌输出是34维，代表丢哪张牌或者胡固定的哪张牌。
  

目的是通过收集人类顶级玩家数据进行训练，学习到基础的打牌策略，例如什么时候可以吃、碰、杠，应该丢什么牌等。两种神经网络的结构基本一致，以 50 层的 ResNet 作为核心组件，只是输入的特征维度和输出的特征维度有些区别，网络结构如下所示：


3.3 模型第二步：提升对战策略 -- RL self-play

监督学习只能学习到部分场景，在数据中没有出现过的场景和长序列决策上的缺乏泛化性。因此需要通过实际对战的方式来进行提升。
Suphx 通过 RL 的方法来更新弃牌模型，为什么只更新弃牌模型呢？官方回答是因为更新别的模型也能提高性能，但是提高得没有弃牌模型那么多，所以为了跑更多iteration就只更新弃牌模型了。
Suphx 的 RL 使用了纳入重要性采样的 Policy Gradient 算法。


看不懂？那下面一点点带你看懂。
3.3.1 什么是 Policy Gradient 算法？

我们使用下面的一张图来利用监督学习理解强化学习，首先我们将数据中的输入和输出分别称为 s 和 a。

• 监督学习是最大化网络看到 s 时输出 a 的概率，例如看到猫的图片，输出识别结果为猫。
  
• 强化学习是根据奖励来调整看到 s 时输出 a 的概率，例如看到老虎跑过去，如果被吃了（Reward 低）就减少这样做的概率，如果玩得很开心（Reward 高）就增大这样做的概率。
  

为什么会有这样的区别呢？这是因为数据的差别，因为监督学习的数据都是好数据，直接拟合就行；而强化学习的数据则有好有坏，需要增强好行为，打压坏行为。


3.3.2 为什么要用 Advantage 函数，不直接用 Reward？



细心的同学一定发现了 Suphx 中使用的不是 R 作为权重，而是使用的 A，这个 A 代表 Advantage，为什么呢？
如果直接用 Reward 作为优化的权重，则会存在一些问题，例如Reward 有可能全是正分或者负分。

• 正分情况：比如乒乓球 A 得 3 分，B 得 5 分，更新完对 action 归一化以后，会导致所有采样到的 (s,a) pair 概率都增加
  
• 负分情况：智能体为了避免继续失分，就会直接自杀
  

如何避免这样的问题发生呢，我们可以创造一个基本线：将 Reward 减去一个平均值，得到 Advantage，作为评价行为好坏的权重。
3.3.3 为什么要加入 entropy？



Suphx 研究团队发现 RL 的训练对网络的 entropy 是十分敏感的，entropy 是熵值，entropy 越大，输出的行为越分散，entropy 越小，输出的行为越集中。

• 当行为集中时，RL 算法收敛很快，自己和自己对战几乎没啥提升
  
• 当行为很分散时，RL 算法十分不稳定，学出来的 policy 会有很大的方差
  

因此 Suphx 增加了一个 entropy 项，entropy 权重 a 是动态更新的，当 entropy 太大就给小一点的 a，当 a 太小就给大一点的 a。
3.3.4 为什么要加入重要性采样？

Suphix 采用的 RL 系统分为两部分

• 自我对抗的任务 Self-play workers
  
  
  
  • 麻将仿真器：由 CPU 进行模拟
    
  • 推理引擎：由 GPU 来推理
    
  
  
• 参数服务器 Parameter server
  
  
  
  • 经验集合：将 Self-play workers 中的对局情况、得分情况数据进行缓存
    
  • 最新的 policy：每 1000 个 mini-batches 就把 policy 更新到推理引擎中
    
  
  

这样的结构会导致一个问题，参数服务器中是用过去的交互数据，训练当前的模型，这样可以重复利用过去的数据，更好的学习经验。
假设经验满足 q 分布，现在我们要更新 p 分布的期望值，那么可以通过重要性采样来进行分布差距的修复。如下面的式子：

• 第一行公式：理想情况下我们希望从 p 分布采样更新 p 分布的期望值
  
• 红色字：但是由于效率低等问题，我们需要从 q 分布中采样
  
• 第二行公式：通过上下同乘一个 q 分布，可以将采样的 x 替换成 q 分布中的采样
  

因此回到 Suphx，θ 代表当前的 policy，θ' 代表交互数据来源的 policy，我们通过将目标函数分母增加一个 θ' policy 的网络函数，就可以的达到从 θ' 采样更新 θ 网络的目的了。


3.3.5 Suphx Policy 完整理解

现在我们再来看 Suphx 的这个式子一定不陌生了：


核心包括三点：

• 首先使用 Policy Gradient 算法来奖励好的行为，抑制坏的行为
  
• 第二使用重要性采样来保证可以用过去的数据，更新当前的网络
  
• 第三使用 entropy 来保证网络输出的行为分布不要太大也不要太小，保证网络训练的收敛速度和有效性
  

但是新的问题出现了，这个 Advantage 怎么获得呢？如果用每一局的得分会导致 policy 只会关注怎么提升当前局的赢面，而不会考虑对局之间的赢牌策略，这个时候 Suphx 的 Global Reward Prediction 就上场啦。
3.3.6 如何找到合适的 Reward ? Global Reward Prediction

麻将游戏中的分数包括以下两个：

• Round Score：每一局的分数（整个游戏通常包括 8~12 局），有胡牌的大小或者放炮的大小决定分数。
  
• Game Score：整个游戏的分数，等于 Round Score 的总和
  

用 Round Score 和 Game Score 都没办法直接作为 RL 训练的 Reward：

• Round Score：并不是每一场游戏的 Round Score 都是越大越好，有时候为了保住第一名，需要战略性输给第三名第四名。
  
• Game Score：所有 Round 都共享一个 Game Score，如果用 Game Score 作为 Reward，则无法区分好的局和坏的局。
  

Suphx 使用神经网络来学习第 k 局的表现应该获得的 Reward，使用的方法为 Global Reward Prediction 来做监督学习，网络结构如上图所示，主要由两层 GRU 组成。网络输入输出如下：

• 输入：前 k 局的分数、庄家是谁、连庄几局、胡牌情况（Riichi bets）
  
• 输出：根据当前情况预测的整个游戏的分数 Game Score，phi_k
  
• Loss：每个游戏、每一局预测的游戏分数和实际的游戏分数越接近越好
  

当前第 k 局打得如何的评价为 phi_k - phi_(k-1)，为什么这个 Reward 是合适的呢？

• 如果这局游戏开始和结束估计的最终分数上升了，说明这一局打的好，给正向奖励
  
• 如果这局游戏开始和结束估计的最终分数下降了，说明这一句打的不好，给负的奖励
  

因此 Suphx 的 reward 设置为 phi_k - phi_(k-1) - baseline。这里的 baseline 为多局游戏 reward 的均值。
3.3.7 为什么不用 value function

大家知道 RL 的算法包括 Policy Based，Value Based 以及 Actor-Critic，Suphx 使用的是 Policy Based 的方法，而后两者相比而言都有一个 Value function，那么为什么 Suphx 不训练 Value Function 呢？这是因为麻将中训练 Value function 很难，比如就算听牌了，也不知道炮牌和胡牌哪个来得快。
3.4 游戏太难学不会？大神带你飞 -- Oracle Guiding

我们知道麻将的隐含信息非常之多，除了手上的 13 张牌和已经被打出来的牌，其他的牌我们一无所知，比如对手的牌和已经被丢掉的牌，这些牌会有非常多的排列组合，多达 10 的 48 次方之复杂。RL 一上来就学习这样的游戏学习起来十分困难，因此 Suphx 提出了一个帮练策略，先创造一个具有”先知“的 policy，学到大神的技能，再用大神的技能来辅助简单任务的学习。
简单来说就是将麻将的 RL 任务设置为由简到难，如何区分难易呢？就是根据隐藏信息的多少来区分。如果玩家能够知道对手和墙面上的牌，游戏就很简单，知道怎么打一定不会出错。而随着玩家知道的信息越少，麻将游戏就越难。


上面公式中，x_n 是正常的玩家可以看到的信息，x_o 是天眼信息（对手手牌、墙面手牌），镜面 6 的符号是天眼权重，当天眼权重高的时候，游戏简单，当天眼权重低的时候，游戏困难。通过不断降低天眼权重，来达到从简单到困难学习游戏的目的。
3.5 模型第三步：根据手牌调整策略 -- policy adaption

大家知道赢牌的策略和初始手牌有很大关系，比如摸起来就百分之八十是万字，那么打万字清一色的赢面是比较大的，就可以在权衡之后把其他花色的牌丢掉，因此 Suphx 提出了根据手牌的 finetune policy 策略。
每一局游戏开始时，根据手牌，模型会进行如下三步的学习：

• 仿真：随机分配三个对手的手牌、墙面的牌，使用当前的 policy 来交互获得轨迹数据
  
• 适配：使用 K 条数据来通过上面的 policy gradient 方法进行 finetune
  
• 推理：通过适配好的 policy 来完成当前局的麻将
  

θ_o 代表根据当前手牌收集到的轨迹数据，θ 代表不断学习的 policy，根据重要性采样的原理，利用当前手牌随机生成的轨迹更新 policy，将学习完最好的 policy 作为当前局的 policy θ_a 来对战。


天凤上的时间限制，自适应算法没有应用到天凤平台上的对局中。
3.6 模型总结



回顾整个模型，包括如下四个核心模块

• 输入表征：Suphx 有独特的输入表征格式，帮助后续任务学习
  
• Resnet 监督学习：学习回合内的基础打牌策略，学完这里就已经可以完成对局了，但是在没见过的场景泛化性不够
  
• RL 提升性能：学习高端玩法，包括如下三个高端部分
  
  
  • 通过 Policy Adaption 根据初始手牌 finetune 打牌策略
    
  • 通过 Oracle Guiding 从简单到困难来学习
    
  • 通过 Global Reward Predictor 来学习局与局之间的输赢策略
    
  
  

好啦，今天麻将 AI Suphx 就介绍到这里啦，有不明白的欢迎留言讨论~

油油娇娇淑芬

一直在看