logo标签列表

如何计算麻将中的向听数？

algorithmmahjong
9
这是我关于判断手牌是否准备好的后续问题。
了解麻将规则非常好，但具有类似扑克或罗密欧的背景也足以理解这个问题。
在麻将中，14张牌（类似于扑克牌）被排列成4组和一对。一个顺子（“123”）总是使用恰好3张牌，既不多也不少。同种类的一组（“111”）也由恰好3张牌组成。这导致总共需要14张牌，即3 * 4 + 2。
有各种例外情况，例如Kan或Thirteen Orphans，在此不相关。颜色和值范围（1-9）对算法也不重要。
一手牌由13张牌组成，每次轮到我们时，我们可以拿一张新牌并必须弃掉任何一张牌，以保持13张牌 - 除非我们能够使用新拿的牌赢得游戏。
一手牌可以组成4副牌和1对牌时，被称为"ready"。只需要交换1张牌就能达到"tenpai"或"1 from ready"的状态。其他任何手牌都有一个"shanten-number"来表示需要交换多少张牌才能达到"tenpai"状态。所以，shanten number为1的手牌需要交换1张牌才能达到"tenpai"状态（相应地需要交换2张牌才能达到"ready"状态）。shanten number为5的手牌需要交换5张牌才能达到"tenpai"状态，以此类推。
我正在尝试计算手牌的shanten number。在Google上搜索了几个小时并阅读了多篇关于这个话题的文章和论文后，似乎这仍然是一个未解决的问题（除了暴力方法）。我找到的最接近的算法依赖于机会，即它不能100％地检测出正确的shanten number。
规则：
我将简要解释实际规则（简化版），然后提出我的想法来解决这个任务。在麻将中，有4种颜色，其中3种是像纸牌游戏（A、红桃等）一样的普通颜色，称为“万”、“筒”和“索”。这些颜色分别从1到9，并且可以用于形成顺子以及相同种类的组合。第四种颜色称为“字牌”，只能用于相同种类的组合，而不能用于顺子。七种字牌将被称为“东、南、西、北、红中、发财、白板”。
让我们看一个听牌的例子：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向听的手牌，即需要额外一张牌才能进入听牌状态。在这种情况下，将一张2p换成一张3p可以使我们回到听牌状态，因此通过抽取一张3p和一张E，我们获胜。

1p，1p，5p，5p，9p，9p，E，E，E，S，S，W，W 是一手两向听的牌组。其中有1个刻子和5个对子。为了完成这手牌组，我们需要再得到一个对子，所以当我们选择其中的1p、5p、9p、S或W中的一个时，就需要弃掉另外一个对子。例如：我们选择一个1饼并丢掉一个W，则手牌现在是1向听，如下所示：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上阅读更多示例或使用谷歌的各种搜索结果。它们都有点技术性，所以我希望以上描述足够了。
算法
正如所述，我想计算手牌的向听数。我的想法是将牌分成4组，根据它们的颜色进行分类。接下来，所有牌都按其各自组内的集合排序，以便我们最终得到雀头组中的三张牌、对子或单张牌，或者在3个普通组中还有顺子。完成的组被忽略。对子被计算，最终数字递减（我们最终需要1对）。单张牌加入到此数字中。最后，我们将数字除以2（因为每次我们选择一张好的牌使我们更接近听牌时，我们可以摆脱另一张不需要的牌）。
然而，我无法证明这个算法是正确的，而且我也很难将顺子合并到包含许多接近范围的牌的困难组中。欢迎任何类型的想法。我正在开发.NET，但伪代码或任何可读语言也是受欢迎的。
无论如何，您都必须搜索整个空间。考虑这手牌：1 2 2 3 3 3 4 4 5，全部为同一颜色。选择333是错误的，因为有更好的选择：123、234、345。所以即使您选择了一个三元组，可能仍有更好的选择。您必须全部搜索。 - Dialecticus
由于这篇文章变得相当冗长且有趣，因此我进行了整理，并在我的博客上发布了这个问题，网址为http://blog.mafutrct.de/2898/how-do-i-calculate-the-shanten-number-in-mahjong。 - mafu
在研究这个问题时，我发现了这篇不错的博客文章：http://blog.ezyang.com/2014/04/calculating-shanten-in-mahjong/ - Rémi
6个回答
6

我对这个问题进行了更深入的思考。要查看最终结果，请跳到最后一节。

第一个想法：蛮力方法

首先，我写了一个蛮力方法。它能够在一分钟内识别出3向听，但不是非常可靠（有时需要更长时间，即使只是3向听，枚举整个空间也是不可能的）。

改进蛮力方法

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

然而，没有必要在手中的每个位置上都放置每个剩余的牌。由于每种颜色必须完全独立，因此我们可以将牌添加到相应的颜色组中，并记录该组是否完全独立。添加确切的1对整体等细节并不难。这样，最多有（13 * 9）^ 6种可能性，即约为10 ^ 12，更可行。

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

我的下一个想法是使用我早期编写的代码来测试麻将，并以两种方式修改它：

  • 发现无效手时不要停止，而是记录缺少的牌
  • 如果有多种可能使用一张牌，则尝试全部使用

