1.背景
前几天刚好有项目需要胡牌算法，查阅资料后，大部分胡牌算法的博客都是只讲原理，实现太过简单，且没有给出测试用例。然后就有了下面的这个胡牌算法，我将从算法原理和算法实现两部分展开，想直接用的，直接跳到算法部分即可。
2.数据结构
这里麻将是108张牌，也就是只带万，条，筒。数据结构可抽象为两种形式
分别将牌的类型(万，条，筒)类型(type) 和值( value)设置为牌的属性将牌的值写成十六进制（十六进制一个数字可以同时表示牌值和牌型）
下面将给出牌值的数据结构
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, //万
0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, //条
0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29 //筒
下面是牌对象的数据结构
module.exports = class CardInfoBO {
isShow = null; //是否显示
value = null; //牌值
isTouch = null; //是否可以选中
}
3.模型分析
每个人搬牌后，手中的牌必是14张(或8张)，胡牌时需满足以下条件
手中有一对将牌(两张一样的牌)剩下的牌满足刻子(三张相同的牌)或顺子（三张连续的牌）
所以胡牌的数学模型可被抽象成以下公式：
N*ABC + M*DDD + EE
4.流程分析
搞清楚如何能够胡牌之后，下面谈一下判断胡牌的流程
找出所有可能的将牌去除将牌，得到所有去除所有将牌之后得到的数组集（去除两张相同牌得到的不同组合）遍历去除将牌之后的数组集，将数组集中的剩余手牌根据是否连续分为不同的断点**([3,4,5,7,7,7]转换为{[3,4,5],[7,7,7]}**)根据刚才得到的断点数组，判断其中断点内的牌是否满足3n的格式(顺子或刻子)，不满足，直接false若断点断的牌符合3n的格式(顺子或刻子)，继续检查所有断点内容是否符合胡牌规则(下面代码中有详述)
5.代码分析
不想看的直接复制(复制可直接运行)！！！
先给出整体的判胡算法
/**
* 胡牌（满足公式:N*ABC + M*DDD + EE）
* @param {*} card_list (自己原来的手牌)
* @param {*} cacheCard（别人打出的牌或自己摸到的牌）
*/
check_can_hu(index, cacheCard, card_list)
{
var hand_holds = card_list; //测试用
//判断手牌张数
var first = hand_holds.length;
//新建数组，来判断是否可以胡牌
var card_copy = hand_holds.slice(0);
card_copy.push(cacheCard);
card_copy.sort((a, b) => a.value - b.value);
//手中牌不符合胡牌规则 3n*2
if ((first + 1) % 3 != 2)
{
return false;
}
else
{
//找出所有可能的将牌，其余长度用0补全
var jiangs = this.get_jiang(card_copy, first + 1);
//去除将牌
var mains = [];
var mains = this.qu_jiang_arrs(card_copy, jiangs, first + 1);
//当前去除将牌后牌的长度
var size = mains.length;
//将去除将牌后分段是否符合可胡牌型的bool值
var ones = [];
//每一个断点的所有牌的集合
var breaks = [];
//根据打的断点 获取到第一个长度的所有牌型
breaks = this.get_breaks(mains[i], first - 2);
for (var i = 0; i < size; i++)
{
if (this.breaks_check(breaks, breaks.length))
{
//获取到的牌不符合3n的格式、直接为false
ones[i] = false;
}
else
{
//如果断点断的牌符合顺子或者刻子（3n）的格式
var mainsparts = this.all_parts(mains[i], breaks);
ones[i] = this.ping_hu(mainsparts, mainsparts.length);
}
}
//满足任意条件即可胡牌
for (var i = 0; i < size; i++)
{
if (ones[i]){ return true;}
}
}
return false;
}
获取到所有将牌
/**
* 获取到所有的将牌(2张相同的),未来可能加个去重
*/
get_jiang(card, cardLength)
{
var count = 1;
var arr = new Array();
for (var i = 1; i < cardLength; i++)
{
if (card[i].value == card[i - 1].value)
{
if (count == 1) arr[i - 1] = card[i].value;
count += 1;
}
else
{
count = 1;
arr[i-1] = 0;
}
}
return arr;
}
去除将牌，返回所有可能的情况
/**
* 去除将牌，返回所有牌的情况
*/
qu_jiang_arrs(card, jiangs, length)
{
var list = [];
var cardInfoBO = new CardInfoBO();
cardInfoBO.isShow = true;
cardInfoBO.value = 0x00;
cardInfoBO.isTouch = true;
cardInfoBO.isCard = false;
for(let i = 0; i < length; i++) {
if (jiangs[i] != 0 && jiangs[i] != null)
{
var src = new Array();
var arr = new Array();
for (var j = 0; j < length; j++)
{
src[j] = card[j];
}
src[i] = cardInfoBO;
src[i + 1] = cardInfoBO;
src.sort((a, b) => a.value - b.value);
for(let k = 2; k < length; k++)
{
arr[k-2] = src[k];
}
list.push(arr);
}
}
return list;
}
获取去除将牌后的断点
/**
* 查找去除将牌后的断点（没有连续的牌就是一个断点）
*/
get_breaks(card, card_length)
{
var breaks = [];
var count = 1;
breaks[0] = 0;
for (var i = 1; i < card_length; i++)
{
if ((card[i].value - card[i - 1].value) > 1 && i < card_length-1)
{
breaks[count] = i;
count += 1;
}
else if(i == card_length-1) //最后一次
{
if ( (card[i+1].value - card[i].value) > 1 ) {
breaks[count] = i+1;
count += 1;
}
if((card[i].value - card[i-1].value) > 1){
breaks[count] = i;
count += 1;
}
}
}
breaks[count] = card_length+1;
var breakss = [];
breakss[0] = 0;
for (var i = 0; i < count + 1; i++)
{
breakss[i] = breaks[i];
}
return breakss;
}
断点后，检查所断的牌型是不是顺子或者刻子
/**
* 断点后，检查所断的牌型是不是顺子或者刻子
* false 表示断牌为顺子或者刻字 true表示不符合胡牌规则
*/
breaks_check(breaks, length)
{
for (var i = 1; i < length; i++)
{
if ( (breaks[i] - breaks[i-1]) % 3 != 0)
return true;
}
return false;
}
根据手牌断点数组，返回经过处理的牌型，例如[5,5,5,6,7,7,8,8,9]->[3,1,2,2,1]
/**
* 根据手牌和断点的数组 返回经过处理的牌型
*/
all_parts(card, breaks)
{
var partnum = breaks.length - 1; //断点个数
var parts = [];
var arr = [];
for (var i = 0; i < partnum; i++)
{
for (var j = 0; j < breaks[i + 1] - breaks[i]; j++)
{
j == 0 ? arr = [] : null;
arr[j] = card[breaks[i] + j];
}
parts[i] = this.postion_translate(arr, arr.length);
}
return parts;
}
/**
* 拆解位转换
* （五万、五万、五万、六万、七万、七万、八万、八万、九万）=》（3 1 2 2 1）
*/
postion_translate(arr,arr_length)
{
var count = 1;
var split = [];
var status = 0; //0状态下为单数状态，1状态下为计数状态
for(var i = 0; i < arr_length-1;)
{
var index_value = arr[i].value;
if (index_value == arr[i+1].value)
{
status = 1;
i++;
count += 1;
}
else
{
status == 1 ? split.push(count) : count = 1 ;
i++;
count = 1;
status == 0 ? split.push(count) : count = 1;
status = 0;
}
i == arr_length - 1 ? split.push(count) : count = count;
}
return split;
}
根据拆解位检测最终是否能胡
/**
* 根据拆解位判断最终是否能平胡
*/
ping_hu(mainsparts, mainsparts_length)
{
for(var i = 0; i < mainsparts_length; i++)
{
if (!this.is_main_part(mainsparts[i], mainsparts[i].length))
{
return false;
}
}
return true;
}
/**
* 判断断点处理后的值是否符合胡牌规则(3,1,2,2,1)
*/
is_main_part(arr, arr_length)
{
var cache = [];
cache = arr;
var count = 0;
for(var i = 0; i < arr_length; i++)
{
//遇到三位直接拆
if(cache[i] >= 3) {
cache.splice(i,1,cache[i]-3);
cache[i] != 0 ? i-- : i=i ;
}
else if(cache[i] != 0 && cache[i] > 0 && i < arr_length-2) //按顺子拆
{
cache[i] -= 1;
cache[i+1] -= 1;
cache[i+2] -= 1;
cache[i] != 0 ? i-- : i=i ;
}
}
for(var i = 0; i < arr_length; i++) {
count += Math.abs(cache[i]);
}
return count == 0 ? true : false;
}
6.胡牌算法测试
function check_can_hu_test()
{
var cards = [0x17,0x18,0x19,0x06,0x06,0x06,0x07,0x07,0x08,0x08,0x09,0x09,0x03];
var card_list = [];
var cardInfoBO = new CardInfoBO();
cardInfoBO.value = 0x03;
cardInfoBO.isTouch = true;
cardInfoBO.isCard = false;
for (var i = 0; i < cards.length; i++)
{
var cib = new CardInfoBO();
cib.value = cards[i];
cib.isTouch = true;
cib.isCard = false;
card_list.push(cib);
}
card_list.sort((a, b) => a.value - b.value);
var bool = gamesMgr.check_can_hu("10010", cardInfoBO, card_list);
console.log(bool);
}
7.测试结果
var cards = [0x17,0x18,0x19,0x06,0x06,0x06,0x07,0x07,0x08,0x08,0x09,0x09,0x03];
结果打印： true
var cards = [0x06,0x06,0x06,0x06,0x07,0x08,0x11,0x12,0x013,0x21,0x21,0x21,0x03];
结果打印: true
var cards = [0x11,0x19,0x19,0x04,0x09,0x06,0x25,0x07,0x27,0x08,0x09,0x09,0x03];
结果打印：false
8.总结
大概用了两天的时间完成的，感觉搞清流程和原理之后，再按着步骤去做，就很简单了。只是原来写习惯java了，用node.js实现时要格外注意内存泄露的问题。