1

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

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

明確にするために、タイルはいつでも選択できる場合は無料で、他のタイルをまったくバインドしていない場合はタイルが緩んでいます。

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

私のアルゴリズムは、複数のスレッドでソリューションを再帰的に検索します。ブランチが終了し（これ以上移動がない位置に）、それが解決に至らなかった場合、それは悪いものを含むベクトルにその位置を置きます。これで、新しいブランチが起動されるたびに、その特定の位置がすでにチェックされているかどうかをチェックするために、悪い位置を繰り返し処理します。
このプロセスは、解決策が見つかるか、すべての可能な位置がチェックされるまで続きます。

これは、たとえば36または72タイルを含むレイアウトでうまく機能します。しかし、それ以上になると、検索する位置が膨大になるため、このアルゴリズムはほとんど役に立たなくなります。

ですから、安全なタイルの削除やアルゴリズムに関するその他の特定の高速化のために、より多くのルールを実装する方法について良いアイデアがあれば、もう一度お聞きします。

よろしくお願いいたします。nhaa123

4

4 に答える 4

2

ソルバーがどのように機能するかを完全には理解していません。動きの選択肢がある場合、最初に探索する可能性をどのように決定しますか？

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

  • 検索
  • ビームサーチ

（Googleはあなたの友達です）

于 2009-05-27T07:57:57.687 に答える
2

数年前、私はソリティア麻雀ボードを覗いて解決するプログラムを書きました。私はそれを使って100万匹のカメを調べました（コンピューターの半分で1日か何かを取りました：2つのコアがありました）、そしてそれらの約2.96パーセントは解決できないようでした。

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

わかりました、それはあなたが尋ねたものではありませんでしたが、コードを見て、これまで気にならなかったいくつかの剪定ヒューリスティックを見つけることができるかもしれません。プログラムは、数メガバイトを超えるメモリを使用しません。

于 2010-10-14T23:19:58.590 に答える
0

「悪い」位置を含むベクトルの代わりに、線形の代わりに一定のルックアップ時間を持っているセットを使用してください。

于 2009-05-27T08:06:52.533 に答える
0

4つのタイルが表示されているが拾えない場合は、最初に周囲の他のタイルを削除する必要があります。パスは、ルールを使用して、これらのタイルに向かって最小限のタイルを削除し、それらを開く必要があります。

タイルが他のタイルによって隠されている場合、問題にはパスを見つけるための完全な情報がなく、残りのタイルの確率を計算する必要があります。

とてもいい問題です！

于 2021-03-14T17:24:29.657 に答える