麻将普通胡牌算法(带混)
最近在玩腾讯的麻将游戏,但是经常需要充值,于是就想自己实现一个简单的单机麻将游戏.第一个难点就是实现胡牌的判断.这里写一下心得.
术语
本文的胡牌是指手牌构成了3N+2的牌型,即一对做将,剩下的牌均为刻子(3张一样的牌)或者顺子(3张连续的牌比如234饼).
下面就是一个14张牌胡牌的例子:
122334饼23499条中中中
其中两张9条做将,三副顺子为123饼、234饼,234条,3个红中组成一副刻子.
我们要实现的函数只判断是否胡牌,但不计算胡牌的番数.
核心要点
我的思路参考了https://blog.csdn.net/weixin_33961829/article/details/88997328.
即首先选出做将的牌,然后看看剩余的牌是否成型.所谓成型,就是牌可以分成N组，每组3张,为顺子或者刻子.
如果允许牌里含有混(也叫癞子或者白搭),于是问题就可以转化为对一门麻将牌,求出还需要多少个混才能让他成型.显然如果所需的混数不超过已有的混数目,则说明原来的手牌是胡牌.
最少混的求法
下面看一些例子:
比如对顺子(比如 123饼) 或者刻子(比如3张3万),他们已经成型了,所需混子数为0.
如果是一对(比如两张7饼)或者二连(比如12万)，隔连(46条),则至少需要再补一张牌才能成型,所以这三种情况都需要补一张混
对单牌,则需要补两张混才能成型.
由此就可以理解下面的一个求某门数牌最小补混数目的算法:
1.将数字牌按面值排序,并记录其数目.
比如九莲宝灯的胡牌11123456789999可以表达为
[3,1,1,1,1,1,1,1,4],即1万3张2到8万各1张,9万4张.
2.从第一张牌开始,每次进行如下处理:
(1)如果本牌的剩余数目不为0,执行(2),否则对下一张牌重新开始进行(1)的操作
(2) 如果本牌的剩余数目>=3,则将本牌的数目-3,即从牌中去掉一组刻子,然后回到(1),否则执行(3)
(3)判断本牌是否可以和后面的两张牌构成顺子,如果可以的话则将这3张牌的数目都减1,然后回到(1) .否则执行(4) 比如当前处理的牌为6万,然后7万和8万的数目都大于0,则把678的数目都减1,也就是去掉这副顺子,不需要补混.如果7万或者8万有一个数目为0,就要执行(4).再比如当前牌为8万,也要执行(4)
(4)判断本牌的数目是否>=2,是的话,即数目减2,然后混子数+1,再回到(1).这一步的目的是每个对子补一张混.如果当前牌无法构成对子,则执行(5)
(5)判断下一张牌的数目是否>0,是的话则本牌和下一张牌的数目都减1,然后混子数+1,再回到(1).这一步是给每个2连补一个混.如果构不成2连的话则继续执行(6)
(6)判断隔一张牌的数目是否>0.是的话则本牌和隔一张牌的数目都减1,然后混子数+1,再回到(1).这一步是给每组隔张补一个混.这一步是给每组隔张补一个混,如果连隔张也不能构成的话,则执行(7)
(7)将本牌的数目减1,混子数+2. 然后对下张牌重复操作(1).这一步的目的是给每个单张补两张混.
算法执行实例:
设手牌为358饼57条115689万
对筒子牌的计算过程为
去掉隔连35筒,需要1个混子
去掉单牌8筒,需要2个混子
所以饼牌成型最少需要3张混
对条牌的计算过程
去掉隔连57条,需要1个混子
条牌成型最少需要1张混
对万字牌的计算过程:
去掉一对1万,需要1个混子
去掉二连56万,需要1个混子
去掉二连89万,需要1个混子
所以万牌最少需要3张混
所以这个手牌想完全成型的话总共需要3+1+3=7张混.
字牌(东西南北中发白)的最小补混数目非常好算:
因为每个字牌的数目只能为1到4。设某个字牌的数目为n.
显然n=3时不需要胡混, n=1或者n=4时需要补两个混.n=2时补一个混才能成型.
下面看一个字牌的最小补混实例.
比如设一组字牌为 东东东西北北北中中发
这手字牌最少需要5张混,即要补两个西风 一个红中 两个发财.
基本胡牌算法
设一组牌的数目为3N+2,且牌中可能含有混子,则判断这组牌是否已经胡牌的算法为
(1)找出所有数目>=2的牌(不包括混),作为将牌的候选列表
(2)对每个候选将牌,判断去掉这组将头之后,用上一节 的算法判断让剩余牌成型的混子数是否不超过剩余的混子数,如果满足的话则说明原来的牌是胡牌，算法结束，返回成功
(3)如果所有的将头尝试完还不能胡,如果手牌中有混的话,则依次尝试将手中的单牌和一个混组成将头,然后仍然用上一节 的算法判断剩余的牌成型所需的混子数是否不超过剩余的混子数,如果某次尝试成型的话,则算法结束,，返回成功.如果所有的单牌都尝试之后还不行，就返回失败.
加速技巧
为了避免过多的重复计算,再去掉将头之前,我们可以先一次分别计算好饼 条 万 字各们的最小补混数目.这样可以避免重复计算,加快运行速度.比如
如果选了2张万字做将头,那么饼 条 和字的最小补混数目就不需要再重复计算了,可以直接使用.
我们只需要计算需要这组将头之后的万字们的最小补混数即可.
一些实例
下面是我构造的一些天胡带混的实例
0张混 : 33饼345777条123万北北北
1张混 : 22567饼12555678万混
2张混 : 111饼44466条7799万混混
3张混 : 55饼222条666777万混混混
4张混 : 1119饼115999万混混混混
5张混 : 6饼12388万发发发混混混混混
6张混 : 22238饼5条56万混混混混混混
7张混 : 88饼11万东东中混混混混混混混
8张混 : 5条34667万混混混混混混混混
9张混 : 5饼4599万混混混混混混混混混
10张混 : 3条244万混混混混混混混混混混
11张混 : 5饼67万混混混混混混混混混混混
12张混 : 8饼3万混混混混混混混混混混混混
13张混 : 北混混混混混混混混混混混混混
14张混 : 混混混混混混混混混混混混混混
均在电脑上测试通过
扩展
有了上面的胡牌算法,判断听牌就很简单了,只要再尝试补一张混,判断补完的牌是否胡牌即可.下面一些听牌带混的例子,也测试通过.
0张混: 12366789条23344万
1张混: 22饼123条2233万白白白混
2张混: 2饼45条45555777万混混
3张混: 133344万北北中中混混混
4张混: 78条44556万东东混混混混
5张混: 13饼36666万发混混混混混
6张混: 666饼37条西西混混混混混混
7张混: 29饼99条66万混混混混混混混
8张混: 224万北发混混混混混混混混
9张混: 7条白白白混混混混混混混混混
10张混: 77条4万混混混混混混混混混混
11张混: 3饼5万混混混混混混混混混混混
12张混: 6万混混混混混混混混混混混混
13张混: 混混混混混混混混混混混混混