可带癞子的通用麻将胡牌算法

tomorrowwu · · 4131 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

笔者前段时间做过一款地方麻将游戏的后端,麻将游戏有个特点就是种类繁多,有的玩法木有癞子,有的玩法有4个癞子,有的甚至癞子数量更多,甚至有的有花牌(春夏秋冬等),有的红中可以代替宝牌,具体玩法笔者在此不介绍,做相关开发的自行研究玩法就好

查表法

笔者看过其它的算法思路,比如查表法,首先生成好麻将牌型的表存文件中,通过将牌型与文件中的牌型进行对比,此类算法,简单玩法效率也挺高

缺点:

  1. 是要提前生成好表文件,并且,由于麻将玩法种类繁多,对于复杂的玩法,表记录非常多,多达数百万条记录,虽然算法中有剪枝,但是效率仍然没有显著优势
  2. 表文件读入到内存中,长期占用大量内存
  3. 移植性弱,换一种玩法,就得重新生成表数据

在此笔者根据自己的经验总结出一种通用的麻将胡牌算法

思路

满足M x ABC + N x DDD + EE 即可胡牌

下面表述中的 3同即DDD牌型,3连即ABC牌型,一对将即EE

一个有136张牌,万,饼,条,东西南北中发白34种牌,有四个癞子是直接就胡牌的,最坏的情况是有3个癞子,如果把癞子分别当做其中一张牌,3个癞子有34x34x34=39304接近4万种排列组合,这种算法明显不好

从另外一个大的思路出发,将手牌分离成宝,万,条,筒,风5个一维数组(同类型牌才能形成整扑或将),先不管出癞子,我先计算出剩下的牌形成整扑一将(整扑即ABC或DDD,将即EE),至少需要多少癞子,如果需要的癞子数量小于或等于手上有的癞子数量,即可胡牌

这里刚开始就分成宝,万,条,筒,风5个一维数组的好处是:分类处理,简化后面的判断牌型逻辑,并且对于有花牌或其他特殊类型牌时,可根据玩法,适当调整或增加类型,容易扩展,通用处理方案,且单独提出函数,模块化,容易根据玩法修改

四种情况
  1. 将在[万]中,饼[风]必然是整扑
  2. 将在[饼]中,万[风]必然是整扑
  3. 将在[条]中,万[风]必然是整扑
  4. 将在[风]中,万[条]必然是整扑

那么问题来了,如何判断形成整扑,需要的最少癞子数量?

经过分析,必须从小到大排序后,先去3同,再去3连,再去2同,再去2连,这些最容易形成整扑的去掉后,然后剩下的每张牌都需要2癞子,这才能得到最少的癞子数量

2连:某张牌如果能和后面的牌差为1或2

2同:如某张牌和下张牌相等

麻将的数据结构

根据麻将牌的特别,通过百位数1,2,3,4,5区别牌类型,个位数代表具体哪张牌,方便后面算法中进行判断

整理代码如下:

其中包含了特殊玩法的 制飞 ,十三烂,7对等特殊玩法的判断,读者可下载运行,

package algorithm

import (
    "fmt"
    "sort"
    "log"
)

/**
 * WuMing
 *2017/7/6 下午2:40
 *针对瑞金麻将的函数
 */

var (
    ruiJinmahjongArr = []int{
        101, 102, 103, 104, 105, 106, 107, 108, 109, //#万
        101, 102, 103, 104, 105, 106, 107, 108, 109,
        101, 102, 103, 104, 105, 106, 107, 108, 109,
        101, 102, 103, 104, 105, 106, 107, 108, 109,
        201, 202, 203, 204, 205, 206, 207, 208, 209, //#饼
        201, 202, 203, 204, 205, 206, 207, 208, 209,
        201, 202, 203, 204, 205, 206, 207, 208, 209,
        201, 202, 203, 204, 205, 206, 207, 208, 209,
        301, 302, 303, 304, 305, 306, 307, 308, 309, //#条
        301, 302, 303, 304, 305, 306, 307, 308, 309,
        301, 302, 303, 304, 305, 306, 307, 308, 309,
        301, 302, 303, 304, 305, 306, 307, 308, 309,
        401, 402, 403, 404, 405, 406, 407, //# 东 西 南 北 中 发 白
        401, 402, 403, 404, 405, 406, 407,
        401, 402, 403, 404, 405, 406, 407,
        401, 402, 403, 404, 405, 406, 407,
        501, 502, 503, 504, //花(春夏秋冬)
    }
)

