麻将向听数拾遗

参考九条可怜大佬的利用查表法求麻将向听数。过程中有一些数学证明省略了，在这里记录一下加深理解。说句题外话，大佬在知乎唯二的两篇文章，最新的一篇大数快速取模魔法，和我当时做的关于伽罗华域（Galois Field, GF）的毕设简直不要太贴合。哎，我真是学艺不精。

原文主要是针对向听数计算和序列生成进行讲解的，本文主题亦如此。

0x01 向听数计算

对于大众麻将，包括日本麻将和国标麻将，不考虑特殊牌型（七对、十三幺、不靠等）基本的胡牌条件为：m 个面子加上 1 个对子，即可胡牌。为行文方便，将胡牌公式简单记为

3m+2

其中 3 代表面子，2 代表对子。结合麻将规则，容易知道对于能够胡牌的手牌总数 $N$ ，有

N \in \{2, 5, 8, 11, 14\}

牌效率理论定义了向听数（Syanten），指一副牌距离听牌状态最少还差几次打摸动作。0 向听 = 听牌，-1 向听 = 胡牌。若非特殊说明，下文所指的向听数皆为一般牌型的向听数。

对两张不同的牌 $x, y$ 定义距离计算函数 $D(x,y)$ ：

D(x,y) = \begin{cases} 0, 　(x, y 为同种牌)\\ 1, 　(x, y 为同种数牌，且数字差 = 1) \\ 2, 　(x, y 为同种数牌，且数字差 = 2) \\ \infty, 　(otherwise) \\ \end{cases}

根据 $3m + 2$ ，将牌组序列 $tiles$ 分为两个部分：要凑成若干个面子的部分 $tiles_{m},\ \sum tiles_{m}\ mod\ 3=0$ 和要凑成一对对子的部分 $tiles_{p},\ \sum tiles_{p}=2$ 。定义向听数计算函数 $S(tiles)$ 。

对于 $tiles_{p}$ ，有：

S(tiles_{p})=\begin{cases} -1,\ \exist\ t_1,\ t_2\in tiles_{p},\ D(t_1,\ t_2) = 0\\ 0,\ otherwise\\ \end{cases} \\

对 $tiles_{p}$ ，最大向听数永远为 0，即处在听牌状态。很好理解，对于任意两张牌 $x, y$ ，只有 $D(x,y)=0$ 时才能凑成对子，使向听数为 -1。

在继续之前，先明确对于三元组（三张牌组成的子牌组） $tiles_{m}'\subset tiles_{m},\ \sum tiles_{m}'=3$ ，是没有“向听数”的概念的，因为其不满足： $3m + 2$ 的公式，但为了方便证明，依然对三元组 $tiles_{m}'$ 设计辅助向听数计算函数 $S'(tiles)$ ，有：

$S'(tiles_{m}')=$

0
- $tiles_{m}'=\emptyset$
- \exist t_1,\ t_2,\ t_3 \in tiles_{m} for
  - $D(t_1,\ t_2) = 0,\ D(t_1,\ t_3) = 0$
  - $D(t_1,\ t_2) = 1,\ D(t_2,\ t_3) = 1,\ D(t_1,\ t_3) = 2$
1
- \exist t_1,\ t_2,\ t_3 \in tiles_{m} for
  - $D(t_1,\ t_2) = 0,\ D(t_1,\ t_3) \ne 0$
  - $D(t_1,\ t_2) = 1\ or\ D(t_1,\ t_2) = 2$
2
- $otherwise$

不难理解，当不存在任何三元组（即手牌数 N = 2）或存在某一组面子时，无需对三元组进行打摸动作，对向听数自然也就不会有影响了，故值为 0。

我们把使 $S'(tiles_{m}')=1$ 的序列 $tiles_{m}'$ 称为次面。同样不难理解，存在一组三元组组成一组次面时，最少只需打摸一次便能将次面组成面子，故值为 1。

其他情况下则为 2，即最少必须要打摸 1 次组成次面，再最少打摸 1 次组成面子。

最终我们可以得到计算序列 $tiles$ 向听数的函数：

