麻将胡牌算法 极速(速度接近理论极限)

此麻将胡牌算法优点：

1.可处理多赖子牌（万能牌）

2.算法速度极快：1ms可大约计算1W+副手牌是否可胡（带赖子、0.08us左右），不带赖子的牌型更快。（最新版的算法速度感觉已很接近理论极限值）

3.不同玩法的麻将，可用同一套胡牌算法，加载不同的胡牌配置文件即可。

4.查bug方便

先讲下理论基础：

将麻将的牌 所有牌值对应的索引设为下面的值

static const BYTE s_HuCardType[34] = 
{
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09,//1~9 万
0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19,//1~9 饼
0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29,//1~9 条
0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37                            //东南西北中发白（风字牌）
};

如果我们有一段数组来表示各张牌的张数，如

手牌：1万*3 、3万*3、 5万*3、7万*3、9万*2 可用如下数组表示

BYTE byFlag[34] = {3,0,3,0,3,0,3,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

但我们发现34种牌，每种牌的数量范围是0~4（3bit），也就是至少需要34*3bit=102bit，int64都得两个才存得下，十分不方便。有什么优化方法么？

优化方法：我们发现麻将不同花色的牌之间不会组成牌型（顺子、刻子、将）赖子牌除外。所以各花色之间是相对独立的。所以我们只需存同一花色的数量就行了

也就是上面的手牌，我们只需如下表示：

BYTE byFlag[9] = {3,0,3,0,3,0,3,0,2};

还有一个问题，许多麻将是存在赖子牌的（万能牌）我们可以在最后加一位表示赖子牌的数量，那这样我们只需10*3bit=30bit，一个int32就可以存下了

BYTE byFlag[10] = {3,0,3,0,3,0,3,0,2,0};

但是这样优化后，会有两个不好的影响需要处理：

1、风字牌与一般花色略有不同（总数只有7种且一般不能组成顺子），得特殊处理

2、各花色的牌型里，总共只有一对将，而将是比较特别的（将只需2张牌）

下面介绍一种直接查表来判断是否可胡牌的方法。也就是将所有可胡的牌型存成一个表，是否可胡，去表里查是否有当前手牌牌型即可。是不是会很快？

那关键的关键，也就是那张表了，我们要如何去构建这张表呢？如下

如何生成这样的表呢？

1、生成所有单独的牌组。如（下图还没考虑赖子，算上赖子的话，会更多）

所有顺子：

0x01, 0x02, 0x03,
0x02, 0x03, 0x04,
0x03, 0x04, 0x05,
...
0x07, 0x08, 0x09,
所有刻子：
0x01, 0x01, 0x01,
0x02, 0x02, 0x02,
0x03, 0x03, 0x03,
...
0x09, 0x09, 0x09,
所有将：
0x01, 0x01,
0x02, 0x02,
0x03, 0x03,
...
0x09, 0x09,
然后将各牌组及将牌，组合生成所有可胡的手牌，并过滤掉非法牌组再存起来，就生成了我们需要表了。


跟朋友讨论，其实还有种数组指针代替hash表寻址的方式，会快几倍，但代价是多了十几倍或几十倍的内存（最新版优化后，内存也很少不到1M）。
它的优化代价也不小且应用面不大（它仅适合麻将，但本算法可适用于多种牌类）。

上面只说了基础设定思路，细节过程要复杂得多，此算法优化了好几版，可参考 GITHUB：https://github.com/pinorr/HuPaiMJ

测试效果如下图：i7cpu 、win7、 随机了1800W组牌，每组有4个赖子（万能牌）有约45W组可胡，总共用时2.3秒