本文来自微信公众号:机器之心(ID:almosthuman2014),作者:机器之心,题图来自IC photo

在去年 8 月底的世界人工智能大会上,时任微软全球执行副总裁的沈向洋正式对外宣布了微软亚洲研究院研发的麻将 AI“Suphx ”。近日,关于 Suphx 的所有技术细节已经正式公布。

继围棋、德州扑克、Dota、星际争霸之后,微软亚洲研究院的“Suphx”创造了 AI 在游戏领域的另一跨越性突破——麻将。

一直以来,麻将都因其复杂的出牌、得分规则和丰富的隐含信息,被视为 AI 研究中极具挑战性的领域。微软亚洲研究院副院长刘铁岩曾表示:“可以说 Dota 这类游戏更‘游戏’,而麻将这类棋牌游戏更‘AI’。

Suphx 代表着 AI 系统在麻将领域取得的最好成绩,它也是首个在国际知名专业麻将平台“天凤”上荣升十段的 AI 系统,其实力超越了该平台与之对战过的 99.9% 的人类选手

不久前,微软麻将 AI 研究团队在 arXiv 上首次公开发布了 Suphx 的论文,而 Suphx 背后的更多技术细节也随之公开。

论文链接:https://arxiv.org/abs/2003.13590

方法概述

在论文中,研究者创建了适用于 4 玩家日本麻将的 AI 系统 Suphx(Super Phoenix 的简称,意为超级凤凰),它采用深度卷积神经网络作为模型。首先,根据人类职业玩家的日志,他们通过监督学习对网络进行训练;然后以网络为策略,通过 self-play 强化学习(RL)实现网络增强。具体而言,研究者使用流行的策略梯度算法来进行 self-play 强化学习,并提出以全局奖励预测(global reward prediction)、Oracle guiding 和 pMCPA 三种技术来解决已知的一些挑战:

  • 全局奖励预测用来训练一个预测器,进而根据当前和先前回合的信息来预测游戏的最终奖励。该预测器提供有效的学习信号,从而可以执行策略网络的训练。此外,研究者还设计了预读(look-ahead)特征,以便对不同必胜手牌(winning hand)的可能性以及回合内的获胜分数进行编码,从而支持 RL 智能体的决策;

  • Oracle guiding 引入了一个 oracle 智能体,它能够查看包括其他玩家私有牌(private title)和 wall title 在内的完美信息。得益于完美的信息访问,该 oracle 智能体成为超级强大的麻将 AI。在 RL 训练过程中,研究者逐渐从 oracle 智能体中删除完美信息,最后将其转换为仅将可观察信息作为输入的常规智能体。在 oracle 智能体的帮助下,与仅利用可观察信息的标准 RL 训练相比,常规智能体的提升速度要快得多;

  • 由于麻将的复杂游戏规则导致了不规则的博弈树,并且限制了蒙特卡洛树搜索(Monte-Carlo tree search)方法的应用,所以研究者提出以蒙特卡洛策略调整(Monte-Carlo Policy Adaptation,pMCPA)来提升智能体的运行时性能。当游戏继续进行并且可观察更多信息时,pMCPA 能够逐渐地修正和调整离线训练策略,从而适应在线比赛阶段的特定回合。

最后,研究者在最流行且拥有 35 万多个活跃玩家的麻将平台天凤上对提出的 Suphx 进行了评估,结果显示,Suphx 达到了 10 段水平,其稳定段位(stable rank)超越了大多数人类玩家。

Suphx 算法

Suphx 的学习主要包含三个步骤。首先通过监督学习,使用从天凤平台收集的顶级玩家对弈数据(状态,动作),训练 Suphx 的五个模型(discard、Riichi、Chow、Pong 和 Kong)。然后通过 self-play 强化学习来改进监督模型,并将这些模型作为策略。研究者采用策略梯度算法,并引入了全局奖励预测和 oracle guiding 来应对麻将中的一些独特挑战。接下来,在线上游戏过程中,研究者采用运行时策略调整来利用当前轮次的新观察结果,以便得到更好的效果。

下图展示了几个模型的结构:

图 4:discard 模型的结构。

图 5:Riichi、Chow、Pong 和 Kong 模型的结构。

结合熵正则化的分布式强化学习

Suphx 的训练是基于分布式强化学习,具体来说是采用了策略梯度方法,并利用重要性采样来处理由于异步分布式训练而导致的轨迹(trajectory)陈旧:

在上式中,θ’是用于训练旧策略的轨迹的参数,θ是更新的最新策略,而 A^{π_θ}(s, a) 则表示 a 相对于策略π_θ操作中的优势。

研究者发现 RL 训练对策略的熵很敏感。如果熵太小,强化学习训练的结果则会迅速收敛,自我迭代不能显著改善其策略;如果熵太大,则 RL 训练会变得不稳定,并且学习的策略也会变得有很大的差异。

其中 H(π_θ) 是策略π_θ的熵,而α> 0 则是权衡系数。

Suphx 使用的分布式 RL 系统如下图 6 所示。该系统由多个自我迭代组成,每个包含一组基于 CPU 的麻将模拟器以及一组基于 GPU 的推理引擎,以生成轨迹。策略π_θ的更新与轨迹的生成是分离的:参数服务器基于缓冲区来使用多个 GPU 制定更新策略。

图6:Suphx 中的分布式 RL 系统。

全局奖励预测机制