/**
吴名
2017/7/10 下午5:26
3n+2牌型的胡牌
*/
func isHU(arr []int, bao int) bool {
    mjArr := append([]int{}, arr...)

    //宝,万,筒,条,风
    sptArr := seperateRuiJinArr(mjArr, bao)

    baoNum := len(sptArr[0]) //手牌中宝的数量
    if baoNum == 4 || (bao > 500 && baoNum == 3) {
        //飞
        log.Println("胡:所有的宝牌都在一家,飞")
        return false
    }

    //检测牌数量
    if len(mjArr)%3 != 2 {
        log.Println("牌数量不符合3n+2")
        return false
    }

    needBaoArr := [5]int{}
    for i := 1; i <= 4; i++ {
        a := append([]int{}, sptArr[i]...)
        needNum := getNeedBaoNumToZhengPu(a)
        needBaoArr[i] = needNum
    }

    // 吴名 2017/7/7 下午8:30 将在"万"中
    needBaoNum := needBaoArr[2] + needBaoArr[3] + needBaoArr[4]
    if needBaoNum <= baoNum {
        leftBaoNum := baoNum - needBaoNum //剩下可用于去拼 "万"成整扑一将的癞子数量
        num := getBaoNumToZhengPuJiang(sptArr[1])
        if leftBaoNum >= num {
            return true
        }
    }

    // 吴名 2017/7/7 下午8:30 将在"筒"中
    needBaoNum = needBaoArr[1] + needBaoArr[3] + needBaoArr[4]
    if needBaoNum <= baoNum {
        leftBaoNum := baoNum - needBaoNum //剩下可用于去拼 "筒"成整扑一将的癞子数量
        num := getBaoNumToZhengPuJiang(sptArr[2])
        if leftBaoNum >= num {
            return true
        }
    }

    // 吴名 2017/7/7 下午8:31 将在"条"中
    needBaoNum = needBaoArr[1] + needBaoArr[2] + needBaoArr[4]
    if needBaoNum <= baoNum {
        leftBaoNum := baoNum - needBaoNum //剩下可用于去拼 "条"成整扑一将的癞子数量
        num := getBaoNumToZhengPuJiang(sptArr[3])
        if leftBaoNum >= num {
            return true
        }
    }
    // 吴名 2017/7/7 下午8:31 将在"风"中
    needBaoNum = needBaoArr[1] + needBaoArr[2] + needBaoArr[3]
    if needBaoNum <= baoNum {
        leftBaoNum := baoNum - needBaoNum //剩下可用于去拼 "风"成整扑一将的癞子数量
        num := getBaoNumToZhengPuJiang(sptArr[4])
        if leftBaoNum >= num {
            return true
        }
    }
    return false
}

/**
吴名
2017/7/12 下午3:05
判断制飞是否成功:来任何一张牌都能胡(2,减去手上一张宝之后,剩下的牌形成整扑 1,减去手上一张宝之后,剩下的牌形成6对子)
*/
func zhiFei(arr []int, bao int) bool {
    mjArr := append([]int{}, arr...)

    //宝,万,筒,条,风
    sptArr := seperateRuiJinArr(mjArr, bao)

    //1:  13张牌,7对的制飞
    if len(mjArr) == 13 {
        danNum := 0
        for i, arr := range sptArr {
            l := len(arr)
            switch i {
            case 0:
                //宝不需要去除对子
                if l == 4 || (bao > 500 && l == 3) {
                    log.Println("对对胡:所有的宝牌都在一家,飞")
                    return false
                }
            default:
                danArr, _ := separate2Same(arr)
                danNum += len(danArr)
            }
        }
        //4,宝数量>=剩下的单张数量(去掉一张宝后,12张牌形成了6对)
        if len(sptArr[0])-1 >= danNum {
            log.Println("对对胡:制飞成功")
            return true
        }
    }

    //2, 减掉一张宝之后,剩下牌形成整扑

    //检测牌数量
    if len(mjArr)%3 != 1 {
        log.Println("牌数量不符合3n+1,不能飞")
        return false
    }

    needBaoNumToZhengPu := 0
    for i := 1; i <= 4; i++ {
        needBaoNumToZhengPu += getNeedBaoNumToZhengPu(sptArr[i])
    }
    if len(sptArr[0])-1 == needBaoNumToZhengPu {
        log.Println("3n+2胡:制飞成功")
        return true
    }
    return false
}

