/
minesweeper.py
357 lines (286 loc) · 10.9 KB
/
minesweeper.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
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
import itertools
import random
class Minesweeper():
"""
Minesweeper game representation
"""
def __init__(self, height=8, width=8, mines=8):
# Set initial width, height, and number of mines
self.height = height
self.width = width
self.mines = set()
# Initialize an empty field with no mines
self.board = []
for i in range(self.height):
row = []
for j in range(self.width):
row.append(False)
self.board.append(row)
# Add mines randomly
while len(self.mines) != mines:
i = random.randrange(height)
j = random.randrange(width)
if not self.board[i][j]:
self.mines.add((i, j))
self.board[i][j] = True
# At first, player has found no mines
self.mines_found = set()
def print(self):
"""
Prints a text-based representation
of where mines are located.
"""
for i in range(self.height):
print("--" * self.width + "-")
for j in range(self.width):
if self.board[i][j]:
print("|X", end="")
else:
print("| ", end="")
print("|")
print("--" * self.width + "-")
def is_mine(self, cell):
i, j = cell
return self.board[i][j]
def nearby_mines(self, cell):
"""
Returns the number of mines that are
within one row and column of a given cell,
not including the cell itself.
"""
# Keep count of nearby mines
count = 0
# Loop over all cells within one row and column
for i in range(cell[0] - 1, cell[0] + 2):
for j in range(cell[1] - 1, cell[1] + 2):
# Ignore the cell itself
if (i, j) == cell:
continue
# Update count if cell in bounds and is mine
if 0 <= i < self.height and 0 <= j < self.width:
if self.board[i][j]:
count += 1
return count
def won(self):
"""
Checks if all mines have been flagged.
"""
return self.mines_found == self.mines
class Sentence():
"""
Logical statement about a Minesweeper game
A sentence consists of a set of board cells,
and a count of the number of those cells which are mines.
"""
def __init__(self, cells, count):
self.cells = set(cells)
self.count = count
def __eq__(self, other):
return self.cells == other.cells and self.count == other.count
def __str__(self):
return f"{self.cells} = {self.count}"
def known_mines(self):
"""
Returns the set of all cells in self.cells known to be mines.
"""
if len(self.cells) == self.count:
return self.cells
def known_safes(self):
"""
Returns the set of all cells in self.cells known to be safe.
"""
if len(self.cells) == 0:
return self.cells
def mark_mine(self, cell):
"""
Updates internal knowledge representation given the fact that
a cell is known to be a mine.
"""
"""
if cell in self.cells:
self.cells.remove(cell)
self.count -= 1
"""
new_Cells = set()
for cells in self.cells:
if cells != cell:
new_Cells.add(cells)
else:
self.count -= 1
self.cells = new_Cells
def mark_safe(self, cell):
"""
Updates internal knowledge representation given the fact that
a cell is known to be safe.
"""
# Previous code that resulted in modification of set during iteration in infer_new()
"""if cell in self.cells:
self.cells.remove(cell)"""
new_Cells = set()
for cells in self.cells:
if cells != cell:
new_Cells.add(cells)
self.cells = new_Cells
class MinesweeperAI():
"""
Minesweeper game player
"""
def __init__(self, height=8, width=8):
# Set initial height and width
self.height = height
self.width = width
# Keep track of which cells have been clicked on
self.moves_made = set()
# Keep track of cells known to be safe or mines
self.mines = set()
self.safes = set()
# List of sentences about the game known to be true
self.knowledge = []
def mark_mine(self, cell):
"""
Marks a cell as a mine, and updates all knowledge
to mark that cell as a mine as well.
"""
self.mines.add(cell)
for sentence in self.knowledge:
sentence.mark_mine(cell)
def mark_safe(self, cell):
"""
Marks a cell as safe, and updates all knowledge
to mark that cell as safe as well.
"""
self.safes.add(cell)
for sentence in self.knowledge:
sentence.mark_safe(cell)
def add_knowledge(self, cell, count):
"""
Called when the Minesweeper board tells us, for a given
safe cell, how many neighboring cells have mines in them.
This function should:
1) mark the cell as a move that has been made
2) mark the cell as safe
3) add a new sentence to the AI's knowledge base
based on the value of `cell` and `count`
4) mark any additional cells as safe or as mines
if it can be concluded based on the AI's knowledge base
5) add any new sentences to the AI's knowledge base
if they can be inferred from existing knowledge
"""
# Step 1
self.moves_made.add(cell)
# Step 2
self.mark_safe(cell)
# Step 3
# Add knowledge about neighbours if they contain at least one mine
new_knowledge = Sentence(self.get_neighbours(cell), count)
if new_knowledge.count > 0:
possibleMines = set()
for sentence in new_knowledge.cells:
# If cell has already been determined to be a mine, decrease count
if sentence in self.mines:
count -= 1
# If cell is undetermined, add it to new set that will be converted to a sentence
elif sentence not in self.mines and sentence not in self.safes:
possibleMines.add(sentence)
newer_knowledge = Sentence(possibleMines, count)
self.knowledge.append(newer_knowledge)
# If neighbours are all safe, add them to safes
if new_knowledge.count == 0:
possibleSafes = set()
for isSafe in new_knowledge.cells:
if isSafe not in self.safes:
self.mark_safe(isSafe)
# Adding new sentences to KB based on subsets
for knowledge in self.knowledge:
if knowledge.cells.issuperset(new_knowledge.cells):
self.mark_and_include(knowledge, new_knowledge)
elif new_knowledge.cells.issuperset(knowledge.cells):
self.mark_and_include(new_knowledge, knowledge)
# Inferring new knowledge
self.infer_new()
# Function that takes 2 sentences and checks for Mines/Safes to mark
# Appends any new knowledge inferred
def mark_and_include(self, cell1, cell2):
CellDifference = cell1.cells - cell2.cells
CountDifference = cell1.count - cell2.count
# Check if remaining cells are safes
if cell1.count == cell2.count:
for isSafe in CellDifference:
# Only add cells that are undetermined
if isSafe not in self.safes:
self.mark_safe(isSafe)
# Check if remaining cells are mines
elif len(CellDifference) == CountDifference:
for isMine in CellDifference:
# Only add cells that are undetermined
if isMine not in self.mines:
self.mark_mine(isMine)
# Adds inferred knowledge to KB
else:
newer_knowledge = Sentence(CellDifference, CountDifference)
if newer_knowledge not in self.knowledge:
self.knowledge.append(newer_knowledge)
# Infers new knowledge based on existing KB
def infer_new(self):
# Initialise an empty list to be used so as to not change size during iteration
confirmed_knowledge = []
for knowledge in self.knowledge:
confirmed_knowledge.append(knowledge)
if knowledge.known_mines():
for foundMine in knowledge.known_mines():
self.mark_mine(foundMine)
confirmed_knowledge.pop()
elif knowledge.known_safes():
for foundSafe in knowledge.known_safes():
self.mark_safe(foundSafe)
confirmed_knowledge.pop()
self.knowledge = confirmed_knowledge
def make_safe_move(self):
"""
Returns a safe cell to choose on the Minesweeper board.
The move must be known to be safe, and not already a move
that has been made.
This function may use the knowledge in self.mines, self.safes
and self.moves_made, but should not modify any of those values.
"""
for move in self.safes:
if move not in self.moves_made:
return move
def make_random_move(self):
"""
Returns a move to make on the Minesweeper board.
Should choose randomly among cells that:
1) have not already been chosen, and
2) are not known to be mines
"""
# Initialise list of all available cells
all_cells = []
# Iterate through all cells, getting those that have not been selected and are not confirmed mines
for i in range(self.height):
for j in range(self.width):
if (i, j) not in self.mines and (i, j) not in self.moves_made:
all_cells.append((i, j))
if len(all_cells) == 0:
return None
return random.choice(all_cells)
# Gets neighbours of a cell
def get_neighbours(self, cell):
i, j = cell
# List of possible moves
moves = [
('down', (i + 1, j)),
('downright', (i + 1, j + 1)),
('downleft', (i + 1, j - 1)),
('up', (i - 1, j)),
('upright', (i - 1, j + 1)),
('upleft', (i - 1, j - 1)),
('left', (i, j - 1)),
('right', (i, j + 1))
]
# Initialise neighbours lsit
neighbours = []
for action, (r, c) in moves:
# Check if action is within limit of height and width, and also if it has already been made
if 0 <= r < self.height and 0 <= c < self.width and (r, c) not in self.moves_made:
neighbours.append((r, c))
return neighbours