赖子胡牌检测算法

先简单的说明一下,基于上一篇博客麻将胡牌算法使用的是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
}

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

欢迎讨论

Email huliuworld@yahoo.com
Github https://github.com/LHCoder2016/MahjongArithmetic.git

本文来自:简书

感谢作者:小黑_Coder

查看原文:赖子胡牌检测算法

• 编辑
• 预览