这应该是最优的想法，并且通过添加一些启发式应该是最优的算法。但是，我发现它很难实现-虽然肯定是可能的。我更喜欢先写一个更容易编写和维护的解决方案。

使用领域知识的高级方法

与经验更丰富的玩家交谈后，似乎有一些可以使用的法则。例如，一组3个牌永远不需要分开，因为那永远不会减少向听数。但是，它可以以不同的方式使用（例如，用于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。通过删除567 3组，我们最终剩下一个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

我相信这个算法总是能准确地找到最小的向听数，但我不知道如何证明它。在我的电脑上，花费的时间在“合理”的范围内（最多10秒，通常为0秒）。
最后一点是根据剩余单牌数量计算向听数。首先，很明显这个数字的形式是3*n+1（因为我们开始有14张牌，并且总是减去3张牌）。
如果只剩下1张牌，那么我们已经是听牌了（我们只等待最后一对）。当只剩下4张牌时，我们必须弃掉其中的2张牌以形成一个3组，然后再次只剩下1张牌。这导致额外的2次弃牌。当有7张牌时，我们有2次2次弃牌，增加4次。以此类推。
这导致简单的公式shanten_added = (number_of_singles - 1) * (2/3)。
所述算法运行良好并通过了所有我的测试，因此我认为它是正确的。正如所述，我无法证明它。
由于该算法首先删除最可能的牌组合，因此它具有内置的优化。添加一个简单的检查if (current_depth > best_shanten) then return;，即使对于高向听数也能很好地工作。
2

我最好的猜测是采用A*算法。您需要找到一些启发式方法，它不会高估听牌数，并将其用于在可能快速进入就绪状态的区域中搜索暴力树。

1

请看这里: ShantenNumberCalculator。快速计算上听数。还有一些相关内容（用日语写的，但有代码示例）http://cmj3.web.fc2.com

算法的精髓：以所有可能的方式切割出所有对子、面子和未完成的形式，并通过此找到上听数的最小值。 普通手牌的上听数最大值为8。

也就是说，我们有4个面子和一个对子的开始，但只有每个面子或对子中的一张牌（总共13-5=8）。 因此，一个对子将减少一张牌的上听数，两个相邻的牌（预设）将减少一张牌的上听数， 一个完整的面子（3张相同或3张连续的牌）将减少两张牌的上听数，因为两张合适的牌来到了一张孤立的牌。

上听数 = 8 - 面子数 * 2 - 对子数 - 预设数

1

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

1s 4s 6s 1m 5m 8m 9m 9m 7p 8p West East North

使用 mafu 的算法，我们只能去掉一对（9m，9m）。然后我们剩下 11 张单牌。现在如果我们应用 mafu 的公式，我们得到 (11-1)*2/3，这不是整数，因此不能成为向听数。这就是我想出这个公式的原因：

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

N代表向听数，S代表分数总和。 什么是分数？它是你需要的牌数来完成不完整的牌组。例如，如果你手里有（4,5），你需要3或6才能使它成为一个完整的三个牌组，也就是只需要一张牌。因此，这个不完整的对子得到1分。同样地，（1,1）只需要1张牌就可以变成三个牌组。任何单个牌显然需要2张牌才能变成三个牌组，并获得2分。当然，任何完整的牌组都得到0分。请注意，我们忽略了单张牌变成对子的可能性。现在，如果我们尝试找到上面手牌中所有不完整的牌组，我们会得到：

（4s，6s）（8m，9m）（7p，8p）1s 1m 5m 9m 西风 东风 北风

然后我们计算它的牌型分数总和= 1*3+2*7 = 17。现在，如果我们将这个数字应用于上面的公式，我们得到(17+1)/3 - 1 = 5，这意味着这手牌是5向听。这比Alexey的公式要复杂一些，我没有证明，但到目前为止似乎对我有效。请注意，这样的手牌也可以用另一种方式解析。例如：(4s,6s) (9m,9m) (7p,8p) 1s 1m 5m 8m West East North。然而，根据公式，它仍然得分总和为17和5向听。我也无法证明这一点，这比Alexey的公式更加复杂，但也引入了可以应用于其他事物的分数。
0

判断你的手牌是否已经听牌听起来像是一个多重背包问题。贪心算法行不通 - 正如Dialecticus指出的那样，你需要考虑整个问题空间。

0

正确的算法示例：syanten.cpp

按顺序从手牌中递归切割出：面子、对子、不完整的形式，并计数。对于所有变化，取最小的Shanten值作为结果： Shanten = Min(Shanten, 8 - * 2 - - )

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

请勿仅提供链接，您的回答应该能独立存在而没有链接。 - mmmmmm
谢谢Alexey，我大致了解那段代码正在发生什么（尽管我不会说一句俄语），我会进行调查。 - mafu
我发现我使用了几个类似的模式。这似乎是一种没有启发式的暴力方法，对吗？顺便问一下，这是你写的吗？我总是很感兴趣与其他麻将程序员联系。 - mafu
这就是为什么你不应该只回答一个链接：链接已经失效，使得这个回答毫无用处。 - Kryomaani
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接