一鸣 思源作者

雀神,微软亚研推出超级麻将AI Suphx,还上了专业十段水平

也许我们以后能拜 AI 为师学习打麻将,成为雀坛冉冉升起的一代新星?

麻将无疑是我国最家喻户晓,老少咸宜的一项棋牌游戏。近年来,随着人工智能在围棋、德州扑克、Dota、星际争霸等众多游戏中获得亮眼的成绩,AI 在麻将领域却一直缺少跨越性的突破。

最近,由微软亚洲研究院开发的麻将 AI 系统 Suphx 成为首个在国际知名专业麻将平台「天凤」上荣升十段的 AI 系统,这是目前 AI 系统在麻将领域取得的最好成绩,其实力超越该平台公开房间顶级人类选手的平均水平。

在今天刚开幕的上海世界人工智能大会上,微软全球执行副总裁沈向洋也正式对外宣布,微软亚洲研究院创造出号称历史上最强大的「麻将 AI」AI Suphx,实力媲美顶级人类选手。

其实今年 Dota 与星际争霸那样的游戏突破,更多的是一种综合能力,不仅有策略,同时还有操作和执行层面的能力。而麻将等棋牌游戏更多是纯智力与策略,因此它的突破更困难一些。微软亚洲研究院副院长刘铁岩表示:「可以说 Dota 这类游戏更「游戏」,而麻将这类棋牌游戏更「AI」。」

微软 Suphx 麻将 AI 有多强

日本在线麻将竞技平台「天凤」因其完善的竞技规则、专业的段位体系,成为了业界知名的高水平专业麻将平台。平台目前有全球近 33 万名麻将爱好者参与,其中不乏大量的专业麻将选手。

微软亚洲研究院开发的麻将 AI 系统 Suphx(Super Phoenix,意为「超级凤凰」)于 2019 年 3 月登陆天凤平台,在 AI 被允许参与的公开竞技房「特上房」与人类选手展开了 5000 余场四人麻将对局。6 月,Suphx 成功晋级十段,成为特上房中段位最高的选手之一,也是首个达到天凤十段的 AI 系统。

这一段位仅次于最强的天凤位,而目前平台上仅有的 14 位天凤位选手都是在只有人类才被允许进入的私有房间「凤凰房」(凤凰房和特上房的计分方式不同)里晋级天凤位的。据悉,鉴于 Suphx 的卓越表现,天凤平台正在讨论是否可以破例让它进入凤凰房。一旦如此,Suphx 问鼎天凤位或许指日可待。

Suphx 的排名位居天凤平台十段之列。

天凤平台通过计算稳定段位(Stable Rank)来衡量玩家的实力水平,在经过多场对局后依然能保持高而稳定的段位是非常不易的。在 5000 余场对局中,Suphx 的稳定段位超过了 8.7,是一个极高的数字。

据统计,即使是天凤平台的所有顶级人类选手在取得十段后的整体稳定段位也仅为 7.4。Suphx 在特上房的稳定水平与所有取得过天凤十段的顶级人类玩家相比要领先约 1.3 个段位,足见这个 AI 的实力非凡。

这样的雀神 AI 是怎样炼成的呢?这要从麻将所处的不完美信息游戏说起。

下棋打牌玩麻将

从围棋到德州扑克,再到麻将 AI,这几年机器学习已经在「拼智力」这条路走了很远。

以前围棋的难主要体现在状态空间非常复杂,19×19 的棋盘上每一个位置都有「黑、白、无」三种状态,这样的复杂度差不多是 10^172。2017 年,AlphaZero 利用蒙特卡洛树搜索 和深度强化学习,成功解决了包括围棋在内的多个完美信息游戏。

既然完美信息博弈已经难不倒智能体了,那么该探索探索不完美信息了。在 NIPS 2017 的最佳论文中,「冷扑大师」提出了一种新型子博弈求解技术,它在一对一无限注德州扑克中打败了顶尖人类选手。在今年 7 月份,冷扑大师的进化版「Pluribus」在六人不限注徳扑上打败了职业玩家,并通过限制搜索深度而大大降低算力需求。

