algorithm - 我该如何计算麻将中的尚滕数？

Question

这是我earlier question about deciding if a hand is ready的后续。

麻将规则的知识将是非常好的，但是基于扑克或romme的背景知识也足以理解这个问题。

In Mahjong 14 tiles (tiles are like cards in Poker) are arranged to 4 sets and a pair. A straight ("123") always uses exactly 3 tiles, not more and not less. A set of the same kind ("111") consists of exactly 3 tiles, too. This leads to a sum of 3 * 4 + 2 = 14 tiles.

There are various exceptions like Kan or Thirteen Orphans that are not relevant here. Colors and value ranges (1-9) are also not important for the algorithm.

一手牌由13张牌组成，每次轮到我们时，我们都必须选择一张新牌，并且必须丢弃任何牌，因此我们将停留在13张牌上-除非我们可以使用新拾取的牌获胜。

可以安排成4组和一对的手是“就绪”的。只需要交换1个图块的手就称为“天派”，或“准备就绪时是1个”。任何其他手都有一个shanten数，该数表示在天派中需要交换多少个图块。因此，Shanten数为1的手需要用1瓦做Tenpai(相应地要准备2瓦)。香丹数为5的手需要5块瓷砖才能腾牌，依此类推。

我正在尝试计算一只手的shanten数。在搜寻了几个小时并阅读了有关该主题的多篇文章和论文后，这似乎是一个 Unresolved 问题(蛮力方法除外)。我能找到的最接近的算法依赖于偶然性，即它无法100％地检测到正确的Shanten数。

规则

我将对实际规则进行一些解释(简化)，然后说明如何解决此任务。在麻将中，有4种颜色，如纸牌游戏(ace，heart等)中的3种普通颜色分别称为“人”，“别针”和“搜”。这些颜色分别从1到9，并且可以用于形成笔直以及相同种类的组。第四种颜色称为“荣誉”，只能用于相同种类的组，而不能用于直形。这七个荣誉将被称为“E，S，W，N，R，G，B”。

我们来看一个Tenpai手的示例:2p, 3p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E。接下来，我们选择一个E。这是一副完整的麻将手(准备好)，由2-4针街道(请记住，针可用于直道)，3针三连冠，5人三连冠，W三连冠和E对组成。

将我们的原始手稍微更改为2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E，我们在1-shanten中得到了一个手，即它需要一个额外的图块来作为Tenpai。在这种情况下，将2p换成3p会使我们回到tenpai，因此通过绘制3p和E可以获胜。
1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W是2手游戏中的一手。有1个完整的三胞胎和5对。我们最后需要一对，因此一旦我们选择1p，5p，9p，S或W中的一个，就需要丢弃其他一对。示例:我们选择一个1针并丢弃W。这只手现在位于1-shanten中，如下所示:1p, 1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W。接下来，我们等待5p，9p或S。假设我们选择5p并丢弃剩余的W，我们得到:1p, 1p, 1p, 5p, 5p, 5p, 9p, 9p, E, E, E, S, S。这只手可以在9针或S上完成。

为避免进一步画出此文本，您可以在wikipedia上阅读更多示例，也可以在Google上使用各种搜索结果之一来阅读。不过，所有这些内容都更具技术性，因此我希望上面的描述足够了。

算法

如前所述，我想计算一只手的shanten数。我的想法是根据瓷砖的颜色将其分成4组。接下来，将所有图块按各自的组进行分组，最后得到荣誉组中的三重，成对或单个图块，或另外按3个正常组中的权重。完成的集将被忽略。成对计数，最终数量递减(最后需要1对)。将单个图块添加到该编号。最后，我们将数字除以2(因为每次选择一个能使我们更接近Tenpai的优质瓷砖时，我们都可以摆脱另一个不需要的瓷砖)。

但是，我无法证明该算法是正确的，而且对于包含近距离范围内许多图块的困难组，我也难以合并直线。每一种想法都值得赞赏。我正在.NET中进行开发，但是也欢迎使用伪代码或任何可读语言。

Answer 1

我考虑了这个问题。要查看最终结果，请跳至最后一部分。

第一个想法:蛮力进取

