这篇文章也是写于3年前，主要介绍了棋牌胡牌检测的核心算法，今天我在回览的时候，觉得可能对有些需要的朋友会有所帮助，特引录过来。原文如下：
本文简单讲讲麻将子的胡牌检测算法。
通常玩家手上的牌张数为3n+1，当别人打出一张牌或者自己摸一张牌时，即牌张数为3n+2可以进行胡牌检测。分析算法之前，我们先看看自然行为的如何处理。
假设有一幅手牌，牌型为：
1万、1万、1万、2万、3万、4万、5万、6万、7万、8万、8万、9万、9万、9万
在手牌里面，三个相同的牌称为刻子，如1万和9万，两个相同的牌称为对子或将，如8万，同花按大小顺序连在一起的三张牌称为顺子，如2万、3万、4万和5万、6万、7万，还有四张相同的牌称为杠子，因为杠子必须从手牌中翻出去才能胡牌，所以这里暂时忽略它。
按规定，如果一幅手牌满足以下条件，则可胡牌：
1）所有的牌均可组成刻子、对子和顺子。
2）对子有且只能有一个。
由于刻子和顺子都是3张牌，所以胡牌时手牌数也满足前面提到的3n+2。
人类非常擅长模式识别，人脑的神经元可以并行处理多维数据，在不经意间，就会成功处理好组出相应的刻子、顺子、对子。而目前的电子计算机，暂时不具备这样的人工智能，所以我们需要把每个牌用数字编码，并设计好算法，利用其快速的运算能力，在极短的时间内求出结果。
我简单描述下这个算法的过程：
1）取出一张手牌，检测是否组成刻子？
如果是，则从手牌中去掉这个刻子，重复第1步。
如果否，继续下一步。
2）检查这张手牌是否组成对子？
如果是，则从手牌中去掉这个对子，重复第1步。
如果否，继续下一步。
3）检查这张手牌是否组成顺子？
如果是，则从手牌中去掉这个顺子，并重复第1步。
如果否，则返回不能胡牌。
如果把上面的算法看成一个递归单元，判断刻子、对子、顺子分别表示这个递归的三条子路径，则用图形表示就是：
image
从取出牌开始，到顺子判断失败返回，完成这个递归所有路径的遍历。如果我们把所有的递归拼接起来，可以组成一颗树，一个三层的树结构如下：
image
到此，一个完整的胡牌算法过程就是：
1）拿到一幅手牌，开始第一层递归。
2）取出一张手牌，分别检测这张牌是否组成刻子、对子、顺子。
3）如果是，则从所在子路径开始，转入下一层递归。
4）如果否，则从所在子路径返回，进入上一层递归。
5）重复执行第2、3、4步，如果某一层递归第2步拿出的手牌为空，表示胡牌成功。如果第4步返回时已经是顶层递归，则胡牌失败。
有一些地方，如广东地区流行鬼牌玩法，何为鬼牌，意思是说指定一张牌，这张牌在胡牌的时候可以充当任意牌，完成刻子、对子、顺子的匹配，增加趣味性。有些地方鬼牌可以为任意牌，也可以有多张，因而使算法变得更加复杂。
image
上图表示判断胡牌算法的一个递归单元，事实上由于多个鬼涉及到多种填充的遍历问题，实现上会更加复杂，有兴趣的朋友直接看代码吧。
以下为递归单元的检测算法，为了保持递归单元的整体性，我没有去拆分它，所以这个函数还是比较长的。代码如下：
bool CCheck::__checkHu(EATCARDS_t& eats)
{
Card card = __remainCard();
if (!card.isValid())
return true;
int theCardCount = __getCardCount(card);
// 处理刻子
{
// 不填充
if (theCardCount >= 3)
{
__opCardCount(card, -3);
bool bRet = __checkHu(eats);
__opCardCount(card, 3);
if (bRet)
{
SEatCard eat;
eat.type = ectPeng;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(card);
eat.realCards.push_back(card);
eats.push_back(eat);
return true;
}
}
// 填充1子
if (theCardCount >= 2)
{
std::map<Card, int> mapGostCount;
__getGostAndCount(mapGostCount);
// 找1个鬼
for (std::map<Card, int>::iterator iter = mapGostCount.begin(); iter != mapGostCount.end(); ++iter)
{
Card theCardFillGost = iter->first;
if (theCardFillGost == card || iter->second < 1)
continue;
__opCardCount(card, -1);
__opCardCount(card, -1);
__opCardCount(theCardFillGost, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(card, 1);
__opCardCount(theCardFillGost, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectPeng;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(card);
eat.realCards.push_back(theCardFillGost);
eats.push_back(eat);
return true;
}
}
}
// 填充2子
if (theCardCount >= 1)
{
std::map<Card, int> mapGostCount;
__getGostAndCount(mapGostCount);
// 找2个同鬼
for (std::map<Card, int>::iterator iter = mapGostCount.begin(); iter != mapGostCount.end(); ++iter)
{
Card theCardFillGost = iter->first;
if (theCardFillGost == card || iter->second < 2)
continue;
__opCardCount(card, -1);
__opCardCount(theCardFillGost, -1);
__opCardCount(theCardFillGost, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(theCardFillGost, 1);
__opCardCount(theCardFillGost, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectPeng;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(theCardFillGost);
eat.realCards.push_back(theCardFillGost);
eats.push_back(eat);
return true;
}
}
// 找2个异鬼
for (std::map<Card, int>::iterator iter1 = mapGostCount.begin(); iter1 != mapGostCount.end(); ++iter1)
{
Card theCardFillGost1 = iter1->first;
if (theCardFillGost1 == card || iter1->second < 1)
continue;
for (std::map<Card, int>::iterator iter2 = mapGostCount.begin(); iter2 != mapGostCount.end(); ++iter2)
{
Card theCardFillGost2 = iter2->first;
if (theCardFillGost2 == card || theCardFillGost2 == theCardFillGost1 || iter2->second < 1)
continue;
__opCardCount(card, -1);
__opCardCount(theCardFillGost1, -1);
__opCardCount(theCardFillGost2, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(theCardFillGost1, 1);
__opCardCount(theCardFillGost2, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectPeng;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(theCardFillGost1);
eat.realCards.push_back(theCardFillGost2);
eats.push_back(eat);
return true;
}
}
}
}
}
// 处理将/乱将
if (!m_local.m_bDui)
{
// 不填充
if (theCardCount >= 2)
{
m_local.m_bDui = true;
__opCardCount(card, -1);
__opCardCount(card, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(card, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectDui;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(card);
eats.push_back(eat);
return true;
}
else
{
m_local.m_bDui = false;
}
}
// 填充1子
if (theCardCount >= 1)
{
std::map<Card, int> mapGostCount;
__getGostAndCount(mapGostCount);
// 找1个鬼
for (std::map<Card, int>::iterator iter = mapGostCount.begin(); iter != mapGostCount.end(); ++iter)
{
Card theCardFillGost = iter->first;
if (theCardFillGost == card || iter->second < 1)
continue;
m_local.m_bDui = true;
__opCardCount(card, -1);
__opCardCount(theCardFillGost, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(theCardFillGost, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectDui;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(theCardFillGost);
eats.push_back(eat);
return true;
}
else
{
m_local.m_bDui = false;
}
}
}
}
// 处理顺子
if (card.getColor() != MJ_COLOR_FZ)
{
// 不填充
if (card.getPoint() <= 7 && __getCardCount(card+1) > 0 && __getCardCount(card+2) > 0)
{
__opCardCount(card, -1);
__opCardCount(card+1, -1);
__opCardCount(card+2, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(card+1, 1);
__opCardCount(card+2, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(card+1);
eat.realCards.push_back(card+2);
eats.push_back(eat);
return true;
}
}
// 填充1子
{
// 前面填充
if (card.getPoint() >= 2 && card.getPoint() <= 8 && __getCardCount(card+1) > 0)
{
std::map<Card, int> mapGostCount;
__getGostAndCount(mapGostCount);
// 找1个鬼
for (std::map<Card, int>::iterator iter = mapGostCount.begin(); iter != mapGostCount.end(); ++iter)
{
Card theCardFillGost = iter->first;
if (theCardFillGost == card || iter->second < 1)
continue;
__opCardCount(theCardFillGost, -1);
__opCardCount(card, -1);
__opCardCount(card+1, -1);
bool bRet = __checkHu(eats);
__opCardCount(theCardFillGost, 1);
__opCardCount(card, 1);
__opCardCount(card+1, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card-1;
eat.eatCard = card-1;
// 真实牌型
eat.realCards.push_back(theCardFillGost);
eat.realCards.push_back(card);
eat.realCards.push_back(card+1);
eats.push_back(eat);
return true;
}
}
}
// 中间填充
if (card.getPoint() <= 7 && __getCardCount(card+2) > 0)
{
std::map<Card, int> mapGostCount;
__getGostAndCount(mapGostCount);
// 找1个鬼
for (std::map<Card, int>::iterator iter = mapGostCount.begin(); iter != mapGostCount.end(); ++iter)
{
Card theCardFillGost = iter->first;
if (theCardFillGost == card || iter->second < 1)
continue;
__opCardCount(card, -1);
__opCardCount(theCardFillGost, -1);
__opCardCount(card+2, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(theCardFillGost, 1);
__opCardCount(card+2, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(theCardFillGost);
eat.realCards.push_back(card+2);
eats.push_back(eat);
return true;
}
}
}
// 后面填充
if (card.getPoint() <= 7 && __getCardCount(card+1) > 0)
{
std::map<Card, int> mapGostCount;
__getGostAndCount(mapGostCount);
// 找1个鬼
for (std::map<Card, int>::iterator iter = mapGostCount.begin(); iter != mapGostCount.end(); ++iter)
{
Card theCardFillGost = iter->first;
if (theCardFillGost == card || iter->second < 1)
continue;
__opCardCount(card, -1);
__opCardCount(card+1, -1);
__opCardCount(theCardFillGost, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(card+1, 1);
__opCardCount(theCardFillGost, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(card+1);
eat.realCards.push_back(theCardFillGost);
eats.push_back(eat);
return true;
}
}
}
}
// 填充2子
{
// 前面填充
if (card.getPoint() >= 3)
{
std::map<Card, int> mapGostCount;
__getGostAndCount(mapGostCount);
// 找2个同鬼
for (std::map<Card, int>::iterator iter = mapGostCount.begin(); iter != mapGostCount.end(); ++iter)
{
Card theCardFillGost = iter->first;
if (theCardFillGost == card || iter->second < 2)
continue;
__opCardCount(theCardFillGost, -1);
__opCardCount(theCardFillGost, -1);
__opCardCount(card, -1);
bool bRet = __checkHu(eats);
__opCardCount(theCardFillGost, 1);
__opCardCount(theCardFillGost, 1);
__opCardCount(card, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card-2;
eat.eatCard = card-2;
// 真实牌型
eat.realCards.push_back(theCardFillGost);
eat.realCards.push_back(theCardFillGost);
eat.realCards.push_back(card);
eats.push_back(eat);
return true;
}
}
// 找2个异鬼
for (std::map<Card, int>::iterator iter1 = mapGostCount.begin(); iter1 != mapGostCount.end(); ++iter1)
{
Card theCardFillGost1 = iter1->first;
if (theCardFillGost1 == card || iter1->second < 1)
continue;
for (std::map<Card, int>::iterator iter2 = mapGostCount.begin(); iter2 != mapGostCount.end(); ++iter2)
{
Card theCardFillGost2 = iter2->first;
if (theCardFillGost2 == card || theCardFillGost2 == theCardFillGost1 || iter2->second < 1)
continue;
__opCardCount(theCardFillGost1, -1);
__opCardCount(theCardFillGost2, -1);
__opCardCount(card, -1);
bool bRet = __checkHu(eats);
__opCardCount(theCardFillGost1, 1);
__opCardCount(theCardFillGost2, 1);
__opCardCount(card, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card-2;
eat.eatCard = card-2;
// 真实牌型
eat.realCards.push_back(theCardFillGost1);
eat.realCards.push_back(theCardFillGost2);
eat.realCards.push_back(card);
eats.push_back(eat);
return true;
}
}
}
}
// 两边填充
if (card.getPoint() >= 2 && card.getPoint() <= 8)
{
std::map<Card, int> mapGostCount;
__getGostAndCount(mapGostCount);
// 找2个同鬼
for (std::map<Card, int>::iterator iter = mapGostCount.begin(); iter != mapGostCount.end(); ++iter)
{
Card theCardFillGost = iter->first;
if (theCardFillGost == card || iter->second < 2)
continue;
__opCardCount(theCardFillGost, -1);
__opCardCount(card, -1);
__opCardCount(theCardFillGost, -1);
bool bRet = __checkHu(eats);
__opCardCount(theCardFillGost, 1);
__opCardCount(card, 1);
__opCardCount(theCardFillGost, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card-1;
eat.eatCard = card-1;
// 真实牌型
eat.realCards.push_back(theCardFillGost);
eat.realCards.push_back(card);
eat.realCards.push_back(theCardFillGost);
eats.push_back(eat);
return true;
}
}
// 找2个异鬼
for (std::map<Card, int>::iterator iter1 = mapGostCount.begin(); iter1 != mapGostCount.end(); ++iter1)
{
Card theCardFillGost1 = iter1->first;
if (theCardFillGost1 == card || iter1->second < 1)
continue;
for (std::map<Card, int>::iterator iter2 = mapGostCount.begin(); iter2 != mapGostCount.end(); ++iter2)
{
Card theCardFillGost2 = iter2->first;
if (theCardFillGost2 == card || theCardFillGost2 == theCardFillGost1 || iter2->second < 1)
continue;
__opCardCount(theCardFillGost1, -1);
__opCardCount(card, -1);
__opCardCount(theCardFillGost2, -1);
bool bRet = __checkHu(eats);
__opCardCount(theCardFillGost1, 1);
__opCardCount(card, 1);
__opCardCount(theCardFillGost2, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card-1;
eat.eatCard = card-1;
// 真实牌型
eat.realCards.push_back(theCardFillGost1);
eat.realCards.push_back(card);
eat.realCards.push_back(theCardFillGost2);
eats.push_back(eat);
return true;
}
}
}
}
// 后面填充
if (card.getPoint() <= 7)
{
std::map<Card, int> mapGostCount;
__getGostAndCount(mapGostCount);
// 找2个同鬼
for (std::map<Card, int>::iterator iter = mapGostCount.begin(); iter != mapGostCount.end(); ++iter)
{
Card theCardFillGost = iter->first;
if (theCardFillGost == card || iter->second < 2)
continue;
__opCardCount(card, -1);
__opCardCount(theCardFillGost, -1);
__opCardCount(theCardFillGost, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(theCardFillGost, 1);
__opCardCount(theCardFillGost, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(theCardFillGost);
eat.realCards.push_back(theCardFillGost);
eats.push_back(eat);
return true;
}
}
// 找2个异鬼
for (std::map<Card, int>::iterator iter1 = mapGostCount.begin(); iter1 != mapGostCount.end(); ++iter1)
{
Card theCardFillGost1 = iter1->first;
if (theCardFillGost1 == card || iter1->second < 1)
continue;
for (std::map<Card, int>::iterator iter2 = mapGostCount.begin(); iter2 != mapGostCount.end(); ++iter2)
{
Card theCardFillGost2 = iter2->first;
if (theCardFillGost2 == card || theCardFillGost2 == theCardFillGost1 || iter2->second < 1)
continue;
__opCardCount(card, -1);
__opCardCount(theCardFillGost1, -1);
__opCardCount(theCardFillGost2, -1);
bool bRet = __checkHu(eats);
__opCardCount(card, 1);
__opCardCount(theCardFillGost1, 1);
__opCardCount(theCardFillGost2, 1);
if (bRet)
{
SEatCard eat;
eat.type = ectEat;
eat.firstCard = card;
eat.eatCard = card;
// 真实牌型
eat.realCards.push_back(card);
eat.realCards.push_back(theCardFillGost1);
eat.realCards.push_back(theCardFillGost2);
eats.push_back(eat);
return true;
}
}
}
}
}
}
return false;
}
最后，请有需要的朋友移步到git上取完整代码：https://github.com/kdjie/libmj