S(tiles) = Min(S(tiles_{p}) + \sum S'(tiles_{m}'))\\\forall tiles_{m}'\subset tiles_{m}\\\forall tiles_{p},\ tiles_{m}\subset tiles

撇开公式 $S(tiles) = Min(S(tiles_{p}) + \sum S'(tiles_{m}'))$ 中的 $Min$ 不谈，单独考虑 $S(tiles_{p}) + \sum S'(tiles_{m}')$ .

无论有无对子，一副总数为 N 的牌最多能组成的三元组组合数 $K$ 必为 $K=\lfloor N \div 3 \rfloor=\frac{N-2}{3}$ ，记某种三元组组合下面子数量为 $G$ ，次面数量为 $G'$ ，无法组成面子和次面的三元组数量为 $K - G - G'$ ，则由辅助向听数 $S(tiles_{m}')$ 的定义，我们有：

\sum S'(tiles_{m}')=0 \cdot G + 1 \cdot G' + 2 \cdot (K - G - G')

记 $P=-S(tiles_{p})$ ，将上式一同代入 $S(tiles_{p}) + \sum S'(tiles_{m}')$ ，记某种对子和三元组的组合下的向听数为 $S$ ，有：

S = 2(K - G) - G'-P

这便是原文中总结出的一般向听数计算公式。

根据定义，向听数是指一副牌距离听牌状态最少还差几次打摸动作。故对一副牌进行分析时，要确保计算公式中 $S(tiles_{p}) + S'(tiles_{m}')$ 最小，我们还需要按照一定的优先级对所有可能的 $tiles_{p} 和 tiles_{m}'$ 进行遍历，即寻求最优（ $Min$ ）组合。

插播一条题外话，经常看到有人说普通牌型的最大合法向听数是 8，根据以上公式便可证明，即每个可能的三元组都无法组成面子或次面，剩下的二元组也不能组成对子，此时向听数最大，为
$S_{max}(N) = \frac{N - 2}{3}\cdot 2$ ，代入 N = 14 即可得到 8.

0x02 查表序列定义和生成

想象一组 N = 14 的手牌，一共有 $\mathrm{C}_{34\cdot 4}^{14} = 425,0305,029,168,216,000$ 种组合，去重后仍有 $326,520,504,500$ 种组合(麻雀の数学) ，要对每种组合的每种可能的对子/面子/搭子/杂牌进行 DFS 剪枝，简直不要太爽。为了更有效率地进行查表的表生成，我们必须定义一种经过抽象的序列，使得可能的组合数大大减少，再计算对应的向听数。

0x02 << 0x00 天凤牌理表达式

对于一组牌，首先按照万、筒、条、字划分牌组，而后数牌以牌面数值从小到大排列，字牌以「东南西北白发中」为顺序分配 1 - 7 的数字作为牌面数值，并从1开始排列。下面是一组排序好的、牌数 N = 14 的一组牌：

11555m223p789s123z

对于已排序的牌组，取每个牌的牌面数值依次拼接，并在每种花色子牌组末尾拼接该花色的标记符号：万-m，筒-p，条-s，字-z。对于上面的牌组，其表达式为：11555m223p789s123z。这便是天凤牌理的表达式。为方便起见，下文所有手牌牌组均用牌组表达式表示。

0x02 << 0x01 序列定义

根据上文可知，决定向听数的是牌序列 $tiles$ 中若干组牌的构成，和牌元素间的距离，即：是否有对子、面子、搭子和其对应的数量。我们可以从具体的牌序列 $tiles$ 中抽象出牌与牌之间的距离信息、牌的数量信息来构建一种新的抽象序列 $s$ ，确保能从抽象序列中恢复出对子、面子、搭子信息。容易想到我们必须保存牌数量和牌距离。

定义序列生成函数 $s=E(tiles)$ ：将每种牌转换为牌数量，并根据上文定义的 $D(x,y)$ ，在各个牌数量间插入牌的距离，对于上面的牌组，可得以下的序列：

2_{\infty}3_{\infty}2_{1}1_{\infty}1_{1}1_{1}1_{\infty}1_{\infty}1_{\infty}1