/**
吴名
2017/7/11 下午1:50
烂胡(在调用这个之前,已经排除了)
*/
func lanHu(arr []int, bao int) bool {

    mjArr := append([]int{}, arr...)

    //1,判断牌长度,必须为14
    if len(mjArr) != 14 {
        return false
    }
    //2,按类型分组
    //宝,万,筒,条,风
    sptArr := seperateRuiJinArr(mjArr, bao)
    //3,万筒条任意两张牌的差必须>=3
    //4,风牌任何两张牌不能相等
    for i, arr := range sptArr {
        l := len(arr)
        switch i {
        case 0:
            //宝不需要处理,只要万筒条风符合要求,不管几个宝,都可以配合
            if l == 4 || (bao > 500 && l == 3) {
                log.Println("烂胡:所有的宝牌都在一家,飞")
                return false
            }
        case 4:
            //风(任何两张不能相等)
            for j, _ := range arr {
                if j <= l-2 && arr[j] == arr[j+1] {
                    log.Println("烂胡:风相等")
                    return false
                }
            }
        default:
            //万筒条(差必须>=3),seperateRuiJinArr()返回的已经是排序后的
            for k, _ := range arr {
                if k <= l-2 && arr[k+1]-arr[k] <= 2 {
                    log.Println("烂胡:万筒条未跳两张")
                    return false
                }
            }
        }
    }
    log.Println("符合烂胡")
    return true
}

func duiDuiHu(arr []int, bao int) bool {

    mjArr := append([]int{}, arr...)

    //1,判断牌长度,必须为14
    if len(mjArr) != 14 {
        return false
    }
    //2,按类型分组
    //宝,万,筒,条,风
    sptArr := seperateRuiJinArr(mjArr, bao)
    //3,去掉所有对子,得到单张数量
    danNum := 0
    for i, arr := range sptArr {
        l := len(arr)
        switch i {
        case 0:
            //宝不需要去除对子
            if l == 4 || (bao > 500 && l == 3) {
                log.Println("对对胡:所有的宝牌都在一家,飞")
                return false
            }
        default:
            danArr, _ := separate2Same(arr)
            danNum += len(danArr)
        }
    }
    //4,宝数量>=剩下的单张数量
    if len(sptArr[0]) >= danNum {
        return true
    }
    return false
}

