麻将游戏数据结构和AI算法

用休息时间零零散散写完了网络麻将游戏，感觉其中有不少值得记录的东西。

基础数据结构

　　　　数据结构确定决定了程序的开发难易程度，就像是游戏的骨架，对于电脑AI难度设定和玩家的游戏体验起着决定性的作用。

0、麻将ID构架

　　　　用一维数组PAICAPTION(143)来记录每张牌的ID和文字信息，数组内容为文字描述，下标用作ID(0-143，共144张牌) 1、胡牌判断基本构架

　　　　用一维数组来记录各个牌型的数量，例如 　　　　 int PAI[38] = { 0, 1,1,1,0,1,1,1,0,0, // PAI[ 1- 9] 壹万～玖万的个数 0, 0,0,0,0,0,3,0,0,0, // PAI[11-19] 壹铜～玖铜的个数 0, 0,0,0,0,0,0,0,0,0, // PAI[21-29] 壹条～玖条的个数 0, 0,1,1,1,0,0,0 // PAI[31-37] 东南西北中发白的个数 };

2、手牌基本构架

　　　　用二维数组来记录，例如

　　　　SELFPAI(17,1) 注：每人手里最多能有18张牌

　　　　参数1：每张牌的ID，即在PAICAPTION数组中的下标

　　　　参数2：每张牌的状态，-1 =》无牌，1=》普通牌，2=》碰牌，3=》吃牌，4=》暗杠，5=》明杠

3、吃碰杠胡的临时数据构架

　　　　主要用来记录触发吃碰杠胡的临时数据，用动态数组记录就行，就不多啰嗦了。

有了这些基本构架，所有的牌和玩家手牌的状态就一目了然了，对于后期开发电脑的AI和游戏流程就方便多了。

客户端主要算法

0、标准胡牌判断算法

　　　　用胡牌判断基本构架，递归检查。一副成胡牌由刻子和顺子组成，每次递归时把刻子或顺子的牌数量减一，最后为0时即是胡牌型。

Public Function HU(arrPai) As Boolean '检查标准胡牌型 Dim i As Integer If Remain(arrPai) = 0 Then HU = True: Exit Function For i = 0 To UBound(arrPai) If arrPai(i) > 0 Then Exit For Next If arrPai(i) = 4 Then arrPai(i) = 0 If HU(arrPai) = True Then HU = True: Exit Function arrPai(i) = 4 End If If arrPai(i) >= 3 Then arrPai(i) = arrPai(i) - 3 If HU(arrPai) = True Then HU = True: Exit Function arrPai(i) = arrPai(i) + 3 End If If Jiang = 0 And arrPai(i) >= 2 Then Jiang = 1 arrPai(i) = arrPai(i) - 2 If HU(arrPai) = True Then HU = True: Exit Function arrPai(i) = arrPai(i) + 2 Jiang = 0 End If If i > 30 Then HU = False: Exit Function If (i Mod 10 < 8) And (arrPai(i + 1) > 0) And (arrPai(i + 2) > 0) Then arrPai(i) = arrPai(i) - 1 arrPai(i + 1) = arrPai(i + 1) - 1 arrPai(i + 2) = arrPai(i + 2) - 1 If HU(arrPai) = True Then HU = True: Exit Function arrPai(i) = arrPai(i) + 1 arrPai(i + 1) = arrPai(i + 1) + 1 arrPai(i + 2) = arrPai(i + 2) + 1 End If HU = False

End Function

　　　　七对、十三幺、全不靠胡牌型属于特例，单独写出算法即可。

　　　　吃、碰、杠的算法用胡牌判断基本构架和手牌基本构架也可轻松解决。

1、游戏流程控制算法

　　　　需要几个重要的标志变量：CurrentIndex（当前控牌玩家ID）、MoPaiIndex（当前摸牌玩家ID）、SharePAIIndex（当前出牌玩家ID）、HostIndex（庄家ID）、SharePAI（最后的出牌ID，对应PAICAPTION数组的下标）、FaPaiFlag（发牌标志），iBool （要牌标志）其中AI开头的变量用于电脑AI，算法实现如下：

If sharePAI = -1 And CurrentIndex = MoPaiIndex Then '自己摸牌

Call MoPAI_Click '调用摸牌模块 ElseIf sharePAI > -1 And sharePAIIndex <> MoPaiIndex And CurrentIndex <> MoPaiIndex Then '别人打出的牌，并且不轮到自己控牌

　　　　iBool = False Call SetOldHPPai '保存上次的手牌，只含普通牌 Call ChkTing '检查听牌 If ChkSharePAI("ChkHu") = True Then'检查胡牌

　　　　　iBool = True Call DelSharePAI '把别人打出的牌放入自己的手牌构架

　　　　　AiHupaiFlag = True End If If QGangFlag = False Then '检查明杠和碰牌 If ChkSharePAI("ChkMingGang") = True Then

　　　　　　iBool = True Call DelSharePAI AiGangFlag = True: AiMingGangFlag = True: AiPengFlag = True Else If ChkSharePAI("ChkPeng") = True Then

　　　　　　　iBool = True Call DelSharePAI AiPengFlag = True End If End If '检查吃牌 If (sharePAIIndex + 1) Mod PlayerCount = MoPaiIndex Then '确认是上家打出得牌 If ChkSharePAI("ChkChi") = True Then iBool = True: Call DelSharePAI AiChiFlag = True End If End If End If Call AddNoUsePAI Call SetCtrlFlag((sharePAIIndex + 1) Mod PlayerCount) '检查要牌完毕

If iBool = False Then '没有自己需要的牌 '向服务器端发送信息，等待服务器反馈。

　　　　　格式：出牌者序号 自己的序号 控牌类型值 Call SendServerData("DoValue=" & CStr(sharePAIIndex) & "_" & CStr(MoPaiIndex) & "_9999") Else '有自己要的牌 Call EventSound("要牌", SoundSex) '出现选择胡、吃等按钮时的声音 Call CallNeedPaiAI End If ElseIf sharePAI > -1 And sharePAIIndex <> MoPaiIndex And CurrentIndex = MoPaiIndex Then '别人打出得牌，轮到自己控牌 '继续完成胡、杠、碰、吃等操作

　　　　（此处非常重要，过程就是，比如要胡别人打出的牌，向服务器端发送“胡”的要牌信息后，等待服务器端检查是否有其他人抢胡，如果没有其他人抢胡，才能完成胡牌过程。如果服务器够强的话，也可以把整个流程控制放到服务器端执行——大概测了一下，每个客户端占用大约5-10M内存，1000人在线内存占用就是5G-10G，再加上电脑AI，CPU也是不堪重负啊。） If Left(EndDoValue, 1) = CStr(MoPaiIndex) Then '确认是自己发出的要牌信息 Call AddSharePAI '恢复14张 iStr = Mid(EndDoValue, 3) EndDoValue = "" Select Case CInt(iStr) Case HuValue '胡 Call EndDoHuPai Case GangValue '明杠 Call EndDoMingGang Case PengValue '碰 Call EndDoPeng Case ChiValue '吃 Call EndDoChi End Select End If ElseIf sharePAI > -1 And sharePAIIndex = MoPaiIndex And CurrentIndex = MoPaiIndex Then '轮到自己控牌 If Len(EndDoValue) > 0 Then '把控制权给需要胡、杠、碰、吃等操作的玩家 CurrentIndex = CInt(Left(EndDoValue, 1)) '3_3000 Call SendServerData("CurrentIndex=" & CStr(CurrentIndex)) Call SendServerData("EndDoValue=" & EndDoValue) Else '打出的牌没人要并且抢杠不成立 EndDoValue = "" If QGangFlag = True Then QGangFlag = False Call SendServerData("QGangFlag=False") '结束抢杠过程，无人抢杠 Call EndDoMingGang '完成自己的明杠 Else '转移控制权给自己的下家 sharePAI = -1 CurrentIndex = (MoPaiIndex + 1) Mod PlayerCount Call NextControlPlayer End If End If End If

服务器端主要算法

0、电脑麻将AI算法

　　　　由于我编的不仅是可以玩家之间联网游戏，而且还可以让电脑加入，所以有了这个AI算法。以防三缺一，呵呵。我把电脑的AI难度设计为了3级，主要说说最基础也是最简单的1级难度：

　　　　要牌判断比较简单，与客户端的要牌判断类似，不在敷述。

　　　　出牌策略是重点，决定了AI的难度。我把它分成了8步。

　　　　a、检查听牌

　　　　b、去除间隔2个空位的不连续单牌，从两头向中间排查

　　　　c、去除间隔1个空位的不连续单牌，从两头向中间排查

　　　　d、去除连续牌数为4、7、10、13中的一张牌，让牌型成为无将胡牌型。如2344条，去除4条。

　　　　e、去除连续牌数为3、6、9、12中的一张牌，有将则打一吃二成为无将听牌型（如233条，去除3条）；无将则打一成将成为有将胡牌型（如233条，去除2条）。

　　　　f、去除连续牌数位2、5、8、11中的一张牌，让牌型成为有将听牌型。如23445条，去除5条。

　　　　g、从将牌中打出一张牌。

　　　　这8步是标准胡牌AI的基础，其中对于七对等特殊胡牌型没有涉及，可以把电脑设定为超过4或5对时转为特殊胡牌AI。AI难度2级时加入海牌的策略，即考虑桌面上已出的牌，AI难度3级时加入记牌分析模块，即记录玩家的出牌过程并进行分析。

1、麻将番数算法

　　　　国标麻将有88种番，可以参考《中国麻将竞赛规则》或者《世界麻将大赛麻将规则》。写算番的过程比较累人，毕竟有88种啊，直接累死-_-!

　　　　麻将算番有5条基本原则：

　　　　1．不重复原则

　　　　　　　　当某个番种，由于组牌的条件所决定，在其成立的同时，必然并存着其他番种，则其他番种不重复计分。

　　　　2．不拆移原则

　　　　　　　　确定一个番种后，不能将其自身再拆开互相组成新的番种计分。

　　　　3．不得相同的原则

　　　　　　　　凡已组合过某一番种的牌，不能再同其他一副牌组成相同的番种计分

　　　　4．就高不就低原则

　　　　　　　　有两副以上的牌，有可能组成两个以上的番种，而只能选其中一种计分时，可选择分高的番种计分。

　　　　5．套算一次原则

　　　　　　　　如有尚未组合过的一副牌，只可同已组合过的相应一副牌套算一次。

　　　　一定要注意最后的套算一次原则，否则算出的番数会过多。

　　　　还有，由于不同的算番过程会导致番数的不同，所以这里也需要使用递归，直至找出能算出最大的番数为止。

结束语：游戏雏形出来后让哥们试玩了一下，还不错，4人联网时没什么问题，就是有电脑参加时AI还是偏高，看来还得写个“AI降低模块”来让电脑随机的“傻一次”，呵呵。