直观上我们已经丢失了对牌组花色和牌面数值的了解，但我们依然可以根据序列来遍历出所有对子、面子和搭子的组合。

0x02 << 0x02 子序列定义

考虑下面两组牌：

11555m223p789s123z
223m789p11555s123z

其序列分别为

2_{\infty}3_{\infty}2_{1}1_{\infty}1_{1}1_{1}1_{\infty}1_{\infty}1_{\infty}1\\ 2_{1}1_{\infty}1_{1}1_{1}1_{\infty}2_{\infty}3_{\infty}1_{\infty}1_{\infty}1

看起来似乎不一样，但若是把第一组牌的万替换成条，条替换成筒，筒替换成万，就变成第二组牌了。两组牌的向听数其实是一样的。再考虑下面两组牌：

11555m
11155m

其序列分别为

2_{\infty}3\\ 3_{\infty}2

进一步我们知道：序列与序列之间可以通过 $\infty$ 进行拆分重组，且不影响向听数。我们把经过 $\infty$ 拆分后得到的序列 $s'$ 称为子序列。子序列不包含 $\infty$ ，自然无法再拆分，但可以进行翻转（Flip），比如考虑下面两个可能的子序列：

2_{1}3\\ 3_{1}2

实际上对于向听数的计算也是一样的。

将能通过拆分、重组子序列得到相同序列的序列称为同义序列，为了进一步减少所有可能序列的总数，我们必须定义一种方法，将多个同义序列统一表示为一种序列；还能将顺序和倒序的子序列同一表示为一种子序列。经过两次统一表示后，得到最终的序列，再进行向听数计算。

0x02 << 0x03 序列编码和排序

参照九条可怜大佬的文章，编码规则部分略。对于子序列，同样应用该种编码规则。

对顺序子序列 $s'=2_{1}3$ 应用编码规则，可以得到二进制序列 $0b11010010$ ，对倒序子序列 $s'_{flip}=3_{1}2$ 应用编码规则，可以得到二进制序列 $0b11100001$ ，对两个二进制数做 $Min$ 运算（做 $Max$ 运算也可，本文采用 $Min$ ），得到最终的子序列。

对已排序子序列的序列中的每一个子序列再次采用升序排序（降序也可，本文采用升序），再用 $\infty$ 两两拼接，得到最终序列，这样就能保证能将多种同义序列统一表示了。

容易知道最长的编码长度为 2位终止符 + 14 * 2 位牌数 + 13 * 2 位距离 = 56 位，而向听数最大为 8，用 4 位来存储绰绰有余了，总的序列 + 向听数占用的位数不会超过 64 位，可以用一个 ulong 类型直接存储。原文九条大佬对向听数进行了排序再存储序列，还做了差分编码和 Huffman 编码，尽可能把生成表压缩到最小，而我直接存储了 ulong。对于生成的 1,292,057 条结果，文件大小为 9.85MB，感觉还可以接受，就不做进一步压榨了。

0x02 << 0x04 序列枚举生成

基本思路：排列组合。

牌数枚举

对于手牌总数 $N \in \{2, 5, 8, 11, 14\}$ ，不考虑牌与牌之间的距离，首先考虑每张牌牌数的排列组合情况，如 $N = 5$ 时，有：

\begin{cases} 1_{?}1_{?}1_{?}1_{?}1\\ 1_{?}1_{?}1_{?}2\\ 1_{?}1_{?}2_{?}1\\ 1_{?}2_{?}1_{?}1\\ 2_{?}1_{?}1_{?}1\\ 1_{?}1_{?}3\\ 1_{?}3_{?}1\\ 3_{?}1_{?}1\\ 1_{?}4\\ 4_{?}1\\ 5, 不符合条件,\ 因为单张手牌最大上限为 4\\ \end{cases}

即生成 N 对应的手牌数下的可能牌数排列组合。

距离枚举

生成数量枚举后，对各个牌之间的距离，即 $?$ 处进行填充，填充区间为 $? \in \{0, 1, 2\}$ ，即对应距离 $\{1, 2, \infty\}$ 。

