Skip to content

Latest commit

 

History

History
105 lines (90 loc) · 5.69 KB

hu.md

File metadata and controls

105 lines (90 loc) · 5.69 KB

简述

麻将作为国粹,为大众所喜爱,每个地区的玩法都不太一样,但是大部分都会有鬼牌,或者叫癞子,本文主要讲的是带多张鬼牌的胡牌算法。首先,简单说下麻将的基本概念。
github地址

使用

maven

<dependency>
    <groupId>com.github.esrrhs</groupId>
    <artifactId>majiang_algorithm</artifactId>
    <version>1.0.15</version>
</dependency>
// load
HuTableJian.load(Files.readAllLines(xxx));
HuTableFeng.load(Files.readAllLines(xxx));
HuTable.load(Files.readAllLines(xxx));
// check
boolean isHu = HuUtil.isHu(cards, gui);
List<Integer> tingCards = HuUtil.isTing(cards, gui);

花色分类

  • 普通牌:万筒条,每门有序数从一至九的牌各四张
    image
  • 风牌:東、南、西、北
    image
  • 箭牌:中、發、白
    image

牌型术语

  • 连子:一万二万三万
    image
  • 刻子:一筒一筒一筒
    image
  • 将:一条一条
    image

胡牌公式

  • N×连子 + M×刻子 + 1×将
  • N>=0, M>=0
    image

鬼牌

鬼牌的定义就是能够变成任意牌的牌,通常是提前指定或者每次随机决定,比如白板做鬼,如下图:
image
此时白板可以变成3万,这手牌已经胡了。

遇到的问题

玩过麻将的人会知道,当鬼牌数目比较少时,看胡牌听牌还比较快,如果有多张鬼牌了,别人打一张牌,可能并不会很快的判断是否能胡,比如下图,当别人打了个6条,这手牌胡了吗?
image
实际上能胡的牌有
image
程序的计算也是同理,所以如果我们只是简单穷举鬼牌的变化可能性,再去计算是否胡牌,那么性能将会很低。本文的目的旨在优化此胡牌算法。

解决思路

既然穷举不行,那么我们提前计算好这手牌胡什么,到时候只需要查字典就知道胡的情况了,这个也就是查表法,即空间换时间。
当然,如果把所有牌一起查表,那样数据量又太大了。所以我们根据花色来分别查表,因为万筒条的数据,是一样的。

牌型编码

查表的第一步,要对手牌进行编码做key。

  • 首先按照花色分成几组,如下图
    image
    分出来万的牌
    image
  • 然后把1万2万5万5万转变成110020000的9位数字,左数第M位是N,说明M万有N张
  • 这样万筒条风箭,就有5个数字key。

表生成

在生成表的阶段,时间是不值钱的,所以生成方法我们可以任意穷举。

  • 首先分为普通、风、箭三张表
  • 穷举出所有的key,比如普通表,就是000000000-444420000,因为每一种牌最大4张,且总和不超过14张牌。
  • 对于每个key,生成这个key在不同鬼的情况下的胡牌信息列表
  • 胡牌信息列表的内容是,在N张鬼的情况下,这个key胡什么牌,并且是否有将
  • 例如1万2万5万5万:110020000
    image
    生成的胡牌信息有
    1万2万5万5万:鬼0 有将 胡3万(0个鬼的时候,这个牌胡3万,此时有将)
    1万2万5万5万:鬼1 无将 胡3万胡5万(1个鬼的时候,这个牌胡3万5万,此时无将)
    1万2万5万5万:鬼1 有将 胡了(1个鬼的时候,这个牌已经胡了(鬼变成3万),此时有将)
    1万2万5万5万:等等...

胡牌算法

有了前面辛苦生成的表格,那么判断胡牌算法就很简单了。

  • 对玩家手上的牌进行编码,变成多个key和鬼牌总数N,例如手牌如下
    image
    得到key:110020000、020000000和鬼牌总数2
  • 对每个key查询表,得到对应的胡牌信息列表
  • 针对每组列表,过滤掉鬼牌总数>N的项以及没有胡的项,上面的例子就会有
    1万2万5万5万:鬼1 有将 胡了
    2筒2筒:鬼1 无将 胡了
  • 简单递归下,看看几组胡牌信息列表里,是否满足鬼牌总数和只有一个将的约束
  • 如果有任意组合满足,则胡了,在上面的例子里,恰好满足条件,于是胡了
  • 总耗时:查表耗时*M + 递归M层分配鬼和将的耗时
    M是花色数目,M<=5

查胡算法

  • 与胡牌算法类似,根据key查出胡牌信息列表
  • 简单递归下,找出满足鬼的总数和只有一个将的约束时,所有不能胡的胡牌信息里可胡牌的集合,就是这手牌能胡什么牌
  • 优化,比如已经知道能胡1万2万3万,那么就不再去递归胡2万(子集)的可能

其他

  • 目前项目中前后端已经使用此算法,读表前端使用sqlite,后端使用txt加载到内存建立成hashmap
  • 可以修改规则重新生成,比如有的麻将东西南也算连子