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

如何判定和牌

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

  • 面子手：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并编码，这样一来，考虑到立直判定在程序中的频繁发生（玩家在门前清状态下，每摸一次牌就需要判定一次），即使我们打了和牌表，仍会非常消耗时间。

打听牌表

用打和牌表的思路，我们也能打出一个听牌表。

如何得到一个听牌的pattern？很简单，只要在和牌的pattern中去掉一张牌即可。

例如，当和牌pattern是「3 3 3 3 2」的「四暗刻」形时，对应的听牌pattern就有以下五种：

  • 「2 3 3 3 2」
  • 「3 2 3 3 2」
  • 「3 3 2 3 2」
  • 「3 3 3 2 2」
  • 「3 3 3 3 1」

然而问题仍未得到解决。考虑一手含有顺子的牌：「1 1 1 0 3 2」，它的听牌pattern有哪些？按去掉一张的思路，我们可以写出下面的几个pattern，似乎是其对应的听牌pattern：

  • 「1 1 0 3 2」
  • 「1 0 1 0 3 2」
  • 「1 1 1 0 2 2」
  • 「1 1 1 0 3 1」

其中第1、3、4个都没有问题，唯独第2个pattern，这个pattern难道一定听牌了吗？显然不是，对于「1 0 1」这种形状，当且仅当这两个1对应的数牌相差2时才是听牌，并且是听嵌张。

于是乎，原先的和牌表的编码方法需要修改思路。

新的编码方式中，我们将额外记录一些数字相差2的嵌张的情况，当两张牌对应的数字相差2时，将其用0进行分隔；当两张牌对应的数字相差3及以上时（或不同字牌、不同类型），将其用00进行分隔。在这种编码方式下，下面几手牌的编码发生了一些变化

「１２３５６７一二三五六七西西」→「１１１０１１１００１１１０１１１００２」

「１１１２３４６７８東東東西西」→「３１１１０１１１００３００２」

另外，转化为二进制序列的方法也要进行一些修改。考虑到0不会连续出现3次，我们可以这样编码：

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

这种编码方法不保证空间效率最高，主打一个能用就行！

代码实现细节可以查看我的项目文件。

通过这种编码方法得到的和牌pattern，只要移除一张牌，就能得到听牌pattern，由此打出听牌表。打听牌表的代码详见我的项目文件。

在打出听牌表后，立直判定的查表次数减少了一个数量级（查10次左右听牌表即可），虽然感觉稍加修改也能打出一个立直表来，但意义不是很大，因为通常情况下我们还需要给出打哪几张牌可以立直，遍历手牌仍是不可或缺的。

最终，我打出的和牌表与听牌表的体积分别为537 KB和845 KB。

如此一来，游戏实现过程中最大的麻烦点 （是吗？我怎么感觉实现游戏逻辑更麻烦） 已经得到解决。