由于字牌两两之间距离永远为 $\infty$ ，故不存在子序列最大距离和。对于数牌，距离小于等于 2 的任意 N 张牌的子序列组合最大距离都只能为 2，这点由 $D(x, y)$ 的定义也可以推导出来。容易知道一组同花色数牌中，满足最大距离之和的数牌有：1 2 3 4 5 6 7 8 9 或 1 3 5 7 9，其距离和都为 8，故可以限制每个经 $\infty$ 分割的子序列内所有编码前距离的和 $\le 8$ 。

另外，对于上述数量枚举生成的可能的牌数的排列组合，如果排列 1 = 逆序排列 2，经距离枚举后都可以生成逆序排列的序列，譬如 $1_{?}1_{?}3$ 和 $3_{?}1_{?}1$ 两种排列就可以只针对 $1_{?}1_{?}3$ 进行距离枚举，相当于在这一步就做了初步的序列排序。当然，这一步也可以交给后续的序列排序来做。需要注意的是： $1_{?}1_{?}3$ 的距离枚举和 $1_{?}3_{?}1$ 的距离枚举结果虽然有交叉，但两者的总距离枚举是不一样的，不能做同义替换。

0x03 改进空间

用简化序列的方式进行向听数的查询，对于表生成来说是便捷的，但若用来辅助打麻将，其实仍有改进的空间。

0x03 << 00 面听数

考虑序列 🀇🀈🀙🀙 和 🀈🀉🀙🀙，转换成序列都是 $1_{1}1_{\infty}2$ ，虽然向听数都是 0，但显然前者单吊 🀉，后者两面听 🀇🀊。按照概率，面听数越多，胡牌概率是越大的。扩展到非听牌的情况也是一样，若想让向听数前进 1，听两个边张和听一个坎张的概率也是不一样的，但是转换成序列就看不出来了，还是得从牌面上来分析。

0x03 << 01 运算量

由于实际使用查表法时，是先将手牌转换成序列再查表的，减少向听数的查询方法是对牌内每一张牌进行替换再重新计算序列、查表，从起牌开始计算到胡牌的运算量呈指数级增长，而出牌一般又有时间限制，遍历完所有的情况并找寻全局最优解显然不现实。所以应用时，一般都要考虑运算的深度，即：当向听数前进多少时停止计算，寻求运算量和局部最优解之间的平衡。这样就引申出下列一系列其他问题。

0x03 << 02 回退

寻求局部最优解带来的问题也显而易见，比如局部最优解不断引导我们听牌，听牌时，我们的序列是 🀈🀉🀙🀙，但假若此时场上 🀇🀊 已经绝张了，我们又不得不将向听数退回到 1 的情况，如果此时无论走任何路径，剩余牌仍无法让我们达成胡牌，向听数还得后退到 2。这样的情况其实并不少见。

0x03 << 03 更新

按照上文的方法，计算向听数的时候手牌数总是满足 N % 3 = 2，意味着当且仅当我们出牌时才能计算向听数。但是一巡中其他三家出牌的时间占了大头，很可能刚计算完局部最优解，打出了一张牌等待下一次摸牌的过程中，其他三家打出的牌（亦或是鸣牌）已经让上一次的局部最优解不成立了，这时候就需要适时更新上一次的局部最优解。

0x03 << 04 特殊规则下的局部最优解

对于部分地方麻将，规则中是不允许吃牌的，也就是说顺子成牌只能靠自摸。考虑下面两种序列：🀈🀉、🀋🀋，假设场上 🀇🀊 和 🀋 都未现，牌山中剩余牌数为 n，则自摸成面（刻）子的最大概率：前者为 8 / n * 0.25 = 2 / n，后者为 2 / n * 0.25，从概率上来说前者自摸成面子的概率比后者大。但是考虑到 🀋🀋 可以由碰形成刻子，所以后者成刻子的实际概率应是比 2 / n * 0.25 大的，最大值正好是 2 / n，这时候就要结合场上其他家在牌海中的情况来分析，当其他人摸到 5m 后是否会打出，进一步来优化局部最优解。