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 and self.count != 0:
return self.cells
else:
return set()
def known_safes(self):
"""
Returns the set of all cells in self.cells known to be safe.
"""
if self.count == 0:
return self.cells
else:
return set()
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
def mark_safe(self, cell):
"""
Updates internal knowledge representation given the fact that
a cell is known to be safe.
"""
if cell in self.cells:
self.cells.remove(cell)
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
self.moves_made.add(cell)
# 2) mark the cell as safe
self.mark_safe(cell)
# 3) add a new sentence to the AI's knowledge base based
# on the value of `cell` and `count`
up = cell[1] - 1
down = cell[1] + 1
left = cell[0] - 1
right = cell[0] + 1
undetermined = set()
mine_counter = 0
horizontal_boundary = self.width
vertical_boundary = self.height
for i in range(left, right + 1):
for j in range(up, down + 1):
# Ignore cell if it is out of boundaries or if is the cell itself
if j < 0 or j > vertical_boundary or i < 0 or i > horizontal_boundary or (i,j) == cell:
continue
# Augment mine counter if cell is in mines list
if (i,j) in self.mines:
mine_counter += 1
# Add the mine to the undetermined list if cell is not in safes
if (i,j) not in self.safes:
undetermined.add((i,j))
new_counter = count - mine_counter
new_sentence = Sentence(undetermined, new_counter)
print(f'Move on cell: {cell} has added sentence to knowledge {undetermined} = {new_counter}' )
self.knowledge.append(new_sentence)
# 4) mark any additional cells as safe or as mines if it
# can be concluded based on the AI's knowledge base
for sen in self.knowledge:
if sen.known_mines():
for cell in sen.known_mines().copy():
self.mark_mine(cell)
if sen.known_safes():
for cell in sen.known_safes().copy():
self.mark_safe(cell)
#5) add any new sentences to the AI's knowledge base if they can
# be inferred from existing knowledge
knowledge_copy = self.knowledge.copy()
for sentence1 in knowledge_copy:
for sentence2 in knowledge_copy:
sen1 = sentence1.cells
sen2 = sentence2.cells
count1 = sentence1.count
count2 = sentence2.count
if sen2.issubset(sen1) and knowledge_copy.index(sentence2) != knowledge_copy.index(sentence1):
for rem in sen2:
if rem in sen1:
sen1.remove(rem)
new_count = count1 - count2
another_sentence = Sentence(sen1, new_count)
self.knowledge.append(another_sentence)
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 and move not in self.mines:
return move
else:
return None
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
"""
for i in range(self.height):
for j in range(self.width):
move = (i, j)
if move not in self.moves_made and move not in self.mines:
return move
return None
当我尝试运行 AI 来玩这个扫雷代码时,它在某些动作中运行正常,但在 6 个或更多动作之后,它就崩溃了,程序退出了。我认为这是我的 PC 资源的问题。如果有人可以帮助我在其他电脑上运行代码并告诉我它是否有效,我将不胜感激。
我假设“资源不足”意味着您的系统内存/RAM 不足。如果是这样,则表明您的 AI 知识库存在问题。只有 64 个单元格(和 8 个地雷),因此 KB 中最多只有 56 个句子。事实上,一旦您的 AI 正常工作,知识库将只有带有
count>0
的句子(因此,永远不会超过 4 或 5 个句子)。
扫雷项目比最初出现的要复杂。在编写下一个步骤之前,您必须正确执行每个步骤。否则,程序早期的错误会传播到整个过程,并且它们变得非常难以诊断(从这方面的经验来看!)。
我修改了发布的代码以仅测试前 4 个要求并玩了 3 步。我的观察:
make_safe_move()
功能:不行make_random_move()
功能:不是真的随机这是打印输出(修改以获取更多详细信息)。
No known safe moves, AI making random move: (0, 0)
After move on cell: (0, 0) new sentence added to knowledge:
{(0, 1), (1, 0), (1, 1)} = 0
Size of KB: 1
# of safe cells: 4
AI making safe move: (0, 1)
After move on cell: (0, 1) new sentence added to knowledge:
{(0, 2), (1, 2)} = 0
Size of KB: 2
# of safe cells: 6
No known safe moves, AI making random move: (0, 2)
After move on cell: (0, 2) new sentence added to knowledge:
{(0, 3), (1, 3)} = 1
Size of KB: 3
# of safe cells: 6
第三步显示
make_safe_move()
函数的错误。当有可用的安全移动时,它返回None
(因此您可以随机移动)。仔细检查逻辑,您就会明白为什么会这样。那是1个问题。它不会导致内存错误,但你的 AI 会在不应该的时候输掉游戏。
在检查 KB 中是否有安全单元或地雷时还有一个问题。第一步后,您添加句子
{(0, 1), (1, 0), (1, 1)} = 0
并正确确定那里的安全单元格。但是,当你退出add_knowledge()
函数时,那句话还在KB中。如果你检查它,它看起来像这样:set() = 0
。随着时间的推移(当你找到更多安全单元格时),你会有越来越多的这样的句子。我怀疑这会导致资源错误。
另外,在你修改知识库中的适当语句后(对于新的安全细胞或地雷),还有可能揭示更多安全细胞或地雷的“新知识”。所以你必须不断迭代,直到没有变化为止。
关于,您的
make_random_move()
功能——它并不是真正的“随机”。它从单元格 (0,0) 开始,一直持续到找到一个不在移动或地雷中的单元格。所以你总是得到一个相似的“随机”单元格顺序(唯一的变化是由于地雷)。
在实施要求 5(“向 KB 中添加可以从现有知识推断出的新句子”)之前修复这些项目。
最后,正如@luk2302 指出的那样,SO 不是此类问题的论坛。有一个 ED 论坛,每个 CS50 AI 项目都有过滤器。它有大量关于扫雷项目的问答。 (也许太多了!)。 :-)