当前位置: 华文问答 > 数码

人工智能在麻将领域能够战胜人类吗?

2016-03-13数码

谢邀。很高兴能借着 AlphaGo 的东风,和大家分享一下 麻将 AI 研究的现状。


一. 麻将和围棋有什么不同?

从博弈论的角度来讲,围棋是 完全信息动态博弈 ,而麻将属于 非完全信息动态博弈 。围棋中对局双方所掌握的 信息 对称 的,而麻将中各对局者间所掌握的 信息不对称 。虽然大家都能看到每位牌手打过什么牌,但 你不知道我的手牌是什么,我也不知道你的手牌是什么 。这种信息不对称的产生的根本原因是 牌墙的随机性

围棋与麻将(或者说 棋与牌 弈与博 )的上述区别,决定了它们 获胜策略 的根本不同。棋类项目本质上就是 蒙特卡洛树 ,获胜策略就是选择或迫使对手选择一个分支,这个分支下面所有的结局都是自己胜。只不过由于棋类变化很多,连 AlphaGo 也远不可能 遍历 整个树,所以 AlphaGo 会通过 价值网络 来估计某一分支下 胜结局的概率 。其实人类的思维也是类似的,在围棋里平白被对手屠掉一条大龙,或者在象棋里平白送给对手一个车总是不好的——在这些分支下,胜结局的概率大大降低了。


而牌类的获胜策略在于尽可能增大自己的 得分期望(EV) 。我并不知道我接下来要摸什么牌,或我的对手有什么牌,但所有可能的情形组成一个 概率空间 ,我只需做出一个选择,使得自己的 得分函数 的期望最大。牌类策略的难点在于,影响这一概率空间的 因素过多 ,且 具体影响 很难确定,比如对手打牌的 习惯

※下图选自【科学化麻雀】,闲家愚形听牌打 10% 危险度的牌对攻,x 轴为自己和牌时得分,y 轴为牌局巡次,z 轴为自己的得分期望。


二. 何谓「获胜」?

选手的 竞技水平 如何 衡量 ?麻将是否是 「运七技三」 的游戏?其实无论围棋还是麻将,区分选手的竞技水平都 不可能只靠一局 ,就好比 AlphaGo 和李世乭要进行 五番棋 对决,AlphaGo 赢第一盘时大家并不觉得 AlphaGo 一定比李世乭强一样。围棋有三番、五番、十番棋,对于 竞技麻将 (国标麻将、日本麻将)而言,区分顶尖选手的竞技水平至少需要 2000~10000 手牌 (如果采用类似桥牌的 复式赛制 ,这一数字会大幅降低)。

至于衡量 一个竞技项目的竞技性 ,单纯用 运气所占比例 是没有意义的。随着对局数的增大,运气所占比例会越来越小, 选手的长期成绩必然会向其真实水平收敛 。一个竞技项目的竞技性应当用「 区分选手竞技水平所需必要对局时间 」来衡量。比如围棋需要三番棋,麻将需要 2000 手牌,围棋一盘平均需要 4 小时,三番棋约 12 小时,而麻将一手牌约 3 分钟(网络对局),2000 手牌约 100 小时。麻将相比围棋有 运气 成分,并不意味着麻将选手的竞技水平无法衡量,而意味着麻将需要 更多的对局时间 来区分选手的竞技水平。

下图选自日本麻将平台天凤麻雀凤凰桌 1000 场以上玩家安定段位排行。这里的「试合」是指半庄,也就是两圈牌,考虑到连庄,平均一试合是 10 手牌,1000 试合是 10000 手牌。可以看到牌手的竞技水平得到了 很显著的区分 ,结果也与麻将圈内认知相似。具体讲解请参见

打麻将的水平可以高到什么程度? - Suwako Zhai的回答

所以在这个问题下我们讨论麻将 AI 能否战胜人类,指的是麻将 AI 长期成绩 (10000 手牌以上)能否比人类更好,并不是单指一手牌。只打一手牌,谁都有可能和牌,这是牌类游戏的本质所决定的。

当然,这里也不考虑牌手或 AI 作弊 的问题。如果通过作弊获得别人手牌的非法信息,麻将的 竞技平衡 就完全被打破了。再强的麻将 AI 成绩也不可能比作弊的人类好,反之亦然。事实上,现在很多单机麻将游戏的 AI 就是通过作弊来增加「智能」的。


