智驾峰会
您正在使用IE低版浏览器,为了您的雷锋网账号安全和更好的产品体验,强烈建议使用更快更安全的浏览器
人工智能 正文
发私信给camel
发送

1

这次 AI 突破的是麻将!

本文作者:camel 2019-08-29 12:18 专题:2019世界人工智能大会
导语:Suphx 荣升天凤十段!

雷锋网AI科技评论按:围棋AlphaGo点燃的AI之火渐渐降温之际,微软今天上午发布了他们在麻将游戏中取得的重大突破:麻将AI “Suphx”在国际知名专业麻将平台“天凤”上荣升十段。

这次 AI 突破的是麻将!

“十段”是什么概念呢?天凤平台上,全球范围内现役十段的人类选手仅十几位。Suphx取得“十段”的成绩,大致可相当于围棋中AlphaGo挑战胜了李世石。

这是一个不凡的成绩。

从AI这门学科诞生之日起,游戏AI始终与 AI 研究进展相生相伴,跳棋、双陆棋、国际象棋和围棋,都曾先后推动了AI的发展。

这次 AI 突破的是麻将!

图:MarionTinsley 与 Chinook 对战(左);GarryKasparov 与 Deep Blue 对战(右)

这些棋类游戏有共同之处是,1)它们均有一个简单而清晰的规则,有清晰的胜负判定条件和行动准则;2)博弈双方能够查看所有游戏状态;3)在公众认知中,掌握和精通这些棋牌类游戏往往在一定程度上是人类智力的彰显。

相比以上这几种棋类游戏,麻将却是规则复杂、胜负判定繁琐、信息非完全公开的,且更重要的是在公众认知中麻将更多地有“运气”和“凭直觉”的成分。

因此麻将AI若能取得超越人类的水平,可以期待它将带来新的一波热潮。

  一、Suphx的晋级之路

“天凤”是日本(不要问为什么不是中国四川)的一个在线麻将竞技平台,创立于2006年。因其完善的竞技规则、专业的段位体系,很快便成为业界知名的高水平专业麻将平台,受到职业麻将界的广泛承认。

这次 AI 突破的是麻将!

图:天风平台logo,by tenhou

我们知道,麻将的输赢与围棋不一样,并不仅仅取决于玩家的实力,还取决于抓到的手牌等,如果一个人运气比较差,拿到一手烂牌,可能再强的实力也只能是输得不那么难看。所以,麻将不像围棋一样,不能单靠一轮对弈,而是要通过多轮(甚至上千轮)对弈才能看出一个雀士的实力。

天凤的评价制度,采用Rating制和段位制并行的制度。刚刚注册时等级从“新人”开始,点数(pt)会根据游戏的情况增减,并最终决定雀士的升段(升级)和降段(降级)。玩家的段位越高,在比赛中排位第四受到的点数惩罚也越多,点数扣除到一定程度会导致降段。按照这种规则,如果雀士的实力水平一定的话,自己的等级也会相对地稳定在某一个段位上。

根据段位,游戏者可以使用的桌也会发生变化。天凤平台为高水平麻将玩家提供两种竞技房间:“特上房”对四段以上所有玩家免费开放,允许AI参与游戏,目前所有玩家在此房间的最高段位是十段;“凤凰房”仅对七段以上的人类付费玩家开放,目前不允许AI参与游戏,在该房间能够达到的最高段位是十一段,称为“天凤位”。

自天凤平台在2006年推出以来,全球范围内达到四人麻将(四麻)天凤位的雀士也不过13人,曾经达到过十段的玩家约有180位,而现役十段的人类玩家仅有十几位。

微软亚洲研究院开发的麻将AI Suphx在今年3月份开始登录天凤平台,经过近三个多月、与人类玩家展开了5000余场四麻对局后,6月份Suphx成功晋级天凤十段,也是首个晋级十段的AI系统。

这次 AI 突破的是麻将!

