通用麻将胡牌算法

【转载】 Unity3D 通用麻将胡牌算法 - JAVA说

正常的麻将胡牌方式为满足N ABC + M DDD +ＥＥ 的形式，及存在一个对子(EE)，剩余牌均能组成顺子（ABC）或者刻子（DDD）。

很容易发现必须满足size%3 == 2的形式才可以去计算胡牌。

数据结构的选取：

麻将有万、饼、条各九种，另外还有东西南北中，春夏秋冬。
种类不是很多，一个字节表示就可以了，前四位代表类型，后四位代表值，东西南北中，春夏秋冬可以集中到一种类型中去。

普通麻将的计算方式：

1.首先找出所有包含一对的情形，移除对子（注意去重），记下剩余牌的所有集合为Tn;
2.针对每个Tn中的数组尝试移除一个顺子，成功转到2，失败到3。
3.针对每个Tn中的数组尝试移除一个刻子（DDD），成功转到2。
4.若当前的数组的数量变为0，则表示，当前的方案可以胡牌。
2,3,4可以作为一个check_3n(检测是否满足N * ABC + M *DDD)的函数，递归调用即可。

针对有癞子的麻将（百搭）：

最简单的办法是尝试将癞子牌变为所有派来进行尝试，不过如果手中有多张癞子牌的话计算量就相当大了，比如3张，则需要计算牌的种类的3次方次，虽然中途可以通过剪枝减少部分计算量，但还是太慢了。
针对这种情况我们可以在计算出癞子的数量，如果出现找出顺子或刻子失败，我们则可以用癞子去补，如果失败了，那么当前的方案就不通过。

1.同样找出所有包含一对的情形，移除对子，移除的时候需要注意更新癞子的数量这里需要注意的是对子是怎么产生的:
原有的对子
一个癞子和一普通的组成的对子
一对癞子
2.针对每个数组尝试移除一个顺子，成功转到2，如果失败尝试用癞子去补，癞子也不够，转到3。
3.针对每个数组尝试移除一个刻子（DDD），成功转到2，如果失败尝试用癞子去补，癞子也不够，当前的方案就不通过。
4.若当前的数组的数量变为0，则表示，当前的方案可以胡牌。
　　算法理解之后就不难了 , 下面开始详细的阐述了.

1. 将麻将抽象为数字

　　数字 {01 ~ 09} 表示 {1 ~ 9} 筒

　　数字 {11 ~ 19} 表示 {1 ~ 9} 条

　　数字 {21 ~ 29} 表示 {1 ~ 9} 万

　　数字 {31 33 35 37 } 表示 { 东 南 西 北 }

　　数字 {41 43 45} 表示 {中 發 白}

　　数字10 20 30 32 34 36 40 42 44 46 空出来不代表任何麻将牌 这样设计的好处就是使得能够形成顺子的牌在用数字表示出来的时候刚好也是连着的 , 而不能够形成顺子的牌,在用数字表示的时候并不是顺子 . 便于以后使用代码进行判断

2. 算法的核心流程

　　玩过麻将的都知道麻将玩家手上一般有两种牌 一种是手牌 一种是已经碰牌或者吃牌或者杠牌之后已经明了的牌 . 现在以玩家A为例 , 把牌分的细一点

　　a. 玩家A的手牌 (数量1 + 3*n n < N , n < 4 )

　　b. 其他玩家打出来的牌 (数量 1)

　　c. 玩家A从牌面上取出来的牌 (数量 1)

　　d. 玩家A吃碰杠的牌 (3n + 4m)

　　能否胡牌主要是看手牌a 和b/c 的组合能否形成一对加n条顺子和m条克子 . 能则能胡 反则不能.

　　

　　如上图 用数字表示为 {1,1,2,2,2,3,4,11,12,12,13,13,14,1} 前13张牌为手牌,最后一张二条为玩家A从牌面上取出的牌

OK, 现在只需要先取出一对将,然后判断剩下的牌能否全部形成顺子或者克子,现在对牌面按照相对应的数字进行从小到大的排序 . 现在从剩余的牌中最左边的牌开始 , 如果只有一张这样的牌那么这张牌A就只能当作顺子的开头 ; 如果有两张这样的牌 , 因为已经有了一对将而这两张也不能组成克子 , 所以这两张只能当作两个顺子的开头 ; 如果有三张这样的牌 , 可以组成克子 , 但是如果让他组成顺子则要求为 AAABBBCCC 与后面的三张也能组成克子 所以组成顺子或者克子本质是相同的 但是组成克子AAA的通用性要高于组成顺子AAABBBCCC 所以当有三个及以上这样牌的时候优先组成克子AAA ; 如果有四张这样的牌,要能胡牌则需要 AAAABBBBCCCC 或者 AAAABC ,对于是先组一个顺子还是一个克子都会回到上述的情况 .