三. 麻将会成为人类面对人工智能的「最后壁垒」吗?

一言以蔽之, 麻将 AI 不是做不了,而是没人做 。之所以目前还没有能够战胜人类的麻将 AI,主要原因还是人们在麻将 AI 研究方面的 投入不够 。目前的麻将 AI 基本都是麻将游戏制作团队为麻将游戏设计的,在单机上就可以运行,强度自然有限。如果像 AlphaGo 一样,世界顶级团队制作,背后庞大资金支持,使用 1000 个 CPU 运行,想要设计一个轻易战胜人类顶尖麻将牌手的 AI 没有任何难度

首先,麻将的 复杂度 要远远小于围棋。单就自己的 14 张手牌来说(总牌数 136 张),组合共有 326520504500 种 (计算方法详见

麻雀の数学

),远远小于围棋的 2.08×10^170。不足 10^12 的手牌种类意味着麻将 AI 完全可以 提前计算好每手牌的打法估值并储存在资料库中 ,打牌时调用即可。

※下图选自日本麻将研究者らすかる的个人网站

麻雀の数学

当然,打麻将也要考虑 别人打的牌 以及 各家的得分 。各家分差的复杂度是很小的,而别人打的牌虽然复杂度会很高(136 张牌的牌墙组合为 4.3×10^185 种,甚至超越了围棋的复杂度),但别人打的 10 张牌大多只有 1~2 张是有用的信息,AI 只需要 识别这种模式并搜索对比以往对局的牌谱 即可。

其次,人类 对麻将的研究 远不及围棋,顶尖麻将牌手的 训练水平 很低。相比围棋研究几千年的历史,麻将诞生不过百余年,人们真正开始利用 科学手段 统计学、大数据 )来研究麻将只是 近十年 刚刚起步。例如 「间四间」 是上世纪流行的日本麻将理论,指的是别人打过中间相隔 4 张的 2 张同花色数牌,则这 2 张牌的 内侧筋牌 是危险牌。如别人打过三筒、八筒(中间相隔四五六七筒),则四七筒是危险牌,这是因为别人手里一开始可能是三五六八筒,三八筒效率较低被打掉,留下的五六筒要四七筒。这一理论在近十年的大数据研究中已被证明是 完全错误 的——别人要四七筒的概率并没有显著性的上升。

可见,目前人们对麻将的研究还处在很 初级 的阶段,通过别人打过的牌来分析别人想要的牌的 科学研究 才刚刚开始。麻将界也没有围棋那样 3 岁开始学棋,10 几岁就和世界顶级高手过招,接受世界顶级指导的 职业选手 。麻将本身复杂度低,人类顶尖牌手水平又不高,被人工智能击败会比围棋要容易得多,不可能是「最后壁垒」。


四. 现在有哪些比较强的麻将 AI?

竞技麻将方面,目前 国标麻将 日本麻将 都有比较强的 AI(高于人类平均水平)。日本麻将的 AI 目前最强的当然是 「爆打」

「爆打」是由东京大学工学系在读博士生 水上直纪 开发的日本麻将 AI,他所在的课题组就是专门研究麻将 AI 的。爆打和 AlphaGo 一样,也具有 自我对局 分析并学习人类牌谱 的能力。水上发表过的论文题目为【Realizing a Four-Player Computer Mahjong Program by Supervised Learning with Isolated Multi-Player Aspects】,全文详见

http://www. logos.ic.i.u-tokyo.ac.jp /~mizukami/paper/jousho_2014.pdf

爆打从 2015 年开始在最大的日本麻将平台—— 天凤麻雀 上开始运行,至 2016 年 2 月已经打了 1.3 万多场(约 13 万手牌)。2015 年 9 月,爆打达到 天凤麻雀四段 ,2015 年 12 月更是一度冲进 天凤七段 ,长期成绩显示平均为 六段以上 。这意味着什么呢?

上图是天凤麻雀平台 2016 年 3 月 13 日的段位成绩分布图(来源

オンライン対戦麻雀 天鳳 / ランキング

)。天凤平台具有非常科学的 段位和 Elo Rating 体系 ,越是和高水平牌手对局,获胜后 Rate 增加越多,失败后 Rate 减少越少;越是和低水平牌手对局,获胜后 Rate 增加越少,失败后 Rate 减少越多。最终段位和 Rate 值的 稳定值 就代表了牌手的 真实实力