/**
吴名
2017/7/8 下午5:01
万,筒,条,风,成为整扑一将需要的最少癞子数量
*/
func getBaoNumToZhengPuJiang(arr []int) int {
    if len(arr) <= 0 {
        //如果数组为空,至少需要2个癞子组成一对将
        return 2
    }
    //寻找对子

    //吴名 2017/7/8 下午8:09 先去掉顺子的影响
    t := arr[0] / 100 //万筒条风类型
    a := []int{}
    switch t {
    case 4:
        a = separateFeng3Lian_ruiJin(arr)
    default:
        a, _ = separate3Lian(arr)
    }

    l := len(a)
    switch l {
    case 0:
        return 2
    case 1:
        return 1
    default:
        //可能是一张牌,两张牌,或3张牌
        for i, _ := range a {
            switch i {
            //只有2张牌,进入这里,为第一张
            case l - 2:
                if l == 2 && a[i] == a[i+1] {
                    //找到对子了
                    b := append(a[:i], a[i+2:]...)
                    return getNeedBaoNumToZhengPu(b)
                }
                //最后1张牌
            case l - 1:
                //到最后一张牌,还没有找到对子

                //此时的3同参与不了顺子
                subArr := separate3Same(a)
                //2连不能拿去拼对子
                //吴名 2017/7/10 上午11:53 分离2连,再形成对子(101,104,105)
                canLianNum := 0
                switch t {
                case 4:
                    subArr, canLianNum = separateFeng2Lian_ruiJin(subArr)
                default:
                    subArr, canLianNum, _ = separate2Lian(subArr, -1, false)
                }

                switch len(subArr) {
                case 0:
                    return canLianNum + 2
                case 1:
                    return canLianNum + 1
                default:
                    //101,105,105,105,不能拆3同

                    return 1 + canLianNum + getNeedBaoNumToZhengPu(subArr[:len(subArr)-1]) //剩下的,最后1张牌拿去拼将去了(只能最后一张,101,101,101,104)
                }
            default:

                //101,104,104,104,107,不拆开3同(3同对形成顺子无影响)

                //举例总结:3同能参与形成顺子时,拆掉3同需要癞子数<=不拆,3同不能参与形成顺子时,3同利用不到,不能拆3同
                switch t {
                case 4:
                    if a[i] == a[i+2] {
                        //3同对子,但是对形成顺子有影响(401,401,401,404)
                        if i >= 1 && (a[i] <= 404 || a[i-1] >= 405) {
                            //401,404,404,404 或 405,406,406,406
                            //3同能和前面形成顺子或有影响(包括4同)
                            b := append(a[:i], a[i+2:]...)
                            return getNeedBaoNumToZhengPu(b)
                        }
                        if l-i >= 4 && (a[i+3] <= 404 || a[i] >= 405) {
                            //403,403,403,404 或 406,406,406,407

                            //3同能和后面形成顺子或有影响(包括4同)
                            b := append(a[:i], a[i+2:]...)
                            return getNeedBaoNumToZhengPu(b)
                        }
                    } else {
                        //纯对子(非3同中的对子)
                        if a[i] == a[i+1] {
                            if i == 0 || a[i-1] != a[i] {
                                b := append(a[:i], a[i+2:]...)
                                return getNeedBaoNumToZhengPu(b)
                            }
                        }
                    }
                default:
                    if a[i] == a[i+2] {
                        //3同对子,但是对形成顺子有影响(101,103,103,103,105)
                        if i >= 1 && a[i]-a[i-1] <= 2 {
                            //3同能和前面形成顺子或有影响(包括4同)
                            b := append(a[:i], a[i+2:]...)
                            return getNeedBaoNumToZhengPu(b)
                        }
                        if l-i >= 4 && a[i+3]-a[i+2] <= 2 {
                            //3同能和后面形成顺子或有影响(包括4同)
                            b := append(a[:i], a[i+2:]...)
                            return getNeedBaoNumToZhengPu(b)
                        }
                    } else {
                        //纯对子(非3同中的对子)
                        if a[i] == a[i+1] {
                            if i == 0 || a[i-1] != a[i] {
                                b := append(a[:i], a[i+2:]...)
                                fmt.Println("b:", b)
                                return getNeedBaoNumToZhengPu(b)
                            }
                        }
                    }
                }
            }
        }
    }
    return 0
}

