背景：我已经为HarvardX CS50AI在线课程的扫雷ai项目工作了几天。目标是为扫雷舰游戏实现人工智能。可在此处访问问题集：https://cs50.harvard.edu/ai/2020/projects/1/minesweeper/
实现：我的任务是实现两个类，扫雷AI和句子句子类是一个关于扫雷游戏的逻辑陈述，该游戏由一组棋盘格和地雷格数组成扫雷AI类是AI的主要处理程序。
问题：尽管程序运行时没有任何错误，但人工智能做出了错误的决定，因此无法成功完成扫雷游戏。根据我的观察，人工智能正在将潜在的地雷标记为安全空间，从而制造自杀符文。
调试我尝试过经典的调试、打印，甚至自言自语地谈论代码。出于某种原因，人工智能将地雷声明标记为安全空间-我无法检测其背后的原因。我已经用注释记录了代码，我看不到实现逻辑的任何崩溃。然而，必须有一个-我插入下面的代码和一些额外的材料。
句子类，游戏中知识的逻辑表示：
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.
"""
# Because we are eliminating safe cells from the the statement, we are looking for statements
# that would contain number of cells that is equal (or smaller) than number of mines.
# Upon fulfilment of such condition, evaluated cells are known to be mines.
if len(self.cells) <= self.count:
return self.cells
else:
return None
def known_safes(self):
"""
Returns the set of all cells in self.cells known to be safe.
"""
# There is only one case when the cells are known to be "safes" - when the number of count is 0.
if self.count == 0:
return self.cells
else:
return None
def mark_mine(self, cell):
"""
Updates internal knowledge representation given the fact that
a cell is known to be a mine.
"""
# Marking mine implies two logical consequences:
# a) the number of counts must decrease by one (n - 1);
# b) the cell marked as mine must be discarded from the sentence (we keep track,
# only of the cells that are still unknown to be mines or "safes".
if cell in self.cells:
self.cells.discard(cell)
self.count -= 1
if self.count < 0: # this is a safeguard from any improper inference set forth.
self.count = 0
else:
pass
def mark_safe(self, cell):
"""
Updates internal knowledge representation given the fact that
a cell is known to be safe.
"""
# Marking "safe" implies one logical consequence:
# a) the cell marked as safe must be discarded from the sentence.
if cell in self.cells:
self.cells.discard(cell)
else:
pass
扫雷AI类，主要AI模块：
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
"""
# 1) mark the cell as a move that has been made.
self.moves_made.add(cell)
# 2) mark the cell as safe. By this we are also updating our internal knowledge base.
self.mark_safe(cell)
# 3) add a new sentence to the AI's knowledge base based on the value of `cell` and `count`
sentence_prep = set()
# Sentence must include all the adjacent tiles, but do not include:
# a) the revealed cell itself;
# b) the cells that are known to be mines;
# c) the cell that are known to be safe.
for i in range(cell[0] - 1, cell[0] + 2):
for j in range(cell[1] - 1, cell[1] + 2): # Those two cover all the adjacent tiles.
if (i, j) != cell:
if (i, j) not in self.moves_made and (i, j) not in self.mines and (i, j) not in self.safes:
if 0 <= i < self.height and 0 <= j < self.width: # The cell must be within the game frame.
sentence_prep.add((i, j))
new_knowledge = Sentence(sentence_prep, count) # Adding newly formed knowledge to the KB.
self.knowledge.append(new_knowledge)
# 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.
while True: # iterating knowledge base in search for new conclusions on safes or mines.
amended = False # flag indicates that we have made changes to the knowledge, new run required.
knowledge_copy = copy.deepcopy(self.knowledge) # creating copy of the database.
for sentence in knowledge_copy: # cleaning empty sets from the database.
if len(sentence.cells) == 0:
self.knowledge.remove(sentence)
knowledge_copy = copy.deepcopy(self.knowledge) # creating copy once again, without empty sets().
for sentence in knowledge_copy:
mines_check = sentence.known_mines() # this should return: a set of mines that are known mines or None.
safes_check = sentence.known_safes() # this should return: a set of safes that are known safes or None
if mines_check is not None:
for cell in mines_check:
self.mark_mine(cell) # marking cell as a mine, and updating internal knowledge.
amended = True # raising flag.
if safes_check is not None:
for cell in safes_check:
self.mark_safe(cell) # marking cell as a safe, and updating internal knowledge.
amended = True # raising flag.
# the algorithm should infer new knowledge,
# basing on reasoning: (A.cells - B.cells) = (A.count - B.count), if
# B is the subset of A.
knowledge_copy = copy.deepcopy(self.knowledge) # creating copy once again, updated checks.
for sentence_one in knowledge_copy:
for sentence_two in knowledge_copy:
if len(sentence_one.cells) != 0 and len(sentence_two.cells) != 0: # In case of the empty set
if sentence_one.cells != sentence_two.cells: # Comparing sentences (if not the same).
if sentence_one.cells.issubset(sentence_two.cells): # If sentence one is subset of sen_two.
new_set = sentence_two.cells.difference(sentence_one.cells)
if len(new_set) != 0: # if new set is not empty (in case of bug).
new_counts = sentence_two.count - sentence_one.count
if new_counts >= 0: # if the counts are equal or bigger than 0 (in case of bug).
new_sentence = Sentence(new_set, new_counts)
if new_sentence not in self.knowledge: # if the sentence is not already in
# the KB.
self.knowledge.append(new_sentence)
amended = True # raising flag.
if not amended:
break # If the run resulted in no amendments, then we can not make any additional amendments,
# to our KB.
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 cell in self.safes:
if cell not in self.moves_made:
return cell
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):
cell = (i, j)
if cell not in self.moves_made and cell not in self.mines:
return cell
return None
问题文档：问题的文档-AI正在采取安全行动，现在应该将其标记为安全
一些评论：一般来说，当句子计数为零时，该单元格就被认为是安全的(这意味着句子中的所有单元格都被认为是"安全的"(。另一方面，如果单元格的(len(等于sentence.count，则该单元格被称为mine。它背后的逻辑相当简单，但在实现方面，我遗漏了一些重要内容。
谢谢你的帮助。请不要对我的代码太苛刻——我还在学习，老实说，这是我第一次为我准备的一段代码而苦苦挣扎。这让我几乎没有休息，因为我无法打击我做错的事情。如果有什么我可以提供的(任何更多的额外数据(-请告诉我！
好的，经过大量调试，我找到了问题的根源：当通过add_knowledge添加新知识时，AI只占它知道是地雷的细胞的一半：它没有将这些细胞添加到新的Sentence中，但还需要将每个已知细胞的count减少一个：
for i in range(cell[0] - 1, cell[0] + 2):
for j in range(cell[1] - 1, cell[1] + 2): # Those two cover all the adjacent tiles.
if (i, j) != cell:
if (i, j) not in self.moves_made and (i, j) not in self.mines and (i, j) not in self.safes:
if 0 <= i < self.height and 0 <= j < self.width: # The cell must be within the game frame.
sentence_prep.add((i, j))
elif (i, j) in self.mines: # One of the neighbors is a known mine. Reduce the count.
count -= 1
new_knowledge = Sentence(sentence_prep, count) # Adding newly formed knowledge to the KB.
self.knowledge.append(new_knowledge)
这现在应该可以工作了(除非某个地方有另一个边缘情况(
这里介绍一下我的旅程。我写了这些工具来帮助调试：
def get_neighbours(size, x, y):
for i in range(x - 1, x + 2):
for j in range(y - 1, y + 2): # Those two cover all the adjacent tiles.
if (i, j) != (x, y):
if 0 <= i < size[0] and 0 <= j < size[1]:
yield i, j
class SimpleBoard:
def __init__(self, size, grid):
self.size = size
self.grid = grid
self.calc()
def calc(self):
for x in range(self.size[0]):
for y in range(self.size[1]):
if self.grid[x][y] != 9:
self.grid[x][y] = sum(1 for i, j in get_neighbours(self.size, x, y) if self.grid[i][j] == 9)
@classmethod
def random(cls, size, count):
self = cls(size, [[0] * size[1] for _ in range(size[0])])
options = list(product(range(size[0]), range(size[1])))
shuffle(options)
mines = options[:count]
for x, y in mines:
self.grid[x][y] = 9
self.calc()
return self
def build_ai_view(ai: MinesweeperAI, board: SimpleBoard):
out = []
for x in range(ai.height):
out.append(l :=[])
for y in range(ai.width):
cell = x,y
if cell in ai.mines:
assert cell not in ai.safes
l.append("X" if board.grid[x][y] == 9 else "%")
elif cell in ai.safes:
l.append(str(board.grid[x][y]) if cell in ai.moves_made else "_")
else:
l.append("?")
cells_to_sentence = defaultdict(list)
for i, sentence in enumerate(ai.knowledge):
for c in sentence.cells:
cells_to_sentence[c].append(sentence)
unique_groups = []
for c, ss in cells_to_sentence.items():
if ss not in unique_groups:
unique_groups.append(ss)
labels = "abcdefghijklmnopqrstuvxyz"
for (x, y), ss in cells_to_sentence.items():
i = unique_groups.index(ss)
l = labels[i]
assert out[x][y] == "?"
out[x][y] = l
for i, ss in enumerate(unique_groups):
out.append(l := [labels[i]])
if len(ss) > 1:
l.append("overlap of")
for s in ss:
if [s] not in unique_groups:
unique_groups.append([s])
l.append(labels[unique_groups.index([s])])
# l.extend(labels[unique_groups.index([s])] for s in ss)
else:
l.append(str(ss[0].count))
out.append([repr(ai)])
return "n".join(map(str, out))
它们可能不是漂亮的代码，但它们可以从人工智能的角度工作并显示所有相关信息。然后我将其与给定的失败案例一起使用：
board = SimpleBoard((8, 8), [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 9, 0, 0, 0, 9, 0, 0],
[0, 0, 0, 9, 0, 0, 0, 0],
[0, 0, 0, 9, 0, 0, 0, 0],
[0, 9, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 9, 0, 9, 0, 9, 0, 0],
])
这个简单的循环：
pprint(board.grid)
start = next((x, y) for x in range(board.size[0]) for y in range(board.size[1]) if board.grid[x][y] == 0)
ai = MinesweeperAI(*board.size)
ai.add_knowledge(start, 0)
print(build_ai_view(ai, board))
while True:
target = ai.make_safe_move()
print(target)
x, y = target
if board.grid[x][y] == 9:
print("FOUND MINE", x, y)
break
else:
ai.add_knowledge((x, y), board.grid[x][y])
print(build_ai_view(ai, board))
能够倒推计算出人工智能在什么时候开始做出错误的假设。
这需要多个步骤：弄清楚第一个%(例如错误标记的我的(何时出现，弄清楚哪些句子导致了这个结论，弄清楚其中哪些是错误的，最后弄清楚为什么要做出这个假设。