首先，我写了一种蛮力的方法。它能够在一分钟之内识别出3-shanten，但是它不是很可靠(有时会更长一些，即使是3-shanten也无法枚举整个空间)。

蛮力法的改进

我想到的一件事是在暴力方法中增加一些智能。天真的方法是添加任何剩余的图块，看看它是否产生了麻将，如果没有，则递归地尝试下一个直到找到为止。假设还剩下大约30个不同的图块，并且最大深度为6(我不确定是否可以使用7+斜角手[编辑:根据稍后开发的公式，最大斜角数为(13-1 )* 2/3 = 8])，我们得到(13 * 30)^ 6的可能性很大(10 ^ 15范围)。

但是，无需将每个剩余的瓷砖放在您手中的每个位置上。由于每种颜色都必须本身完整，因此我们可以将图块添加到各个颜色组中，并记下该组本身是否完整。总的说来就好像只有1对这样的细节并不难添加。这样，大约有(13 * 9)^ 6个可能性，即大约10 ^ 12，并且更可行。

更好的解决方案:修改现有的麻将检查器

我的下一个想法是使用我早期编写的代码来测试麻将并以两种方式对其进行修改:

当发现无效手牌时，

不会停止，但记下丢失的磁贴

如果有多种使用图块的方法，请尝试所有方法

这应该是最佳方案，并添加一些启发式方法应该是最佳算法。但是，我发现实现起来相当困难-不过这绝对是可能的。我希望先编写和维护解决方案比较容易。

使用领域知识的高级方法

与经验丰富的玩家交谈时，似乎可以使用一些法律。例如，无需拆分3个瓦片的集合，因为那样就永远不会减少Shanten数。但是，它可以以不同的方式使用(例如，对于111或123组合)。

列举所有可能的3组，并为它们中的每一个创建一个新的模拟。拆下三件套。现在，在生成的手中创建所有2套，并针对将其改进为3套的每个图块进行模拟。同时，模拟要删除的1组中的任何1组。继续这样做，直到所有3套和2套都消失了。最后应保留1套(即单个图块)。

从实现和最终算法中学到的东西

我实现了上面的算法。为了更容易理解，我用伪代码将其记录下来:

Remove completed 3-sets
If removed, return (i.e. do not simulate NOT taking the 3-set later)

Remove 2-set by looping through discarding any other tile (this creates a number of branches in the simulation)
If removed, return (same as earlier)

Use the number of left-over single tiles to calculate the shanten number

顺便说一句，这实际上与我自己计算数字时所采用的方法非常相似，并且显然绝不会产生太大的数字。

这几乎在所有情况下都非常有效。但是，我发现有时以前的假设(“删除已经完成的3套绝对不是一个坏主意”)是错误的。反示例:23566M 25667P 159S。重要的部分是25667。通过删除567 3-set，我们最终得到了一个剩余的6磁贴，导致了5角。最好使用单个图块中的两个来形成56x和67x，从而使总体上成为4分。

要解决此问题，我们只需删除错误的优化，即可得到以下代码:

Remove completed 3-sets
Remove 2-set by looping through discarding any other tile
Use the number of left-over single tiles to calculate the shanten number

我相信这总是可以准确地找到最小的Shanten数，但是我不知道如何证明这一点。所花费的时间在“合理的”范围内(在我的机器上，最长为10秒，通常为0秒)。

最后一点是从剩余的单个图块的数量中计算出阴影。首先，很明显，数字的形式为3*n+1(因为我们从14个图块开始，总是减去3个图块)。

如果只剩下1个图块，则说明我们已经做好了准备(我们正在等待最后一对)。剩下4个图块时，我们必须丢弃其中的2个图块以形成3套，从而再次使我们剩下一个图块。这导致另外2次丢弃。对于7个图块，我们有2次丢弃2次，加4次。依此类推。

这导致了简单的公式shanten_added = (number_of_singles - 1) * (2/3)。

所描述的算法效果很好，并通过了我的所有测试，因此我假设它是正确的。如前所述，我无法证明这一点。

由于该算法会先删除最可能的图块组合，因此它具有内置的优化功能。添加一个简单的检查if (current_depth > best_shanten) then return;，即使对于较高的shanten数字也非常有效。