麻将AI难在哪?微软宣布公开麻将AI Suphx 的十段秘

 电动行业     |      2020-04-10     |     作者:万富电动科技有限公司
  4月9日消息,日前,微软亚洲研究院在 arXiv 平台上正式发表了关于麻将 AI 系统 Suphx 的论文,公布了 Suphx 背后的包括决策流程、模型架构、训练算法等核心技术细节。
 
  那么,麻将 AI 到底有哪些难点?Suphx 这一在游戏 AI 领域具有跨越性的突破具体是如何实现的?近日,微软亚洲研究院 Suphx 研发团队在 arXiv 平台上正式发表论文,公布了 Suphx 背后的核心技术。
 
  麻将 AI 面临的挑战
 
  麻将 AI 系统 Suphx 主要基于深度强化学习技术。尽管深度强化学习在一系列游戏 AI 中取得了巨大的成功,但想要将其直接应用在麻将 AI 上殊为不易,面临着若干挑战。
 
  挑战一:麻将的计分规则通常都非常复杂,在如天凤平台等竞技麻将中,计分规则更加复杂。
 
  首先,一轮麻将游戏通常有 8 局甚至更多,每一局结束后四位玩家都会有这一局的得分(可能为正,可能为负)。当一整轮游戏都结束后,四位玩家按照所有局的累计得分排名,计算这一轮游戏的点数奖励。在天凤平台上,排在一二名的玩家会得到一定数目的点数,排在第三位的玩家点数不变,排在第四位的玩家会被扣去一定数目的点数 。因此玩家的点数和段位都可能会起起落落,当点数增加到一定程度时段位上升,而点数扣到 0 时则会被降段。因此,为了提高段位,玩家需要尽量多的排在第一位或者第二位,尽量避免被排在第四位。
 
  有趣的是,由于一轮游戏的最终点数是由多局的累计得分决定,所以高手可能会策略性地输掉一些局,也就是说,某一局的输赢并不能直接代表玩家打的好不好,所以不能直接使用每局的得分来作为强化学习的奖励反馈信号。微软亚洲研究院的研究员们找到了一种其他的方法,会在后文中解释。
 
  其次,天凤平台上每一局游戏的计分规则都需要根据赢家手里的牌型来累计计算得分,牌型有非常多的可能,例如清一色、混一色、门清等等,不同牌型的得分会相差很大。这样的计分规则比象棋、围棋等游戏要复杂得多。麻将高手需要谨慎选择牌型,以在胡牌的概率和胡牌的得分上进行平衡,从而取得第一、二位或者摆脱第四位。
 
  挑战二:从博弈论的角度来看,麻将是多人非完美信息博弈。麻将一共有 136 张牌,每一位玩家只能看到很少的牌,包括自己的 13 张手牌和所有人打出来的牌,更多的牌是看不到,包括另外三位玩家的手牌以及墙牌。面对如此多的隐藏未知信息,麻将玩家很难仅根据自己的手牌做出一个很好的决策。
 
  挑战三:麻将除了计分规则复杂之外,打法也比较复杂,需要考虑多种决策类型,例如,除了正常的摸牌、打牌之外,还要经常决定是否吃牌、碰牌、杠牌、立直以及是否胡牌。任意一位玩家的吃碰杠以及胡牌都会改变摸牌的顺序,因此研究员们很难为麻将构建一棵规则的博弈树(game tree)。即使去构建一棵博弈树,那么这棵博弈树也会非常庞大,并且有不计其数的分支,导致以前一些很好的方法,如蒙特卡洛树搜索(MCTS)、蒙特卡洛反事实遗憾最小化(MCCFR)算法等都无法直接被应用。
 
  Suphx的决策流程及模型架构
 
  Suphx 的打牌策略包含 5 个需要训练的模型,以应对麻将复杂的决策类型——丢牌模型、立直模型、吃牌模型、碰牌模型以及杠牌模型,5 个模型都基于深度残差卷积神经网络。另外 Suphx 还有一个基于规则的赢牌模型决定在可以赢牌的时候要不要赢牌。
 
  这些模型的输入包含了两大类信息:
 
  1. 当前可观测的信息,例如玩家自己的手牌、公开牌(包括丢出来的牌、碰的牌、明杠的牌),以及每个玩家的累计得分、座位、段位等等。
 
  2. 对将来进行预测的信息,比如打某张牌还需要拿几张牌才能胡牌、能够赢多少分、胡牌概率有多大,等等。
 
  Suphx训练算法
 
  Suphx 训练过程分为三个主要步骤:首先使用来自天凤平台的高手打牌记录,通过监督学习来训练这 5 个模型,然后使用自我博弈强化学习以及由微软亚洲研究院 Suphx 研发团队设计的两个技术解决麻将本身的独特性所带来的挑战,最后在实战时采用在线策略自适应算法来进一步提高 Suphx 的能力。
 
  分布式强化学习
 
  Suphx 的整个训练过程十分复杂,需要多 GPU 和多 CPU 协同,因此 Suphx 研发团队采用了分布式架构(图 2 所示)。架构包括一个参数服务器以及多个自我博弈节点,每个节点里包含了多个麻将的模拟器以及多个推理引擎来进行多个策略之间的博弈(即打麻将)。每个自我博弈节点定期将打牌的记录发送给参数服务器,参数服务器会利用这些打牌记录来训练提高当前策略。每过一段时间,自我博弈节点就会从参数服务器拿回最新的策略,用来进行下一阶段的自我博弈。
 
  全局奖励预测
 
  麻将的计分规则很复杂——玩家每局有得分,一轮游戏根据多局累计分数的排名计算点数。如何让麻将 AI 知道自己打得好不好呢?
 
  无论是每局得分还是一轮游戏的最终点数,都不适合用来做强化学习训练的反馈信号。以最终奖励点数作为反馈信号不能区分打得好的局和打得差的局,因此研究员们需要对每局都单独提供强化学习的训练信号。但单独计算每局分数也未必能反映出一局打的好坏,因为顶级玩家会策略性输牌,比如,在一轮游戏的最后一两局中,累计得分排位第一的选手在累计分数领先较大的情况下,会有意识地让排位第三或第四的选手赢下这一局,不让排第二位的玩家赢,这样就可以稳稳地保住总排位第一。也就是说,某一局得分为负不一定意味着策略不好。
 
  因此,为了给强化学习训练提供有效的信号,需要将最终的游戏奖励适当地归因到每一轮的游戏中。Suphx 研发团队引入了一个全局奖励预测器,它可以基于本局的信息和之前的所有局信息预测出最终的游戏奖励。在 Suphx 中,奖励预测器是一个递归神经网络 (GRU),训练数据来自于高手玩家在天凤平台的历史记录。预测器训练好后,对于自我博弈生成的游戏,Suphx 研发团队用当前局预测的最终奖励和上一局预测的最终奖励之间的差值作为该局强化学习训练的反馈信号。
 
  先知教练
 
  麻将中存在着丰富的隐藏信息,如其他玩家的手牌、墙牌等,如果不能获得这些隐藏信息,那么就很难确保某个动作(例如丢三万)的好坏,这也是麻将很难的一个根本原因。在这种情况下,虽然 Suphx 可以通过强化学习来提高策略,但学习速度会非常慢。
 
  为了加快强化学习训练的速度,Suphx 研发团队引入了一个“先知”,它可以看到所有的信息,包括(1) 玩家自己的私有手牌,(2) 所有玩家的公开牌,(3) 其他公共信息, (4) 其他三个玩家的私有手牌,(5) 墙牌。只有(1)(2) 和(3) 是正常的玩家可以获得的,而(4) 和(5) 是只有“先知”才能获得的额外的"完美"信息。
 
  有了这些“不公平”的完美信息,“先知”在经过强化学习训练后,很容易成为麻将超级高手,安定段位也很容易就可以超过 20 段。如何利用“先知”来引导和加速 AI 的训练呢?实验表明,简单的知识萃取(knowledge distillation)或者模仿学习(imitation learning)并不能很好地把“先知”的“超能力”转移到 AI 系统上——对于一个只能获取有限信息的正常 AI 来说,它很难模仿一个训练有素的“先知”的行为,因为“先知”的能力太强,普通 AI 无法理解。比如,“先知”看到了其他玩家的手牌,知道每个玩家胡什么牌,所以它可以打出绝对安全的牌,避免点炮,然而正常的 AI 并没有这些信息,它可能完全不能理解为什么“先知”会打这张牌,所以也不能学到这种行为。 因此,研究人员需要一个更聪明的方法,用“先知”来引导正常 AI 的训练。
 
  在 Suphx 中,Suphx 研发团队首先使用包括完美信息在内的所有特征来对“先知”进行强化学习训练,在这一步中控制“先知”的学习进度,不能让其过于强大。然后,通过对完美特征增加 mask 逐渐使“先知”最终过渡到正常 AI。接着,继续训练正常 AI 并进行一定数量的迭代,采用衰减学习率和拒绝采样的技巧来调整训练过程,让 AI 的技术不断精进。
 
  参数化的蒙特卡洛策略自适应
 
  对一个麻将高手来说,初始手牌不同时,打牌策略也会有很大的不同。例如,如果初始手牌好,他会积极进攻,以获得更多的得分;如果初始手牌不好,他会倾向防守,放弃胡牌,以减少损失。这与此前的围棋 AI 和星际争霸等游戏 AI 有很大的不同。所以,如果能够在对战过程中对线下训练的策略进行调整,那么就可以得到更强的麻将 AI。
 
  蒙特卡洛树搜索(MCTS)是围棋等游戏 AI 中一种成熟的技术,以提高对战时的胜率。然而遗憾的是,如前所述,麻将的摸牌、打牌顺序并不固定,很难建立一个规则的博弈树。因此,MCTS 不能直接应用于麻将 AI。在 Suphx 中,Suphx 研发团队设计了一种新的方法,命名为参数蒙特卡洛策略自适应(pMCPA)。
 
  当初始的手牌发到麻将 AI 手中时,通过模拟来调整离线训练好的策略,使其更适应这个给定的初始手牌。微软亚洲研究院的实验表明,相对麻将隐藏信息集的平均大小 10 的 48+ 次方倍而言,模拟的次数不需要很大,pMCPA 也并不需要为这一局手牌收集所有可能后续状态的统计数据。由于 pMCPA 是一种参数化的方法,所以微调更新后的策略可以帮助研究团队将从有限的模拟中获得的知识推广泛化到未见过的状态。
 
  天凤平台在线实战
 
  在经历这样的训练后,Suphx 就可以“出道”了。Suphx 已在天凤平台特上房和其他玩家对战了 5000 多场,达到了该房间目前的最高段位 10 段,其安定段位达到了 8.7 段(如图 4 所示),超过了平台上另外两个知名 AI 以及顶级人类选手的平均水平。
 
  在实战中 Suphx 非常擅长防守,它的 4 位率和点炮率(deal-in rate)都尤其低(如图5)。此外,Suphx“牌风”比较鲜明,也另辟蹊径地创造了许多新的策略和打法,例如它特别擅长保留安全牌,倾向于胡混一色等等。图 6 展示了 Suphx 在天凤平台实战时保留安全牌的一个例子。当前时刻 Suphx(南家)需要丢牌,人类玩家在这时通常会丢北风,但是 Suphx 丢掉一张 7 条,这在人类玩家看起来会觉得很不寻常,因为 7 条是一张好牌,丢掉 7 条会使得胡牌的进度变慢。Suphx 之所以丢掉 7 条而留住北风,是因为北风是一张安全牌,这样在未来某一时刻,如果有人突然立直要胡牌了,Suphx 可以打出北风而不点炮,这样后面还有机会胡牌;如果它在前面已经把北风丢掉,那这个时候为了打出一张安全牌就不得不拆掉手里的好牌,从而大大降低了胡牌的可能。
 
  许多观看 Suphx 比赛的玩家表示在观战过程中受到了启发,甚至有麻将爱好者将 Suphx 称作“麻将教科书”、“Suphx 老师”,通过学习 Suphx 的打法来提升和丰富自己的麻将技巧。
 
  “我已经看了 300 多场 Suphx 的比赛,我甚至不再观看人类玩家的比赛了。我从 Suphx 身上学到了很多新技术,它们对于我的三人麻将打法有着非常大的启发,”麻将选手太くないお在社交媒体上说,他是第一位在四人麻将和三人麻将中均取得天凤位的顶级玩家。
 
  据介绍,Suphx 在天凤平台上取得的成绩只是一个开始,未来,微软亚洲研究院将为 Suphx 引入更多新技术,继续推动麻将 AI 和不完美信息游戏研究的前沿。