python - 扫雷 AI 将地雷标记为安全地点
问题描述
背景： 我已经为HarvardX CS50AI在线课程的Minesweeper AI项目工作了几天。目标是为扫雷游戏实现人工智能。问题集可以在这里访问：https ://cs50.harvard.edu/ai/2020/projects/1/minesweeper/
实现： 我的任务是实现两个类，MinesweeperAI 和 Sentence。句子类是关于扫雷游戏的逻辑语句，它由一组棋盘单元和作为地雷的单元的数量组成。MinesweeperAI 类是 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
MinesweeperAI 类，主要的 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 正在采取安全措施，现在应该将其标记为安全措施
一些评论： 一般来说，当 sentence.count 为零时，单元格被认为是安全的（这意味着句子中的所有单元格都被认为是“安全的”）。另一方面，如果单元格的 (len) 等于 sentence.count，则该单元格称为地雷。它背后的逻辑相当简单，但在实现方面我仍然遗漏了一些重要的东西。
谢谢你的帮助。请不要对我的代码太苛刻 - 我还在学习，老实说，这是我第一次为我准备好的一段代码而苦苦挣扎。它让我很少休息，因为我无法打击我做错的事情。如果有什么我可以提供的（任何其他数据） - 请告诉我！
解决方案
好的，经过大量调试后，我找到了问题的根源：当通过添加新知识时add_knowledge，人工智能只占它知道是我的单元格的一半：它没有将这些添加到新的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))
它们可能不是漂亮的代码，但它们可以从 AI 的角度工作并显示所有相关信息。然后我将它与给定的失败案例一起使用：
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))
能够向后找出人工智能在什么时候开始做出错误的假设。
这分为多个步骤：找出第一个%（例如错误标记的我的）何时出现，找出导致该结论的句子，找出其中哪些是错误的，最后找出做出该假设的原因。
推荐阅读
- python-3.x - Python 映射列表乱序返回字典
- javascript - 用打字稿和角度对父母和孩子进行排序
- android - 根据屏幕密度分离 Jetpack 可组合功能
- vue.js - 覆盖 Vuetify 变量
- node.js - 为什么 api 调用需要很长时间才能响应？通过邮递员调用相同的 api url 立即给出结果
- google-apps-script - Google Apps 脚本从 Stripe 接收 webhook，未能提取部分接收到的事件信息
- rust - 使用类似“复制”的语义在可变引用上创建包装器
- c# - 如何使用 CsvHelper 正确映射集合
- django - 如何在 Django ModelForm 中测试自定义的清理方法
- javascript - 该站点似乎使用了滚动链接的定位效果。这可能不适用于异步平移