Golang演算法實戰之鬥地主<一>

摘要： 逢年過節，回到老家，玩的最多的就是打麻將、鬥地主。今天要說的，就是這個經典遊戲——鬥地主。 一、鬥地主牌面分析 鬥地主需要多少張牌？大部分人都知道需要一副完整的牌即可，也就是54張牌。 2-10 黑桃、紅桃、梅花、方片各4張。 J、Q、K、A 黑桃、紅桃、梅花、方片各...

逢年過節，回到老家，玩的最多的就是打麻將、鬥地主。今天要說的，就是這個經典遊戲——鬥地主。

一、鬥地主牌面分析

鬥地主需要多少張牌？大部分人都知道需要一副完整的牌即可，也就是54張牌。

1. 2-10 黑桃、紅桃、梅花、方片各4張。
2. J、Q、K、A 黑桃、紅桃、梅花、方片各4張。
3. 大小王各1張。

在鬥地主中，牌的花色不影響。所以，在牌面比對時，不需要單獨比對花色。而單張牌面值的大小順序為: 大王>小王>2>A>K>Q>J>10……3

鑑於此，牌面的表達可以用以下方式來規定：

A：黑桃 B：紅桃 C：梅花 D：方片

撲克原始值	對映值
3-10	3-10數字
J	11
Q	12
K	13
A	14
2	15
小王	Q88
大王	K99

例如：
A14----->黑桃A
C9----->梅花9

二、如何開始遊戲

先來看一張圖

遊戲初始化拆分成3大塊

1. 構造一副牌
2. 洗牌
3. 發牌

1、構造一副牌

構造一副牌就是根據牌面分析中規定的牌面表達方法構造一副完整的54張撲克牌。

程式碼如下:

func CreateNew() []string {
numbers := make([]string, 54) //構造一個大小為54的陣列
start := 0//造牌遊標
for i := 3; i <= 16; i++ {
if i == 16 { //i為16說明已經到大小王
numbers[start] = "Q88"
numbers[start+1] = "K99" //直接構造大小王
} else {
numbers[start] = "A" + strconv.Itoa(i)
numbers[start+1] = "B" + strconv.Itoa(i)
numbers[start+2] = "C" + strconv.Itoa(i)
numbers[start+3] = "D" + strconv.Itoa(i)
start += 4 //每造一套單值牌，遊標移4位
}
}
return numbers
}

驗證一下:

func main() {
initValues := card.CreateNew()
fmt.Println(initValues)
}

列印：
[A3 B3 C3 D3 A4 B4 C4 D4 A5 B5 C5 D5 A6 B6 C6 D6 A7 B7 C7 D7 A8 B8 C8 D8 A9 B9 C9 D9 A10 B10 C10 D10 A11 B11 C11 D11 A12 B12 C12 D12 A13 B13 C13 D13 A14 B14 C14 D14 A15 B15 C15 D15 Q88 K99]

2、洗牌

洗牌就是將牌原有的順序打亂，形成新的順序的牌。主要利用隨機數來處理。

func Shuffle(vals []string) {
r := rand.New(rand.NewSource(time.Now().Unix()))//根據系統時間戳初始化Random
for len(vals) > 0 {//根據牌面陣列長度遍歷
n := len(vals)//陣列長度
randIndex := r.Intn(n)//得到隨機index
vals[n-1], vals[randIndex] = vals[randIndex], vals[n-1]//最後一張牌和第randIndex張牌互換
vals = vals[:n-1] 
}
}

這是一種抽牌插底的洗牌演算法，時間複雜度為O(n)，當然還有效率更高的洗牌演算法，具體可以另做研究。

驗證一下:

func main() {
initValues := card.CreateNew()
fmt.Println("洗牌前: " , initValues)
card.Shuffle(initValues)
fmt.Println("洗牌後", initValues)
}

