记录下麻将胡牌算法

2024-02-01后端10 分钟428 次阅读
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面

前言

最近在学习用 Go 写一个麻将游戏服务端的逻辑,其中在写胡牌逻辑时,使用了穷举法的逻辑,列举了麻将所有胡牌的可能性,之后根据手牌的类型去查表即可得出当前是否胡牌,算是一种用空间换时间的算法。

麻将胡牌逻辑

麻将的胡牌逻辑是一项复杂而有趣的规则,其中包括对刻子、顺子、将牌等的组合。下面是对麻将胡牌逻辑的简要描述:

  1. 牌型组合: 一副合法的胡牌需要满足以下条件:
    • 必须有 14 张牌。
    • 必须包含一对将牌,将牌是相同的两张牌。
    • 其余的 12 张牌可以是刻子、顺子、杠、将牌的组合。
  2. 刻子: 刻子是由三张相同的牌组成的组合。在胡牌逻辑中,可以包含任意数量的刻子。
  3. 顺子: 顺子是由三张连续数字的牌组成的组合。在胡牌逻辑中,可以包含任意数量的顺子。
  4. 杠: 杠是由四张相同的牌组成的组合,可以是明杠(已经亮出)或暗杠(未亮出)。在胡牌逻辑中,可以包含任意数量的杠。
  5. 将牌: 将牌是相同的两张牌,是胡牌的关键之一。

总体来说,麻将的胡牌逻辑是相当灵活的,允许不同组合形式的牌型。这种规则的灵活性也导致了不同地区和不同规则集中的胡牌条件可能有所不同。在具体的麻将规则中,可能还会包括一些特殊的胡牌条件,例如七对子、清一色、字一色等,这些条件也会影响到胡牌的逻辑。

代码实现

这里我以红中麻将为例。下边是部分核心代码的实现,主要记录下逻辑实现的过程。

实体枚举抽取

proto.go,这里主要存放一些游戏状态枚举、类型别名、需要用到的逻辑方法抽取等。

go 复制代码
type CardID int

type CardIDs []CardID

func (c CardIDs) Len() int {
	return len(c)
}
func (c CardIDs) Less(i, j int) bool {
	return c[i] < c[j]
}
func (c CardIDs) Swap(i, j int) {
	c[i], c[j] = c[j], c[i]
}

type OperateType int

const (
	OperateTypeNone OperateType = iota
	HuChi                       //吃胡
	HuZi                        //自摸
	Peng                        //碰
	GangChi                     //吃杠
	GangBu                      //补杠
	GangZi                      //自摸杠
	Guo                         //过
	Qi                          //弃
	Get                         //拿牌
)

type GameStatus int

const (
	GameStatusNone GameStatus = iota
	Dices                     //掷骰子
	SendCards                 //发牌
	Playing                   //游戏
	ZhaMa                     //扎码
	Result                    //结算
)

type GameStatusTm int

const (
	GameStatusTmNone   GameStatusTm = 0
	GameStatusTmDices               = 3 //掷骰子
	GameStatusTmSend                = 3 //发牌
	GameStatusTmPlay                = 0 //游戏
	GameStatusTmZha                 = 5 //扎码
	GameStatusTmResult              = 5 //结算
)

type GameType int

const (
	HongZhong4 GameType = 1
	HongZhong8          = 2
)

utils.go 工具代码,这里就只放个随机数方法吧。

go 复制代码
func Rand(n int) int {
	rand.New(rand.NewSource(time.Now().UnixNano()))
	return rand.Intn(n)
}

逻辑抽取

logic.go代码,这块代码主要是对麻将相关操作的逻辑代码,例如洗牌、发牌、取牌、判断是否胡牌等。

go 复制代码
package mj

import (
	"common/utils"
	"game/component/mj/mp"
	"game/component/mj/mp/alg"
	"sync"
)

