笔者前段时间做过一款地方麻将游戏的后端,麻将游戏有个特点就是种类繁多,有的玩法木有癞子,有的玩法有4个癞子,有的甚至癞子数量更多,甚至有的有花牌(春夏秋冬等),有的红中可以代替宝牌,具体玩法笔者在此不介绍,做相关开发的自行研究玩法就好
查表法
笔者看过其它的算法思路,比如查表法,首先生成好麻将牌型的表存文件中,通过将牌型与文件中的牌型进行对比,此类算法,简单玩法效率也挺高
缺点:
- 是要提前生成好表文件,并且,由于麻将玩法种类繁多,对于复杂的玩法,表记录非常多,多达数百万条记录,虽然算法中有剪枝,但是效率仍然没有显著优势
- 表文件读入到内存中,长期占用大量内存
- 移植性弱,换一种玩法,就得重新生成表数据
在此笔者根据自己的经验总结出一种通用的麻将胡牌算法
思路
满足M x ABC + N x DDD + EE 即可胡牌
下面表述中的 3同即DDD牌型,3连即ABC牌型,一对将即EE
image.png
一个有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 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,欢迎给予指正,希望和大神们共同进步
网友评论