algorithm - 我如何计算麻将中的shanten数？

Question

这是我之前关于决定一手牌是否准备好的问题的后续。

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

在麻将中，14 张牌（牌就像扑克牌中的牌）被排列成 4 组和一对。顺子（“123”）总是使用 3 张牌，不多也不少。一组相同类型（“111”）也正好由 3 个牌组成。这导致总和为 3 * 4 + 2 = 14 个图块。

有各种例外，例如 Kan 或十三孤儿，在这里不相关。颜色和值范围 (1-9) 对算法也不重要。

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

可以安排形成 4 组和一对的手是“准备好的”。只需要交换 1 张牌的手被称为“tenpai”，或“1 from ready”。任何其他手都有一个shanten-number，表示需要交换多少张牌才能进入tenpai。因此，一手牌数为 1 的牌需要 1 张牌才能成为 1 牌（相应地需要 2 张牌）。一手牌数为 5 的牌需要 5 张牌才能成为十牌，以此类推。

我正在尝试计算一手牌的 shanten 数。在谷歌搜索了几个小时并阅读了关于这个主题的多篇文章和论文之后，这似乎是一个未解决的问题（除了蛮力方法）。我能找到的最接近的算法依赖于机会，即它无法 100% 地检测到正确的 shanten 编号。

规则

我将解释一下实际规则（简化），然后我的想法是如何解决这个任务。在麻将中，有 4 种颜色，3 种正常的颜色，就像纸牌游戏中一样（ace、heart、...），称为“man”、“pin”和“sou”。这些颜色各从 1 到 9，可用于形成直线以及同类组。第四种颜色被称为“荣誉”，只能用于同类组，但不能用于直道。七项荣誉将被称为“E、S、W、N、R、G、B”。

让我们看一个十牌手的例子：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 的一手牌，即它需要一个额外的牌才能成为十牌。在这种情况下，将 2p 换成 3p 会让我们回到tenpai，所以通过抽出 3p 和 E 我们赢了。

1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W是 2-shanten 中的一手牌。有 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（因为每次我们选择一个能让我们更接近天牌的好牌，我们就可以去掉另一个不需要的牌）。

但是，我不能证明这个算法是正确的，而且我也很难为包含许多近距离瓷砖的困难组合并直道。每种想法都值得赞赏。我正在使用 .NET 进行开发，但也欢迎使用伪代码或任何可读语言。

Answer 1

我对这个问题想得更多。要查看最终结果，请跳到最后一部分。

第一个想法：蛮力方法

首先，我写了一个蛮力方法。它能够在一分钟内识别出 3-shanten，但它不是很可靠（有时太长了，并且即使仅 3-shanten 也无法枚举整个空间）。

蛮力方法的改进

想到的一件事是为蛮力方法添加一些智能。天真的方法是添加任何剩余的牌，看看它是否产生了麻将，如果没有，则递归尝试下一个，直到找到为止。假设剩下大约 30 个不同的牌，最大深度是 6（我不确定 7+-shanten 手是否可能[编辑：根据后来开发的公式，最大可能的 shanten 数是（13-1 )*2/3 = 8] )，我们得到 (13*30)^6 种可能性，很大（10^15 范围）。

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

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

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

• 发现无效牌时不要停下来，但记下丢失的牌
• 如果有多种可能的方式来使用瓷砖，请尝试所有方式

这应该是最优的想法，加上一些启发式的，它应该是最优的算法。然而，我发现它很难实现——不过这绝对是可能的。我更喜欢首先编写和维护更容易的解决方案。

使用领域知识的高级方法

与更有经验的玩家交谈，似乎有一些可以使用的法则。例如，一组 3 个瓷砖永远不需要分解，因为这永远不会减少 shanten 数。但是，它可以以不同的方式使用（例如，用于 111 或 123 组合）。

枚举所有可能的 3 组并为每个组创建一个新的模拟。删除 3 组。现在在生成的手牌中创建所有 2 组，并为每个将它们改进为 3 组的牌进行模拟。同时，模拟任何被移除的 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. 通过删除5673 组，我们最终得到一个剩余6的牌，导致 5 组。最好使用两个单独的瓷砖来形成56x和67x，从而导致整体 4-shanten。

