高速化が必要な麻雀ソリティア ソルバー アルゴリズム

Question

私は麻雀ソリティア ソルバーを開発していますが、今のところかなりうまくいっていました。しかし、それは私がそれを望んでいるほど速くはないので、私はあなたが知っているかもしれない追加の最適化技術を求めています。

すべてのタイルはレイアウトからわかりますが、解決策はわかりません。現時点では、同じタイルの特定のペアの安全な除去を保証するルールはほとんどありません（これは、可能な解決策の障害にはなりません）。

明確にするために、タイルはいつでもピックできる場合はフリーであり、タイルが他のタイルをまったく束縛していない場合はタイルが緩んでいます。

• 空きタイルが 4 つある場合は、すぐに削除してください。
• 拾えるタイルが 3 つあり、そのうちの少なくとも 1 つが緩いタイルである場合は、緩んでいないタイルを取り除きます。
• 拾えるタイルが 3 つあり、フリー タイルが 1 つだけ (ルーズが 2 つ) の場合は、フリー タイルとランダムなルーズ 1 つを削除します。
• 3 つのルース タイルが利用可能な場合は、そのうちの 2 つを削除します (どのタイルでも構いません)。
• まったく同じタイルが 4 つあるので、2 つ残っている場合は、それしか残っていないので削除します。

私のアルゴリズムは複数のスレッドで解決策を再帰的に検索します。分岐が終了し (もう移動のない位置まで)、解決策に至らなかった場合、その位置は不良ベクトルを含むベクトルに入れられます。これで、新しいブランチが起動されるたびに、特定の位置がすでにチェックされているかどうかを確認するために、不正な位置を反復処理します。
このプロセスは、解決策が見つかるか、すべての可能な位置がチェックされるまで続きます。

これは、たとえば 36 個または 72 個のタイルを含むレイアウトでうまく機能します。しかし、もっとある場合、このアルゴリズムは、検索する膨大なポジションのためにほとんど役に立たなくなります。

そこで、もう一度お願いします。安全なタイルの削除やアルゴリズムに関するその他の特定の高速化のためのルールをさらに実装する方法について、良いアイデアをお持ちの方がいらっしゃいましたらお願いします。

よろしく、NHAA123

Answer 1

ソルバーがどのように機能するのか完全に理解できません。手を選択するとき、どの可能性を最初に検討するかをどのように決定しますか?

任意のものを選択した場合、それは十分ではありません。基本的に、それは単なる総当たり検索です。最初に「より良いブランチ」を探索する必要があるかもしれません。どのブランチが「より良い」かを判断するには、位置を評価するヒューリスティック関数が必要です。次に、一般的なヒューリスティック検索アルゴリズムの 1 つを使用できます。以下を確認してください。

• 検索
• ビームサーチ

(Google はあなたの友達です)

Answer 2

数年前、私はソリティア麻雀盤を覗き見ることで解くプログラムを書きました。私はこれを使って 100 万匹のカメを調べました (コンピューターの半分で 1 日かそこらかかりました:2 つのコアがありました)、そのうちの約 2.96% は解決できないようでした。

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

OK、それはあなたが質問したことではありませんが、コードを見て、これまで思いつかなかった枝刈りヒューリスティックを見つけることができるかもしれません。プログラムは数メガバイトを超えるメモリを使用しません。

Answer 3

「悪い」位置を含むベクトルの代わりに、線形ではなく一定の検索時間をもつセットを使用します。