图:天凤平台“天凤位”和“现役十段”名单

在5000余场对局中,Suphx的稳定段位超过了8.7。这样的稳定段位是一个极高的数字。

据统计,天凤平台的所有顶级人类玩家在取得十段后,在“特上房”共参加过近万场比赛,整体稳定段位为7.4。与所有取得过天凤十段的顶级人类玩家相比,Suphx在特上房的稳定水平要领先约1.3个段位。

这次 AI 突破的是麻将!

此前,天凤平台还活跃着另外两个麻将AI系统,由东京大学在2015年开发的“爆打”和 Dwango 公司于 2018 年开发的基于深度学习模型的“NAGA25”,二者的稳定段位均在6.5左右。

事实上,在晋级十段之前,Suphx很长一段时间稳定在九段,其独特的打牌风格在麻将领域刮起了不小的“AI风”,很多麻友都尝试从中学习新的打牌方式,并且在中国,很多麻友亲切地称她为“苏菲老师”、“苏菲姐姐”。


这次 AI 突破的是麻将!这次 AI 突破的是麻将!

图:bilibili网站Suphx牌局解析下用户留言

此外,麻将领域神一级存在、被天凤平台冠为“God of mahjong”的朝仓康心(天凤ID:ASAPIN)也曾表示:“我看了Suphx的比赛,我感觉它好像比我更强大!”

  二、麻将AI难在哪里?

为什么说麻将AI战胜人类,是游戏AI的又一次重大突破呢?因为麻将AI相比于棋类游戏(例如国际象棋、围棋等)更难。

这里需要解释的一个问题是,游戏的复杂度与游戏的难度并不完全等价,游戏难度除了与游戏本身的复杂度有关以外,还与战略等多种要素相关,也就是说,数学上更复杂的游戏,玩起来不一定更难。

一般来说,我们可以根据信息的暴露程度可以将游戏分为两大类:完美信息游戏(Perfect-Information Games)和非完美信息游戏(Imperfect-InformationGames)。如果所有的参与者,在游戏的任何阶段都可以访问所有关于游戏(包括对手)状态及其可能延续的信息,那么称这类游戏为完美信息游戏;否则称为非完美信息游戏。

围棋、象棋等棋类游戏,对局双方可以看到局面的所有信息,属于完美信息游戏;而扑克、桥牌、麻将等游戏,虽然每个参与者都能看到对手打过的牌,但并不知道对手的手牌和游戏的底牌,也就是说各个对局者所掌握的信息是不对称的,因此属于不完美信息游戏。

完美信息游戏和非完美信息游戏难度的衡量指标通常是有区别的。

对于完美信息游戏,通常游戏的复杂度就决定了难度,我们可以用状态空间复杂度(State-Space Complexity)和游戏树复杂度(Game-TreeComplexity)对其难度进行衡量:

这次 AI 突破的是麻将!

图:完美信息游戏的状态空间复杂度和游戏树复杂度

可以看出,对于传统的完美信息棋类游戏中,围棋不管从状态空间复杂度,还是游戏树复杂度上都远远领先其他棋类游戏。2017年,AlphaZero 利用MCTS 和深度强化学习,成功解决了包括围棋在内的多个完美信息游戏。我们也有理由相信,只要算力足够,对于更加复杂的棋类游戏,我们都能通过已有的方法得到解决。

而另一方面,对于非完美信息游戏,隐藏信息对于游戏的难度影响很大。例如麻将,参与者只能看到他手中的13张牌的信息,对于另外三家的手牌以及剩余的底牌则完全不知。由于这种信息的不完全、非对称性,对于参与者来说许多不同的游戏状态看起来是无法区分的。

显然,对于非完美信息游戏而言,合理的游戏策略应该建立在信息集而不是游戏状态之上。相应地,当我们衡量非完美信息游戏的难度的时候,也应该依据信息集的数目,而不是游戏状态空间的大小。信息集的数目通常小于状态空间的数目。

