赖子胡牌检测算法

小黑_Coder · · 2249 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

先简单的说明一下，基于上一篇博客麻将胡牌算法使用的是Lua语言，有一些同学私信我，之后博客能不能使用大众一点的后端语言，所以这篇博客将使用Google强力推荐的后端语言Golang。不过在这里值得一提的是，编程特别是算法更应该注重的是思想，编程语言本身并不会流露出你的算法能力和设计思想，语言只是表达你思想的一个工具而已。装逼到此结束，进入正文我们来讨论一下赖子胡牌应该怎么检测

当然一些麻将中使用到的基本名词和胡牌规则，在这里就不在重复解释了。如果不了解的可以参考上一篇博客麻将胡牌算法

赖子胡牌

胡牌规则和普通胡牌一样，不过出现了一个赖子牌。这张牌可以是任意牌，如果我们依然按照普通胡牌算法那样检测去遍历的话，即使只算万,筒,条我们简单的计算一下麻将共有27种牌。如果有四个赖子，那么赖子检测算法的时间复杂度将是普通胡牌算法的27 * 27 * 27 * 27倍，最坏的情况将是最后一种情况能胡牌，那么就比普通胡牌算法多检测19683次，按照目前的PC性能来看其实还是可以接受的，不过我们通过算法可以去优化那何乐而不为呢。

遍历检测

在优化之前我们还是先说说如何遍历去检测赖子胡牌，因为这不是这篇博客讨论的重点，所以只是简单的介绍一下便利的思想。

去除手牌赖子

// 去除赖子牌 func getAndRmoveLaiZiCard(cardList []int) []int { laiZiCardList := make([]int, 0, len(allLaiZiCardList)) for i := 0; i < len(cardList); i++ { for _, laiZiValue := range allLaiZiCardList { if laiZiValue == cardList[i] { laiZiCardList = append(laiZiCardList, cardList[i]) cardList[i] = 0 break } } } return laiZiCardList }

这一步主要目的有两个
- 获取手上的赖子牌，便于之后将赖子作为任意一张牌放入手牌
- 去除手中的赖子牌，便于加入一种赖子牌组成新的手牌

组合手牌(遍历赖子胡牌检测算法的关键)

// 赖子胡牌检测(遍历) func checkLaiZiHu(cardList []int, laiZiCount int) bool { for _, mahjongValue := range mahjongValueList { tempCardList := append(cardList, mahjongValue) if laiZiCount == 1 { checkCount++ mahjongMatrix := getMahjongMatrixWithCardList(tempCardList) printCardsInfoByMahjongMatrix(mahjongMatrix) isHu := checkHu(mahjongMatrix) if isHu { return isHu } } else if laiZiCount > 1 { isHu := checkLaiZiHu(tempCardList, laiZiCount-1) if isHu { return isHu } } } return false }

上面我们提到了，胡牌检测的时候一张赖子牌可以作为任意牌出现在手牌中。一个赖子的时候毫无疑问，赖子组合有27种(只涉及万，筒，条三种花色)。那么两个赖子的时候就是27*27种组合了。因此上面使用递归的算法去创建每一种组合。

胡牌检测

因为在上一步已经构造好赖子组合并且加入到手牌中，因此只需要将手牌按照普通胡牌检测方法检测即可。

胡牌检测

// 检测胡牌 func checkHu(mahjongMatrix MahjongMatrix) bool { mahjongMatrixList := getMahjongMatrixListByRemoveTwoCards(mahjongMatrix) for i := 0; i < len(mahjongMatrixList); i++ { removeThreeLinkCards(&mahjongMatrixList[i]) removeTheSameThreeCards(&mahjongMatrixList[i]) isHu := checkMatrixAllElemEqualZero(mahjongMatrixList[i]) if isHu { return isHu } } return false }

去除麻将矩阵中一个将之后的麻将矩阵列表

// 通过去除麻将矩阵中一个将之后的麻将矩阵列表 func getMahjongMatrixListByRemoveTwoCards(mahjongMatrix MahjongMatrix) []MahjongMatrix { var mahjongMatrixList []MahjongMatrix for i := 0; i < 3; i++ { for j := 0; j < 12; j++ { if mahjongMatrix[i][j] >= 2 { temp := mahjongMatrix temp[i][j] -= 2 mahjongMatrixList = append(mahjongMatrixList, temp) } } } return mahjongMatrixList }

去除句子

