退役后的麻将生活

· · 科技·工程

引子

NOI 的时候是不是看到有选手在搓面麻（面基麻将）？在机房训练的时候是不是看到有人在奇妙的二字日麻网站上玩？

著名笑话：“当你看到一个程序员在电脑前面时而紧张时而放松的时候，他是在调试程序。”

那是不是也可以说：“当你看到一个 OIer 在电脑前面时而紧张时而放松的时候，他不是在打 CF 之类的比赛就是在打雀魂。”

退役了照样能打麻将。

前言

本文章的前半部分非原创，来自搬运外网文章并翻译，并加入了一定的个人理解。

本人的注释会通过这样的引用方式写在原文翻译中。另外，为了表意连贯性和简洁性，不一定会全部照原文翻译。

原文链接：@tomohxx [麻雀]シャンテン数計算アルゴリズム

立直麻将就是日本规则玩法的麻将。

背景

立直麻将中通常用「向听数」来表示做牌进度，其定义为一副手牌达到听牌状态需要的最小的自摸数。

通俗解释：向听数就是理想情况下（摸进来的牌都有用）当前手牌还要打掉多少张。可以理解为废牌数量。之后简记向听数为 S。

向听数的计算需要考虑和牌的形状有三种：七对子，国士无双 / 十三幺，面子手（四个面子加一个雀头）。其中七对子和国士无双的计算方法很简单，只需要考虑对子或幺九牌：

汉字太多用公式写很丑。这一部分的表达式就不用公式写了。

关于面子手，多数情况下手牌有多种分解方式，此时要考虑所有分解方式，取向听数最小的一个即为最终结果。

但是，不是所有分解形式都可以和牌，比如一个搭子转化为顺子的时候需要第五枚进张；再比如做染手（即：混一色或清一色役种）的话，含四枚牌的和牌分解形式不好处理，为了解决这个问题，本文采用另一种方法计算面子手的向听数。

抽象，不理解讲的是什么。

麻将牌的表示

用 h 表示一副手牌。h_i 表示手中编号为 i 的牌的数量。牌的编号规则如下：

手牌顺序无关紧要，重要的只是手中有哪些牌、每种牌又各有几张。

距离

为了计算向听数，需要引入距离的概念。对于两副手牌 g 和 h，定义距离 d(h,g) 的表达式为:

d(h,g)=\frac{1}{2}\sum_{i=0}^{33}(|h_i-g_i|+h_i-g_i)

也就是说，距离定义为表示 h 和 g 各种牌数量差值的代数和。下面也写作置换数。

由于向听数的定义为“一副手牌达到听牌状态需要的最小的自摸数”，换言之，也就是“一副手牌达到和牌需要的最小的自摸数减去 1”。所以，只需要计算当前手牌与所有和牌情况的距离，取最小值并减去 1 即可算出向听数。用数学符号表述，设集合 W 为所有和牌组合的集合，手牌 h 向听数的表达式为：

S(h)=-1 +\min_{w \in W} d(w,h)

如上定义也适用于七对子和国士无双型和牌。

置换数的计算

直接用上述表达式计算在理论上可行，但是实际上，光是面子手和牌的种类就有 11498658 种（数据来源链接），时间空间均无法承受。这里介绍一种更高效的算法，此处只考虑面子手。

假设 h 只由 2 种花色的数牌组成。显然，最接近的和牌形状 h_g 也由同样的 2 种花色组成。此时，“各花色的 n 组面子”组成的集合（记作 V_n ）、或者“各花色的 n 组面子加雀头”组成的集合（记作 W_n ），其直积即为所有 h_g 组成的集合 W。

W=(V_0^0 \times W_4^1) \cup (V_1^0 \times W_3^1) \cup ... \cup (V_4^0 \times W_0^1) \cup (W_0^0 \times V_4^1) \cup (W_1^0 \times V_3^1) \cup ... \cup (W_4^0 \times V_0^1)

这里的上角标表示花色，0 到 3 依次表示万、饼、索和字牌。

再定义两个部分置换数记号 u 和 t：

u^n_m=\min _{v\in V^n_m} \frac{1}{2}\sum_{i=9n}^{9n+k}(|v_i-h_i|+v_i-h_i) t^n_m=\min _{v\in W^n_m} \frac{1}{2}\sum_{i=9n}^{9n+k}(|v_i-h_i|+v_i-h_i)

