C++实现麻将胡牌算法：回溯搜索与癞子处理全解析

简介面向C游戏开发与算法学习者的麻将胡牌算法参考实现聚焦普通胡牌规则与癞子万能牌胡牌规则的编码尤其适合需要快速理解牌型判定与搜索策略的开发者。资源包含4个文件由2个cpp与2个h组成压缩包仅23KB其中头文件负责牌型数据结构、接口声明cpp文件分别实现基础胡牌判定和癞子牌替换搜索逻辑核心使用回溯法遍历对子、顺子、刻子等组合并引入剪枝策略降低计算量。针对癞子牌需动态评估最佳替代角色并兼顾番数计算源码中也有相应处理思路。文件结构简洁可直接结合麻将规则研读适合用来理解牌型枚举、递归回溯、剪枝优化以及万能牌的适配方法。已有1361人学习对于想快速上手麻将AI或棋牌逻辑的开发者有较好参考价值。 麻将胡牌这事乍一看是个规则问题仔细一琢磨其实是个搜索问题。尤其是加了癞子万能牌之后原本“这张牌能不能胡”的简单判断直接变成了“哪几张牌可以被替代、怎么替代才能胡”的组合爆炸问题。我自己在写这个算法的过程中踩了不少坑也重构了好几版今天把这套思路完整梳理一遍给正在折腾同类需求的同学一个可复用的参考。1. 从“能不能胡”到“怎么胡”把胡牌判定建模成搜索问题先说清楚胡牌的本质。普通麻将胡牌核心就一句话手牌能被拆成“1个雀头 4组面子顺子或刻子”在某些玩法里还要额外支持七对子等特殊牌型。这个定义看起来简单但真要用代码表达清楚关键是要找到一种“有规律可循”的拆解方式而不是靠肉眼在14张牌里乱试。我用的方案是回溯搜索。思路是这样的先把14张牌按牌型计数然后从最小牌面开始尝试拆出顺子或刻子每拆出一组就递归处理剩余牌直到所有牌都被拆完。最后单独验证能否找到雀头。这个方案天然适合C实现因为手牌规模固定最多14张搜索深度最多也就4~5层即便加上癞子的通配分支回溯量也完全可控不会出现指数爆炸的问题。这套建模方式的核心价值在于它把“胡牌判断”统一成了“拆牌搜索”后续不管叠加癞子、特殊牌型还是听牌检测都只需要在这个搜索框架上做扩展不用推翻重来。很多刚开始写胡牌算法的人容易走入一个误区——试图用枚举所有牌型组合的方式去匹配一旦牌的数量变多或者加入癞子代码复杂度直接失控。2. 牌的表示与计数编码方式的取舍决定了后续所有逻辑的复杂度动手写算法之前最先要解决的是牌的表示问题。这一层如果设计得不好后面的顺子判断、刻子判断、癞子替换都会写得很痛苦。我把牌编码成整数0~8表示万子的1~99~17表示条子的1~918~26表示筒子的1~927~33表示字牌东南西北中发白。这样设计的好处是顺子判断只需要检查“相邻三张牌的编号是否连续”而且同一个花色内部天然连续不需要额外维护花色信息。// 牌面编码0-8万子9-17条子18-26筒子27-33字牌 // 判断三张牌是否为顺子 bool isSequence(int a, int b, int c) { if (a 0 || c 27) return false; // 字牌不参与顺子 return (b a 1) (c a 2); }牌的存储我直接用一个长度为34的整数数组下标就是牌面编码值就是这张牌的数量。很多初学者喜欢用vector存储每一张牌然后反复做查找和删除操作这样也能实现但效率低而且容易出错。用计数数组的好处是任何一张牌的数量都能O(1)访问递归传参时只需要拷贝34个int成本非常低。编码这一步还有个容易忽略的细节牌必须排序吗其实不需要。因为计数数组天然按牌面编码递增排列回溯搜索时从0号牌开始往后遍历每次处理当前最小的非零牌就保证了拆解顺序的有序性不会重复也不会遗漏。3. 无癞子场景标准牌型的回溯搜索实现先把最简单的情况写扎实。没有癞子时胡牌判断的核心逻辑就是“找雀头 拆面子”。我的实现分两步第一步枚举所有可能作为雀头的牌型数量至少为2张的牌第二步在剩余的牌上递归拆面子。递归拆面子的核心逻辑如下bool canFormMelds(vectorint cnt, int melds) { if (melds 4) return true; // 找到当前最小的非零牌 int start -1; for (int i 0; i 34; i) { if (cnt[i] 0) { start i; break; } } if (start -1) return false; // 还有面子没凑齐但牌已经用完 // 尝试拆刻子 if (cnt[start] 3) { cnt[start] - 3; if (canFormMelds(cnt, melds 1)) { cnt[start] 3; return true; } cnt[start] 3; } // 尝试拆顺子 if (start 27 cnt[start 1] 0 cnt[start 2] 0) { cnt[start]--; cnt[start 1]--; cnt[start 2]--; if (canFormMelds(cnt, melds 1)) { cnt[start]; cnt[start 1]; cnt[start 2]; return true; } cnt[start]; cnt[start 1]; cnt[start 2]; } return false; } bool canWin(const vectorint cnt) { for (int i 0; i 34; i) { if (cnt[i] 2) { cnt[i] - 2; bool ok canFormMelds(cnt, 0); cnt[i] 2; if (ok) return true; } } return false; }这个实现里有个关键细节为什么优先拆最小的牌而不是随意选择因为最小编号的牌如果不是雀头就必须被组合进一组面子刻子或顺子里否则它永远也消不掉。这是回溯搜索的核心剪枝依据保证每次递归都往“必然能消掉最小牌”的方向走避免大量无效分支。递归终止条件也有讲究。我用的是“已经凑齐4组面子”作为终止而不是“手牌用完”。因为雀头的拆分已经在上一层完成了剩余牌数必然是3的倍数凑齐4组面子就等价于全部拆完。这里的回溯现场恢复一定要做干净cnt数组在递归返回后必须还原。我一开始写的时候偷懒没恢复结果同一个牌型第一次判断正确、第二次就误判排查了很久才发现是计数被递归过程改掉了。4. 加入癞子给回溯搜索加一个“万能牌”维度癞子的加入让问题复杂度上升了一个量级。癞子牌可以替代任意一张牌参与顺子、刻子或雀头的组合。这意味着在递归拆解过程中每一组面子都有可能用掉0到3张癞子而且癞子的使用位置不同拆分结果也完全不同。我的处理方式是把癞子从普通牌计数中单独摘出来用一个整数wildcardCount表示剩余可用癞子数。每尝试一种面子组合时先看缺少几张牌再判断癞子数量是否足够补位。bool canFormMeldsWild(vectorint cnt, int wildcards, int melds) { if (melds 4) { // 所有面子凑齐后剩余癞子必须能被雀头消化掉通常是0或2张 // 注意这里雀头是主流程单独处理的剩余癞子数要回传给上层验证 return true; } int start -1; for (int i 0; i 34; i) { if (cnt[i] 0) { start i; break; } } // 如果手牌已经用完剩下的面子全用癞子凑 if (start -1) { return wildcards 3 * (4 - melds); } // 拆刻子如果cnt[start]1或2可以额外补癞子凑刻子 int needForTriplet 3 - cnt[start]; if (needForTriplet wildcards) { int used min(3, cnt[start]); int old cnt[start]; cnt[start] 0; if (canFormMeldsWild(cnt, wildcards - needForTriplet, melds 1)) { cnt[start] old; return true; } cnt[start] old; } // 拆顺子分三种情况补癞子 // 1) start本身数量多可以用1-2张直接凑刻子但优先试顺子 // 2) start1缺牌时补癞子 // 3) start2缺牌时补癞子 if (start 27) { for (int use 0; use 3; use) { int need 3 - use; int cntNeed 0; int origCnt[3] {cnt[start], cnt[start1], cnt[start2]}; // 统计这组顺子使用了多少张实际牌 int actual 0; if (cnt[start] 0 use 1) { actual; cnt[start]--; } if (cnt[start1] 0 use 2) { actual; cnt[start1]--; } if (cnt[start2] 0 use 3) { actual; cnt[start2]--; } // 这里逻辑需要更精细use表示这组面子中实际使用的牌张数 // 实际使用1张时组合为 (start, start1癞子, start2癞子) 等 // 需要显式枚举三种顺子补位方式 } } return false; }上面这段代码是示意实际的癞子顺子补位逻辑比这个更繁琐。癞子的核心难点在于顺子缺的牌可能在第1位、第2位或第3位而且一个顺子可能同时缺2张牌这两张癞子可以补在不同的位置。处理方式是把顺子的三种缺位情况全部显式枚举出来。枚举的核心思想是保证顺子三张牌的牌面值分别是a、a1、a2其中每一张牌可以是真实牌也可以是癞子。我按“缺第几位”分成三类缺第一位a不存在用癞子代替、缺第二位、缺第三位。每次递归只处理“当前最小牌”所在的顺子这样不会重复枚举。5. 癞子雀头的处理与特殊牌型的边界癞子不仅影响面子组合也影响雀头的确定。没有癞子时雀头必须是真实存在的对子有了癞子之后单张牌也能靠一张癞子凑成雀头甚至两张癞子可以当作一对雀头。我在主流程中这样枚举雀头bool canWinWild(vectorint cnt, int wildcardCount) { // 先从最直接的做起真实对子做雀头 for (int i 0; i 34; i) { if (cnt[i] 2) { cnt[i] - 2; if (canFormMeldsWild(cnt, wildcardCount, 0)) { cnt[i] 2; return true; } cnt[i] 2; } } // 用一张癞子补雀头 if (wildcardCount 1) { for (int i 0; i 34; i) { if (cnt[i] 1) { cnt[i] - 1; if (canFormMeldsWild(cnt, wildcardCount - 1, 0)) { cnt[i] 1; return true; } cnt[i] 1; } } } // 用两张癞子做雀头 if (wildcardCount 2) { if (canFormMeldsWild(cnt, wildcardCount - 2, 0)) { return true; } } // 七对子等特殊牌型如果规则需要单独判断 return false; }这里有一个很容易被忽视的边界癞子本身如果也是牌池中的一张牌那么这张牌既可以作为普通牌使用也可以作为癞子使用。到底什么时候当普通牌、什么时候当癞子需要在回溯中同时保留两种可能性。我的处理方式是在主流程进入胡牌判断之前先把所有癞子牌从普通牌计数中抽出来全部视为万能牌。这样实现简单也符合大多数带癞子玩法的规则——癞子牌不再作为普通牌参与组合。但如果游戏规则是“癞子也可以被当作它本身的牌面来胡”比如癞子是5万玩家可以把它当5万用那上面的实现就不够了。这种情况下需要在回溯搜索里增加一个分支遇到癞子牌时既可以选择消耗一张癞子当万能牌也可以选择把它当作真实牌面参与组合。两种分支都要尝试取其一能胡即可。这个逻辑会显著增加搜索分支但癞子数量通常有限一般4到8张性能依然可控。6. 性能优化与实测剪枝策略和缓存技巧写完了基础版本接下来就是压性能。虽然手牌规模不大但在线麻将服务端每局动辄要判断几千次胡牌尤其是在出牌检测和听牌提示场景下性能还是要认真对待的。第一个优化是“最小牌剪枝”。这个前面提过每轮递归必须处理当前最小的非零牌因为它不能被跳过。这样能大幅减少无效递归分支。实测下来无癞子场景下平均判断耗时在微秒级别完全不用担心。第二个优化是“癞子数量上限剪枝”。当剩余癞子数量超过了剩余需要凑齐的面子数乘以3时直接返回false同理如果剩余癞子数为负立即剪枝。这两个条件能快速终止大量不可能的分支。第三个优化是针对频繁重复判断的场景。比如听牌检测时需要遍历所有34张牌轮流假设摸到判断是否胡牌。这时候可以用一个简单的哈希缓存每次判断前将cnt数组和癞子数序列化成字符串或按位压缩的整数作为key存入unordered_map下次遇到相同牌型直接返回缓存结果。// 按位压缩牌型作为缓存key uint64_t encode(const vectorint cnt, int wildcards, int melds) { uint64_t key wildcards; key | (uint64_t)melds 8; for (int i 0; i 34; i) { key ^ ((uint64_t)cnt[i] ((i % 8) * 2 16)); } return key; }这里要注意缓存的key必须包含当前已经凑齐的面子数melds否则不同阶段相同牌型会被错误地共用结果。另外缓存只在同一轮的多次判断中复用即可不要跨牌局保留防止内存膨胀。实测一个典型的听牌检测场景手牌13张加上癞子2张遍历34张牌做胡牌判断整体耗时不到2毫秒。这个性能在服务端完全够用。如果是在客户端做离线提示甚至可以做到毫秒级实时响应。7. 踩坑记录与测试策略几个让我排查到崩溃的边界问题这个算法写出来不算难但调试过程相当折磨人。分享几个让我印象深刻的坑希望对大家有帮助。第一个坑是“癞子数量在递归中没有正确恢复”。因为癞子数量是通过参数传递的递归里对它做减法操作但实际上参数是按值传递还是按引用传递很容易搞混。我一开始用引用传递导致回溯时上一层的癞子数已经被子递归改掉了结果同一手牌反复判断结果不一致。后来统一改成按值传递问题立刻消失。第二个坑是“顺子补癞子时没有考虑边界”。比如牌面编码为26筒子9时start 1就是27已经是字牌的编码了此时不应该尝试组顺子。我最初在循环里忘了判断这个边界导致筒子9被错误地跟字牌组成顺子出现“筒子9、字牌、癞子”这种非法面子组合。第三个坑是“空手牌但癞子不足以凑齐面子”的情况。当start -1时说明真实牌已经全部用完此时如果癞子数量是1或2是无法凑齐面子的除非已经满足终止条件。这个分支必须显式判断否则会返回错误的true。为了验证算法的正确性我总结了几个测试方法构造标准的胡牌牌型比如经典的一色双龙会、普通混一色逐一验证返回true。构造缺一张牌的“听牌牌型”用癞子补上验证返回true。构造明显胡不了的牌型验证返回false。随机生成牌型用暴力枚举法穷举所有癞子替换方案和回溯算法对比结果确保一致性。特别是第4点我写了一个暴力验证脚本随机生成上万组带癞子的牌型同时用两种方法判断一旦发现结果不一致就打印牌型和癞子分布逐一定位问题。这个测试帮我抓出了至少5个隐藏bug强烈建议大家也这样做。8. 扩展思考从胡牌判断到听牌提示、最优胡牌路径胡牌判断只是基础实际产品里更需要的是听牌提示和胡牌路径展示。这两个功能都可以在现有框架上扩展。听牌提示的思路是遍历所有可摸到的牌假设摸到手牌中判断是否可以胡牌。这里可以直接复用胡牌判断函数。但如果要给出“听哪些牌、每种牌有几张可胡”就需要额外统计牌池中剩余牌的数量同时排除已经打出的牌和对手手中的牌虽然对手信息不可见但可以根据已知牌推算。最优胡牌路径是更高级的需求告诉玩家“如果把这手牌拆成这组面子胡的牌型是什么”。这需要在回溯搜索中记录每一种成功的拆分方案然后在多种方案中选择得分最高的比如门清、清一色、碰碰胡等不同番型。这个功能的核心改造点在于canFormMelds返回的不再是bool而是一个包含拆分方案列表的结构体然后由上层统计评分。struct WinSolution { vectorvectorint melds; // 面子组合 int paiType; // 番型编码 int score; // 总分 }; bool findWinSolutions(vectorint cnt, int wildcards, vectorWinSolution out);从胡牌判断扩展到最优解计算搜索空间会变大很多因为每一层递归都要保留所有可能的拆分方式而不只是一条可行的。此时缓存策略也需要调整不能只缓存bool结果要缓存整个方案列表或者按评分剪枝。这一块我在实际项目中做过一次工作量大约增加了三倍但效果很好玩家反馈“提示特别聪明”。回到最开始的标题C实现麻将军棋胡牌算法和癞子胡牌算法说白了就是把“牌的组合”抽象成“搜索与剪枝”的组合优化问题。无论你是做棋牌游戏服务端、客户端辅助工具还是单纯为了练习算法思维这套实现思路都能提供比较清晰的参考。我的体会是代码本身不难难的是把各种边界情况想清楚、把递归现场恢复干净、把测试用例做全。把这些坑都趟平之后整个算法结构会非常清晰也能很容易地扩展出更多玩法需求。本文还有配套的精品资源点击获取