マインスイーパーを自動で解いてみる
マインスイーパーを自動で解いてみよう
今更ながらにマインスイーパーを自動で解くプログラムを作った。
まずはマインスイーパーの問題を作るプログラム。
これは簡単。これに加えて、指定した場所から爆弾orパネルの開放する処理。
これも再帰するだけなので、簡単。
あっというま。ま、昔7行プログラムでできたぐらいだしね。
問題を作ったら、今度は問題を解くほうの処理。
自分で解いていくわけではないので、テキストで表示して解いていく過程を
見せるプログラムにした。
未開放のパネルに対し、爆弾の確率を設定する。設定した確率の内、最も低いパネルを開く。
ただそれだけ。
盤面を全体的に走査し、確実に爆弾の場所もしくは確実に爆弾ではない場所を調べる。
どちらかが見つかったら、その周囲の８マスの確率を計算し直す。
確率の計算が発生した場合は、再度盤面全体を走査する。
そして最後に爆弾の確率が最も低い基本的には確率０のパネルを開く。
それだけでもまあまあな正答率にはなる。でも、まあまあはまあまあ。
確率０のパネルがない時はそこそこの確率で爆弾を引いてしまう。
そこでさらに一工夫して、確率０が見つからない場合に
各地点の発生しうる爆弾の組み合わせを全通り試し、その結果矛盾が発生しない
全組み合わせのチェックの結果、爆弾が絶対発生する／絶対発生しえないパネルを
確定するようにする。爆弾の仮置きで矛盾がないかということね。
これらにより、まあまあの正答率はなかなかの正答率になる。
マインスイーパーのゲームで試す
ある程度ロジックが問題ないレベルになったとおもわれるので、ウェブサイトのマインスイーパーで試してみる。
試したのは楽天ポイントモールのゲームセンター内のマインスイーパー。20x20のLevel5の盤面で試す。(ちなみにラクマ版ゲームセンター(https://fril.jp/games#)でも同じだしLINE版のゲームセンター(https://kantan.game/lightgame)もおなじ。)
盤面の情報などは外側から取得できる気がしなかったので、単純に画像を直接解析して、盤面情報を取得しようとした。
ところが、微妙にマス目ごとに文字の形が違う。マス目が20マスあるのに幅が387ピクセル。
人間の目では同じっぽく見えるけど、アンチエイリアスも含め、1マスの幅が一定じゃないってことね。
と、いうことで、まずは盤面を拡大できないかとスタイルを変えてみたらほぼ400ピクセルので画像も見た感じだいたい同じっぽくなった。
これでOpenCvSharpを使って一致率などを幅を持たせて盤面の表示を取得してみた。
正直、この盤面を取得する処理が一番時間かかっている。２つの意味で。
１つは単純に、画像を検索して、正しい盤面情報を取得する処理を作る時間。なかなかOpenCvSharpでの処理でも正しく認識できず。いろいろ手を変え品を変え。
なんとかほぼ正しく読み取ることができるようになった。
もう１つは盤面情報解析にかかる時間。単純に盤面の画像から盤面がどんな状態になっているのかを取得するのに、10秒ぐらいかかる。1手10秒になってしまうので、だいたい150手前後になるのだけど、25分ぐらいかかってしまう。ここも工夫して最低時間で盤面を解析できるように、処理方法を工夫。
マインスイーパーをやっている様子
と、いうことでPlaywrightで操作するコードも追加し、いろいろ工夫してやっとまともに動くようになったので動画でご紹介。
フルスクリーンにして見ないと、小さすぎてわかりにくいです。
盤面を解析したうえで、爆弾の確率が一番低い(普通は確率0)のパネルを選択していく。
左下側が盤面の解析状況。
22COMBO目あたりで、右上の「2」のパネルを「6」と判断してしまうところは画像解析がいまいち。多分COMBOで表示される文字がパネルに微妙に重なるので、極まれに画像の解析ミスすることもある。たまたま今回は影響ないけど。
13COMBOや16COMBOのあたりで、いったん確率0のパネルが見つからないと判断するが、そこで「熟考実施」とでる。これは最初の項目で書いた通り、未知のパネルに接した各数値パネルの爆弾の組み合わせを全通り試して矛盾しない置き方をしたときに常に爆弾である場所と常に爆弾がない場所を判断する。
見たままの状態でみつからない時だけ爆弾を全パターン仮置きして深く読む。つまり普段は浅い読みだけで素早く終わり、仮定なしでは見つからない時に、仮定爆弾で判定をする。
ま、それだけなんだけどね。
それでも動画は最後の数か所は読みようがなく運で確率が低いと思われるパネル、今回の場合は40~50%の確率でOUTのパネルをランダムで開けてみて、たまたま見事に運よく成功してノーミスクリアとなりました。
土日をこんな遊びでつぶしてしまった。
コメント
コメントを投稿