列印：
洗牌前:[A3 B3 C3 D3 A4 B4 C4 D4 A5 B5 C5 D5 A6 B6 C6 D6 A7 B7 C7 D7 A8 B8 C8 D8 A9 B9 C9 D9 A10 B10 C10 D10 A11 B11 C11 D11 A12 B12 C12 D12 A13 B13 C13 D13 A14 B14 C14 D14 A15 B15 C15 D15 Q88 K99]
洗牌後 [A4 D15 C12 D13 A10 D4 A9 Q88 A7 A6 D6 D14 D10 A14 B4 B15 C8 B13 C14 C13 B11 C4 A12 D11 A3 C5 C10 A13 B5 D8 B6 D9 B10 D7 A5 B7 B3 B14 B12 C3 B8 C7 C15 C6 D3 D5 A8 A15 C11 B9 K99 C9 D12 A11]

可見洗牌達到了預期。

3、發牌

發牌可以說是鬥地主開始前的最後一個環節(不包含叫地主搶地主)，發牌是要將牌先均分給3個玩家(保留3張底牌)，並從玩家中隨機抽取一位玩家為地主。

首先，將牌分成4部分:

玩家一：17張牌

玩家二：17張牌

玩家三：17張牌

底牌：3張

/**
*發牌
*order==0 玩家1次序
*order==1 玩家2次序
*order==2 玩家3次序
*order==3 底牌次序
 */
func Dispacther(order int, vals []string) []string {
var playCards []string
if order < 0 || order > 3 {//判斷玩家次序是否正確
return []string{}
} else {
size := 17 //預設總長度為17
if order == 3 {
size = 3 //次序為3(底牌次序)時，總長度為3
}
for i := 0; i < len(playCards); i++ {
playCards = append(playCards, vals[order*17+i])//根據次序發牌
}
}
return playCards
}

驗證一下:

func main() {
initValues := card.CreateNew()
card.Shuffle(initValues)
fmt.Println("玩家1：", card.Dispacther(0, initValues))
fmt.Println("玩家2：", card.Dispacther(1, initValues))
fmt.Println("玩家3：", card.Dispacther(2, initValues))
fmt.Println("底牌：", card.Dispacther(3, initValues))
}

列印：
玩家1： [A4 C14 B14 C4 C13 C15 D6 D14 A13 B13 D11 B4 B12 C12 B9 D8 B6]
玩家2： [A9 D3 D10 A5 C5 C7 C8 A7 C6 A6 C11 B15 C9 A3 C10 A8 D13]
玩家3： [K99 D15 C3 B3 B5 A15 A11 B7 Q88 A10 D12 A12 A14 D7 B11 B8 D9]
底牌： [B10 D4 D5]

從列印結果來看，發牌也是滿足場景的。

三、出牌分析

接下來，就是最複雜的點，出牌的處理。

1. 牌面分類

首先要處理的是根據所出的牌，判斷出出牌的型別。

根據以往遊戲中的經驗來看，出牌型別總的可以分為以下幾種型別(由簡單到複雜)

1. 單根
2. 對子
3. 三不帶
4. 三帶一
5. 炸彈（4張同值牌）
6. 四帶二
7. 飛機
8. 三不帶飛機
9. 連對
10. 順子
11. 王炸

那麼，根據以上型別，我們首先定義出出牌型別列舉

type CardTypeStatus int

const (
_CardTypeStatus = iota
SINGLE//單根
DOUBLE//對子
THREE//三不帶
THREE_AND_ONE//三帶一
BOMB//炸彈
FOUR_TWO//四帶二
PLANE//飛機
PLANE_EMPTY//三不帶飛機
DOUBLE_ALONE//連對
SINGLE_ALONE//順子
KING_BOMB//王炸
ERROR_TYPE//非法型別

)

2.計算推理

玩家出的牌張數不固定，那麼，如何有效的判斷出玩家所出牌的型別呢。

首先從最簡單的，根據牌的張數可以判斷出最簡單的兩種場景