// 牌枚举
const (
	Wan1  mp.CardID = 1
	Wan2  mp.CardID = 2
	Wan3  mp.CardID = 3
	Wan4  mp.CardID = 4
	Wan5  mp.CardID = 5
	Wan6  mp.CardID = 6
	Wan7  mp.CardID = 7
	Wan8  mp.CardID = 8
	Wan9  mp.CardID = 9
	Tong1 mp.CardID = 11
	Tong2 mp.CardID = 12
	Tong3 mp.CardID = 13
	Tong4 mp.CardID = 14
	Tong5 mp.CardID = 15
	Tong6 mp.CardID = 16
	Tong7 mp.CardID = 17
	Tong8 mp.CardID = 18
	Tong9 mp.CardID = 19
	Tiao1 mp.CardID = 21
	Tiao2 mp.CardID = 22
	Tiao3 mp.CardID = 23
	Tiao4 mp.CardID = 24
	Tiao5 mp.CardID = 25
	Tiao6 mp.CardID = 26
	Tiao7 mp.CardID = 27
	Tiao8 mp.CardID = 28
	Tiao9 mp.CardID = 29
	Dong  mp.CardID = 31
	Nan   mp.CardID = 32
	Xi    mp.CardID = 33
	Bei   mp.CardID = 34
	Zhong mp.CardID = 35
)

type Logic struct {
	sync.RWMutex
	cards    []mp.CardID
	gameType GameType
	qidui    bool
	huLogic  *alg.HuLogic // 胡牌逻辑
}

func NewLogic(gameType GameType, qidui bool) *Logic {
	return &Logic{
		gameType: gameType,
		qidui:    qidui,
		huLogic:  alg.NewHuLogic(),
	}
}

// washCards 洗牌
func (l *Logic) washCards() {
	l.Lock()
	defer l.Unlock()
	l.cards = []mp.CardID{
		Wan1, Wan2, Wan3, Wan4, Wan5, Wan6, Wan7, Wan8, Wan9,
		Wan1, Wan2, Wan3, Wan4, Wan5, Wan6, Wan7, Wan8, Wan9,
		Wan1, Wan2, Wan3, Wan4, Wan5, Wan6, Wan7, Wan8, Wan9,
		Wan1, Wan2, Wan3, Wan4, Wan5, Wan6, Wan7, Wan8, Wan9,
		Tong1, Tong2, Tong3, Tong4, Tong5, Tong6, Tong7, Tong8, Tong9,
		Tong1, Tong2, Tong3, Tong4, Tong5, Tong6, Tong7, Tong8, Tong9,
		Tong1, Tong2, Tong3, Tong4, Tong5, Tong6, Tong7, Tong8, Tong9,
		Tong1, Tong2, Tong3, Tong4, Tong5, Tong6, Tong7, Tong8, Tong9,
		Tiao1, Tiao2, Tiao3, Tiao4, Tiao5, Tiao6, Tiao7, Tiao8, Tiao9,
		Tiao1, Tiao2, Tiao3, Tiao4, Tiao5, Tiao6, Tiao7, Tiao8, Tiao9,
		Tiao1, Tiao2, Tiao3, Tiao4, Tiao5, Tiao6, Tiao7, Tiao8, Tiao9,
		Tiao1, Tiao2, Tiao3, Tiao4, Tiao5, Tiao6, Tiao7, Tiao8, Tiao9,
		Zhong, Zhong, Zhong, Zhong,
	}
	if l.gameType == HongZhong8 {
		l.cards = append(l.cards, Zhong, Zhong, Zhong, Zhong)
	}
	for i := 0; i < 300; i++ {
		index := i % len(l.cards)
		random := utils.Rand(len(l.cards))
		// 交换下位置
		l.cards[index], l.cards[random] = l.cards[random], l.cards[index]
	}
}

// getCards 获取开局的手牌
func (l *Logic) getCards(num int) []mp.CardID {
	//发牌之后 牌就没了
	l.Lock()
	defer l.Unlock()
	if len(l.cards) < num {
		return nil
	}
	// 发出牌并减去
	cards := l.cards[:num]
	l.cards = l.cards[num:]
	return cards
}

// getRestCardsCount 剩余牌的数量
func (l *Logic) getRestCardsCount() int {
	return len(l.cards)
}

// getCard 取牌
func (l *Logic) getCard(card mp.CardID) mp.CardID {
	// 查看这副牌是否在这里面,并返回他的位置
	indexOf := alg.IndexOf(l.cards, card)
	if indexOf == -1 {
		return 0
	}
	// 将其中牌中抽走
	l.cards = append(l.cards[:indexOf], l.cards[indexOf+1:]...)
	return card
}

