19

ゲーム Globs ( http://www.deadwhale.com/play.php?game=131 ) を解決するためのアルゴリズムとデータ構造を提案してください。オタクな意味でとても楽しいです。

アプローチの時空間の複雑さ (big-O) をグリッドのサイズ (N>=14) で表します。複雑さが低く、十分に効率的なアルゴリズムが優先されます。

(MatrixFrog は、このゲームが FloodIt としても知られていることを正しく指摘しており、Smashery は 3 か月前に、彼が以下に引用したリンクで解決策を示しました。あなたたち全員が、最適ではない解決策を提供する 1 回の先読みのみでプルーニング/貪欲を提案しています。)

ゲームは nxn ノードのランダムな正方形グリッドを生成します。各ノードは 6 色 (Grn=1、Ylw=2、Red=3、Blu=4、Pur=5、Orn=6) のいずれかに着色されています。レベル 1 には 9x9 のグリッドがあり、n は各レベルを最大 14 まで増やします。各レベルは最大 25 ターンを取ることができます。各ターンで、左上のノードを変更する色を選択します。たとえば、新しい色の接続された隣接する (水平/垂直) ノードが形状に同化され、同化されたノードごとに 1 ポイントが追加されます。あなたのスコア。スコアリングの目的は、各グリッドをできるだけ少ないターンで完了することです。たとえば、16 ターンで完了した場合、未使用の 9 つの移動 => 累積スコアの 2*9 乗数倍になります。

明らかに、これを分解する方法はたくさんあります。14x14 グリッドを使用した再帰的バックトラッキングのデフォルトの選択は実行可能な候補です。これは、他にどのようなタイプのデータ構造に適していますか? あ*? 最適性にこだわらないでください。「十分な」アルゴリズムがあるかどうか疑問に思っています。

(ロボットのコードを作成して馬鹿げた高得点を獲得するのは楽しいプロジェクトかもしれないと思いました。ただし、3.5E+12 はすべてフレッシュウェアの自分で採点しました。)

4

7 に答える 7

5

このゲームは本当に私の興味を引いたので、私はそれに取り組んで数日を過ごしました。

私が最初に気付いたのは、最初のボード（場合によっては2）の後で、スコアを上げる最も速い方法は乗数を使用することであることを簡単に示すことができるということです。そのため、各ボードを最小限のステップで解決することを目標にシステムを構築しました。A *は一般的にこれらのタイプの検索問題のためだけに構築されているため、私はA *を使いたいと思い始めました...しかし、この問題は依然としてやっかいなものであることが判明しました。

A *について話すとき、それの有効性は実際にヒューリスティック推定の選択を要約します。実際の距離を推測することに近づくほど、目標に到達するために拡張する必要のあるノードが少なくなります。この問題について、私は推定のためにいくつかのアイデアを検討しましたが、それらのほとんどはA *ルールを破りました。つまり、実際の距離を過大に推定することはできません。そうしないと、A*の最適性を破ることになります。

ただし、機能するものがいくつかあります。このスレッドの他の人は、残りの色の数だけを推定としてとることについて投稿していますが、これは過大評価できないため許容されます（メインの「フラッド」領域の一部ではない残りの色ごとに少なくとも1回は色を変更する必要があります。このヒューリスティックの問題は、実際の距離の推定が非常に不十分であるということです。たとえば、最初の動きを考えてみましょう。これは、通常、色数6を推定します。多くの場合、2つの動きに拡張され、それぞれの動きは、通常7を推定します。 、などなど。この5レベルの深さを取り、ボードサイズが10x10の場合、ほとんどのリーフの推定値は11です。このヒューリスティックは、基本的に、目標。これはあまり効率的ではなく、私自身のテストでは、指数はボードサイズ9を中心に実行され、ソリューションでは約14回の移動が必要になることがよくあります。しかし、私の解決策は非常に高レベルであり、物事をスピードアップするためにあまり注意が払われていなかったことに注意する必要があります。

問題は、A *が実際に優れているのは、各ステップでソリューション全体の実際の距離が大幅に改善された場合のみであるということです。問題を直接見ると、コストを過大に見積もることなく、これよりもはるかに優れたヒューリスティックを見つけることができないでしょう。ただし、問題を別の問題に変換すると、より優れたヒューリスティックが飛び出します。ヒューリスティックな「残りの色の数」は、残りの可能な動きの最小数は何であるかという質問に答えています。その質問に答えるために、私は「ボード上のどの場所に到達するために最大のステップ数が必要か」と自問しました。ヒューリスティックでは、「右下隅までのステップ数」の答えに落ち着きました。これは、地図の方向を見つけてソリューションのステップ数を数えるように機能する別のA *検索を実行することで、かなり簡単に実装できます。これはボード上の任意のポイントを選択することだと思いますが、テストでは非常にうまく機能し、残りのすべてのポイントでA *を実行するには、シングルプロセッサテストマシンでかなりの時間がかかりました。

ただし、このヒューリスティックだけでは、右下隅が浸水区域の一部になった後に崩壊する傾向があったため、最終結果はMAX（右下隅の最小ステップ、メインの浸水に含まれない残りの色の数）でした。これは、私の高レベルの実装で、1秒以内にいくつかの非常に大きなボードサイズを最終的に達成することができました。

レコードの設定はあなたにお任せします。

于 2010-01-12T18:53:59.107 に答える
1

固定された開始状態と限られた数の移動を考えると、決定木を完全に探索できると思います。各ラウンドで可能な移動は 5 つだけであり、無駄な移動 (隣人を「グロブ」にしない色を選択する) は、ツリーが構築されるにつれて排除できます。決定木が構築されたら、各パスのポイント値を調べることができると思いますが、さらに最適化が必要な場合は、A* を使用すると確実に近づくことができます。

ラウンドごとに、基本的な状態を、グロブ化されていない場所の状態のビット配列のマトリックスとして保持します (グロブ化された場所では色が重要でなくなるため、色ビットを除外することで状態データ構造のメモリを節約できます)。可能な各決定のポイント値。次に、A *、または幅優先アルゴリズムは、通常どおりパス値を最大化できます。パスを保存し、分析が完了したら、決定されたすべての動きを実行します。

于 2009-12-31T19:18:24.947 に答える
1

別のアプローチは、遺伝的アルゴリズムを使用することです。(部分的な) ソリューションは色のリストで構成されているため、非常にうまく遺伝子に変換されます。フィットネス関数は、連結成分の 4 倍から、使用される色の総数 (遺伝子の長さ) を差し引いたようなものになる可能性があります。

非常に最適化されていないアルゴリズムを使用して、Mathematica の 10x10 ボードでこれを試したところ、短い解決策がすぐに得られました。私はそれが最適であるとは主張しませんが、十分な時間があれば、遺伝子を変異させるプロセスのランダム性により、最終的に最適なソリューションにたどり着くことが保証されます.

于 2011-09-26T20:04:00.413 に答える
0
  1. 可能であれば、色を削除します。
  2. あなたのためにより多くの新しい隣人を生成する色を選びました！
  3. 手順1に進みます。
于 2009-12-29T05:55:58.110 に答える
0

もう 1 つの最適化は、すぐに取得する必要のない色の塊がいくつかあることです。ネットワーク距離グラフには、1 つのカラー ブロブに隣接するブロブがないリーフが存在する場合があります。この色のブロブは、同じ色の最も遠いブロブまで取得する必要はありません。このアプローチを使用すると、距離マップを調整して、カラー ブロブを取得する必要がある最小時間を取得できます。

いくつかのボード位置については、次のターンに適格な色を取得する必要がないことを示すことができます。その色を避けて、分岐要因を減らすことができます。

于 2015-05-01T09:25:10.157 に答える
0

力ずくの再帰的検索により、最大スコアが検出されます。考慮すべき終了状態は最大で 5^25 です。多くの中間状態は等価です。これらを認識し、重複の検索スペースを取り除く方が速い場合があります。検索中に見つかった最高スコアと、そこに到達するまでにかかったパス (一連の動き) を追跡します。

于 2009-12-30T14:13:48.083 に答える
0

優れたヒューリスティックは、色で接続された距離マップを生成することです。たとえば、現在の洪水は距離ゼロにあります。距離 'i' の正方形に接続された色のグループは、距離 'i+1' にあります。

次に、最大距離にある色の数を観察します。最大距離で 1 つの色を削除するには最大距離の移動が必要であり、最大距離で追加の各色を削除するには追加の移動が必要です。すべての色が最大距離にない場合は、前の距離にあるまだ除去されていない色を考慮してください。「最大距離」の移動中にこれらの色の 1 つを削除する場合がありますが、追加の各色を削除するには移動が必要になります。

これにより、かなり適切な見積もりが得られます。最初の 14x14 のボード ポジションでは、最適なソリューションを得るには 20 ～ 22 回の移動が必要ですが、17 ～ 18 回の見積もりが得られる傾向があります。14x14 のボードは通常、この下限を使用して、約 10,000 のボード位置を見ながら解決できます。（そのような動きが利用可能な場合、色を排除する動きをするという最適化を使用します。）

于 2013-09-16T10:01:02.227 に答える