对于完美信息游戏,由于所有信息都是已知的,每个信息集只包含一个游戏状态,因此它的信息集数目与状态空间数目是相等的。

除了信息集的数目,还有一个重要的指标:信息集的平均大小,即在信息集中平均有多少不可区分的游戏状态。

按照这两个标准来衡量非完美信息游戏的难度:

这次 AI 突破的是麻将!

图:非完美信息游戏的信息集数目和信息集平均大小

2017年卡耐基梅隆大学和阿尔伯特大学相继发布了Libratus 和 DeepStack,在两人无限注德州扑克上成功击败了世界顶级人类玩家。

我们可以以信息集数目和信息集平均大小为准则,来对比像完美信息游戏和非完美信息游戏:

这次 AI 突破的是麻将!

图:围棋、德州扑克、桥牌和麻将的信息集数目和信息集平均大小对比

从图中可以看出,围棋和德州扑克的信息集平均大小远远小于桥牌和麻将。目前的AI在围棋和德州扑克上的成功很大程度依赖于搜索算法,因为搜索可以最大程度地发挥计算机的计算优势。但是因为巨大的信息集平均大小带来的环境不确定性,传统的搜索算法在桥牌和麻将面前很难发挥同样的功效。

这次 AI 突破的是麻将!

图:游戏 AI 发展历史

如果把过去的游戏AI的研究看做“一维延展”(信息集数目)的话,那么德州扑克则是向二维方向(信息集平均大小)的初始尝试。但整个二维平面还有更广阔的的空间需要探索,这需要我们发明全新的方法论,同时这也将成为游戏AI的一个主要研究方向。

三、技术详解

具体到麻将这个游戏。

一方面,136张麻将牌的排列组合可能性非常多,再加上打牌过程中4位玩家出牌的顺序并不是固定的(例如碰杠等),导致游戏树不仅不规则而且还是动态变化。这些特点使得麻将AI很难使用AlphaGo那样的蒙特卡洛树搜索算法。

其次是非完美信息问题。麻将中每个玩家除了手中的13张牌和已经打出的牌外,其他玩家手中的牌和剩余的底牌都是未知的(最多可以有超过120张未知的牌),由于隐藏信息过多导致游戏树的宽度非常大,树搜索算法基本不可行。

另外还需要注意的就是麻将本身的奖励机制,毕竟这才是评判胜负的标准。对于日本麻将而言,一轮游戏共包含8局,最后根据8局得分总和进行排名,来形成最终影响段位的点数奖惩。因此有时麻将高手会策略性输牌,以保证自己在最终结算时获得最大的点数奖励。这为构建高超的麻将AI策略带来了额外的挑战,AI需要审时度势,把握进攻与防守的时机。

微软亚洲研究院的几位研究员针对麻将的这些特点,将整个训练过程分为三个阶段。

首先是“初始化”阶段,本质上就是用专家数据(天凤平台提供的一些公开数据)做有监督学习,得到一个初始模型。

这次 AI 突破的是麻将!

图:先知教练,即利用隐藏信息指导AI模型训练方向。

随后在这个初始模型基础上用自我博弈的方式进行强化学习。在这个阶段,为了克服非完美信息博弈的问题,研究者在训练阶段利用不可见的一些隐藏信息来引导AI模型的训练方向,让它的学习路径更加清晰、更加接近完美信息意义下的最优路径,从而倒逼AI模型更加深入地理解可见信息,从中找到有效的决策依据。他们称之为“先知教练”技术。

与此同时,对于麻将复杂的牌面表达和计分机制,研究团队还利用“全盘预测”技术搭建起每轮比赛和8轮过后的终盘结果之间的桥梁。这个预测器通过精巧的设计,可以理解每轮比赛对终盘的不同贡献,从而将终盘的奖励信号合理地分配回每一轮比赛之中,以便对自我博弈的过程进行更加直接而有效的指导,并使得Suphx可以学会一些具有大局观的高级技巧。