/**
吴名
2017/7/6 下午7:05
万,筒,条,风,成为顺子或者三连需要的癞子数量
*/
func getNeedBaoNumToZhengPu(subArr []int) int {
    length := len(subArr) //万的张数
    switch length {
    case 0:
        return 0
    case 1:
        return 2
    case 2:
        t := subArr[0] / 100 //万筒条风类型
        switch t {
        case 4:
            //风
            if subArr[1] <= 404 {
                //两个都是东南西北(不管做顺子或刻),东南西北任何三个也可以互吃
                return 1
            }
            if subArr[0] >= 405 {
                //两个都是中发白,中发白任何三个可以互吃
                return 1
            }
            //一个东南西北,一个是中法白
            return 4
        default:
            //万,筒,条
            d := subArr[1] - subArr[0] //subArr是已经经过排序的
            if d <= 2 {
                //1万1万,1万2万,1万3万
                return 1
            } else {
                //1万4万
                return 4
            }
        }
    default:
        //3张以上万筒条或风
        //++++++++必须从小到大排序后,先去3同,再去3连,再去2同,再去2连,这些最容易形成整扑的去掉后,然后剩下牌两个一组分割算需要癞子数,这才能得到最少的癞子数量++++++++++
        //1,分离3同
        subArr = separate3Same(subArr)
        if len(subArr) <= 2 {
            //去除3同后剩余牌数<=2,直接结束
            return getNeedBaoNumToZhengPu(subArr)
        }
        t := subArr[0] / 100 //万筒条风类型
        switch t {
        case 4:
            //风
            //2,分离3连
            subArr = separateFeng3Lian_ruiJin(subArr)
            l := len(subArr)
            if l <= 2 {
                return getNeedBaoNumToZhengPu(subArr)
            } else {
                needCount := 0
                //3,分离2同
                subArr, duiZiNum := separate2Same(subArr)
                needCount += duiZiNum //有多少个对子就需要多少个癞子把它变整扑
                //3,分离2连
                subArr, canLianNum := separateFeng2Lian_ruiJin(subArr)
                needCount += canLianNum + getNeedBaoNumToZhengPu(subArr)
                return needCount
            }
        default:
            //万或筒或条
            //2,分离3连
            subArr, _ = separate3Lian(subArr)
            l := len(subArr)
            if l <= 2 {
                return getNeedBaoNumToZhengPu(subArr)
            } else {
                needCount := 0
                //3,分离2同和2连(相当于只需要1癞子就能成的牌都去掉)
                subArr, canLianOrSameNum, _ := separate2LianAnd2Same(subArr, -1, false)
                needCount += canLianOrSameNum + getNeedBaoNumToZhengPu(subArr) //有多少个对子或2连就需要多少个癞子把它变整扑
                return needCount
            }
        }
    }
}

/**
吴名
2017/7/8 上午11:54
分离2连(风,适用):返回去除后的数组,以及2连数量(里面3顺子,对子必须提前已去除)
*/
func separateFeng2Lian_ruiJin(arr []int) ([]int, int) {
    is := false
    lianNum := 0

    l := len(arr)
    for i, _ := range arr {
        if arr[i] != 0 && i <= l-2 {
            if arr[i+1] <= 404 || arr[i] >= 405 {
                //1,东南西北三张互吃 2,中发白互吃(对子前一步已经去除,所以不可能相等)
                arr[i] = 0
                arr[i+1] = 0
                lianNum++
                is = true
                break
            }
        }
    }

    if is {
        //如果祛除过顺子,那么需要清洗0之后继续祛除
        r := []int{}
        for _, v := range arr {
            if v != 0 {
                r = append(r, v)
            }
        }
        a, num := separateFeng2Lian_ruiJin(r)
        return a, lianNum + num
    } else {
        return arr, 0
    }
}

/**
吴名
2017/7/7 下午5:45
分离顺子(针对风):东南西北任何三个也可以互吃,中发白任何三个可以互吃
*/
func separateFeng3Lian_ruiJin(arr []int) []int {
    is := false
    for i, _ := range arr {
        //前3张无对子的情况下(401,402,403,404)
        if i <= len(arr)-3 {
            if arr[i+2] <= 404 && arr[i] != arr[i+1] && arr[i+1] != arr[i+2] {
                //连续3张都是中南西北,且三张各不相等,可以互吃
                arr[i] = 0
                arr[i+1] = 0
                arr[i+2] = 0
                //log.Println("去除顺子:%v", arr)
                is = true
                break
            }
            if arr[i] == 405 && arr[i+1] == 406 && arr[i+2] == 407 {
                //连续3张是中发白
                arr[i] = 0
                arr[i+1] = 0
                arr[i+2] = 0
                //log.Println("去除顺子:%v", arr)
                is = true
                break
            }
        }
        //前3张有对子的情况下(401,401,402,403,404)
        if i <= len(arr)-4 {
            if arr[i+3] <= 404 && arr[i] != arr[i+1] && arr[i+1] != arr[i+3] {
                arr[i] = 0
                arr[i+1] = 0
                arr[i+3] = 0
                //log.Println("去除顺子:%v", arr)
                is = true
                break
            }
        }
    }
    if is {
        //如果祛除过顺子,那么需要清洗0之后继续祛除
        r := []int{}
        for _, v := range arr {
            if v != 0 {
                r = append(r, v)
            }
        }
        return separateFeng3Lian_ruiJin(r)
    } else {
        return arr
    }
}

