机器之心编辑部报道

超越99.9%人类玩家,微软专业十段麻将AI论文细节首次公布

在去年 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} 的时候,就没有合适的牌可以出了,只能把手里已经有的对子拆开,最终会影响和牌,导致更小的获胜概率。

理论微软AI微软亚研AI Suphx麻将
相关数据
微软亚洲研究院机构

微软亚洲研究院于1998年在北京成立,是微软公司在亚太地区设立的基础及应用研究机构,也是微软在美国本土以外规模最大的一个研究院。微软亚洲研究院从事自然用户界面、智能多媒体、大数据与知识挖掘、人工智能、云和边缘计算、计算机科学基础等领域的研究,致力于推动计算机科学前沿发展,着眼下一代革命性技术的创新,助力微软实现长远发展战略。通过与微软产品部门紧密合作,微软亚洲研究院将众多创新技术转移到了微软的核心产品中,如Office、Windows、Azure、Bing、Visual Studio、Xbox Kinect以及小冰、Cortana和Microsoft Translator等人工智能产品。

https://www.msra.cn/
博弈树技术

游戏树(game tree)是指组合博弈理论中用来表达一个赛局中各种后续可能性的树,一个完整的游戏树(complete game tree)会有一个起始节点,代表赛局中某一个情形,接着下一层的子节点是原来父节点赛局下一步的各种可能性,依照这规则扩展直到赛局结束。游戏树相同于扩展形式的博弈理论中的树。游戏树中形成的叶节点代表各种游戏结束的可能情形,例如井字游戏会有26,830个叶节点。

门控循环单元技术

门控循环单元(GRU)是循环神经网络(RNN)中的一种门控机制,与其他门控机制相似,其旨在解决标准RNN中的梯度消失/爆炸问题并同时保留序列的长期信息。GRU在许多诸如语音识别的序列任务上与LSTM同样出色,不过它的参数比LSTM少,仅包含一个重置门(reset gate)和一个更新门(update gate)。

监督学习技术

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

策略网络技术

在强化学习中,策略网络指一组相对稳定的关系,这些关系具有非等级和相互依赖的性质,将各个行为者(actor)联系起来。

正则化技术

当模型的复杂度增大时,训练误差会逐渐减小并趋向于0;而测试误差会先减小,达到最小值后又增大。当选择的模型复杂度过大时,过拟合现象就会发生。这样,在学习时就要防止过拟合。进行最优模型的选择,即选择复杂度适当的模型,以达到使测试误差最小的学习目的。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

暂无评论
暂无评论~