サイト内検索

2016/02/05(金)マインスイーパーアルゴリズム(基本編)

この記事は概要からの続きです。
概要ページ

まずゲームを始めた時に適当にポチポチ押す瞬間が発生しますが、この瞬間からゲームは始まるわけです。
私はいつも四隅を押さえるようにしています。その方が特定が楽なのと、後半戦で「どっちか」押さざるを得ない状況が生まれやすいからです。

具体的には以下のような図です。
□|□|□|□|□|
1|1|1|1|1|
ケースバイケースですが、この図は以下の可能性があります。
■|●|1|■|●|
1|1|1|1|1|
中央は安全ですが確実に1と出るので何の参考にもなりません。
つまり■と●の二通りが出た時にはじめてユーザーの判断を待つようにします。

ではこれを発展させましょう。
□|2|□|□|1|
□|2|1|2|□|
これは比較的簡単にできますね。
では解いてみます。
□|2|□|□|1|
□|2|1|2|□|
この時、未確認ブロックで確定している情報は以下の通りです。
・右2を挟むように爆弾がある。
・右2の上、右上1の左隣は2である。
□|2|■|2|1|
□|2|1|2|■|
さて、この時は未確認ブロックで確定している情報はどちらかに爆弾があり、どちらかは1である事です。
が、どちらなのかは分からないのです。
(こういう事が起こるから四隅はさっさと抑えてしまいたいですね)
  • やりたいこと
1の場合は自動化したい
2の場合はそこで止めてほしい

2は比較的楽です。
問題は1の実装。

今、このように簡単に述べましたがどういうケースなのか、真面目に考えてみたいと思います。
まず最初に1を順番に見ていきます。
  • A案
?|×|●|□|1|
?|×|1|×|●|
  • B案
?|×|□|●|1|
?|×|1|×|□|
(紛らわしいので2は×に置き換えています)
1の候補だけでも黒塗りの数だけあります。
実際に置くと上記2パターンが候補になります。
?は使われないものなので、明示的にするために分けました。
理由は後述します。


続いて2の候補についてフォーカスしましょう。
と、言いたいところですが実は全てが候補です。
ちょっと分かりにくいので一つずつフォーカスしましょう。
  • A案
●|2|●|●|×|
□|2|×|2|□|
  • B案
●|2|●|□|×|
□|2|×|2|●|
  • C案
□|2|●|●|×|
●|2|×|2|□|
  • D案
□|2|●|□|×|
●|2|×|2|●|
  • E案
●|2|□|●|×|
●|2|×|2|●|
(紛らわしいので1を×に置き換えています)
上記が2だけで考えられる全パターンです。

3はないので1・2で考えた時にANDを取ると最も評価値が高いパターンは以下の2通りができます。
ただし、?は任意の値が入るものとします。
  • 8点
1のA案
?|2|●|□|1|
?|2|1|2|●|
2のB案
●|2|●|□|1|
□|2|×|2|●|
  • 8点
1のA案
?|2|●|□|1|
?|2|1|2|●|
2のD案
□|2|●|□|1|
●|2|1|2|●|
【考え方】
ここから一気に難しくなります。ついてきてくださいね?

マインスイーパーアルゴリズム(応用編)
OK キャンセル 確認 その他