要修复，我们必须删除错误的优化，导致以下代码：

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 秒）。

最后一点是根据剩余的单个瓷砖的数量计算 shanten。首先，很明显数字是表格中的3*n+1（因为我们一开始是 14 个牌，总是减去 3 个牌）。

如果还剩 1 张牌，我们已经是 shanten（我们只是在等待最后一对）。剩下 4 张牌，我们必须丢弃其中 2 张以形成 3 组，再次留下一张牌。这导致 2 个额外的丢弃。有 7 张牌，我们有 2 次 2 次弃牌，再加 4。依此类推。

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

所描述的算法运行良好并且通过了我所有的测试，所以我假设它是正确的。如前所述，我无法证明这一点。

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

Answer 2

我最好的猜测是受 A* 启发的方法。您需要找到一些永远不会高估 shanten 数的启发式算法，并仅在可以足够快地进入就绪状态的区域中使用它来搜索蛮力树。

Answer 3

正确的算法示例：syanten.cpp

按顺序从手上递归切割形式：集合、对、不完整形式，并计算它。在所有变化中。结果是所有变体的最小 Shanten 值： Shanten = Min(Shanten, 8 - * 2 - - )

C# 示例（从 c++ 重写）可以在这里找到（俄语）。

Answer 4

我做了一些思考，想出了一个与 mafu 略有不同的公式。首先，考虑一手牌（一手非常糟糕的牌）：

1s 4s 6s 1m 5m 8m 9m 9m 7p 8p 西 东 北

通过使用 mafu 的算法，我们所能做的就是抛出一对 (9m,9m)。然后我们剩下 11 个单曲。现在，如果我们应用 mafu 的公式，我们会得到 (11-1)*2/3，它不是整数，因此不能是 shanten 数。这就是我想出这个的地方：

N = ( (S + 1) / 3 ) - 1

N 代表 Shanten 数，S 代表分数总和。什么是分数？完成一个不完整的集合需要许多图块。例如，如果您手中有 (4,5)，则需要 3 或 6 才能使其成为完整的 3 套，即只有一张牌。所以这个不完整的对得到 1 分。因此，(1,1) 只需要 1 就可以成为 3 组。任何单张牌显然需要 2 张牌才能成为 3 组并得 2 分。任何完整的牌组当然得 0 分。请注意，我们忽略了单打成对的可能性。现在，如果我们尝试在上面的手牌中找到所有不完整的集合，我们会得到：

(4s,6s) (8m,9m) (7p,8p) 1s 1m 5m 9m 西 东 北

然后我们计算它的分数总和 = 1*3+2*7 = 17。现在如果我们将这个数字应用到上面的公式中，我们得到 (17+1)/3 - 1 = 5，这意味着这手牌是 5-shanten . 它比 Alexey 的要复杂一些，我没有证据，但到目前为止它似乎对我有用。请注意，可以以另一种方式解析这样的手。例如：

(4s,6s) (9m,9m) (7p,8p) 1s 1m 5m 8m 西 东 北

但是，它仍然根据公式得到分数总和 17 和 5-shanten。我也无法证明这一点，这比 Alexey 的公式要复杂一些，但也引入了可以应用于其他事物的分数（？）。

Answer 5

看看这里：ShantenNumberCalculator。计算shanten真的很快。还有一些相关的东西（日语，但有代码示例）http://cmj3.web.fc2.com

算法的本质：以所有可能的方式切出所有对、集合和未完成的形式，从而找到shanten数的最小值。普通手牌的最大值：8。

也就是说，我们有 4 组和一对的开始，但每组只有一个牌（总共 13 - 5 = 8）。因此，一对将减少一个单板的数量，两个（与其余的隔离）相邻的瓷砖（预设）将减少单板的数量，一套完整的（3个相同的或3个连续的瓷砖）将减少数量shantens 2，因为两个合适的瓷砖来到一个孤立的瓷砖。

Shanten = 8 - 组 * 2 - 对 - 预设

Answer 6

确定您的手是否已经在tenpai 听起来像是一个多背包问题。贪心算法行不通——正如 Dialecticus 指出的那样，您需要考虑整个问题空间。