可以看到,天凤麻雀平台的活跃用户数约为 17 万人(不包括新人僵尸号),而六段以上的用户总数为 5793 人,约占 3.4% 。也就是说,爆打打麻将比 96.6% 的麻将玩家要好,全世界麻将打得比爆打好的人,数量仅有 几万人 左右(包含所有麻将规则的估算)。这只是一个课题组,用时一年多研究出的,在一台电脑上运行的麻将 AI,就已经基本赶上 AlphaGo 早期版本所取得的成绩了。

国标麻将 方面,目前最强的 AI 大概是我本人目前正在参与设计的国标麻将 AI 了。最初的版本只加入了最常用的十几个番种的分值判断,防守端几乎没有做,实测对随机牌手和牌率就已经达到 24% 左右,基本与国标麻将平均和牌率 24.3% 持平(国标麻将数据可见

国标麻将、日本麻将对局时,「点炮、自摸、流局」的比例分别是多少? - 段昊的回答

)。实际水平大概处在所有牌手中 上位 10~20% 左右的水平(低段位牌手多,大部分牌手的水平处在平均以下)。


五. 麻将 AI 的算法应该是什么样子的?

最后,我来浅谈一下麻将 AI 的基本算法。

1. 基础牌效率

麻将的牌效率指的是 能使手牌更快和牌的打牌方法 ,是麻将的基本功。来简单举个例子:

※下图牌画取自 联众国标麻将 (http:// gbmj.lianzhong.com )。

这是一手 13 张牌的手牌,现阶段是 一上听 (差 1 张牌就可以听牌),那么哪些牌是 有用 的牌,或者说我摸到哪些牌会 留下 呢?这些有用的牌称为「 有效牌 」,最有用的当然是能让我直接听牌的牌,这类牌称为「 第一类有效牌 」。

●第一类有效牌:能使手牌向和牌前进一步(上听数降低)的牌,包括:

除了第一类有效牌,有用的牌还有以下这些:

●第二类有效牌:不能使上听数降低,但能使第一类有效牌增多的牌,包括:

比如摸到九索,一般情况下应该选择留下九索打掉三索,因为第一类有效牌变多了:

※计算采用天凤牌理

オンライン対戦麻雀 天鳳 / 牌理

●第三类有效牌:不能使上听数降低,也不能使第一类有效牌增多,但能使第二类有效牌增多的牌,包括:

比如摸到五索,一般情况下应该选择留下三五索拆掉八九索,虽然第一类有效牌张数没变,但三五索相比八九索多了 1 种第二类有效牌——六索(原是第三类有效牌)。

(也许看到这里,你有点算不过来,或者感觉这和你平时打的麻将压根不是一个游戏。没关系,这很正常,你可以找张纸,在纸上仔细算一下每种第二类有效牌都新增了哪些第一类有效牌。)

可见,对于一开始一上听的 13 张手牌而言,除了七八九筒外的所有数牌都是有用的牌。麻将的牌效率就是这样—— 不断通过有效牌增大自己的进张面,最终使得和牌的概率越来越大 。也许你已经发现,麻将牌效率的本质就是一个 搜索树 ,最开始的手牌

经过多轮选择后可能对应多种结局(和牌),例如:

路径:摸到第一类有效牌八万或七索听牌,再自摸另一张和牌(最大概率结局)。

路径:先摸到第二类有效牌一万或七万后打掉三索,然后摸到一万或七万的另一张听七索,或者摸到七索选择听一万和七万对倒和牌。

路径:先摸到第三类有效牌三筒后打掉三索,然后摸到四筒后拆掉八九索,之后和牌。

对于一个 两上听以内 的手牌来说,这个树的深度最多也就是 4~5 步 ,每一步的分支平均在 15 种 左右,也就是说复杂度最多在 10^5 数量级 。由于每条路径都对应着一个确定的 概率 ,一个好的麻将 AI 完全可以做到 遍历 这个树,比较两种或更多种打牌选择之间所对应结局的 和牌期望之和

对于 三上听以外 的手牌(由上文图中可知三上听以外的手牌约占手牌所有组合的 80%),由于手牌中会存在大量的孤张或简单搭子,只需单独比较孤张或简单搭子的效率即可,计算量更小。

除了上述穷举手牌搜索树的方法,还可以采用 模拟 的方法。比如让麻将 AI 在短时间内模拟两种打法各 1000 手牌,哪个和牌率更高就选哪种打法。虽然这样不太精确但已经足够保证比人要强了。

2. 和牌限制与番数价值

很多麻将规则 对和牌有限制 ,比如国标麻将必须八番起和,四川麻将必须缺一门,太原麻将和牌必须包含指定牌张等等。我们只需在上述 基础牌效率算法搜索树 的基础上,「 砍掉 」那些结局不符合要求的分支即可。

有些时候我们不仅关注和牌的概率,也关注 和牌的大小 ,比如有些牌我们宁可损失一些进张也想去做清一色,追求更高的 和牌得分 。我们只需为树的所有结果赋值(和牌得分),并用 结局对应的值 路径对应的概率 求出不同打法的 得分期望 并进行比较。

3. 副露判断

「这个牌该不该碰」似乎是打麻将时比较令人头疼的问题。但其实 副露判断 只是 计算量大 ,并不需要特殊的算法,依然是 对比 碰与不碰两种选择所对应的所有结局的 得分期望 即可。日本麻将中的 立直(报听)判断 也是同理。

只不过当我们在考虑「打哪张好」的时候,两种打牌选择之间所对应的路径和结局有 大部分都是重合的 ;而我们在考虑「该不该碰」的时候,两种选择所对应的路径和结局基本是 完全不同 的,这无形中 增大了计算量 。其实人脑在做蒙特卡洛树搜索时,比较容易做到 「想得很深」 ,比如职业棋手可以提前算到 20 甚至 30 步棋;但难以做到 「想得很广」 ,通常情况下大脑只能做到从两种选择中找几个概率较大、有代表性的 结局样本 做比较。所以副露判断显得难,其实只是 计算量 的问题,而对于麻将 AI 来说,这 不是问题

4. 防守端

防守端需要解决的是 攻守判断 防守打法 两个问题,即「什么时候要防守」和「要防守应该打什么」。解决这些问题最好的方法是让麻将 AI 自己通过大量的牌谱(千万场量级)进行 自我学习 。正如前文我所提到的,其实人们对于麻将应该如何 科学防守 的研究也才刚刚开始,想要分析一个打过三筒和八筒的人真正需要的是几筒,需要 大量 的牌谱作为样本进行研究。这部分研究现在还要等待电脑去完成,未来的麻将 AI 在这方面要比人类做得更好可以说是必然的。

对大量牌谱所做的 出牌模式研究 还可反过来应用于牌效率算法的 改进 中。比如早巡打过八万的人手牌中有九万的概率较小,那么牌墙中剩余九万的概率就有所上升,牌效率中利用九万的路径的概率就可以做出相应的 修正

5. 状况判断

状况判断指的是麻将的 「大局观」 ,如为了争取第一名或者为了规避第四名而采取不同的策略。状况判断其实就是对 得分期望 做进一步的 修正 。比如某状况下我必须自摸 13 番牌才能逆转,那么最终结果是 13 番以下的牌的得分期望可以进一步降低,而 13 番及以上的牌的得分期望则可以提高。


总之,麻将的复杂度较低,算法上可以用 搜索树穷举法 以及 大量牌谱的自我学习 来解决,只要有大量牌谱资料,有人肯花时间,有人愿意出资,开发一个能胜过人类的麻将 AI, 非常容易

————————准备跑题的分割线————————

最后的最后我想说,同为智力运动,相比棋类,人们对牌类的研究真的是太少了。虽然牌类的竞技性(区分选手竞技水平的必要对局时间)要普遍弱于棋类,但牌类也有其独特的策略与魅力。诚然,人们普遍对牌类项目有着各种各样的偏见与误解,比如认为牌类是纯运气项目,比如说起牌类就联系到赌博……也正由于此,牌类项目的规范化、竞技化、运动化才显得尤为迫切与重要。

我希望有朝一日,麻将、斗地主、德州扑克这些项目能够获得与桥牌同样的地位与发展空间。我希望未来的孩子们既可以选择学习围棋,也可以选择学习麻将。我正走在追寻理想的道路上,而且我坚信理想并不遥远:

国际智盟执委会:麻将扑克有望亮相下届智英赛