// canHu 是否可以胡牌
func (l *Logic) canHu(cards []mp.CardID, card mp.CardID) bool {
	//胡牌判断 复杂的一套逻辑
	return l.huLogic.CheckHu(cards, []mp.CardID{Zhong}, card)
}

字典表

table.go,这里主要用于存储胡牌的可能性,放在内存中,后续也可以放入缓存等数据库中。

go 复制代码
package alg

import (
	"strconv"
)

// Table 字典表
// 1A-9A B C 非字牌 一样 生成一种就行 D生成一种(没有连子的)
// 穷举所有胡牌可能 存入Table0  D TableFeng0
// 有1个鬼 将Table0中的数据 替换一个 然后存入 Table1
// 有2个鬼 将Table0中的数据 替换2个 然后存入 Table2
// 有3个鬼 将Table0中的数据 替换3个 然后存入 Table3
// 有4个鬼 将Table0中的数据 替换4个 然后存入 Table4
// 有5个鬼 将Table0中的数据 替换5个 然后存入 Table5
// 有6个鬼 将Table0中的数据 替换6个 然后存入 Table6
// 有7个鬼 将Table0中的数据 替换7个 然后存入 Table7
type Table struct {
	keyDic        map[string]bool         //非字牌ABC(万、筒、条) 无鬼 字典
	keyGuiDic     map[int]map[string]bool //非字牌ABC 有鬼 字典
	keyFengDic    map[string]bool         //字牌D(东、西、南、北、发、中) 无鬼 字典
	keyFengGuiDic map[int]map[string]bool //字牌D 有鬼 字典
}

// NewTable 生成胡牌字典表
func NewTable() *Table {
	t := &Table{
		keyDic:        make(map[string]bool),
		keyGuiDic:     make(map[int]map[string]bool),
		keyFengDic:    make(map[string]bool),
		keyFengGuiDic: make(map[int]map[string]bool),
	}
	t.gen()
	return t
}

// gen 生成字典
func (t *Table) gen() {
	//311100000 一种hu可能
	cards := []int{0, 0, 0, 0, 0, 0, 0, 0, 0}
	level := 0
	jiang := false // 是否将牌
	feng := false  // 是否风牌
	t.genTableNoGui(cards, level, jiang, feng)
	//挨个去替换即可
	t.genTableGui(feng)
	feng = true // 有风牌的情况
	t.genTableNoGui(cards, level, jiang, feng)
	t.genTableGui(feng)
	//t.save()
}

// genTableNoGui 无鬼牌
func (t *Table) genTableNoGui(cards []int, level int, jiang bool, feng bool) {
	//生成的逻辑 比较简单
	//ABC
	//挨个去放 AAA组合 刻子   14张  3+3+3+2+3 5个层级  最多递归5次就可以
	//ABC 连子
	//DD 将 这个只能有一个 jiang=true
	for i := 0; i < 9; i++ {
		//feng 东南西北中发白 7张牌*4  春夏秋冬梅兰竹菊 没用的牌
		// 这里只算东、西、南、北、发财、白板、红中七种牌的情况,所以只计算到6即可
		if feng && i > 6 {
			continue
		}
		// 1. 需要先将cards中的牌数量计算出来,后续做判断用
		totalCardCount := t.calTotalCardCount(cards)
		// 这种情况生成一个AAA 刻子   某个位置的牌最多只能放四张牌,所以要cards[i]<=1
		if totalCardCount <= 11 && cards[i] <= 1 {
			cards[i] += 3
			// 计算当前的编码
			key := t.generateKey(cards)
			if feng {
				t.keyFengDic[key] = true
			} else {
				t.keyDic[key] = true
			}
			if level < 5 {
				t.genTableNoGui(cards, level+1, jiang, feng)
			}
			// 减去,重新计算其它可能
			cards[i] -= 3
		}
		//连子 ABC
		//在非风牌的情况下,如果当前位置及其后两个位置的牌数量均小于等于3,且总牌数小于等于11,
		//则可以将这三个位置的牌各加上1张,表示生成一个 ABC 连子
		if !feng && totalCardCount <= 11 && i < 7 && cards[i] <= 3 &&
			cards[i+1] <= 3 && cards[i+2] <= 3 {
			cards[i] += 1
			cards[i+1] += 1
			cards[i+2] += 1
			key := t.generateKey(cards)
			t.keyDic[key] = true
			if level < 5 {
				t.genTableNoGui(cards, level+1, jiang, feng)
			}
			// 减去,重新计算其它可能
			cards[i] -= 1
			cards[i+1] -= 1
			cards[i+2] -= 1
		}
		//DD 将
		//在未生成将牌的情况下,如果当前位置的牌数量小于等于2,且总牌数小于等于12,
		//则可以将该位置的牌加上2张,表示生成一个 DD 将
		if !jiang && totalCardCount <= 12 && cards[i] <= 2 {
			cards[i] += 2
			key := t.generateKey(cards)
			if feng {
				t.keyFengDic[key] = true
			} else {
				t.keyDic[key] = true
			}
			if level < 5 {
				t.genTableNoGui(cards, level+1, true, feng)
			}
			// 减去,重新计算其它可能
			cards[i] -= 2
		}
	}
}

