麻将的胡牌算法算麻将中最主要的一个算法，这里说的算法是一个O(1)的算法，当然是用空间换时间了，如果我们可以把每个胡牌类型都实现存到hash表中，只需要把牌带进去查询就可以知道是否可胡了。
那到底hash表如何生成呢，这里来讲解一个回溯+剪枝的算法提前计算好所有的胡牌类型。先说明下牌型术语。
- 牌型术语
顺子 : 比如123 或者 345
刻子 ：333 或者 666
将 : 22 或者 55
先只考虑一种花色，当牌可以胡时，一定是3N+2的组合，2做将，3N表示3N个顺子或者刻子。
-
可以使用数组的下表来表示牌的值，数组的值表示牌的张数。
比如array = {2,2,2,0,0,0,3,3,3},表示牌值1，2，3分别2张，牌值7，8，9分别是3张。 -
针对不同花色，当只有一种花色为3n+2，其余花色都为3n，那么可以胡牌。所有要找到所有3n以及所有3n+2的数组。
-
因为牌值的大小最大为9，如果找到了数组可以用一个64位整数存储，所以最终hash表的key可以是个64位整数（如果是8位多好，就可以用32位整数存储了）。
现在先来通过一个算法来找到值1到9中，所有的表示3N的组合。
思路：
- 通过加法添加，每次加3张牌，要么是加顺子 要么是加刻子
2.加顺子或者加刻子，只需要一个参数来表示，比如要加刻子{n,n,n}，顺子{n,n+1,n+2}。这里需要注意的是加刻子时n小于等于9，顺子时n小于等于7
3.构建树，然后回溯。
//定义数组 array
gen3n(array,level)
//这里之所以定义大于4层就退出不继续构造树，因为麻将的3n的张树最多12张
if(level >= 4) return
for i=1 to 16
if i <= 9 //这里添加刻子
array[i] = array[i] + 3
if array[i] > 4 //麻将的张数不能超过4，剪枝
goto backtrace
else //这里添加顺子
index = i-9
array[index] = array[index]+1
array[index+1] = array[index+1]+1
array[index+2] = array[index+2]+1
if array[index] > 4 OR array[index+1] > 4 OR array[index+2] > 4//麻将的张数不能超过4，剪枝
goto backtrace
print(array) //这里可以把array转换成64整数，然后记录进hash表
gen3n(array,level+1)
//回退
backtrace:
if(i<=9)
array[i] = array[i]-3
else
index = i-9
array[index] = array[index] -1
array[index+1] = array[index+1] -1
array[index+2] = array[index+2] -1
目前来说应该对如何生成3N的算法应该理解了，那么生成3n+2也简单了，先添加个将在来生成3N+2算法就可以了。
伪代码如下
gen3n2()
//定义array
for i= 1 to 9
array.add({i,i})
gen3n(array,0)
array.remove({i,i}) //回溯
当时我们项目中这个工具，使用lua来编写的，生成所有的组合的时间在2秒左右，如果改成c++肯定要小于1秒的。这种事先生成data的工具对时间要求不敏感，因为生成一次终生可用。
说完了工具的伪代码，现在说说服务器胡牌判定的伪代码
check(array)
//1:万 2:筒 3:条
b3n2 = false //定义是否有3n2
for i=1 to 3
key = tokey(array[i]) //把这个一个花色的牌转换成key
if hash3n2[key] //在3N2的哈希表中查找到
if b3n2 == true //之前花色已经查找到了3n2的key了，再次查找到3n2的key
return false
b3n2 = true
else if hash3n[key] //在3N的哈希表中查找到
else //在3N2以及3N+2的哈希表中都查找不到
return false
return true
服务器开始运行时加载data到hash表，这个表差不多一共占用5M内存左右，但是换来的是胡牌判定的O(1)的效率，这个很值得。这样麻将中几乎没有消耗性能的业务了。后面有空谈谈麻将AI的部分，也是通过预先生成一个牌型对应概率的做法，让AI模块变成非常高性能的模块。
网友评论