从零开始的麻将AI论文复现（二）

本来想省略掉所有麻将游戏的实现细节的，但后来发现强化学习算法需要一个游戏环境，因此完整实现一整套麻将游戏的流程也属于论文复现的一部分，还是有必要对游戏实现时遇到的一些技术细节进行解释。

如何判定和牌

立直麻将共有三种和牌形，分别是：

面子手：m * AAA + (4-m) * ABC + DD
七对：7 个互不相同的对子
国士无双：所有幺九牌各一张，并且其中之一成对子

七对和国士无双比较容易判定，但面子手的和牌形涉及到刻子、顺子、雀头的不同拆分，判定方法会比较麻烦。最容易想到的方法就是用 dfs 遍历所有的拆分可能性，如果能拆分完全，则满足面子手形状。曾经我也实现过这个算法，但 dfs 的问题在于时间复杂度不是很能接受。

考虑一个用程序实现的麻将游戏，这个程序在什么时候会需要进行和牌的判定？实际上，在每一个玩家摸完牌之后，程序都需要为该玩家判定一次和牌；另外，当玩家切出一张牌时，程序都需要为其他三位玩家各判定一次和牌。因此，在一局 20 巡目左右的麻将游戏中，程序大约共需要进行至少 20 * 4=80 次和牌判定。另外，程序还需要为玩家判定一手牌是否听牌、是否可以立直等，显然这两者比和牌判定更为复杂。因此，dfs 应该是在这个场合不可接受的算法。（后来发现可以通过维护每个玩家的听牌列表来减少这种和牌判定的次数，但这也同样会涉及到打听牌表）

目前普遍用在各种网络麻将平台的判和算法是查表法。显然，麻将所有的和牌组合是有限的，因此查表法理论上可行，唯二需要解决的就是如何打表以及如何压缩表体积。

经过一顿搜索，我查到了一种比较先进的打和牌表的算法：

引用站外地址，不保证站点的可用性和安全性

麻雀和了判定

hp.vector.co.jp

虽然满篇的日文，但作为中国人还是能对其基本思路看懂个大概的 /doge。

简单而言，这种算法不关注每张牌具体是什么，而只关注牌之间的连续性。显然，若仅仅只判定是否形成和牌形状，「一万二万三万」和「二万三万四万」是没有任何区别的。

该算法只捕获手牌之间的连续性特征，对手牌进行编码，连续的手牌将其枚数连续写在一起，不连续的手牌之间以 0 为分隔符。举几个简单的例子凑一下篇幅：

→「１１１」

→「３」

→「３３３」

→「１１２１１」

→「１１１０１１１０１１１０１１１０２」

→「３１１１０１１１０３０２」

→「３４４３」

由此，我们可以将手牌转化为一串数字，称为这手牌的 pattern，这串数字的特点是：每个数字介于 0-4 之间，并且不会连续出现两个 0。

接下来将这串数字按下面的规则编码为二进制串

「１」→「０」
「２」→「１１０」
「３」→「１１１１０」
「４」→「１１１１１１０」
「１０」→「１０」
「２０」→「１１１０」
「３０」→「１１１１１０」
「４０」→「１１１１１１１０」

则可以将手牌转化为一串 01 序列，这串二进制数就是被写进哈希表的内容。

该算法在打表时还做了一个操作，即记录下该种 pattern 的一些信息，包含顺子数、刻子数、所有的面子在牌组中的位置，还有一些仅通过形状就能判定的役种：「一杯口」、「二杯口」、「七对子」、「一气通贯」、「九莲宝灯」。

如此，打表的工作只剩下「如何遍历完全部的和牌 pattern」，可以参考一下这份用 ruby 实现的代码或者直接阅读我的项目代码中的文件。

如何判定听牌

当我们可以 o (1) 时间复杂度判定和牌后，应如何判定一手牌是否听牌？

最直接的思路是，分别将 34 种牌插入手牌后计算其是否和牌。稍加优化，可以修改成只遍历手牌附近的牌（国士无双除外）。但感觉还是很浪费时间，稍后我们将其进行优化。

如何判定立直

当我们可以判定一手牌是否听牌后，应如何判定一手牌能不能立直？

所谓「立直」，即若玩家处于「门前清」的状态下，通过打掉一张手牌就可以「听牌」时，可以做出的一种声明行为，「立直」之后，只能摸切直到和牌（一定条件下可以开暗杠）。

因此，判断一手牌能不能立直，就要遍历所有手牌，看看将它切掉以后这手牌是否听牌，于是，如果使用前面那种未经过任何优化的听牌判断方法，最坏情况下判定一次立直就需要做 34 * 14 次和牌查表，然而这个查表并非严格意义上的常数时间，它还需要将手牌转化为 pattern 并编码，这样一来，考虑到立直判定在程序中的频繁发生（玩家在门前清状态下，每摸一次牌就需要判定一次），即使我们打了和牌表，仍会非常消耗时间。