不过德州扑克每个人只有两张隐藏手牌,它的隐藏信息并不是很多。那么机器学习能不能挑战隐藏信息更多的游戏,运气程度更大的游戏?从桥牌到麻将,微软已经在非完美信息博弈上做了很多研究,这一个维度还有很多值得探索的问题。

如下展示了不同游戏的两种复杂度,其中信息集数目表示游戏可观察状态的多少,而信息集平均大小则表示隐藏性的多少。

刘铁岩博士表示:「如果我们沿着不可见的隐藏信息维度,再极致化地推演游戏的发展,就会发现目前的游戏 AI 技术还有很大的发展空间,需要更多全新的技术。」

从完美到不完美信息博弈

当博弈是完美信息时,只要算力足够多,那么肯定就能通过搜索的方式找到最优的策略。

我们可以利用搜索树来理解这一过程,例如棋手每一步棋可以看作选择一个子节点,那么整盘棋一定可以表示为某条路径,现在 AI 要做的就是选择能带来胜利的路径。如下是最为经典的一种搜索树,AI 在每一个状态都希望最小化对手的最大收益。

刘铁岩博士说:「即使是围棋那种状态空间非常复杂的游戏,只要在搜索过程中加一些指导、做一些剪枝,就能在有限算力的情况下找到很好的决策。」

现在再看看德州扑克与麻将等不完美信息博弈,它们和围棋有很大的不同。因为参与者互不知道对方的底牌是什么,所以 AI 基本上没法向前推演。尤其是在参与者只知道几张牌,周围缺失信息远远超过已知信息时,模型差不多只能靠「预测」。对于这样的游戏,核心技术就不再是树搜索,而是需要在某种预测的指导下做决策。

完美信息博弈与不完美信息博弈,它们最基本的指导思想有着很大的差别。」刘铁岩博士说,「在信息不完全的情况下,更重要的是去做预测而不是简单地搜索。」

除了底牌和对方手牌不可见以外,麻将的游戏顺序也存在很大的不确定性。想象一下,象棋围棋都是一手一手轮着来,然而麻将天生就有「吃碰杠」,它会随机打乱游戏的顺序。这种情况下,麻将的游戏树是很不规则的、且动态变化的,我们无法判断什么时候搜索就跳到了另一个区域,因此传统的树搜索就很难真正起作用。所以我们需要新技术来做预估和预测。

这样看来,尽管围棋或麻将对于人类而言只是玩法不一样,但完美信息与不完美信息对强化学习智能体的影响还是非常巨大的。

麻将 AI 都能怎么做

既然麻将与围棋 AI 在本质上有很多不同,那么以前这个任务都是怎样解决的?早期的麻将 AI 会人为地把领域知识编码到游戏 AI 的程序里。后来随着深度学习强化学习的流行,人们开始研究利用它们来自动学习和强化游戏 AI 的能力。微软的 Suphx 就是基于深度强化学习,同时还发明了很多针对非完美信息博弈的新技术。

但是这里有一个问题,前面都是从博弈论的角度讨论围棋和麻将,而如果我们要使用博弈论强化学习解决麻将游戏,那么它们之间的关系又是什么样的?

刘铁岩博士表示,博弈论是一个比较广的概念,现实中有很多策略都是通过博弈论设计的。一般规则比较简单的游戏可以推导出最佳策略,只要智能体按照策略来玩游戏就不太可能会输。比如说在德州扑克的 2 人博弈中,我们可以通过纳什均衡推导出最佳策略。

但是对于更复杂的麻将,博弈论一般只能作为框架来指导智能体做自我博弈,或者作为指引来设计各种奖励项函数。博弈论主要提供设计思想,没办法提供建模能力,因此我们需要强化学习这种可计算的方式找到更好的解决方案。

博弈论强化学习的结合更像指导与实践的联合,两者在打造麻将 AI 的过程中起着不同的作用。

Suphx 是如何打造的

前面已经介绍过非完美信息博弈的难点,然而除了非完美信息,麻将的状态空间和奖励机制都非常复杂。比如说奖励机制,因为一轮游戏包含 8 局,每一局得分通过和牌牌型与番数计算,最后 8 局的总分才会最终影响段位奖惩。而和牌牌型与番数的计算规则非常复杂,因此怎样给智能体分配奖励就非常重要了。

