这是我之前关于决定一只手准备就绪的问题的后续内容.
对麻将规则的了解非常好,但基于扑克或罗姆的背景也足以理解这个问题.
在Mahjong中,14个瓷砖(瓷砖就像扑克中的卡片)被安排成4套和一对.笔直("123")总是使用3个瓷砖,而不是更多而不是更少.一组相同类型("111")也包含3个瓷砖.这导致3*4 + 2 = 14个瓦片的总和.
有一些例外,如Kan或十三个孤儿,这里没有相关性.颜色和值范围(1-9)对于算法也不重要.
一只手由13块瓷砖组成,每次我们轮到我们选择一块新瓷砖并且必须丢弃任何瓷砖,所以我们留在13块瓷砖上 - 除非我们能够使用新挑选的瓷砖获胜.
可以安排形成4组和一对的手是"准备好"的.只需要交换1块瓷砖的手称为"tenpai",或"1 ready from ready".任何其他手牌都有一个shanten数字,表示需要交换多少牌块才能在tenpai中.因此,具有shanten数量为1的手需要1个瓷砖为tenpai(并且相应地准备2个瓷砖).一个shanten数为5的手需要5个瓷砖才能成为tenpai,依此类推.
我正在尝试计算一只手的数字.谷歌搜索了几个小时,阅读了关于这个主题的多篇文章和论文,这似乎是一个未解决的问题(蛮力方法除外).我能找到的最接近的算法依赖于偶然性,即它无法在100%的时间内检测到正确的数字.
我将解释一下实际规则(简化),然后我的想法如何解决这个任务.在麻将中,有4种颜色,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-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上完成.
为了避免更长时间地绘制此文本,您可以在维基百科上阅读更多示例或在谷歌上使用各种搜索结果之一.所有这些都有点技术性,所以我希望上面的描述就足够了.
如上所述,我想计算一只手的shanten数.我的想法是根据颜色将瓷砖分成4组.接下来,所有图块在其各自的组内被分类成集合,以便在荣誉组中以三元组,对或单个图块结束,或者另外,在3个正常组中结合.已完成的集将被忽略.对数进行计数,最终数量减少(最后我们需要1对).单个图块将添加到此编号.最后,我们将数字除以2(因为每次我们选择一个能让我们接近tenpai的好的瓷砖,我们就可以摆脱另一个不需要的瓷砖).
但是,我不能证明这个算法是正确的,而且我也很难将直道包含在近距离包含许多瓷砖的困难群体中.各种想法都值得赞赏.我正在使用.NET进行开发,但也欢迎使用伪代码或任何可读语言.
我已经考虑过这个问题了.要查看最终结果,请跳到上一部分.
首先,我写了一个蛮力的方法.它能够在一分钟内找出3 shanten,但它不是非常可靠的(有时也长了不少,并列举了整个空间甚至仅有3 shanten是不可能的).
我想到的一件事是为蛮力方法增加一些智慧.天真的方法是添加任何剩余的瓷砖,看它是否产生麻将,如果没有递归尝试,直到找到它.假设有左约30不同瓦片和最大深度为6(我不知道如果7 + -shanten手甚至有可能[编辑:根据以后开发的配方,最大可能数目shanten是(13-1 )*2/3 = 8]),我们得到(13*30)^ 6种可能性,这是大的(10 ^ 15范围).
但是,没有必要将每个剩余的瓷砖放在手中的每个位置.由于每种颜色本身都必须完整,我们可以将瓷砖添加到相应的颜色组中,并记下该组本身是否完整.总共只有1对的细节并不难添加.这样,存在最大约(13*9)^ 6种可能性,即大约10 ^ 12并且更可行.
我的下一个想法是使用我早期编写的代码来测试Mahjong并以两种方式修改它:
这应该是最佳的想法,并且添加一些启发式算法应该是最优算法.但是,我发现它很难实现 - 但它绝对是可能的.我希望首先更容易编写和维护解决方案.
与经验丰富的玩家交谈时,似乎可以使用一些法律.例如,一组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.通过移除5673组,我们最终得到一个左侧的6瓦片,导致5-shanten.最好使用两个单个瓷砖来形成,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
我相信这总能准确找到最小的数字,但我不知道如何证明这一点.所花费的时间是在"合理的"范围内(在我的机器上最多10秒,通常是0秒).
最后一点是计算剩余单个图块数量的shanten.首先,很明显这个数字是在形式中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;即使对于高数字也很好.