Pythonプログラミング ~マインスイーパーのユーザー補助アルゴリズム~

研究

 今回マインスイーパーというPCゲームを自動的に解くためのアルゴリズムをPythonによって実装しました。

開発・実行環境

マシン:PC

開発OS:Ubuntu18.04

実行環境:Ubuntu、Windows10 (Anacondaがインストールできれば何でも動くと思います)

言語:Python3.6.4 

その他:AnacondaのインストールとAnacondaでpygameをインストール

Anacondaのインストールはここから

pygameのインストール方法

Anaconda上で次のコマンドを打つ

pip install pygame

 

環境設定について詳しくはほかのサイトを調べてみてください。

プログラムの概要

 マインスイーパーのルールはマインスイーパー Wikiから調べてみてください。

プレイ画面

mine_sweeper.pyのゲーム画面 20×15マスバージョン 

×印はプレイヤーが予想して目印としてつけるもの。

 

mine_sweeper_cheat.pyバージョン

×と〇が自動でつく仕様。〇印をクリックしていればクリアできるが、難しい問題(爆弾の数が増えると)〇がなくなる可能性もある。そこが課題点。

mine_sweeper.py

 下に乗せたmine_sweeper.pyは実際にマインスイーパーで遊ぶことができるプログラムになっています(*1)。

操作

左クリック→タイルを開く

右クリック→マーキングをつける

中クリック(スクロールボタン長押し)→表示される数値の範囲9×9マスを可視化する。

mine_sweeper_cheat.py

もう一つのmine_sweeper_cheat.pyは自動で爆弾の位置や安全な位置を可視化してくれます。

操作

左クリック→タイルを開く

×印→爆弾があるところ

〇印→安全なところ

 

それぞれグローバル変数のWIDTH、HWIGHT、NUM_OF_BOMBSを変更することで、ステージの横幅、縦幅、爆弾の数(ランダム)を設定することができるので、好きな難易度でプレイすることができます。

アルゴリズムの説明

 下の図を使って爆弾の発見と安全地帯の発見のアルゴリズムを簡単に説明します。

爆弾確定条件

 プレイ画面にあるすべての数字が書いてあるマスについて(3×3マス 図では赤色の枠)、次の条件が成り立つとき、その数字のマスの周りにある何もマークがついていない未開封のマスは爆弾があることになります。

マークのついていない未開封マスの数 = マスに書いてある数字(黄色)X ー すでに爆弾だとわかっているマス(×印がついているマス) ー すでに安全だとわかっているマス(〇印がついているマス)

 Xとマークのわからない未開封のマスの数が同じ数になったとき、その未開封のマスは爆弾であるということになります。しかし、未開封のマスが多いと、爆弾を確定することができなくなります。

 

安全確定条件

 同じく、プレイ画面にあるすべての数字が書いてあるマスについて、次の条件が成り立つとき、その数字のマスの周りにある、何もマークがついていない未開封のマスの安全が確定します。

マスに書いてある数字(黄色)X ー 爆弾だとわかっているマス <= 0

 すでにX個の爆弾の位置が分かっているので、それ以外のマスには爆弾がないことが保証されているということを表しています。

 

 

課題点

 現段階では、すべての爆弾と安全地帯を見つけられるわけではありません。数字1つの情報からわかるものはすべて表示できていますが、マインスイーパーには、複数の数字の情報から推測を行うことができる場合があります。例えば次のような場合です。

 これはマインスイーパーの定石で1,2,1の並びがある場合は2の前が安全で、1の前が爆弾であるとわかります。このように、複数の数字情報を使った判定がないため、完全とは言えないプログラムになっています。ここが課題点です。

 

考察・感想

 このプログラムを研究室の中で発表したところ、課題点となっているところはSATに帰着することで解くことができると先生に教わりました。つまり複数の数値を扱うためには、論理式として判定する必要があり、それができるようになると、今回の数値に対してのアルゴリズムは必要なくなることになるようです。したがって、これから(時間があれば)SAT型のアルゴリズムを搭載したプログラムも考えてみようかなと考えています。

 Pygameを使ってゲームをプログラムすると、遊ぶだけでなく、ゲームの中身を知ることができるので、こういった自分の考えをコードとして実装することができるという体験を今回することができました。これからゲーム情報学を勉強するうえでは、重要な一歩になったと思います。

 私は下にある参考文献を読んでいて初めてマインスイーパーというゲームを知ったので、得意なわけではありませんが、こうしてプログラムの補助を使うことで自分よりも賢く問題を解いてもらうプログラムを作ったということが、賢いプログラムの第一歩になったような気がしています。

ソースコード

mine_sweeper.py

mine_sweeper_cheat.py

参考文献

*1)田中賢一郎「ゲームを作りながら楽しく学べるPythonプログラミング」よりmine_sweeper.py

 

コメント

タイトルとURLをコピーしました