其中 0 \le n \le 3，0 \le m \le 4。如果 n=3（也就是字牌）则常数 k=6，否则 k=8。

对于一副只包含两种花色共 14 张的手牌，两种花色的数量有十种情况：

\{ (0,14),(3,11),(6,8),(9,5),(12,2),(2,12),(5,9),(8,6),(3,11),(14,0)\}

可以发现，其实就是按照雀头花色分成了两类、然后细分成各种拆分模式。比如，(3,11) 指的是：第一种花色只有一个面子（3 张）、第二种花色是三个面子加一个雀头（3\times 3+2=11 张）。

所以，计算 \min _{w\in W}d(w,h) 可以写为：

\min\{ \min_{v \in V^0_0, w \in W^1_4} d(v+w,h),\min_{v \in V^0_1, w \in W^1_3} d(v+w,h),...,\min_{v \in V^0_4, w \in W^1_0} d(v+w,h),\min_{v \in W^0_0, w \in V^1_4} d(w+v,h),\min_{v \in W^0_1, w \in V^1_3} d(w+v,h),...,\min_{v \in W^0_4, w \in V^1_0} d(w+v,h) \}

而对于任意 x、y、p 和 q，显然有

\min_{v \in V^x_y, w \in W^p_q} d(v+w,h)=\min_{v \in V^x_y, w \in W^p_q} [d(v,h)+d(w,h)]=u^x_y+t^p_q

所以，S(h) 的表达式可以简化表示为：

S(h)=-1+\min \{t^0_0+u^1_4,t^0_1+u^1_3,...,t^0_4+u^1_0,u^0_0+t^1_4,u^0_1+t^1_3,...,u^0_4+t^1_0 \}

上面是只考虑两种花色的情况，可以重复使用这个式子来推广到四种花色的情况。没错，这就是动态规划的思想。状态转移方程有：

t^{(n+1)}_m=\min_{0\le i \le m}(t^{(n)}_i+u^{n+1}_{m-i},u^n_i+t^{n+1}_{m-i}) u^{(n+1)}_m=\min_{0\le i \le m}(u^{(n)}_i+u^{n+1}_{m-i})

边界条件为：t^{(0)}_m=t^0_m、u^{(0)}_m=u^0_m。答案为 t^{(3)}_4。其中，0 \le n \le 3 且 0 \le m \le 4。

如果能够预处理所有 t 和 u 的值（保存到文件中或者打表），就可以直接代入上式中计算，所需内存大小仅为 78MB。

对上述动态规划式子再进行一次变形，可以得到：

f^{(n+1,i+1)}_m = \min \{\min(f^{(n+1,i)}_m,t^{(n)}_{i+1}+u^{n+1}_{m-i-1}),u^{(n)}_{i+1}+t^{n+1}_{m-i-1}\} f^{(n+1,0)}_m = \min \{t^{(n)}_{0}+u^{n+1}_{m},u^{(n)}_{0}+t^{n+1}_{m}\} t^{(n+1)}_m=f^{(n+1,m)}_m g^{(n+1,i+1)}_m = \min \{g^{(n+1,i)}_m,u^{(n)}_{i+1}+u^{n+1}_{m-i-1}\} g^{(n+1,0)}_m = u^{(n)}_{0}+u^{n+1}_{m} u^{(n+1)}_m=g^{(n+1,m)}_m

注意 t^x_y 和 t^{(x)}_y 的含义是不一样的。t^x_y 是可以预处理的，预处理之后代入上式，递推后，自身的值会被更新，更新后的结果就是 t^{(x)}_y。

代码实现使用的递推式子即为上述，配合预处理出的 t 和 u（预处理计算方式，见上面 t 和 u 的定义）。

/*
参数中：
lhs[5~9] 为 t???? 到 t????
lhs[0~4] 为 u???? 到 u????
rhs[5~9] 为 t??1? 到 t??1? 
lhs[0~4] 为 u??1? 到 u??1?

计算完成后
lhs[5~9] 为 t???1?? 到 t???1?? 
lhs[0~4] 为 u???1?? 到 u???1?? 
*/

using Vec = std::vector<int>;