为了使得为 RL 训练提供有效的信号,需要适当地将最终游戏奖励(全局奖励)归因至每一回合游戏中去。为此研究者引入了全局奖励预测Φ,它能够根据游戏的当前回合和所有先前回合的信息来预测最终的游戏奖励。在 Suphx 中,奖励预测因子Φ是循环神经网络。具体一点,是两层门控循环单元(gated recurrant unit,GRU),以及两层完全连接的层,如下图 7 所示:

奖励预测器:GRU 网络。

奖励预测变量Φ的训练数据是来自“天凤麻将”里的顶级玩家的日志,并且通过最小化均方误差来训练Φ:

当Φ训练得差不多时,对于具有 K 轮的自我迭代,将“Φ(x^k)-Φ(x^{k-1})”作为 RL 训练的第 k 轮奖励。

Oracle Guiding

在 Suphx 中,要做的首先是使用所有特征(包括完善特征)进而通过强化学习来训练 oracle agent。然后,再逐渐减少完美特征,以便 oracle agent 最终能将转换为 normal agent:

其中,x_n(s) 表示状态 s 的一般完美特征,x_o(s) 表示状态 s 的其他理想特征,而δ_t 是第 t 次迭代时的丢失矩阵,其原理是伯努利变量,其中 P(δt(i, j) = 1)=γ_t。

参数化蒙特卡洛策略调整

研究者提出一种称为参数化蒙特卡洛策略调整的全新方法。在每一局的开始阶段,使用如下方法调整离线训练的策略以适应其初始私有牌:

  1. 模拟。随机采样另外三个对手的私有牌和排除了自身私有牌后的所有牌,使用离线预训练的策略进行 rollout,并完成整个环境轨迹的探索。于是,总共会产生 K 条轨迹;

  2. 调整。使用 rollout 产生的轨迹进行梯度更新,以此微调离线策略;

  3. 推断。在本局中使用微调后的策略与其他玩家进行对弈。

使用 h 表示本轮中智能体的私有手牌,θ_o 表示离线训练策略的参数,θ_a 为针对本轮调整后新策略的参数,于是:

其中,T (h) 为在 h 手牌下的轨迹集合,p(τ;θ) 表示策略在以θ为参数时产生轨迹τ的概率。

离线评估

监督学习

在 Suphx 中,研究者通过监督学习分别训练了五个模型。每个训练样本都是从职业玩家那里收集的“状态-动作”对,状态作为输入,动作作为监督学习的标签。

训练数据的大小以及测试准确性如下图:

表 3: 监督学习结果。

强化学习

为了演示 Suphx 中每个 RL 组件的价值,研究者训练了几个麻将智能体:

  • SL:监督学习智能体,如上节所述,该智能体(所有五个模型)都受到监督训练。

  • SL-weak:训练不足的 SL 智能体版本,在评估其他智能体时可作为对比模型。

  • RL-basic:强化学习智能体的基础版本。在 RL-basic 中,discard 模型用 SL discard 模型进行初始化,然后通过策略梯度方法进行迭代,以回合得分作为奖励以及熵正则化用。Riichi、Chow、Pong 和 Kong 的模型与 SL 智能体的模型相同。

  • RL-1:这个 RL 智能体通过全局奖励预测增强 RL-basic。奖励预测器使用了来自天凤的游戏日志,通过监督学习进行训练。

  • RL-2:该智能体通过 oracle guiding 进一步增强 RL-1。在 RL-1 和 RL-2 中,仅用 RL 训练了 discard 模型,而其他四个模型则与 SL 智能体相同。

下图 8 展示了这些智能体的 1000 多个样本中稳定段位的四分位间距。

图 8:一百多万场比赛的稳定段位数据。

通过全局奖励预测器将游戏奖励分配到每个回合,训练有素的智能体能够更好地将最终游戏奖励最大化,而不只是每一回合的得分。图 9 中的智能体(朝南向的玩家)在最后一局中遥遥领先,并且抓得一手好牌。

在线评估

为了评估 Suphx 的真实性能,研究者让 Suphx 在最流行的日本麻将在线平台“天凤”上实战,“天凤”有两种房间,一种是专家室(expert room),一种是凤凰室(phoenix room)。专家室仅对 AI 和 4 段以上的人类玩家开放,凤凰室仅对 7 段以上的人类玩家开放。基于此,Suphx 只能选择专家室。

下表 4 是 Suphx 与 AI/人类玩家的对战结果比较,在稳定性上,Suphx 比 Bakuuchi 和 NAGA 都要高出大概两个段位,后两者是此前最强大的两个麻将 AI 系统。

表 4:Suphx 与其他 AI/人类玩家的对比。

下图 11 展示了天凤上活跃用户的段位记录,Suphx 超越了 99.9% 的人类玩家。

图 11:天凤平台上的人类玩家分数记录情况。每个条形图代表的是该平台上每一级别以上的玩家数量。

图 13:Suphx 保留了一张安全牌来平衡攻与守。一般来说,人类玩家可能会把红框里的那张牌打出去,但 Suphx 却留它在手,打了蓝框里的那张牌。这样可能会和牌慢一些,但可以为之后的出牌提供更大的灵活性。

假如另一玩家打出了意料之外的 s_{t+k},那么 Suphx 可以将安全牌打出去,但不影响和牌;如果 Suphx 先前就打了红框那张牌,那么等到 s_{t+k} 的时候,就没有合适的牌可以出了,只能把手里已经有的对子拆开,最终会影响和牌,导致更小的获胜概率。

本文来自微信公众号:机器之心(ID:almosthuman2014),作者:机器之心