本文原创文章,转载注明出处,博客地址 https://segmentfault.com/u/to... 第一时间看后续精彩文章。觉得好的话,顺手分享到朋友圈吧,感谢支持。
笔者前段时间做过一款地方麻将游戏的后端,麻将游戏有个特点就是种类繁多,有的玩法木有癞子,有的玩法有4个癞子,有的甚至癞子数量更多,甚至有的有花牌(春夏秋冬等),有的红中可以代替宝牌,具体玩法笔者在此不介绍,做相关开发的自行研究玩法就好
查表法笔者看过其它的算法思路,比如查表法,首先生成好麻将牌型的表存文件中,通过将牌型与文件中的牌型进行对比,此类算法,简单玩法效率也挺高
缺点:
是要提前生成好表文件,并且,由于麻将玩法种类繁多,对于复杂的玩法,表记录非常多,多达数百万条记录,虽然算法中有剪枝,但是效率仍然没有显著优势 表文件读入到内存中,长期占用大量内存 移植性弱,换一种玩法,就得重新生成表数据在此笔者根据自己的经验总结出一种通用的麻将胡牌算法
思路满足M x ABC + N x DDD + EE 即可胡牌
下面表述中的 3同即DDD牌型,3连即ABC牌型,一对将即EE
一个有136张牌，万，饼，条，东西南北中发白34种牌,有四个癞子是直接就胡牌的，最坏的情况是有3个癞子,如果把癞子分别当做其中一张牌,3个癞子有34x34x34=39304接近4万种排列组合,这种算法明显不好
从另外一个大的思路出发,将手牌分离成宝,万,条,筒,风5个一维数组(同类型牌才能形成整扑或将),先不管出癞子,我先计算出剩下的牌形成整扑一将(整扑即ABC或DDD,将即EE),至少需要多少癞子,如果需要的癞子数量小于或等于手上有的癞子数量,即可胡牌
这里刚开始就分成宝,风5个一维数组的好处是:分类处理,简化后面的判断牌型逻辑,并且对于有花牌或其他特殊类型牌时,可根据玩法,适当调整或增加类型,容易扩展,通用处理方案,且单独提出函数,模块化,容易根据玩法修改
四种情况 将在[万]中,饼[风]必然是整扑 将在[饼]中,万[风]必然是整扑 将在[条]中,万[风]必然是整扑 将在[风]中,万[条]必然是整扑那么问题来了,如何判断形成整扑,需要的最少癞子数量?
经过分析,必须从小到大排序后,先去3同,再去3连,再去2同,再去2连,这些最容易形成整扑的去掉后,然后剩下的每张牌都需要2癞子,这才能得到最少的癞子数量
2连:某张牌如果能和后面的牌差为1或2
2同:如某张牌和下张牌相等
麻将的数据结构根据麻将牌的特别,通过百位数1,2,3,4,5区别牌类型,个位数代表具体哪张牌,方便后面算法中进行判断
整理代码如下:其中包含了特殊玩法的 制飞,十三烂,7对等特殊玩法的判断,读者可下载运行,
package algorithmimport ( "fmt" "sort" "log")/** * WuMing *2017/7/6 下午2:40 *针对瑞金麻将的函数 */var ( ruiJinmahjongArr = []int{ 101,102,103,104,105,106,107,108,109,//#万 101,101,201,202,203,204,205,206,207,208,209,//#饼 201,301,302,303,304,305,306,307,308,309,//#条 301,401,402,403,404,405,406,407,//# 东 西 南 北 中 发 白 401,501,502,503,504,//花(春夏秋冬) })/**吴名2017/7/10 下午5:263n+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) //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,按类型分组 //宝,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,去掉所有对子,得到单张数量 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,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,不能拆3同 return 1 + canlianNum + getNeedBaoNumToZhengPu(subarr[:len(subarr)-1]) //剩下的,最后1张牌拿去拼将去了(只能最后一张,104) } default: //101,不拆开3同(3同对形成顺子无影响) //举例总结:3同能参与形成顺子时,拆掉3同需要癞子数<=不拆,3同不能参与形成顺子时,3同利用不到,不能拆3同 switch t { case 4: if a[i] == a[i+2] { //3同对子,但是对形成顺子有影响(401,404) if i >= 1 && (a[i] <= 404 || a[i-1] >= 405) { //401,404 或 405,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,404 或 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,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:]...) 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张以上万筒条或风 //++++++++必须从小到大排序后,然后剩下牌两个一组分割算需要癞子数,这才能得到最少的癞子数量++++++++++ //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,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,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,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 { //如果祛除过顺子,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} arr := []int{101,409,501} t.Logf("烂胡:%v",lanHu(arr,104))}func Test_duIDuiHu(t *testing.T) { arr := []int{101,407} t.Logf("对对胡:%v",duIDuiHu(arr,407))}func Test_zhiFei(t *testing.T) { arr := []int{101,407} t.Logf("制飞:%v",zhiFei(arr,407))}func Test_isHU(t *testing.T) { arr := []int{101,407} t.Logf("胡:%v",isHU(arr,407))}func Benchmark_isHU(b *testing.B) { for i := 0; i < b.N; i++ { arr := []int{101,407} isHU(arr,407) //b.Logf("胡:%v",407)) } //b.RunParallel(func(pb *testing.PB) { // // for pb.Next() { // arr := []int{101,407} // isHU(arr,407) // //b.Logf("胡:%v",407)) // } //})} 性能测试结果 1s=10^3ms(毫秒)=10^6μs(微秒)=10^9ns(纳秒)
可胡牌:arr := []int{101,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,欢迎给予指正,希望和大神们共同进步 总结
以上是内存溢出为你收集整理的可带癞子的通用麻将胡牌算法全部内容，希望文章能够帮你解决可带癞子的通用麻将胡牌算法所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）