今回マインスイーパーというPCゲームを自動的に解くためのアルゴリズムをPythonによって実装しました。
開発・実行環境
マシン:PC
開発OS:Ubuntu18.04
実行環境:Ubuntu、Windows10 (Anacondaがインストールできれば何でも動くと思います)
言語:Python3.6.4
その他:AnacondaのインストールとAnacondaでpygameをインストール
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個の爆弾の位置が分かっているので、それ以外のマスには爆弾がないことが保証されているということを表しています。
課題点
現段階では、すべての爆弾と安全地帯を見つけられるわけではありません。数字1つの情報からわかるものはすべて表示できていますが、マインスイーパーには、複数の数字の情報から推測を行うことができる場合があります。例えば次のような場合です。
これはマインスイーパーの定石で1,2,1の並びがある場合は2の前が安全で、1の前が爆弾であるとわかります。このように、複数の数字情報を使った判定がないため、完全とは言えないプログラムになっています。ここが課題点です。
考察・感想
このプログラムを研究室の中で発表したところ、課題点となっているところはSATに帰着することで解くことができると先生に教わりました。つまり複数の数値を扱うためには、論理式として判定する必要があり、それができるようになると、今回の数値に対してのアルゴリズムは必要なくなることになるようです。したがって、これから(時間があれば)SAT型のアルゴリズムを搭載したプログラムも考えてみようかなと考えています。
Pygameを使ってゲームをプログラムすると、遊ぶだけでなく、ゲームの中身を知ることができるので、こういった自分の考えをコードとして実装することができるという体験を今回することができました。これからゲーム情報学を勉強するうえでは、重要な一歩になったと思います。
私は下にある参考文献を読んでいて初めてマインスイーパーというゲームを知ったので、得意なわけではありませんが、こうしてプログラムの補助を使うことで自分よりも賢く問題を解いてもらうプログラムを作ったということが、賢いプログラムの第一歩になったような気がしています。
ソースコード
mine_sweeper.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
import sys from math import floor from random import randint import pygame from pygame.locals import QUIT, MOUSEBUTTONDOWN, K_SPACE, MOUSEBUTTONUP WIDTH = 25 HEIGHT = 15 SIZE = 50 NUM_OF_BOMBS = 50 EMPTY = 0 BOMB = 1 OPENED = 2 OPEN_COUNT = 0 CHECKED = [[0 for _ in range(WIDTH)] for _ in range(HEIGHT)] R_CHECKED = [[0 for _ in range(WIDTH)] for _ in range(HEIGHT)] pygame.init() SURFACE = pygame.display.set_mode([WIDTH*SIZE, HEIGHT*SIZE]) FPSCLOCK = pygame.time.Clock() #爆弾の個数を数える関数 def num_of_bomb(field, x_pos, y_pos): count = 0 for yoffset in range(-1, 2): for xoffset in range(-1, 2): xpos, ypos = (x_pos + xoffset, y_pos + yoffset) if 0 <= xpos < WIDTH and 0 <= ypos < HEIGHT and \ field[ypos][xpos] == BOMB: count += 1 return count #タイルを開くための再帰関数 def open_tile_start(field,x_pos,y_pos): if num_of_bomb(field,x_pos,y_pos) != 0 and \ field[y_pos][x_pos] == OPENED: return open_tile(field,x_pos,y_pos) def open_tile(field, x_pos, y_pos): global OPEN_COUNT if CHECKED[y_pos][x_pos]: return CHECKED[y_pos][x_pos] = True for yoffset in range(-1, 2): for xoffset in range(-1, 2): xpos, ypos = (x_pos + xoffset, y_pos + yoffset) if 0 <= xpos < WIDTH and 0 <= ypos < HEIGHT and \ field[ypos][xpos] == EMPTY: field[ypos][xpos] = OPENED OPEN_COUNT += 1 count = num_of_bomb(field, xpos, ypos) if count == 0 and \ not (xpos == x_pos and ypos == y_pos): open_tile(field, xpos, ypos) #メインルーチン def main(): smallfont = pygame.font.SysFont(None, 36) largefont = pygame.font.SysFont(None, 72) message_clear = largefont.render("!!CLEARED!!", True, (0, 255, 225)) message_over = largefont.render("GAME OVER!!", True, (0, 255, 225)) message_rect = message_clear.get_rect() message_rect.center = (WIDTH*SIZE/2, HEIGHT*SIZE/2) game_over = False field = [[EMPTY for xpos in range(WIDTH)] for ypos in range(HEIGHT)] # 爆弾を設置 count = 0 while count < NUM_OF_BOMBS: xpos, ypos = randint(0, WIDTH-1), randint(0, HEIGHT-1) if field[ypos][xpos] == EMPTY: field[ypos][xpos] = BOMB count += 1 while True: for event in pygame.event.get(): if event.type == QUIT: pygame.quit() sys.exit() #左クリック if event.type == MOUSEBUTTONDOWN and \ event.button == 1: xpos, ypos = floor(event.pos[0] / SIZE),\ floor(event.pos[1] / SIZE) if field[ypos][xpos] == BOMB: game_over = True else: open_tile_start(field, xpos, ypos) #右クリック elif event.type == MOUSEBUTTONDOWN and \ event.button == 3: xpos, ypos = floor(event.pos[0] / SIZE),\ floor(event.pos[1] / SIZE) #マークなしならば if R_CHECKED[ypos][xpos] == 0: R_CHECKED[ypos][xpos] = 1 #マークありならば else: R_CHECKED[ypos][xpos] = 0 #中クリック elif event.type == MOUSEBUTTONDOWN and \ event.button == 2: xpos, ypos = floor(event.pos[0] / SIZE),\ floor(event.pos[1] / SIZE) R_CHECKED[ypos][xpos] = 2 elif event.type == MOUSEBUTTONUP and \ event.button == 2: xpos, ypos = floor(event.pos[0] / SIZE),\ floor(event.pos[1] / SIZE) R_CHECKED[ypos][xpos] = 0 # 描画 SURFACE.fill((0, 0, 0)) for ypos in range(HEIGHT): for xpos in range(WIDTH): tile = field[ypos][xpos] rect = (xpos*SIZE, ypos*SIZE, SIZE, SIZE) if tile == EMPTY or tile == BOMB: pygame.draw.rect(SURFACE, (192, 192, 192), rect) if game_over and tile == BOMB: pygame.draw.ellipse(SURFACE, (225, 225, 0), rect) elif tile == OPENED: count = num_of_bomb(field, xpos, ypos) if count > 0: num_image = smallfont.render( "{}".format(count), True, (255, 255, 0)) SURFACE.blit(num_image, (xpos*SIZE+10, ypos*SIZE+10)) if R_CHECKED[ypos][xpos] == 1: pygame.draw.line(SURFACE,(0,0,225), (xpos*SIZE,ypos*SIZE),(xpos*SIZE+SIZE,ypos*SIZE+SIZE),10) pygame.draw.line(SURFACE,(0,0,225), (xpos*SIZE+SIZE,ypos*SIZE),(xpos*SIZE,ypos*SIZE+SIZE),10) # 線の描画 for index in range(0, WIDTH*SIZE, SIZE): pygame.draw.line(SURFACE, (96, 96, 96), (index, 0), (index, HEIGHT*SIZE)) for index in range(0, HEIGHT*SIZE, SIZE): pygame.draw.line(SURFACE, (96, 96, 96), (0, index), (WIDTH*SIZE, index)) #中クリック範囲描画 for ypos in range(HEIGHT): for xpos in range(WIDTH): rect2 = ((xpos-1)*SIZE,(ypos-1)*SIZE,3*SIZE,3*SIZE) if R_CHECKED[ypos][xpos] == 2: pygame.draw.rect(SURFACE, (225, 0, 0), rect2,10) # メッセージの描画 if OPEN_COUNT == WIDTH*HEIGHT - NUM_OF_BOMBS: SURFACE.blit(message_clear, message_rect.topleft) elif game_over: SURFACE.blit(message_over, message_rect.topleft) pygame.display.update() FPSCLOCK.tick(15) if __name__ == '__main__': main() |
mine_sweeper_cheat.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 |
import sys from math import floor from random import randint import pygame from pygame.locals import QUIT, MOUSEBUTTONDOWN, K_SPACE, MOUSEBUTTONUP WIDTH = 25 HEIGHT = 15 SIZE = 50 NUM_OF_BOMBS = 80 EMPTY = 0 #何もない(まだ開いていない) BOMB = 1 #爆弾あり(まだ開いていない) OPENED = 2 #すでに開いた OPEN_COUNT = 0 #再帰メソッドで使われる CHECKED = [[0 for _ in range(WIDTH)] for _ in range(HEIGHT)] #特殊な状態の座標の保持 S_CHECKED = [[0 for _ in range(WIDTH)] for _ in range(HEIGHT)] pygame.init() SURFACE = pygame.display.set_mode([WIDTH*SIZE, HEIGHT*SIZE]) FPSCLOCK = pygame.time.Clock() def num_of_bomb(field, x_pos, y_pos): count = 0 for yoffset in range(-1, 2): for xoffset in range(-1, 2): xpos, ypos = (x_pos + xoffset, y_pos + yoffset) if 0 <= xpos < WIDTH and 0 <= ypos < HEIGHT and \ field[ypos][xpos] == BOMB: count += 1 return count def open_tile_start(field,x_pos,y_pos): if num_of_bomb(field,x_pos,y_pos) != 0 and \ field[y_pos][x_pos] == OPENED: return open_tile(field,x_pos,y_pos) def open_tile(field, x_pos, y_pos): global OPEN_COUNT if CHECKED[y_pos][x_pos]: return CHECKED[y_pos][x_pos] = True for yoffset in range(-1, 2): for xoffset in range(-1, 2): xpos, ypos = (x_pos + xoffset, y_pos + yoffset) if 0 <= xpos < WIDTH and 0 <= ypos < HEIGHT and \ field[ypos][xpos] == EMPTY: field[ypos][xpos] = OPENED OPEN_COUNT += 1 count = num_of_bomb(field, xpos, ypos) if count == 0 and \ not (xpos == x_pos and ypos == y_pos): open_tile(field, xpos, ypos) #爆弾、安全地帯を見つけるプログラム def serch_bomb(field): for y_pos in range(HEIGHT): for x_pos in range(WIDTH): #数字が見えている場合 if num_of_bomb(field,x_pos,y_pos) > 0 and \ field[y_pos][x_pos] == OPENED: #aは爆弾があると予測されない未開封 #bは爆弾があると予測される未開封 #cは爆弾がないことが確定した未開封 →開封とみなしたい a = 0 b = 0 c = 0 d = num_of_bomb(field,x_pos,y_pos) #9*9マス a,bを数える for yoffset in range(-1, 2): for xoffset in range(-1, 2): xpos, ypos = (x_pos + xoffset, y_pos + yoffset) if 0 <= xpos < WIDTH and 0 <= ypos < HEIGHT: if field[ypos][xpos] != OPENED: if S_CHECKED[ypos][xpos] == 1 : b += 1 elif S_CHECKED[ypos][xpos] == 2: c += 1 else: a += 1 #爆弾が確定する条件 if a == d-b-c: for yoffset in range(-1, 2): for xoffset in range(-1, 2): xpos, ypos = (x_pos + xoffset, y_pos + yoffset) if 0 <= xpos < WIDTH and 0 <= ypos < HEIGHT: if field[ypos][xpos] != OPENED and \ S_CHECKED[ypos][xpos] != 1 and \ S_CHECKED[ypos][xpos] != 2 : S_CHECKED[ypos][xpos] = 1 #全体に対して絶対安全予測を立てる for y_pos in range(HEIGHT): for x_pos in range(WIDTH): #数字が見えている場合 if num_of_bomb(field,x_pos,y_pos) > 0 and \ field[y_pos][x_pos] == OPENED: #aは爆弾があると予測されない未開封 #bは爆弾があると予測される未開封 #cは爆弾がないことが確定した未開封 →開封とみなしたい a = 0 b = 0 c = 0 d = num_of_bomb(field,x_pos,y_pos) #9*9マス a,bを数える for yoffset in range(-1, 2): for xoffset in range(-1, 2): xpos, ypos = (x_pos + xoffset, y_pos + yoffset) if 0 <= xpos < WIDTH and 0 <= ypos < HEIGHT: if field[ypos][xpos] != OPENED: if S_CHECKED[ypos][xpos] == 1 : b += 1 elif S_CHECKED[ypos][xpos] == 2: c += 1 else: a += 1 #安全が確定する条件 if d-b <= 0: for yoffset in range(-1, 2): for xoffset in range(-1, 2): xpos, ypos = (x_pos + xoffset, y_pos + yoffset) if 0 <= xpos < WIDTH and 0 <= ypos < HEIGHT: if field[ypos][xpos] != OPENED and \ S_CHECKED[ypos][xpos] != 1 and \ S_CHECKED[ypos][xpos] != 2 : S_CHECKED[ypos][xpos] = 2 def main(): smallfont = pygame.font.SysFont(None, 36) largefont = pygame.font.SysFont(None, 72) message_clear = largefont.render("!!CLEARED!!", True, (0, 255, 225)) message_over = largefont.render("GAME OVER!!", True, (0, 255, 225)) message_rect = message_clear.get_rect() message_rect.center = (WIDTH*SIZE/2, HEIGHT*SIZE/2) game_over = False field = [[EMPTY for xpos in range(WIDTH)] for ypos in range(HEIGHT)] # 爆弾を設置 count = 0 while count < NUM_OF_BOMBS: xpos, ypos = randint(0, WIDTH-1), randint(0, HEIGHT-1) if field[ypos][xpos] == EMPTY: field[ypos][xpos] = BOMB count += 1 while True: for event in pygame.event.get(): if event.type == QUIT: pygame.quit() sys.exit() #左クリック if event.type == MOUSEBUTTONDOWN and \ event.button == 1: xpos, ypos = floor(event.pos[0] / SIZE),\ floor(event.pos[1] / SIZE) if field[ypos][xpos] == BOMB: game_over = True else: open_tile_start(field, xpos, ypos) serch_bomb(field) # 描画 SURFACE.fill((0, 0, 0)) for ypos in range(HEIGHT): for xpos in range(WIDTH): tile = field[ypos][xpos] rect = (xpos*SIZE, ypos*SIZE, SIZE, SIZE) rect2 = ((xpos-1)*SIZE,(ypos-1)*SIZE,3*SIZE,3*SIZE) if tile == EMPTY or tile == BOMB: pygame.draw.rect(SURFACE, (192, 192, 192), rect) if game_over and tile == BOMB: pygame.draw.ellipse(SURFACE, (225, 225, 0), rect) elif tile == OPENED: count = num_of_bomb(field, xpos, ypos) if count > 0: num_image = smallfont.render( "{}".format(count), True, (255, 255, 0)) SURFACE.blit(num_image, (xpos*SIZE+10, ypos*SIZE+10)) if S_CHECKED[ypos][xpos] == 1: pygame.draw.line(SURFACE,(0,0,225), (xpos*SIZE,ypos*SIZE),(xpos*SIZE+SIZE,ypos*SIZE+SIZE),10) pygame.draw.line(SURFACE,(0,0,225), (xpos*SIZE+SIZE,ypos*SIZE),(xpos*SIZE,ypos*SIZE+SIZE),10) if S_CHECKED[ypos][xpos] == 2 and tile != OPENED: pygame.draw.ellipse(SURFACE, (225, 0, 0), rect,10) # 線の描画 for index in range(0, WIDTH*SIZE, SIZE): pygame.draw.line(SURFACE, (96, 96, 96), (index, 0), (index, HEIGHT*SIZE)) for index in range(0, HEIGHT*SIZE, SIZE): pygame.draw.line(SURFACE, (96, 96, 96), (0, index), (WIDTH*SIZE, index)) # メッセージの描画 if OPEN_COUNT == WIDTH*HEIGHT - NUM_OF_BOMBS: SURFACE.blit(message_clear, message_rect.topleft) elif game_over: SURFACE.blit(message_over, message_rect.topleft) pygame.display.update() FPSCLOCK.tick(15) if __name__ == '__main__': main() |
参考文献
*1)田中賢一郎「ゲームを作りながら楽しく学べるPythonプログラミング」よりmine_sweeper.py
コメント