/**
吴名
2017/7/6 下午4:27
分割 宝,万,筒,条,风
*/
func seperateRuiJinArr(mjArr []int, bao int) [5][]int {
    result := [5][]int{}
    for _, mj := range mjArr {
        index := mj / 100
        //宝是花牌
        if bao > 500 {
            switch index {
            case 5:
                //宝
                result[0] = append(result[0], mj)
            default:
                result[index] = append(result[index], mj)
            }
        } else {
            switch index {
            case 5:
                //此时花牌处理成宝的本位牌
                i := bao / 100
                result[i] = append(result[i], bao)
            default:
                if mj == bao {
                    //宝
                    result[0] = append(result[0], mj)
                } else {
                    result[index] = append(result[index], mj)
                }
            }
        }
    }
    //升序排列
    for _, arr := range result {
        sort.Sort(sort.IntSlice(arr))
    }
    return result
}

单元测试及性能测试:

func Test_lanHu(t *testing.T) {
    //arr := []int{101, 104, 104, 104, 104}
    arr := []int{101, 104, 104, 107, 201, 204, 209, 302, 305, 309, 403, 406, 409, 501}
    t.Logf("烂胡:%v", lanHu(arr, 104))
}

func Test_duiDuiHu(t *testing.T) {
    arr := []int{101, 101, 104, 104, 201, 201, 209, 209, 305, 306, 407, 407, 407, 407}
    t.Logf("对对胡:%v", duiDuiHu(arr, 407))
}

func Test_zhiFei(t *testing.T) {
    arr := []int{101, 101, 104, 104, 201, 201, 209, 209, 305, 306, 407, 407, 407}
    t.Logf("制飞:%v", zhiFei(arr, 407))
}

func Test_isHU(t *testing.T) {
    arr := []int{101, 101, 104, 104, 201, 201, 209, 209, 305, 306, 307, 407, 407, 407}
    t.Logf("胡:%v", isHU(arr, 407))
}
func Benchmark_isHU(b *testing.B) {

    for i := 0; i < b.N; i++ {
        arr := []int{101, 101, 104, 104, 201, 201, 209, 209, 305, 306, 307, 407, 407, 407}
        isHU(arr, 407)
        //b.Logf("胡:%v", isHU(arr, 407))
    }

    //b.RunParallel(func(pb *testing.PB) {
    //
    //    for pb.Next() {
    //        arr := []int{101, 101, 104, 104, 201, 201, 209, 209, 305, 306, 307, 407, 407, 407}
    //        isHU(arr, 407)
    //        //b.Logf("胡:%v", isHU(arr, 407))
    //    }
    //})
}

性能测试结果

1s=10^3ms(毫秒)=10^6μs(微秒)=10^9ns(纳秒)
可胡牌:
arr := []int{101, 101, 104, 104, 201, 201, 209, 209, 305, 306, 307, 407, 407, 407}

可胡牌情况下,一次判断只需要4822ns,即一秒钟可以执行约20万次判断,如果牌数量更少时的n%3=2,则效率更高

pkg: dataStructures-algorithm-demo/麻将相关算法
300000          4822 ns/op
--- BENCH: Benchmark_isHU-8
    ruijinMjHu_test.go:95: 胡:true

不可胡牌时,效率比可胡牌的牌型效率略高一些

pkg: dataStructures-algorithm-demo/麻将相关算法
500000          3711 ns/op
--- BENCH: Benchmark_isHU-8
    ruijinMjHu_test.go:95: 胡:false

综上,此算法不仅效率很高,且通用性很强(任何类型玩法的麻将都可用)

完整代码已上传GitHub,欢迎star并提出优化建议,如发现bug,欢迎给予指正,希望和大神们共同进步


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:tomorrowwu

查看原文:可带癞子的通用麻将胡牌算法

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

4131 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传