1. 單根
2. 對子
3. 王炸

func ParseCardsInSize(plays []string) {
switch len(plays) {
case 1:
fmt.Println("單根")
break
case 2:
if plays[0] == "Q88" && plays[1] == "K99" {
fmt.Println("王炸")
} else {
fmt.Println("對子")
}
break
}
}

這是最簡單的判定方法，接下來，張數越多，複雜度越高。

第二個方法就是根據出牌中值相同的牌的張數來判定型別。

這裡首先要抽象出計算模型

type CardShow struct {
ShowValue[]string//牌面陣列
CardMapmap[int]int//牌面計算結果
MaxCountint//最大牌值
MaxValues[]int//最大牌值出現的次數
CompareValueint//用於比較大小的值
CardTypeStatus enum.CardTypeStatus //牌面型別
}

1. 牌面陣列，表示出牌的所有牌值
2. 牌面計算結果，表示出每個牌值出現的次數
3. 最大牌值
4. 最大牌值出現的次數
5. 用於比較大小的值
6. 牌面型別

3.確定計算方法:

超過兩張的計算方法

1. 根據同值牌出現的次數確定牌種類範圍：
   同值牌出現的次數均為1次---->可能為順子
   同值牌出現的次數均為2次---->可能為連對
   同值牌出現的次數均為3次---->可能為飛機或三帶一(暫時不考慮三帶二)
   同值牌出現的次數均為4次---->可能為炸彈或者四帶二
2. 其中順子、連對、飛機需都要鑑別牌值的連續性
3. 飛機需要額外鑑別非連續牌的張數是否可連續次數相等
4. 連對組數要大於或等於3組
5. 順子張數要大於或等於5

再根據計算方法填充計算模型

/**
* 根據牌面數量判斷牌面型別
 */
func ParseCardsInSize(plays []string) cardmodel.CardShow {
cardShow := cardmodel.CardShow{
ShowValue: plays,
ShowTime:util.GetNowTime(),
}
switch len(plays) {
case 1:
cardShow.CardTypeStatus = enum.SINGLE
cardShow.CompareValue = GetCardValue(plays[0])
cardShow.MaxCount = 1
cardShow.MaxValues = []int{cardShow.CompareValue}
fmt.Printf("根%d", GetCardValue(plays[0]))
break
case 2:
if plays[0] == "Q88" && plays[1] == "K99" {
cardShow.CardTypeStatus = enum.KING_BOMB
cardShow.CompareValue = GetCardValue(plays[0])
cardShow.MaxCount = 2
cardShow.MaxValues = []int{cardShow.CompareValue}
fmt.Println("王炸")
} else {
ParseCardsType(plays, &cardShow)
}
break
}
if len(plays) > 2 {
ParseCardsType(plays, &cardShow)
} else {
cardShow.CardTypeStatus = enum.ERROR_TYPE
}
return cardShow
}

/**
* 獲取牌面型別
 */