(这里没有对七对等各类大胡作出判断)

步骤一:从上述数组中找到一对做”将”,并从数组中移除 , 这里共有4对牌所以要分成4种情况

　　1. {1,1}(将牌) , {1,2,2,2,3,4,11,12,12,13,13,14}(余牌)

　　2. {2,2}(将牌) , {1,1,1,2,3,4,11,12,12,13,13,14}(余牌)

　　3. {12,12}(将牌) , {1,1,1,2,2,2,3,4,11,13,13,14}(余牌)

　　4. {13,13}(将牌) , {1,1,1,2,2,2,3,4,11,12,12,14}(余牌)

　　依次进行步骤二的检查 检查完最后一种情况而没有返回 “能胡牌” 则返回 不能胡牌

步骤二: 余牌数量为0 则返回 “能胡牌” 否则进入下一步 .

步骤三: 判断余牌前三张是否相同 相同-> 步骤四 ; 不同 -> 步骤五.

步骤四: 移除余牌中的前三张牌 , 返回步骤二.

步骤五: 若余牌中第一个数为N , 则判断是否有N + 1 与 N + 2 同时存在与余牌中 , 有将N , n+1 , n+2 从余牌中移除并返回 步骤二 , 否则返回 步骤一

演示如下

　　1. {1,1}(将牌) , {1,2,2,2,3,4,11,12,12,13,13,14}(余牌)

　　　　步骤二 –> 步骤三 –> 步骤五 == {2,2,4,11,12,12,13,13,14}(余牌) –>

　　 步骤二 –> 步骤三 –> 步骤五 –> 步骤一

　　2. {2,2}(将牌) , {1,1,1,2,3,4,11,12,12,13,13,14}(余牌)

　　　　步骤二 –> 步骤三 –> 步骤四 == {2,3,4,11,12,12,13,13,14}(余牌) –>

　　　　步骤二 –> 步骤三 –> 步骤五 == {11,12,12,13,13,14}(余牌)–>

　　　　步骤二 –> 步骤三 –> 步骤五 == {12,13,14}(余牌)–>

　　　　步骤二 –> 步骤三 –> 步骤五 == {}(余牌) –>

　　　　步骤二 “能胡牌”

代码如下

public  static  bool  IsCanHU(List< int > mah,  int  ID)
{
     List< int > pais =  new  List< int >(mah);
 
     pais.Add(ID);
     //只有两张牌
     if  (pais.Count == 2)
     {
         return  pais[0] == pais[1];
     }
 
     //先排序
     pais.Sort();
 
     //依据牌的顺序从左到右依次分出将牌
     for  ( int  i = 0; i < pais.Count; i++)
     {
         List< int > paiT =  new  List< int >(pais);
         List< int > ds = pais.FindAll( delegate  ( int  d)
         {
             return  pais[i] == d;
         });
 
         //判断是否能做将牌
         if  (ds.Count >= 2)
         {
             //移除两张将牌
             paiT.Remove(pais[i]);
             paiT.Remove(pais[i]);
 
             //避免重复运算 将光标移到其他牌上
             i += ds.Count;
 
             if  (HuPaiPanDin(paiT))
             {
                 return  true ;
             }
         }
     }
     return  false ;
}
 
private  static  bool  HuPaiPanDin(List< int > mahs)
{
     if  (mahs.Count == 0)
     {
         return  true ;
     }
 
     List< int > fs = mahs.FindAll( delegate  ( int  a)
     {
         return  mahs[0] == a;
     });
 
     //组成克子
     if  (fs.Count == 3)
     {
         mahs.Remove(mahs[0]);
         mahs.Remove(mahs[0]);
         mahs.Remove(mahs[0]);
 
         return  HuPaiPanDin(mahs);
     }
     else
     {  //组成顺子
         if  (mahs.Contains(mahs[0] + 1) && mahs.Contains(mahs[0] + 2))
         {
             mahs.Remove(mahs[0] + 2);
             mahs.Remove(mahs[0] + 1);
             mahs.Remove(mahs[0]);
 
             return  HuPaiPanDin(mahs);
         }
         return  false ;
     }
}

原文链接

Unity3D 通用麻将胡牌算法 - JAVA说