为了应对巨大的状态空间,研究团队引入全新的机制对探索过程的多样性进行动态调控,让Suphx可以比传统算法更加充分地试探牌局状态的不同可能。另一方面,一旦某一轮的底牌给定,其状态子空间会大幅缩小,所以研究团队让Suphx在推理阶段根据本轮的牌局来动态调整策略,对缩小了的状态子空间进行更有针对性的探索,从而更好地根据本轮牌局的演进做出自适应的决策。

第三个阶段则是在线比赛,通过不断参与到与人类玩家的对局中,从而不断得到自我更新和提高。

自今年3月进入天凤平台以来,Suphx在与人类玩家的对局中学得非常快。目前,在平衡攻击和防御方面,Suphx表现出了比许多顶尖人类玩家更明智的策略,能够战略性地完成短期损失与长期收益之间的权衡,并根据已有的模糊信息进行快速决策。

四、开拓游戏AI二次元

尽管目前来看Suphx在天凤平台上只是达到十段水平,距离“天凤位”还有一定距离,但我们可以相信一旦天凤平台开放权限,Suphx达到并超越“天凤位”的诸位玩家将指日可待,这也将成为继AlphaGo之后再次挑战人类认知的历史事件。

不过它的意义并不仅在于“震惊”,更在于对研究和应用方向的开拓。

正如前面提到的,麻将AI的研究为游戏AI在“第二维度”开辟了新的方向,并进行了极大地拓展。我们可以期待未来在“第二维度”上将会有更多的研究出现。甚至为了更进一步拓展研究范围,可能会有一些研究人员发明出具有更大信息集数目和更大信息集平均大小的新游戏来。这不是不可能。

此外,我们所生活的世界也正是一个非完美信息的决策过程,麻将游戏中复杂的推理策略和带有随机性的博弈过程,比完美信息游戏更加贴近人类复杂的真实生活。我们同样可以期待,对非完美信息游戏的研究,将有助于我们开发出适用于真实生活场景的更加“智能”的AI系统。

这次 AI 突破的是麻将!

当然,最直接的意义还在于,Suphx“苏菲老师”在牌风上已经自成一派,创造了许多新的策略和打法,这将直接改变麻将社区的生态。许多麻将爱好者已经开始学习Suphx的打法来提升和丰富自己的麻将技巧,这其中包括天凤位的大神太くないお,他是世界上第15位三人麻将天凤位获得者,也是第一位在四人麻将和三人麻将中均取得天凤位的顶级玩家。他表示:“我已经看了300多场Suphx的比赛,我甚至不再观看人类玩家的比赛了。我从Suphx身上学到很多新技术,它们对于我的三人麻将打法有着非常大的启发意义。”

期待“苏菲老师”晋升天凤位。雷锋网报道。


相关阅读

[1] 游戏 AI 的缘起与进化,https://mp.weixin.qq.com/s/p1XYJIqVrUUvSxRQcxBkoA

[2] 哪类游戏AI难度更高?用数学方法来分析一下,https://mp.weixin.qq.com/s/ZIlhWK19qXFsb3jOQaGGfw

[3] 游戏 AI 挑战进阶,即时策略游戏和非完美信息游戏成为热点,https://mp.weixin.qq.com/s/cB0zczZ5ZkqaNvNw2KDshw

雷锋网(公众号:雷锋网)报道。

雷锋网原创文章,未经授权禁止转载。详情见转载须知

这次 AI 突破的是麻将!
分享:
相关文章

文章点评:

表情
最新文章
请填写申请人资料
姓名
电话
邮箱
微信号
作品链接
个人简介
为了您的账户安全,请验证邮箱
您的邮箱还未验证,完成可获20积分哟!
请验证您的邮箱
立即验证
完善账号信息
您的账号已经绑定,现在您可以设置密码以方便用邮箱登录
立即设置 以后再说