マインスイーパゲームについては、ほとんどの人が知っていると思います。私は自分のマインスイーパ ゲームを (C# で) コーディングしたいと考えており、そのゲームに適したアルゴリズムについての情報を探していました。私はかなり長い間ウェブを閲覧してきましたが、良い解決策を見つけることができませんでした. 誰でも私を助けることができますか？
58570 次
8 に答える
6
ソルバーを作成しようとする場合は、次を追加したいだけです - Minesweeper is NP complete (Archive Link)。つまり、誰かがP = NPを証明するまで、場合によっては総当たり探索を実行する以外に何もできない可能性があることを意味します (ただし、小さなフィールドでは完全な NP ではないゲームかもしれません)。
于 2009-11-18T20:18:31.540 に答える
5
Henri が述べたように、掃海艇を解決する正しい方法は、数学、特に決定論的な部分の線形代数行列数学を使用することです。ここに投稿全体があります：
- その方法がどのように機能するかを説明します
- どのプラットフォームでもコンパイルして実行できる実用的なコードがあります
- ゲームを作成するためのコードとソルバーも含まれています
ここですべてを見ることができます：https ://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/
それを読んでから、それについてよく考えることをお勧めします。Minsweeper の確率的な部分は、統計を使用して解決することもできますが、そのための適切な計画はまだありません。ただし、他の人も調べました。
于 2013-01-16T03:36:39.670 に答える
4
私は間違いなく掃海艇の専門家ではありませんが、解決しようとするときに使用するアルゴリズムは次のとおりです。
明らかにされた領域の境界であるすべての正方形を通過します。これらの各マスについて、その隣にある地雷の数を数えます。四角に書かれた数字を引きます（その周りにある地雷の真の数）。それは、この広場の周囲に残された未発見の地雷の数です。それを、現在の正方形の周りの未公開の正方形の数で割ります。これは、地雷を含む隣接する各マスの確率です。いずれかのマスの確率が 1 の場合、それを地雷としてマークします。いずれかの正方形の確率が 0 の場合、それを安全とマークします。次に、関連する数値を更新します。
確率が 0 または 1 の正方形がない場合はどうしますか? 最適なアルゴリズムでは、複数の正方形からの制約が考慮されます。しかし、最初に書いたように、私はマインスイーパの専門家ではないので、確率が 0 または 1 に最も近い他のマスからランダムに選択します。
于 2009-11-15T20:18:50.377 に答える
3
ここに私の掃海艇ソルバーがあります：
- 各数の二乗について:
- 周囲の未開封数 == 平方数の場合: すべて地雷
- 平方数 - 周囲にフラグが立てられた数 == 0 の場合: 未開封のものはすべて地雷ではありません
- サブセット ルールを使用する
これは実際の実装です。説明が難しいサブセット規則を使用していることに注意して ください
もちろん、私のアルゴリズムは時々失敗することがあります。Prolog スタイルのバックトラッキング ソルバーを実装する予定です
于 2010-12-05T02:07:17.910 に答える
2
これを確認してください：http://quantum-p.livejournal.com/19616.html
サル推論で直感的に解決できないボード上の任意の位置は、個々の (または位置全体の) 正方形を解決できるマトリックスであり、より良い解決率につながる可能性があります。単純なランダムな推測では、良い結果が得られませんでした。方程式ソルバーの線形システムを追加することで、C++ の解法アルゴリズムにこの方法を実装しました。マインスイーパの難易度については、アルゴリズムを使って数万回のゲームを実行し、統計をとることで研究しています。
私のアルゴリズムは、(9,9,10) レベルの掃海艇の最大 85% を解決します。私はまだ他の難易度レベルで完全なテストを実行していませんが、小規模なテストでは、中レベル (16,16,40) の解決率は 55-60 % で、ハード レベル (30,16,99) は 5 程度であることが示されています。 -10%。私はそれを最も最適にするいくつかの新しいものを追加するつもりです.
于 2010-10-25T18:50:08.550 に答える
2
コメントは、ゲームを構築するのにアルゴリズムは必要ないということです。解決するという意味でのアルゴリズムを意味していると思いますが、誰もがそのように理解しているかもしれません。
ただし、問題の解決策はすべてアルゴリズムと見なすことができます。
ほとんどの数学の問題と同様に、解決するのに十分小さな問題に到達するまで、アルゴリズム全体をより小さな複雑でないアルゴリズムに分解できます。これにより、最初の正しい解が得られます。後で、アルゴリズム全体のコンテキストで小さなアルゴリズムを最適化できます。
ゲームボードは 2 次元配列と考えることができます。各操作に関連付けられたアルゴリズムがあります。最初の操作は、おそらく、地雷の数とボードのサイズのパラメーターを使用して、x、y 座標を使用してランダムに生成された地雷の場所のセットです。正方形を明らかにすることに関連する別のアルゴリズムがあり、ボードと場所を取り、それに隣接する地雷の数を決定します。最終的なアルゴリズムは、ボードを取り、地雷のない正方形が明らかになるまで残っているかどうかを確認します。
これらのアルゴリズムのそれぞれを使用して、パフォーマンスを向上させるためにそれぞれを最適化し、「x、y 座標を使用した 2 次元配列が与えられた場合、現在の正方形に隣接する地雷を含む正方形を数える最良の方法は何か」と言うことができます。
于 2009-11-15T17:37:41.263 に答える