func ParseCardsType(cards []string, cardShow *cardmodel.CardShow) {
mapCard, maxCount, maxValues := ComputerValueTimes(cards)
cardShow.MaxCount = maxCount
cardShow.MaxValues = maxValues
cardShow.CardMap = mapCard
cardShow.CompareValue = maxValues[len(maxValues)-1]
switch maxCount {
case 4:
if maxCount == len(cards) {
cardShow.CardTypeStatus = enum.KING_BOMB
fmt.Println("炸彈")
} else if len(cards) == 6 {
cardShow.CardTypeStatus = enum.FOUR_TWO
fmt.Println("四帶二")
} else {
cardShow.CardTypeStatus = enum.ERROR_TYPE
fmt.Println("不合法出牌")
}
break
case 3:
alive := len(cards) - len(maxValues)*maxCount
if len(maxValues) == alive {
if len(maxValues) == 1 {
cardShow.CardTypeStatus = enum.THREE_AND_ONE
fmt.Println("三帶一")
} else if len(maxValues) > 1 {
if IsContinuity(mapCard, false) {
cardShow.CardTypeStatus = enum.PLANE
fmt.Printf("飛機%d", len(maxValues))
} else {
cardShow.CardTypeStatus = enum.ERROR_TYPE
fmt.Println("非法飛機")
}
}
} else if alive == 0 {
if len(maxValues) > 1 {
if IsContinuity(mapCard, false) {
cardShow.CardTypeStatus = enum.PLANE_EMPTY
fmt.Printf("三不帶飛機%d", len(maxValues))
} else {
cardShow.CardTypeStatus = enum.ERROR_TYPE
fmt.Println("非法三不帶飛機")
}

} else {
cardShow.CardTypeStatus = enum.THREE
fmt.Println("三不帶")
}
} else {
cardShow.CardTypeStatus = enum.ERROR_TYPE
fmt.Println("不合法飛機或三帶一")
}
break
case 2:
if len(maxValues) == (len(cards) / 2) {
if len(maxValues) > 1 {
if IsContinuity(mapCard, false) && len(maxValues) > 2 {
cardShow.CardTypeStatus = enum.DOUBLE_ALONE
fmt.Printf("%d連隊", len(maxValues))
} else {
cardShow.CardTypeStatus = enum.ERROR_TYPE
fmt.Println("非法連對")
}
} else if len(maxValues) == 1 {
cardShow.CardTypeStatus = enum.DOUBLE
fmt.Printf("對%d", GetCardValue(cards[0]))
}
} else {
cardShow.CardTypeStatus = enum.ERROR_TYPE
fmt.Println("不合法出牌")
}
break
case 1:
if IsContinuity(mapCard, true) && len(cards) >= 5 {
cardShow.CardTypeStatus = enum.SINGLE_ALONE
fmt.Printf("%d順子", len(mapCard))
} else {
fmt.Println("非法順子")
}
break
}
}

/**
* 獲取順序的key值陣列
 */
func GetOrderKeys(cardMap map[int]int, isSingle bool) []int {
var keys []int
for key, value := range cardMap {
if (!isSingle && value > 1) || isSingle {
keys = append(keys, key)
}
}
sort.Ints(keys)
return keys
}

/**
* 計算牌面值是否連續
 */
func IsContinuity(cardMap map[int]int, isSingle bool) bool {
keys := GetOrderKeys(cardMap, isSingle)
lastKey := 0
for i := 0; i < len(keys); i++ {
if (lastKey > 0 && (keys[i]-lastKey) != 1) || keys[i] == 15 {
return false
}
lastKey = keys[i]
}
if lastKey > 0 {
return true
} else {
return false
}
}

/**
* 計算每張牌面出現的次數
* mapCard 標記結果
* MaxCount 出現最多的次數
* MaxValues 出現次數最多的所有值
 */
func ComputerValueTimes(cards []string) (mapCard map[int]int, MaxCount int, MaxValues []int) {
newMap := make(map[int]int)
if len(cards) == 0 {
return newMap, 0, nil
}
for _, value := range cards {
cardValue := GetCardValue(value)
if newMap[cardValue] != 0 {
newMap[cardValue]++
} else {
newMap[cardValue] = 1
}
}
var allCount []int //所有的次數
var maxCount int//出現最多的次數
for _, value := range newMap {
allCount = append(allCount, value)
}
maxCount = allCount[0]
for i := 0; i < len(allCount); i++ {
if maxCount < allCount[i] {
maxCount = allCount[i]
}
}
var maxValue []int
for key, value := range newMap {
if value == maxCount {
maxValue = append(maxValue, key)
}
}
sort.Ints(maxValue)
return newMap, maxCount, maxValue
}

/**
* 獲取牌面值
 */
