循网移动 | 购买点卡 | 卡密充值
网站颜色:
三七透骨黄酊【主要成份】透骨草、鸭跖草、生姜、红花、鸡血..
袁则红针对门诊量下滑的原因、解决方案和运营指导方案做了详..
干赢生物在诊所渠道具有双跨优势,既能为诊所终端提供实体产..
循环科技

麻将的数推原理是什么?其实AI不待见它
2017-01-05 10:39:47 来源: 作者: 【 】 浏览:303次 评论:0
简述:对大量牌谱所做的出牌模式研究还可反过来应用于牌效率算法的改进中。比如早巡打过八万的人手牌中有九万的概率较小,那么牌墙中剩余九万的概率就有所上升,牌效率中利用九万的路径的概率就可以做出相应的修正。
责任编辑:admin


随着Master完成对人类棋手的60胜,人工智能(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 一样,也具有自我对局和分析并学习人类牌谱的能力。爆打从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,非常容易。

Tags:
责任编辑:admin
您看到此篇文章时的感受是:
】【打印繁体】【投稿】 【收藏】 【推荐】 【举报】 【评论】 【关闭】【返回顶部

1、凡标注“原创” 的所有作品,版权均属于县域医疗卫生市场研究中心,未经本网授权,任何单位及个人不得转载、摘编或以其它方式使用上述作品。已经本网授权使用作品的,应在授权范围内使用,并注明“县域医疗卫生市场研究中心”。违反上述声明者,本网将追究其相关法律责任。

2、凡本网注明 “来源:XXX” 的作品,均转载自其它媒体,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如因作品内容、版权和其它问题需要同本网联系的,请在30日内进行。 021-60526838

我来说两句
帐  号: 密码: (新用户注册)
验 证 码:
表 情:
内  容:

《诊所营销》2018出版版本(包邮)

139

3748人已购买       我要买