// save 保存
func (t *Table) save() {
	// TODO  缓存或者数据库存储起来
}

// calTotalCardCount 计算cards中牌的数量
func (t *Table) calTotalCardCount(cards []int) int {
	count := 0
	for _, v := range cards {
		count += v
	}
	return count
}

// generateKey 计算编码,每个位置的数量
func (t *Table) generateKey(cards []int) string {
	key := ""
	dic := []string{"0", "1", "2", "3", "4"}
	for _, v := range cards {
		key += dic[v] // 进行字符串拼接 310013000
	}
	return key
}

// genTableGui 生成带鬼的牌情况
func (t *Table) genTableGui(feng bool) {
	// 根据是否带风牌进行处理鬼牌
	dic := t.keyDic
	if feng {
		dic = t.keyFengDic
	}
	//311200000  3 1 1 2 分表 3-1   211200000
	for k := range dic {
		// 将当前的编码转为整形数组
		cards := t.toNumberArray(k)
		// 从只有一张鬼牌的情况开始,最多可以有八种鬼牌的情况
		t.genGui(cards, 1, feng)
	}
}

// toNumberArray 将编码转为整形数组
func (t *Table) toNumberArray(k string) []int {
	cards := make([]int, len(k))
	for i := 0; i < len(k); i++ {
		// 将字符串数字转为整形数字
		card, _ := strconv.Atoi(k[i : i+1])
		cards[i] = card
	}
	return cards
}

// genGui 生成鬼牌
func (t *Table) genGui(cards []int, guiCount int, feng bool) {
	for i := 0; i < 9; i++ {
		//此位置没有牌,就无需替换
		if cards[i] == 0 {
			continue
		}
		cards[i]-- // 减去一个牌,代表它可以被鬼牌代替
		//需要判断其有没有 有就不处理 没有就添加到字典中
		if !t.tryAdd(cards, guiCount, feng) {
			cards[i]++ // 无需处理,则重新加回去,恢复成没有被鬼牌代替的情况,接着处理下一种被鬼牌代替的情况
			continue
		}
		// 等于8的话,就直接胡了,这里就没必要计算了
		// 例如:1条 5条 9条 9条 8筒 3万 西风 这里七张牌
		// 七个鬼牌代替:2条、3条、9条、西风、三万、三万、5条,胡不了
		// 1条 9条 9条 8筒 3万 西风 这里六张牌
		// 八个鬼牌代替:西风、2条、3条、9条、三万、三万、8筒、8筒,胡了
		// 组成是西风、西风(将子),1条、2条、3条(顺子),9条、9条、9条(刻子),三万、三万、三万(刻子)、8筒、8筒、8筒(刻子)
		if guiCount < 8 {
			t.genGui(cards, guiCount+1, feng)
		}
		cards[i]++
	}
}

// findCards 从胡牌表中查询对应的牌
func (t *Table) findCards(cards []int, guiCount int, feng bool) bool {
	// 先编码
	key := t.generateKey(cards)
	// 有鬼牌的情况
	if guiCount > 0 {
		// 根据鬼牌数以及编码查看是否有胡牌的可能
		if feng {
			_, ok := t.keyFengGuiDic[guiCount][key]
			if ok {
				return true
			}
		} else {
			_, ok := t.keyGuiDic[guiCount][key]
			if ok {
				return true
			}
		}
	} else {
		if feng {
			_, ok := t.keyFengDic[key]
			if ok {
				return true
			}
		} else {
			_, ok := t.keyDic[key]
			if ok {
				return true
			}
		}
	}
	return false
}