为了解决这些问题,微软 Suphx 通过一系列新型强化学习算法,令智能体在具有策略学习能力的同时具备大局意识,从整轮游戏的高度做出策略性的判断。总体而言,Suphx 的技术创新主要分为以下三部分:

  • 自适应决策

  • 先知教练

  • 全盘预测

1. 针对巨大的状态空间,Suphx 会对探索过程的多样性进行动态调控,从而比传统算法更加充分地试探牌局状态的不同可能。另一方面,一旦某一局的底牌给定,其状态子空间会大幅缩小,Suphx 也就能进行有针对性的调整。

因为麻将每一次洗牌都会有不同的牌面,所以智能体还要学会将以前的打牌经验与本局的牌面联系起来,从而调整策略。研究团队让 Suphx 在推理阶段根据本轮的牌局来动态调整策略,对缩小了的状态子空间进行更有针对性的探索,从而更好地根据本次牌局的演进做出自适应的决策。

简单而言,自适应决策会令智能体进行大量的学习后,在离线推理过程中还根据实际情况调整打牌策略,这样才能适应不同的初始牌面。

2. 针对非完美信息博弈,Suphx 创新性地使用「先知教练」技术来提升强化学习的效果。其基本思想即在自我博弈的训练阶段利用不可见的一些隐藏信息来引导模型的训练方向,使其学习路径更加接近完美信息意义下的最优路径。从而迫使 AI 模型更加深入地理解可见信息,并找到有效的决策依据。

也就是说在自我博弈的过程中,先知教练是可以「窥探」到底牌的,它要在近乎完美信息的情况下决定如何出牌。然后再据此为指导,去训练看不到底牌的 AI 智能体。这样会引导智能体根据目前的牌局「预测」对手的手牌和底牌可能是什么样的,并作出更正确的决策。

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

那么麻将的随机性呢

麻将与其它棋牌游戏有一个很大的差别,麻将拥有大量的随机性,例如每次初始的牌面、摸到的牌、吃碰杠打乱的顺序等等。Suphx 很大一部分工作都在建模这些随机性,前面介绍的先知教练与全盘预测也都是在处理这个问题。

在训练过程中,麻将的这种随机性是不可控的,如果智能体一开始就从非完美信息出发,那么它是完全不知道该怎么制定策略的。这种随机性会令智能体在训练过程中产生很大的波动,在稍微不同的可观测信息下获得很大不同的策略。所以先知教练会间接地让智能体在完全信息的指导下进行训练,从而在一定程度上消除这些随机性,以便学习到更加鲁棒的策略。

虽然先知教练可以消除训练过程的随机性,但是真正对弈的时候会产生新的随机性,因为当局的牌面和底牌都会焕然一新,是训练过程中没有见过的。自适应决策则尝试利用以前的通用学习结果,并快速地适应当前牌局,从而抵抗底牌变化带来的随机性。总体来说,Suphx 几乎所有核心技术,都在尝试处理不完美信息带来的随机性。

想象一下,如果智能体通过各种技术建模了随机性,那么就相当于预测出所有的隐藏牌面和底牌,麻将又回到了完美信息博弈。而完美信息博弈,只要有足够的算力,那么一定可以找到非常优秀的解。

Suphx 需要数学基础

如果读者们想要试试麻将 AI,那么注意了,可能你需要的数学基础要比一般的机器学习还强一些。刘铁岩博士表示,在整个游戏 AI 中,有以下数学知识非常重要:

  • 统计学知识:需要对麻将中的大量随机性进行估计与建模;

  • 博弈论知识:需要将打麻将形式化为博弈过程,并将其作为模型设计的指导;

  • 机器学习知识:线性代数、最优化方法等常规的数学基础。

很多机器学习算法工程师并不太了解博弈论,但做麻将 AI 确实需要一些跨界知识。例如机器学习是一种纯统计的方法,我们看重的是模型平均效果,而博弈论更看重最差的情况,它们两者间的世界观都有一些不同。

其实像 AlphaGo,它几乎是由纯机器学习团队构建的,而冷扑大师的德州扑克团队关注更多的是博弈论。所以对于他们的研究或论文,风格是非常不同的。

因此,对于麻将,我们既无法通过纯机器学习来建模,又无法通过博弈论处理这么复杂的博弈。只有结合两者,才能为 Suphx 提供足够强大的基础。

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

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

