麻將紙牌求解器算法，需要加速

Question

我正在開發一個麻將紙牌求解器，到目前爲止，我做得很好。然而， 它不是我想要的那麼快，所以我要求任何額外的優化 技術你們可能知道。

所有的瓷磚都從佈局中知道，但解決方案不是。目前，我有幾個規則可以保證安全移除某些相同瓷磚對（這不能成爲可能的解決方案的障礙）。

爲了清楚起見，當瓷磚隨時可以被揀選並且瓷磚鬆散時瓷磚是免費的，而瓷磚根本不會綁定任何其他瓷磚。

• 如果有四個免費的免費磁貼可用，立即刪除它們。
• 如果有三塊瓷磚可以被撿起，而且至少其中一塊瓷磚是鬆散的瓷磚，請將其取下。
• 如果有三塊瓷磚可以撿起並且只有一塊免費瓷磚（兩塊瓷磚鬆動），請移除空閒的瓷磚和一塊隨機的瓷磚。
• 如果有三個可用的鬆動瓷磚，請將其中的兩個去掉（不要緊）哪一個。
• 由於有四次完全相同的圖塊，如果剩下兩個圖塊，請刪除它們，因爲它們是唯一剩下的圖塊。

我的算法遞歸搜索多線程的解決方案。一旦一個分支完成（到一個沒有更多移動的位置）並且它不會導致解決方案，它會將該位置放在一個包含壞分支的向量中。現在，每次啓動一個新分支時，它都會通過不良位置進行迭代檢查，如果該特定位置已經被檢查過。
該過程一直持續到找到解決方案或正在檢查所有可能的位置。

這很適合包含36或72瓦的佈局。但是當更多的時候，由於需要搜索大量的頭寸，這個算法變得非常無用。所以，我再問你一次，如果你們有什麼好的想法，如何實施更多的安全瓷磚移除規則或任何其他特定的加速算法。

非常問候， nhaa123

Answer 1

我不完全理解你的求解器是如何工作的。當你有選擇的動作時，你如何決定首先探索哪種可能性？

如果你選擇一個任意的，那就不夠好 - 基本上這只是一個粗暴的搜索。您可能需要首先探索「更好的分支」。要確定哪些分支「更好」，您需要一個啓發式函數來評估一個位置。然後，您可以使用流行的啓發式搜索算法之一。檢查這些：

• A *搜索
• 束搜索

（谷歌是你的朋友）

Answer 2

而是含有 「壞」 位置的載體，使用一組具有不變的查找時間而不是線性的。

Answer 3

在進行優化時，明確問自己線程是否在HW線程上運行，以及它們是否可以獨立運行，否則它們可能會減速而不是加速。

同樣如raindog-2所述。訂購您的搜索路徑。你有規則，所以根據這些規則給予積分。去尋找最大寬鬆的瓷磚，然後獲得最大的免費瓷磚。 因此，請嘗試在某種情況下可以執行的每一步，然後排序並繼續處理最佳狀況。

Answer 4

幾年前，我寫了一個程序，通過偷看解決紙牌麻將板。我用它來檢查一百萬只海龜（在一臺計算機上花了一天或一天​​的時間：它有兩個核心），似乎有大約2.96％不能解決。

http://www.math.ru.nl/~debondt/mjsolver.html

好吧，這不是你問什麼，但你可能有一個看代碼找到它的一些修剪啓發式沒有越過你的心靈迄今。該程序不會使用超過幾兆字節的內存。