赖子胡牌检测算法

小黑_Coder · · 1611 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

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

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1611 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传