https://www.msra.cn/
微软机构

微软是美国一家跨国计算机科技公司,以研发、制造、授权和提供广泛的计算机软件服务为主。总部位于美国华盛顿州的雷德蒙德,最为著名和畅销的产品为Microsoft Windows操作系统和Microsoft Office办公室软件,以及Xbox的游戏业务。微软是美国《财富》杂志2015年评选的世界500强企业排行榜中的第95名。

https://www.microsoft.com/en-us/about
沈向洋人物

微软全球执行副总裁,美国工程院院士。

刘铁岩人物

刘铁岩博士毕业于清华大学电子工程系。现任微软亚洲研究院主任研究员,互联网经济与计算广告学研究组负责人。他是美国计算机学会(ACM)、国际电子电气工程师学会(IEEE)、和中国计算机学会(CCF)的高级会员。中国科技大学和南开大学的客座教授。

纳什均衡技术

纳什平衡,又称为非合作赛局博弈,是在非合作博弈状况下的一个概念解,在博弈论中有重要地位,以约翰·纳什命名。 如果某情况下无一参与者可以通过独自行动而增加收益,则此策略组合被称为纳什均衡点。

深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

深度强化学习技术

强化学习(Reinforcement Learning)是主体(agent)通过与周围环境的交互来进行学习。强化学习主体(RL agent)每采取一次动作(action)就会得到一个相应的数值奖励(numerical reward),这个奖励表示此次动作的好坏。通过与环境的交互,综合考虑过去的经验(exploitation)和未知的探索(exploration),强化学习主体通过试错的方式(trial and error)学会如何采取下一步的动作,而无需人类显性地告诉它该采取哪个动作。强化学习主体的目标是学习通过执行一系列的动作来最大化累积的奖励(accumulated reward)。 一般来说,真实世界中的强化学习问题包括巨大的状态空间(state spaces)和动作空间(action spaces),传统的强化学习方法会受限于维数灾难(curse of dimensionality)。借助于深度学习中的神经网络,强化学习主体可以直接从原始输入数据(如游戏图像)中提取和学习特征知识,然后根据提取出的特征信息再利用传统的强化学习算法(如TD Learning,SARSA,Q-Learnin)学习控制策略(如游戏策略),而无需人工提取或启发式学习特征。这种结合了深度学习的强化学习方法称为深度强化学习。

AlphaZero技术

DeepMind 提出的 AlphaZero 不仅征服了围棋,也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。DeepMind 推出的 AlphaGo 曾在围棋项目中取得了超越人类的表现,其研究曾经两次登上 Nature。2018 年 12 月,AlphaGo 的「完全自我博弈加强版」AlphaZero 的论文又登上另一大顶级期刊 Science 的封面。在论文中,AlphaZero 不仅征服了围棋,也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

剪枝技术

剪枝顾名思义,就是删去一些不重要的节点,来减小计算或搜索的复杂度。剪枝在很多算法中都有很好的应用,如:决策树,神经网络,搜索算法,数据库的设计等。在决策树和神经网络中,剪枝可以有效缓解过拟合问题并减小计算复杂度;在搜索算法中,可以减小搜索范围,提高搜索效率。

博弈论技术

博弈论,又译为对策论,或者赛局理论,应用数学的一个分支,1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》,标志着现代系统博弈理论的的初步形成,因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

完美信息博弈技术

在经济学中,完全的信息是完美竞争的特征。 随着市场信息的完善,所有消费者和生产者都被假定在对自由市场体系进行理论化和财务政策效应时,对产品的价格,效用,质量和生产方法有完整的认识。

线性代数技术

线性代数是数学的一个分支,它的研究对象是向量,向量空间(或称线性空间),线性变换和有限维的线性方程组。向量空间是现代数学的一个重要课题;因而,线性代数被广泛地应用于抽象代数和泛函分析中;通过解析几何,线性代数得以被具体表示。线性代数的理论已被泛化为算子理论。由于科学研究中的非线性模型通常可以被近似为线性模型,使得线性代数被广泛地应用于自然科学和社会科学中。

强化学习技术

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

推荐文章
暂无评论
暂无评论~