func GetCardValue(card string) int {
stringValue := util.Substring(card, 1, len(card))
value, err := strconv.Atoi(stringValue)
if err == nil {
return value
}
return -1
}

5.驗證一下

1. 驗證飛機

func main() {
cardsA := []string{"A3", "B3", "C3", "A4", "B4", "C4", "A5", "B5", "A5", "A6", "B6", "A6", "A11", "A7", "B12", "B7"}
ashowMode := card.ParseCardsInSize(cardsA)
fmt.Println("\nA玩家:", ashowMode.CardTypeStatus)
}
列印：
飛機4
A玩家: 7

說明此玩家出的是4連飛機

為了驗證校驗的準確性，從牌中去掉一張餘牌，看是否能檢驗出合法

func main() {
cardsA := []string{"A3", "B3", "C3", "A4", "B4", "C4", "A5", "B5", "A5", "A6", "B6", "A6", "A11", "A7", "B12"}
ashowMode := card.ParseCardsInSize(cardsA)
fmt.Println("\nA玩家:", ashowMode.CardTypeStatus)
}
列印：
不合法飛機或三帶一

A玩家: 12

然後去掉所有餘牌，看校驗的準確性

func main() {
cardsA := []string{"A3", "B3", "C3", "A4", "B4", "C4", "A5", "B5", "A5", "A6", "B6", "A6"}
ashowMode := card.ParseCardsInSize(cardsA)
fmt.Println("\nA玩家:", ashowMode.CardTypeStatus)
}

列印：
三不帶飛機4
A玩家: 8

說明此玩家出的是4連不帶餘數飛機

2. 順子驗證

func main() {
cardsA := []string{"A3", "B4", "C5", "A6", "B7"}
ashowMode := card.ParseCardsInSize(cardsA)
fmt.Println("\nA玩家:", ashowMode.CardTypeStatus)
}
列印：
5順子
A玩家: 10

去掉一張順子牌，或使其不連續

func main() {
cardsA := []string{"A3", "B4", "C5", "A6"}
cardsB := []string{"A3", "B4", "C5", "A8"}
ashowMode := card.ParseCardsInSize(cardsA)
bshowMode := card.ParseCardsInSize(cardsB)
fmt.Println("\nA玩家:", ashowMode.CardTypeStatus)
fmt.Println("\nB玩家:", bshowMode.CardTypeStatus)
}

列印:
 非法順子
非法順子

A玩家: 0

B玩家: 0

3. 炸彈驗證

func main() {
cardsA := []string{"A3", "B3", "C3", "D3"}
ashowMode := card.ParseCardsInSize(cardsA)
fmt.Println("\nA玩家:", ashowMode.CardTypeStatus)
}
列印：
炸彈
A玩家: 11

其餘幾種驗證不在此列出

四、出牌比對

出牌比對就是對同類型的出牌進行值比對，也就是用前面計算模型中的比較值進行比較，其實也就是出現次數最多的最大值。

下面以 一個飛機的比對做例子

func main() {
cardsA := []string{"A3", "B3", "C3", "A4", "B4", "C4", "A5", "B5", "A5", "A6", "B6", "A6", "A11", "A7", "B12", "B7"}
ashowMode := card.ParseCardsInSize(cardsA)
cardsB := []string{"A4", "B4", "C4", "A5", "B5", "C5", "A6", "B6", "A6", "A7", "B7", "A7", "A11", "A10", "B12", "13"}
bshowMode := card.ParseCardsInSize(cardsB)
fmt.Println("\nA玩家:", ashowMode.CompareValue)
fmt.Println("B玩家:", bshowMode.CompareValue)
}
列印：
飛機4飛機4
A玩家: 6
B玩家: 7

玩家A的比對值為6，玩家B的比對值為7，所以玩家B出的牌比玩家A出的牌大。

以上為鬥地主基本演算法分析完整程式碼地址： ofollow,noindex">github ，期待star...

下一期將會對自動出牌簡易AI演算法作分析。