// tryAdd 尝试添加到鬼牌字典中
func (t *Table) tryAdd(cards []int, guiCount int, feng bool) bool {
	// 非法情况处理
	for i := 0; i < 9; i++ {
		if cards[i] < 0 || cards[i] > 4 {
			return false
		}
	}
	key := t.generateKey(cards)
	if feng {
		if t.keyFengGuiDic[guiCount] == nil {
			t.keyFengGuiDic[guiCount] = make(map[string]bool)
		}
		// 判断有风牌的情况,该鬼牌情况是否存在
		_, ok := t.keyFengGuiDic[guiCount][key]
		if ok {
			return false
		}
		t.keyFengGuiDic[guiCount][key] = true
		return true
	}
	if t.keyGuiDic[guiCount] == nil {
		t.keyGuiDic[guiCount] = make(map[string]bool)
	}
	// 判断无风牌的情况,该鬼牌情况是否存在
	_, ok := t.keyGuiDic[guiCount][key]
	if ok {
		return false
	}
	t.keyGuiDic[guiCount][key] = true
	return true
}

检验逻辑

hu.go,用于胡牌的具体逻辑实现

go 复制代码
package alg

import "game/component/mj/mp"

var table = NewTable()

type HuLogic struct {
}

func NewHuLogic() *HuLogic {
	return &HuLogic{}
}

// CardData 牌数据
type CardData struct {
	cards    []int // 带处理的牌,用于编码判断是否在预生成的table中
	guiCount int   // 鬼牌数
	jiang    bool  // 是否有将牌
}

// CheckHu cards当前需要判断的玩家的牌 guiList 鬼牌 代替任何一种牌(红中) card 拿牌/吃牌
// A 万(1-9 *4) B 筒 (1-9 *4) C 条(1-9 *4) D 风 (东南西北 白板 发财等等 1-9 * 4)
// A B C D(红中) 36+36+36+红中数量
// 胡牌的逻辑=N*连子+M*刻子+1*将  连子 = 1,2,3 刻子=2,2,2 将=3,3(对子)
// 13 + 1= 14 在这个牌的基础上去判断  1A 2A 3A 4A 4A 4A 6A 6A 6A 2B 3B 4B 5C 5C
// 算法:1. 编码的操作 1-9A  000000000 每一个位置代表牌有几个 1A 2A 3A 4A 4A 4A 6A 6A 6A (111303000)
// 2. 生成胡牌的信息:111303000编码 代表此牌胡了
// 这样类似的胡的编码非常多,我们把这种很多种可能 叫做穷举法,需要将所有的可能的胡牌的排列 计算出来,转换成编码
// 1A2A5A5A 110020000 如果要胡 0鬼 3A 鬼1 无将 胡3A5A都行 有将 直接胡 我们需要计算这种能胡的所有可能性
// 无鬼 n可能 鬼1 n种可能 鬼2 n种可能 .... 8个 如果有8个鬼 直接胡的 0-7
// 3. 已经把胡牌所有的可能计算出来了,然后将其加载进内存,空间换时间,进行胡牌检测的时候,直接进行匹配即可,查表法
// 1A 2A 3A 4A 4A 4A 6A 6A 6A 2B 3B 4B 5C 5C  111303000  011100000 000020000  = hu
// 先去生成表(所有胡牌的可能) 8张表   feng 8张
// 校验是否胡牌 当前的手牌,鬼牌是什么牌,当前抽的牌
func (h HuLogic) CheckHu(cards []mp.CardID, guiList []mp.CardID, card mp.CardID) bool {
	if card > 0 && card < 36 && len(cards) < 14 {
		cards = append(cards, card)
	}
	return h.isHu(cards, guiList)
}