// 去除句子 func removeThreeLinkCards(mahjongMatrix *MahjongMatrix) { for i := 0; i < len(mahjongMatrix); i++ { for j := 0; j < len(mahjongMatrix[i])-2; j++ { if mahjongMatrix[i][j] > 0 && mahjongMatrix[i][j+1] > 0 && mahjongMatrix[i][j+2] > 0 { mahjongMatrix[i][j] -= 1 mahjongMatrix[i][j+1] -= 1 mahjongMatrix[i][j+2] -= 1 j-- } } } }

注意：可能存在0x0101, 0x0102, 0x0201, 0x0202, 0x0301, 0x0302这个样的牌，因此检测到一个句子之后，需要执行j--避免漏掉一个句子的检测

去除克子

// 去除克子 func removeTheSameThreeCards(mahjongMatrix *MahjongMatrix) { for i := 0; i < len(mahjongMatrix); i++ { for j := 0; j < len(mahjongMatrix[i]); j++ { if mahjongMatrix[i][j] >= 3 { mahjongMatrix[i][j] -= 3 } } } }

检测矩阵中元素是否全为零

// 检测矩阵中元素是否全为0 func checkMatrixAllElemEqualZero(mahjongMatrix MahjongMatrix) bool { for i := 0; i < len(mahjongMatrix); i++ { for j := 0; j < len(mahjongMatrix[i]); j++ { if mahjongMatrix[i][j] != 0 { return false } } } return true }

计数检测

计数检测，就是对遍历检测的一种优化。计数的思想就除先去除赖子牌之后剩余的牌进行胡牌检测，然后检测还没有组成刻字顺子将的牌需要多少个赖子牌才能组成将赖子克子。如果需要的个数大于已有赖子个数则不能胡牌，否则可以胡牌。

计数赖子

首先将赖子牌从手牌中移除并且记录赖子的个数，这个算法与上面的去除赖子算法一致，可以参考上面去除赖子算法。

去除克子和句子

将除去赖子牌后剩余牌放入麻将矩阵中进行胡牌检测，算法与上面的胡牌检测算法一致，可以参考上面胡牌检测算法。

检测麻将矩阵中剩余牌

计算将麻将矩阵中剩余牌凑出一个将所需要的赖子个数
计算剩余的牌组成克子顺子所需要的赖子个数
总共需要赖子个数如果小于等于手中所持有赖子个数则胡牌

func checkLaiZiHu(cardList []int, laiZiCount int) bool { mahjongMatrix := getMahjongMatrixWithCardList(cardList) removeThreeLinkCards(&mahjongMatrix) removeTheSameThreeCards(&mahjongMatrix) for i := 0; i < len(mahjongMatrix); i++ { for j := 0; j < len(mahjongMatrix[i]); j++ { if mahjongMatrix[i][j] > 0 { tempMahjong := mahjongMatrix needLaiZiCount := tempMahjong[i][j] % 2 tempMahjong[i][j] = 0 needLaiZiCount = getNeedLaiZiCountByMahjongMatrix(tempMahjong, needLaiZiCount) if needLaiZiCount <= laiZiCount { return true } } } needLaiZiCount := getNeedLaiZiCountByMahjongMatrix(mahjongMatrix, 2) if needLaiZiCount <= laiZiCount { return true } } return false } // 计算需要赖子的数量 func getNeedLaiZiCountByMahjongMatrix(mahjongMatrix MahjongMatrix, needLaiZiCount int) int { minLaiZiCount := needLaiZiCount if !checkMatrixAllElemEqualZero(mahjongMatrix) { for i := 0; i < len(mahjongMatrix); i++ { for j := 0; j < len(mahjongMatrix[i]); j++ { if mahjongMatrix[i][j] <= 0 { continue } if mahjongMatrix[i][j+1] > 0 { mahjongMatrix[i][j]-- mahjongMatrix[i][j+1]-- j-- minLaiZiCount++ continue } if mahjongMatrix[i][j+2] > 0 { mahjongMatrix[i][j]-- mahjongMatrix[i][j+2]-- j-- minLaiZiCount++ continue } if mahjongMatrix[i][j] == 1 { mahjongMatrix[i][j]-- minLaiZiCount += 2 continue } if mahjongMatrix[i][j] == 2 { mahjongMatrix[i][j] -= 2 minLaiZiCount++ } } } } return minLaiZiCount }

注意：在组成将的过程中可能一个花色里面都没有剩余牌，此时应该使用两个赖子组成一个将