パズル ゲーム Flood-It をプレイするのが好きです。このゲームは次の URL でオンラインでプレイできます。
https://www.lemoda.net/javascript/flood-it/game.html
iGoogle ガジェットとしても利用できます。目的は、連続するフラッド フィルの数を最小限に抑えてボード全体を埋めることです。
このパズルを最適に解決できるプログラムを作成しようとしています。この問題にアプローチする最善の方法は何ですか? 理想的にはA*アルゴリズムを使用したいのですが、残りのステップ数を推定する関数がどうあるべきかわかりません。塗りつぶされた領域を最大化するために深さ 4 のブルート フォース検索を実行するプログラムを作成しました。それはかなりうまく機能し、パズルを解くことで私を打ち負かしましたが、私はそのアルゴリズムに完全に満足していません.
助言がありますか？前もって感謝します。
ヒューリスティックとして、各ノードが連続した同じ色の四角形のセットを表し、各ノードが接触するノードに接続されているグラフを作成できます。(各エッジは 1 として重み付けされます)。次に、パス検索アルゴリズムを使用して、左上から他のすべてのノードまでの「距離」を計算できます。次に、他の 5 色のそれぞれを使用してフラッド フィリングの結果を見て、どれが「最も遠い」ノードまでの距離を最小化するかを判断します。これがボトルネックになる可能性が高いためです。
その計算の結果をこれまでに行われた塗りつぶしの数に追加し、それを A* ヒューリスティックとして使用します。
ゲームを数回プレイした後、私は良い戦略は常に「深く」行き、洪水のない領域に最も遠くまで行く色を選ぶことであることに気付きました.
A* は単なる優先グラフ検索です。各ノードはゲームの状態であり、ヒューリスティックに基づいてノードをランク付けし、常に予想される最終コストが最も低いノードを展開します。ヒューリスティックがコストを過小評価しない限り、最初に見つけたソリューションが最適であることが保証されます。
数回ゲームをプレイした後、反対側のコーナーにドリルしてすべてのコーナーにドリルしようとすると、勝つ傾向があることがわかりました。したがって、適切な開始コストの見積もりは、(これまでのコスト) + 反対側のコーナーに到達するのに十分な数の塗りつぶしになります [注: 最小ではなく、十分です。貪欲にコーナーに向かって埋めて、ヒューリスティックを計算します]。
Smashery の答えは少し調整できます。推定移動数の合計について、最大距離に「k」個の色がある場合、推定移動数に「k-1」を追加します。
より一般的には、色ごとに、色をクリアできる最大距離を考慮します。これにより、いくつかの最大距離を、その距離でクリアできるゼロ以外の数の色にマッピングする辞書が得られます。キー全体で値-1 を合計し、これを最大距離に追加して、推定移動数を取得します。
また、無料のケースもあります。いずれかの時点で 1 つの手で色をクリアできれば、他の手は考慮せずにその手を取ることができます。
私はこれに取り組んでおり、ソルバーが機能するようになった後、他の人が取ったアプローチを調べました。
そこにあるほとんどのソルバーはヒューリスティックであり、最適性を保証しません。ヒューリスティックは、選択されていない正方形の数と色の分布、または「最も遠い」正方形までの距離を調べます。優れたヒューリスティックと境界のある DFS (または先読みを伴う BFS) を組み合わせると、標準の 14x14 グリッドに対して非常に高速なソリューションが得られます。
「良い」パスだけでなく、証明可能な最適なパスを見つけることに興味があったため、少し異なるアプローチを取りました。かなり多くの重複する位置があるため、検索空間は実際には検索ツリーの分岐係数よりもはるかにゆっくりと成長することがわかりました。(したがって、深さ優先戦略では、冗長な作業を避けるために履歴を維持することが重要です。) 有効な分岐係数は、5 よりも 3 に近いようです。
私が取った検索戦略は、状態の数が実行不可能になる「中間点」の深さまで BFS を実行することです。次に、中点の深さで各状態を調べ、それをルートとして開始する新しい BFS を実行します。これらの BFS 検索はどちらも、前の深さで見つかった状態を除外することで刈り取ることができ、後者の検索は、最もよく知られている解の深さによって制限することができます。(2 番目のステップで調べたサブツリーの順序にヒューリスティックを適用することも、おそらく役立つでしょう。)
高速ソルバーの鍵であることが証明されたもう 1 つの剪定手法は、現在の最適解から N ステップ以下離れている場合に、N 色以上が残っているかどうかを単純にチェックすることです。
どの中点状態が最適解へのパス上にあるかがわかると、プログラムはその中点状態を目標として使用して DFS を実行できます (そして、中点にない四角形を選択するパスを枝刈りします)。 BFS ステップでパスを構築しますが、メモリがいくらか追加されます。
私のソルバーは超高速ではありませんが、保証された最適解を数分以内に見つけることができます。( http://markgritter.livejournal.com/673948.html、またはhttp://pastebin.com/ZcrS286bのコードを参照してください。)
Smashery のヒューリスティックをサポートするためにグラフを実装するためのアイデアを次に示します。
隣接する同じ色の正方形の各グループを素集合で表し、隣接する正方形のグループのリストを表します。フラッド フィルは、セットを隣接するすべてのセットにマージし、隣接リストをマージします。この暗黙的なグラフ構造により、左上隅から最も遠いノードまでの距離を見つけることができます。
現在の色に一致する、または一致しない正方形の数を考慮することができると思います。したがって、「距離」のヒューリスティックな尺度は、ステップ数ではなく、選択した色と同じ色ではないボード上の正方形の数になります。
単純なヒューリスティックは、残っている色の数 (マイナス 1) を使用することです。これは、ボードをクリアするのに少なくとも同じ回数のクリックが必要になるため、許容されます。
確かではありませんが、これが貪欲に解決できることはかなり確信しています。カラー フィールドの数を 1 に減らそうとしているので、より多くのカラー フィールドを先に減らしても、以前に減らした場合よりも効率が低下することはありません。
1) 既存の同色グループのコレクションを定義します。
2) コレクションごとに、隣接するコレクションの数を色別に数えます。単一の色を持つ隣接するコレクションの最大数は、このコレクションの重みです。
3) 単一の色の隣接点の数が最も多いコレクションを取得し、その色で塗りつぶします。コレクションをマージし、マージによって影響を受けるすべてのコレクション (マージされたコレクションのすべての新しい隣接) の並べ替えを更新します。
全体として、これは実際には O(n log n) 時間で計算する必要があると思います。ここで、n はピクセル数で、log(n) はソートされた重みのリストを維持することからのみ得られます。
ただし、複数のフィールドの重みが同じ場合にタイブレーカーが必要かどうかはわかりません。おそらく、タイブレーカーは、マップ上のほとんどのグループに共通する色になります.
いずれにせよ、ゲームの目的は異なるカラー フィールドの数を減らすことであり、周囲を最大化することではないことに注意してください。さまざまなカラー スキームによって、より大きなフィールドが次善の選択となる場合があるからです。次のフィールドを検討してください。
3 3 3 3 3
1 1 1 1 1
1 1 1 1 1
2 2 2 2 2
1 2 2 2 2
色 1 の周囲の長さはどの尺度よりも大きくなりますが、色 2 が最適な選択です。
編集>
それをスクラッチします。例：
3 1 3 1 3
1 1 1 1 1
1 1 1 1 1
2 2 2 2 2
1 2 2 2 2
私自身の貪欲なアルゴリズムを無効にします。しかし、2 つの隣人が共有する色に変更すると1 つではなく2 つのノードにアクセスするため、これが単純なグラフ トラバーサルであるとは確信できません。
色の除去は、おそらくヒューリスティックで何らかの役割を果たすはずです。
1) グラフにまだない色で塗りつぶすことは決して正しくありません。
2) 固有の色を持つカラー フィールドが 1 つある場合、少なくとも 1 つの塗りつぶしが必要になります。他のフィルとの同梱はできません。これは、遅かれ早かれそれを埋めるのが安全であることを意味すると思います。
3) 隣接フィールド カウントの貪欲なアルゴリズムは、2 色マップに適しています。