// isHu 判断是否胡牌
func (h *HuLogic) isHu(cardList []mp.CardID, guiList []mp.CardID) bool {
	// 四种花色 A B C D
	cards := [][]int{
		{0, 0, 0, 0, 0, 0, 0, 0, 0}, // 万  0
		{0, 0, 0, 0, 0, 0, 0, 0, 0}, // 筒  1
		{0, 0, 0, 0, 0, 0, 0, 0, 0}, // 条  2
		{0, 0, 0, 0, 0, 0, 0, 0, 0}, // 字(东、南、西、北、红中) 3
	}
	// 统计出当前手牌中的鬼牌数量
	guiCount := 0
	for _, card := range cardList {
		// 判断牌中是否有鬼牌
		if IndexOf(guiList, card) != -1 {
			guiCount++
		} else {
			i := int(card) / 10   // 0~3:得出当前是万、筒、字等牌类型
			j := int(card)%10 - 1 // 0~9:得出具体对应的下标
			cards[i][j]++         // 累加当前该种牌的数量
		}
	}
	cardData := &CardData{
		guiCount: guiCount,
		jiang:    false,
	}
	for i := 0; i < 4; i++ {
		feng := i == 3            // 代表是风牌
		cardData.cards = cards[i] // 取出当前要处理的牌型
		// 查表出没有对应的情况,说明胡不了
		if !h.checkCards(cardData, 0, feng) {
			return false
		}
	}
	// 如果当前牌没有将牌,且鬼牌数量有多余两张可用的,则可以胡牌(鬼组成将牌)
	if !cardData.jiang && cardData.guiCount%3 == 2 {
		return true
	}
	// 如果当前有将牌,且鬼牌数量已经用尽,不能有多余的
	if cardData.jiang && cardData.guiCount%3 == 0 {
		return true
	}
	return false
}

// checkCards 根据是否风牌校验牌
func (h HuLogic) checkCards(data *CardData, guiCount int, feng bool) bool {
	// 计算该类型牌的数量
	totalCardCount := table.calTotalCardCount(data.cards)
	// 为0则无需判断
	if totalCardCount == 0 {
		return true
	}
	//查表 如果正常无鬼的表没有这种情况,那么就加一个鬼
	if !table.findCards(data.cards, guiCount, feng) {
		// 可用的鬼牌数限制
		if guiCount < data.guiCount {
			// 递归,查询满足的带鬼牌情况,每次鬼+1
			return h.checkCards(data, guiCount+1, feng)
		} else {
			return false
		}
	} else {
		// 将只能有一个(一对凑成一个将子)
		// 如果当前该牌类型的数量加上鬼牌,多出两个,判断是否有用将
		if (totalCardCount+guiCount)%3 == 2 {
			if !data.jiang {
				data.jiang = true
			} else if guiCount < data.guiCount {
				// 如果当前有将牌了,还有多余的鬼牌,需要再次尝试+1鬼 看是否胡 只能有一个将
				return h.checkCards(data, guiCount+1, feng)
			} else {
				// 如果凑不出将或多余的鬼牌没有可以组的情况
				return false
			}
		}
		// 剩余的鬼牌数
		data.guiCount = data.guiCount - guiCount
	}
	return true
}

// IndexOf 判断元素是否存在于数组中
func IndexOf[T mp.CardID](list []T, v T) int {
	for index, value := range list {
		if value == v {
			return index
		}
	}
	return -1
}

测试

go 复制代码
package alg

import (
	"fmt"
	"game/component/mj/mp"
	"testing"
)

func TestGen(t *testing.T) {
	table := NewTable()
	table.gen()
	//321110033
	//1A1A1A 2A2A 3A4A5A 8A8A8A 9A9A9A  3*n+2  =  3*n + 3*m + 2
	//301221020
	//1A1A1A 3A4A5A 4A5A6A    8A8A   B
}
func TestCheckHu(t *testing.T) {
	h := NewHuLogic()
	cards := []mp.CardID{
		mp.Wan1, mp.Wan1, mp.Wan1, mp.Wan2, mp.Wan3, mp.Wan5, mp.Wan5, mp.Wan5,
		mp.Tong1, mp.Tong1, mp.Tong1, mp.Zhong, mp.Tong4,
	}
	checkHu := h.CheckHu(cards, []mp.CardID{mp.Zhong}, mp.Tong2)
	fmt.Println(checkHu)
}

运行结果
image.png

觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句