麻将纸牌求解器算法，需要加速
我正在开发一个麻将纸牌解算器，到目前为止，我做得很好。 然而， 它没有我希望的那么快，所以我要求任何额外的优化 你们可能知道的技术。
所有的图块都可以从布局中得知，但解决方案却不是。 目前，我有几个 保证安全移除某些相同瓷砖对的规则（这不会成为可能解决方案的障碍）。
为了清楚起见，当一块瓷砖可以随时拾取时，它是自由的；当它根本不绑定任何其他瓷砖时，一块瓷砖是松散的。
- 如果有四个可用的免费瓷砖，请立即将其移除。
- 如果可以捡起三块瓷砖，并且其中至少一块是松动的瓷砖，则将非松动的瓷砖移走。
- 如果有三块可以拾取的牌，而只有一张空闲的牌（两块松散的），则移除空闲的和随机松散的一块。
- 如果有三块松散的瓷砖可用，请移除其中两块（无论是哪一块）。
- 由于完全相同的图块有四倍，因此如果剩下其中两个，请将它们删除，因为它们是唯一剩下的。
我的算法在多个线程中递归地搜索解决方案。 一旦分支完成（到达没有更多移动的位置）并且它没有导致解决方案，它就会将该位置放入包含不良位置的向量中。 现在，每次启动新分支时，它都会遍历错误位置来检查该特定位置是否已被检查。
此过程持续进行，直到找到解决方案或检查所有可能的位置。
这在包含 36 或 72 个图块的布局上效果很好。 但当有更多的时候， 由于需要搜索的位置数量巨大，该算法几乎变得毫无用处。
因此，我再次询问你们，是否有人有好的想法，如何实施更多规则来安全地移除瓷砖或任何其他有关算法的特定加速。
美好祝愿， 恩哈亚123
I'm developing a Mahjong-solitaire solver and so far, I'm doing pretty good. However,
it is not so fast as I would like it to be so I'm asking for any additional optimization
techniques you guys might know of.
All the tiles are known from the layouts, but the solution isn't. At the moment, I have few
rules which guarantee safe removal of certain pairs of same tiles (which cannot be an obstacle to possible solution).
For clarity, a tile is free when it can be picked any time and tile is loose, when it doesn't bound any other tiles at all.
- If there's four free free tiles available, remove them immediately.
- If there's three tiles that can be picked up and at least one of them is a loose tile, remove the non-loose ones.
- If there's three tiles that can be picked up and only one free tile (two looses), remove the free and one random loose.
- If there's three loose tiles available, remove two of them (doesn't matter which ones).
- Since there is four times the exact same tile, if two of them are left, remove them since they're the only ones left.
My algorithm searches solution in multiple threads recursively. Once a branch is finished (to a position where there is no more moves) and it didn't lead to a solution, it puts the position in a vector containing bad ones. Now, every time a new branch is launched it'll iterate via the bad positions to check, if that particular position has been already checked.
This process continues until solution is found or all possible positions are being checked.
This works nicely on a layout which contains, say, 36 or 72 tiles. But when there's more,
this algorithm becomes pretty much useless due to huge amount of positions to search from.
So, I ask you once more, if any of you have good ideas how to implement more rules for safe tile-removal or any other particular speed-up regarding the algorithm.
Very best regards,
nhaa123
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我不完全理解你的解算器是如何工作的。 当你可以选择行动时，你如何决定首先探索哪种可能性？
如果你任意选择一个，那还不够好——基本上，这只是粗暴搜索。 您可能需要首先探索“更好的分支”。 要确定哪些分支“更好”，您需要一个评估位置的启发式函数。 然后，您可以使用一种流行的启发式搜索算法。 检查这些：
（Google 是你的朋友）
I don't completely understand how your solver works. When you have a choice of moves, how do you decide which possibility to explore first?
If you pick an arbitrary one, it's not good enough - it's just brute search, basically. You might need to explore the "better branches" first. To determine which branches are "better", you need a heuristic function that evaluates a position. Then, you can use one of popular heuristic search algorithms. Check these:
(Google is your friend)
几年前，我编写了一个程序，通过查看纸牌麻将牌来解决问题。 我用它检查了 100 万只海龟（在半台计算机上花了一天左右的时间：它有两个核心），似乎其中大约 2.96% 无法解决。
http://www.math.ru.nl/~debondt/mjsolver.html
好吧，这不是你问的，但你可能会看一下代码，找到一些到目前为止你还没有想到的修剪启发式方法。 该程序使用的内存不超过几兆字节。
Some years ago, I wrote a program that solves Solitaire Mahjongg boards by peeking. I used it to examine one million turtles (took a day or something on half a computer: it had two cores) and it appeared that about 2.96 percent of them cannot be solved.
http://www.math.ru.nl/~debondt/mjsolver.html
Ok, that was not what you asked, but you might have a look at the code to find some pruning heuristics in it that did not cross your mind thus far. The program does not use more than a few megabytes of memory.
使用具有恒定查找时间而不是线性查找时间的集合，而不是包含“坏”位置的向量。
Instead of a vector containing the "bad" positions, use a set which has a constant lookup time instead of a linear one.
如果有 4 个图块可见但无法拾取，则必须先移除周围的其他图块。 路径应该使用您的规则移除最少的图块，朝向这些图块，以打开它们。
如果图块被其他图块隐藏，则问题没有完整的信息来查找路径，并且需要计算剩余图块的概率。
非常好的问题！
If 4 Tiles are visible but can not be picked up, the other Tiles around have to be removed first. The Path should use your Rules to remove a minimum of Tiles, towards these Tiles, to open them up.
If Tiles are hidden by other Tiles, the Problem has no full Information to find a Path and a Probability of remaining Tiles needs to be calculated.
Very nice Problem!