マインスイーパ ソルバーを作成する必要がありますが、どこから始めればよいかわかりません。問題は、アリのコロニー最適化、シミュレートされたアニーリング、遺伝的プログラミングなどのメタヒューリスティック アルゴリズムを利用する必要があることです。インターネットで関連資料を見つけましたが、どれが役に立ち、どれが役に立たないかはよくわかりません。 、「完璧にフィットする」ものは何もないからです。以前にやった人が書いた記事に従わずに、メタヒューリスティックアルゴリズムを自分で調整する必要があるようです。だからこそ、始める前に知っておくべきことをすべて知りたいのです。
「アリコロニーの最適化、シミュレートされたアニーリング、遺伝的プログラミング」...大げさな言葉ですが、それらをどのように使用するかわかりません!
2 つのソルバーを用意することをお勧めします。
最初に完全ソルバーを適用し、失敗した場合は不完全ソルバーを適用します。
完全なソルバーは、すべての組み合わせの可能性を見つけ、それらのどれが機能するかをチェックする必要があります。一度に 1 ～ 5 個のタイルを検討することになるため (人間のソルバーとして、通常はその数のタイルに制限されます)、簡単に確認できる組み合わせは最大で 32 個しかないため、実際にはそれほど難しくありません。
不完全なソルバーの場合、すべての組み合わせを検討し、有効な組み合わせを見つけ、有効な組み合わせを使用してさまざまな場所での地雷の確率を計算し、地雷の確率が最も低いものを選択できます。
考えてみれば、この 2 つのアプローチは同じです。パーフェクト ソルバーでは、地雷確率が 0 のタイルを選択します。要約すると、次のようになります。
ステップ 1 は思ったほど悪くはありません。両方の条件 (解決済みの地雷ではない場所に隣接している、または隣接している) を満たす組み合わせはほとんどないためです。
メタヒューリスティックは、マインスイーパにとって最適なアルゴリズムではないかもしれません - 少なくとも簡単な部分ではそうではありません。
代わりに、推論を備えた単純なルール エンジンが、すでに多くの爆弾にタグを付けて、空いている場所を明らかにすることができます。爆弾がタグ付けされると、その情報でさらに推論するために推論が必要になります。インスピレーションについては、Drools のコンウェイのライフ ゲームの例を参照してください。