void add(Vec& lhs, const Vec& rhs)
{
  // 计算 t? 到 t?
  for(int j=9; j>=5; --j){
    int sht = std::min(lhs[j]+rhs[0], lhs[0]+rhs[j]);

    for(int k=5; k<j; ++k){
      sht = std::min({sht, lhs[k]+rhs[j-k], lhs[j-k]+rhs[k]});
    }
    lhs[j] = sht;
  }

  // 计算 u? 到 u?
  for(int j=4; j>=0; --j){
    int sht = lhs[j]+rhs[0];

    for(int k=0; k<j; ++k){
      sht = std::min(sht, lhs[k]+rhs[j-k]);
    }
    lhs[j] = sht;
  }
}

这里用的是类似滚动数组的优化，会修改传进来的参数。可以把这个函数理解为 dp 循环的循环体。

用如上算法实现了向听数计算，以及蒙特卡洛法计算配牌的向听数的示例程序。更多详细信息请前往 GitHub：shanten-number-calculator - GitHub。

代码长度更短的，JavaScript 实现的版本：snc_js - GitHub。

用如上算法进行一亿次随机模拟（即：随机生成一副手牌然后计算向听数），得到结果中，亲家配牌向听数的期望值为 3.15599、子家配牌向听数的期望值为 3.57966。严谨的值是亲家为 3.15593，子家为 3.57967，已经充分接近了，说明算法是正确的。

实战应用

接下来的部分不是原文内容。实战需要比向听数多得多的信息，下面讲述必要的几个信息的计算。

有效进张的计算

如果要在实践中实用，光是计算向听数可能还不够，计算有效进张的算法：necessary-and-unnecessary-tiles-calculator - GitHub。原文作者没有给出具体解释。

显然，一次切牌，最多只能让向听数减少 1。注意到手上的麻将最多只有 14 种、可能进张的牌最多只有 34 种，非常少。所以可以枚举打出手上的哪种牌，再枚举可能摸到什么牌，计算向听数。如果向听数更少了，显然就是有效进张。

天凤也可以计算向听和有效进张，通过扒代码出来看，可以发现确实用的就是枚举法。其 JavaScript 代码如下（原本的源代码是被混淆过的，这里格式化并且规范命名才比较可读）：

for (discard = 0; 34 > discard; ++discard) {
    if (handCount[discard]) {
        handCount[discard]--;
        expecting[discard] = [];
        for (income = 0; 34 > income; ++income){
            if (discard != income && 4 > handCount[income]) {
                handCount[income]++;
                if (CalculateShanTen(handCount, isRegular) == currentShanTen - 1) expecting[discard].push(income);
                handCount[income]--;
            }
        }
        handCount[discard]++;
        if (expecting[discard].length) {
            expecting[discard] = {
                "摸": expecting[discard],
                "切": discard,
                "进张枚数": ExpectingCount(expecting[discard], handCount)
            }
        }
    }
}

顺带提一句，天凤用的计算向听数的方法似乎并非与上面用的算法完全一致。有能力的可以去啃一啃源码看看具体原理。

期望打点的计算

前往原作者的仓库有现成的实现：https://github.com/nekobean/mahjong-cpp/。大概看了一下，原理是通过建立状态转移图，然后在每个终止状态（也就是和了的状态）计算打点，再一步步换算回来。由于要计算所有可能的路径，算法相对耗时，哪怕已经有预处理出的表，算 3 向听也明显有性能开销。

此外期望打点还受到鸣牌（吃碰杠）的影响，这一点也要考虑进去。包括潜在的鸣牌可能，比如手中有三元牌的对子。真正用于实战的话还有不少的路要走。

这个仓库需要 boost 库来编译，所以不要下载下来然后扔 Dev C++ 里说编译不了——见过一堆这样的 issue（相当数量的提出者是有 OI 背景的）。如果嫌安装 boost 库麻烦，魔改一下编译文件然后用 Github Actions 构建是可行的。

实在不愿意构建可以去作者在主页放的链接麻雀何切るシミュレーター version 0.9.5。

铳率的计算

有一个仓库的提到了计算铳率，是根据牌河的存量结合筋壁理论去计算的，只是非常粗略的估计。

具体计算先放个坑在这。

（大约两个月后得出结论）

非完美博弈算个头啊

而且大部分人打不过纯牌效天凤牌理

闭着眼纯牌效做牌都能天凤六段甚至七段

科学麻将死路一条

我选择训练 AI

（一个月后）

30 小时速通雀豪段位！

（三小时后）

号被封了。

广告

退役生活快乐。不过如果是高中生的话，还是先去学习吧。