先简单的说明一下,基于上一篇博客麻将胡牌算法使用的是
Lua
语言,有一些同学私信我,之后博客能不能使用大众一点的后端语言,所以这篇博客将使用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
}
注意:在组成 将 的过程中可能一个花色里面都没有剩余牌,此时应该使用两个赖子组成一个 将
欢迎讨论
Email huliuworld@yahoo.com
Github https://github.com/LHCoder2016/MahjongArithmetic.git
有疑问加站长微信联系(非本文作者)