Minesweeper  扫雷舰

Write an AI to play Minesweeper.
编写一个 AI 来玩扫雷。

When to Do It
何时做

By Wednesday, January 1, 2025 at 12:59 PM GMT+8
截至 2025 年 1 月 1 日星期三中午 12:59 GMT+8

How to Get Help
如何获得帮助

1. Ask questions via Ed! 通过 Ed 提问！
2. Ask questions via any of CS50’s communities!
   通过任何 CS50 社区提问！

Background  背景

Minesweeper  扫雷舰

Minesweeper is a puzzle game that consists of a grid of cells, where some of the cells contain hidden “mines.” Clicking on a cell that contains a mine detonates the mine, and causes the user to lose the game. Clicking on a “safe” cell (i.e., a cell that does not contain a mine) reveals a number that indicates how many neighboring cells – where a neighbor is a cell that is one square to the left, right, up, down, or diagonal from the given cell – contain a mine.
扫雷是一款由单元网格组成的益智游戏，其中一些单元包含隐藏的“地雷”。单击包含地雷的单元格会引爆地雷，并导致用户输掉游戏。单击“安全”单元格（即不包含地雷的单元格）会显示一个数字，指示有多少个相邻单元格 - 其中邻居是向左、向右、向上、向下或向下各一格的单元格给定单元格的对角线 – 包含一个地雷。

In this 3x3 Minesweeper game, for example, the three 1 values indicate that each of those cells has one neighboring cell that is a mine. The four 0 values indicate that each of those cells has no neighboring mine.
例如，在这款 3x3 扫雷游戏中，三个 1 值表示每个单元格都有一个相邻单元格是地雷。四个 0 值表示每个单元格没有相邻的地雷。

Given this information, a logical player could conclude that there must be a mine in the lower-right cell and that there is no mine in the upper-left cell, for only in that case would the numerical labels on each of the other cells be accurate.
有了这些信息，逻辑玩家就可以得出结论，右下单元格中一定有一个地雷，而左上角单元格中没有地雷，因为只有在这种情况下，其他每个单元格上的数字标签才会是准确的。

The goal of the game is to flag (i.e., identify) each of the mines. In many implementations of the game, including the one in this project, the player can flag a mine by right-clicking on a cell (or two-finger clicking, depending on the computer).
游戏的目标是标记（即识别）每个地雷。在游戏的许多实现中，包括本项目中的实现，玩家可以通过右键单击单元格（或用两根手指单击，具体取决于计算机）来标记地雷。

Propositional Logic  命题逻辑

Your goal in this project will be to build an AI that can play Minesweeper. Recall that knowledge-based agents make decisions by considering their knowledge base, and making inferences based on that knowledge.
你在这个项目中的目标是构建一个可以玩扫雷的人工智能。回想一下，基于知识的代理通过考虑其知识库并根据该知识做出推断来做出决策。

One way we could represent an AI’s knowledge about a Minesweeper game is by making each cell a propositional variable that is true if the cell contains a mine, and false otherwise.
我们可以表示人工智能对扫雷游戏的了解的一种方法是让每个单元格成为一个命题变量，如果该单元格包含地雷，则该命题变量为真，否则为假。

What information does the AI have access to? Well, the AI would know every time a safe cell is clicked on and would get to see the number for that cell. Consider the following Minesweeper board, where the middle cell has been revealed, and the other cells have been labeled with an identifying letter for the sake of discussion.
AI可以访问哪些信息？好吧，每次点击安全单元格时，人工智能都会知道，并会看到该单元格的编号。考虑下面的扫雷板，其中中间的单元格已被显示，并且其他单元格已标有识别字母以便于讨论。

What information do we have now? It appears we now know that one of the eight neighboring cells is a mine. Therefore, we could write a logical expression like the below to indicate that one of the neighboring cells is a mine.
我们现在有什么信息？看来我们现在知道八个相邻单元格之一是一个地雷。因此，我们可以编写如下逻辑表达式来指示相邻单元格之一是地雷。

Or(A, B, C, D, E, F, G, H)

But we actually know more than what this expression says. The above logical sentence expresses the idea that at least one of those eight variables is true. But we can make a stronger statement than that: we know that exactly one of the eight variables is true. This gives us a propositional logic sentence like the below.
但我们实际上知道的不仅仅是这个表达的内容。上面的逻辑句子表达了这样的想法：这八个变量中至少有一个为真。但我们可以做出比这更强有力的声明：我们知道八个变量中有一个是真的。这给了我们一个如下的命题逻辑句子。

Or(
    And(A, Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), B, Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), C, Not(D), Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), D, Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), E, Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), Not(E), F, Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), G, Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), H)
)

That’s quite a complicated expression! And that’s just to express what it means for a cell to have a 1 in it. If a cell has a 2 or 3 or some other value, the expression could be even longer.
这是一个相当复杂的表达！这只是为了表达单元格中包含 1 的含义。如果单元格具有 2 或 3 或其他值，则表达式可能会更长。

Trying to perform model checking on this type of problem, too, would quickly become intractable: on an 8x8 grid, the size Microsoft uses for its Beginner level, we’d have 64 variables, and therefore 2^64 possible models to check – far too many for a computer to compute in any reasonable amount of time. We need a better representation of knowledge for this problem.
尝试对此类问题执行模型检查也会很快变得棘手：在 8x8 网格（微软用于初级水平的大小）上，我们有 64 个变量，因此需要检查 2^64 个可能的模型 - 远对于计算机来说，数量太多，无法在合理的时间内进行计算。我们需要更好地表示这个问题的知识。

Knowledge Representation
知识表示

Instead, we’ll represent each sentence of our AI’s knowledge like the below.
相反，我们将像下面这样表示人工智能知识的每个句子。

{A, B, C, D, E, F, G, H} = 1

Every logical sentence in this representation has two parts: a set of cells on the board that are involved in the sentence, and a number count, representing the count of how many of those cells are mines. The above logical sentence says that out of cells A, B, C, D, E, F, G, and H, exactly 1 of them is a mine.
此表示中的每个逻辑句子都有两部分：句子中涉及的棋盘上的一组 cells 和一个数字 count ，表示这些单元格的数量是地雷。上面的逻辑语句表示，在单元格 A、B、C、D、E、F、G 和 H 中，恰好有 1 个是地雷。

Why is this a useful representation? In part, it lends itself well to certain types of inference. Consider the game below.
为什么这是一个有用的表示？在某种程度上，它非常适合某些类型的推理。考虑下面的游戏。

Using the knowledge from the lower-left number, we could construct the sentence {D, E, G} = 0 to mean that out of cells D, E, and G, exactly 0 of them are mines. Intuitively, we can infer from that sentence that all of the cells must be safe. By extension, any time we have a sentence whose count is 0, we know that all of that sentence’s cells must be safe.
利用左下数字中的知识，我们可以构建句子 {D, E, G} = 0 来表示在单元格 D、E 和 G 中，恰好有 0 个是地雷。凭直觉，我们可以从这句话中推断出所有的细胞都一定是安全的。通过扩展，任何时候我们有一个 count 是 0 的句子，我们知道该句子的所有 cells 都必须是安全的。

Similarly, consider the game below.
同样，考虑下面的游戏。

Our AI would construct the sentence {E, F, H} = 3. Intuitively, we can infer that all of E, F, and H are mines. More generally, any time the number of cells is equal to the count, we know that all of that sentence’s cells must be mines.
我们的人工智能将构造句子 {E, F, H} = 3 。直观上我们可以推断E、F、H都是地雷。更一般地说，只要 cells 的数量等于 count 的数量，我们就知道该句子的所有 cells 都一定是我的。

In general, we’ll only want our sentences to be about cells that are not yet known to be either safe or mines. This means that, once we know whether a cell is a mine or not, we can update our sentences to simplify them and potentially draw new conclusions.
一般来说，我们只希望我们的句子是关于 cells 的，而且还不知道是安全的还是地雷的。这意味着，一旦我们知道某个单元是否是地雷，我们就可以更新句子以简化它们，并可能得出新的结论。

For example, if our AI knew the sentence {A, B, C} = 2, we don’t yet have enough information to conclude anything. But if we were told that C were safe, we could remove C from the sentence altogether, leaving us with the sentence {A, B} = 2 (which, incidentally, does let us draw some new conclusions.)
例如，如果我们的人工智能知道句子 {A, B, C} = 2 ，我们还没有足够的信息来得出任何结论。但如果我们被告知 C 是安全的，我们可以从句子中完全删除 C ，留下句子 {A, B} = 2 （顺便说一句，这确实让我们得出了一些新的结论。 ）

Likewise, if our AI knew the sentence {A, B, C} = 2, and we were told that C is a mine, we could remove C from the sentence and decrease the value of count (since C was a mine that contributed to that count), giving us the sentence {A, B} = 1. This is logical: if two out of A, B, and C are mines, and we know that C is a mine, then it must be the case that out of A and B, exactly one of them is a mine.
同样，如果我们的人工智能知道句子 {A, B, C} = 2 ，并且我们被告知 C 是一个地雷，我们可以从句子中删除 C 并减少 count （因为 C 是一个矿井，对这个计数有贡献），给我们句子 {A, B} = 1 。这是符合逻辑的：如果 A、B、C 中有两个是地雷，并且我们知道 C 是地雷，那么 A 和 B 中一定有一个是地雷。

If we’re being even more clever, there’s one final type of inference we can do.
如果我们更聪明的话，我们还可以进行最后一种推理。

Consider just the two sentences our AI would know based on the top middle cell and the bottom middle cell. From the top middle cell, we have {A, B, C} = 1. From the bottom middle cell, we have {A, B, C, D, E} = 2. Logically, we could then infer a new piece of knowledge, that {D, E} = 1. After all, if two of A, B, C, D, and E are mines, and only one of A, B, and C are mines, then it stands to reason that exactly one of D and E must be the other mine.
考虑一下我们的人工智能根据顶部中间单元格和底部中间单元格知道的两个句子。从顶部中间的单元格开始，我们有 {A, B, C} = 1 。从底部中间的单元格开始，我们有 {A, B, C, D, E} = 2 。从逻辑上讲，我们可以推断出一个新的知识，即 {D, E} = 1 。毕竟，如果 A、B、C、D、E 中有两个是地雷，而 A、B、C 中只有一个是地雷，那么按理说，D 和 E 中一定有一个是地雷。

More generally, any time we have two sentences set1 = count1 and set2 = count2 where set1 is a subset of set2, then we can construct the new sentence set2 - set1 = count2 - count1. Consider the example above to ensure you understand why that’s true.
更一般地，任何时候我们有两个句子 set1 = count1 和 set2 = count2 ，其中 set1 是 set2 的子集，那么我们可以构造新的句子 set2 - set1 = count2 - count1 。考虑上面的例子以确保您理解为什么会这样。

So using this method of representing knowledge, we can write an AI agent that can gather knowledge about the Minesweeper board, and hopefully select cells it knows to be safe!
因此，使用这种表示知识的方法，我们可以编写一个人工智能代理，它可以收集有关扫雷板的知识，并希望选择它知道安全的单元格！

Getting Started  入门

• Download the distribution code from https://cdn.cs50.net/ai/2023/x/projects/1/minesweeper.zip and unzip it.
  从 https://cdn.cs50.net/ai/2023/x/projects/1/minesweeper.zip 下载分发代码并解压。
• Once in the directory for the project, run pip3 install -r requirements.txt to install the required Python package (pygame) for this project if you don’t already have it installed.
  进入项目目录后，运行 pip3 install -r requirements.txt 来安装该项目所需的 Python 包 ( pygame )（如果尚未安装）。

Understanding  理解

There are two main files in this project: runner.py and minesweeper.py. minesweeper.py contains all of the logic the game itself and for the AI to play the game. runner.py has been implemented for you, and contains all of the code to run the graphical interface for the game. Once you’ve completed all the required functions in minesweeper.py, you should be able to run python runner.py to play Minesweeper (or let your AI play for you)!
该项目中有两个主要文件： runner.py 和 minesweeper.py 。 minesweeper.py 包含游戏本身以及 AI 玩游戏的所有逻辑。 runner.py 已为您实现，并包含运行游戏图形界面的所有代码。完成 minesweeper.py 中所有必需的功能后，您应该能够运行 python runner.py 来玩扫雷（或者让您的 AI 为您玩）！

Let’s open up minesweeper.py to understand what’s provided. There are three classes defined in this file, Minesweeper, which handles the gameplay; Sentence, which represents a logical sentence that contains both a set of cells and a count; and MinesweeperAI, which handles inferring which moves to make based on knowledge.
让我们打开 minesweeper.py 来了解所提供的内容。该文件中定义了三个类 Minesweeper ，用于处理游戏玩法； Sentence ，表示一个逻辑句子，包含一组 cells 和一个 count ；和 MinesweeperAI ，它处理基于知识的推断。

The Minesweeper class has been entirely implemented for you. Notice that each cell is a pair (i, j) where i is the row number (ranging from 0 to height - 1) and j is the column number (ranging from 0 to width - 1).
Minesweeper 类已完全为您实现。请注意，每个单元格都是一对 (i, j) ，其中 i 是行号（范围从 0 到 height - 1 ），而 j 到 width - 1 ）。

The Sentence class will be used to represent logical sentences of the form described in the Background. Each sentence has a set of cells within it and a count of how many of those cells are mines. The class also contains functions known_mines and known_safes for determining if any of the cells in the sentence are known to be mines or known to be safe. It also contains functions mark_mine and mark_safe to update a sentence in response to new information about a cell.
Sentence 类将用于表示背景中描述的形式的逻辑句子。每个句子都有一组 cells 和一个 count 表示这些单元中有多少是地雷。该类还包含函数 known_mines 和 known_safes ，用于确定句子中的任何单元是否已知是地雷或已知是安全的。它还包含函数 mark_mine 和 mark_safe 来更新句子以响应有关单元格的新信息。

Finally, the MinesweeperAI class will implement an AI that can play Minesweeper. The AI class keeps track of a number of values. self.moves_made contains a set of all cells already clicked on, so the AI knows not to pick those again. self.mines contains a set of all cells known to be mines. self.safes contains a set of all cells known to be safe. And self.knowledge contains a list of all of the Sentences that the AI knows to be true.
最后， MinesweeperAI 类将实现一个可以玩扫雷的AI。 AI 类跟踪许多值。 self.moves_made 包含一组已单击的所有单元格，因此 AI 知道不要再次选择这些单元格。 self.mines 包含一组已知为地雷的所有单元格。 self.safes 包含一组已知安全的所有单元格。 self.knowledge 包含 AI 知道的所有 Sentence 的列表。

The mark_mine function adds a cell to self.mines, so the AI knows that it is a mine. It also loops over all sentences in the AI’s knowledge and informs each sentence that the cell is a mine, so that the sentence can update itself accordingly if it contains information about that mine. The mark_safe function does the same thing, but for safe cells instead.
mark_mine 函数向 self.mines 添加一个单元格，因此 AI 知道它是一个地雷。它还循环遍历 AI 的 knowledge 中的所有句子，并通知每个句子该单元格是一个地雷，以便该句子可以在包含有关该地雷的信息时相应地进行自我更新。 mark_safe 函数执行相同的操作，但用于安全单元格。

The remaining functions, add_knowledge, make_safe_move, and make_random_move, are left up to you!
其余的函数 add_knowledge 、 make_safe_move 和 make_random_move 都由您决定！

Specification  规格

Complete the implementations of the Sentence class and the MinesweeperAI class in minesweeper.py.
完成 minesweeper.py 中 Sentence 类和 MinesweeperAI 类的实现。

In the Sentence class, complete the implementations of known_mines, known_safes, mark_mine, and mark_safe.
在 Sentence 类中，完成 known_mines 、 known_safes 、 mark_mine 和 mark_safe 的实现。

• The known_mines function should return a set of all of the cells in self.cells that are known to be mines.
  known_mines 函数应返回 self.cells 中已知为地雷的所有单元格的集合。
• The known_safes function should return a set of all the cells in self.cells that are known to be safe.
  known_safes 函数应返回 self.cells 中已知安全的所有单元格的集合。
• The mark_mine function should first check to see if cell is one of the cells included in the sentence.
  mark_mine 函数应首先检查 cell 是否是句子中包含的单元格之一。
  • If cell is in the sentence, the function should update the sentence so that cell is no longer in the sentence, but still represents a logically correct sentence given that cell is known to be a mine.
    如果 cell 在句子中，该函数应该更新句子，以便 cell 不再在句子中，但仍然表示一个逻辑上正确的句子，因为 cell 已知是一个地雷。
  • If cell is not in the sentence, then no action is necessary.
    如果句子中没有 cell ，则无需执行任何操作。
• The mark_safe function should first check to see if cell is one of the cells included in the sentence.
  mark_safe 函数应首先检查 cell 是否是句子中包含的单元格之一。
  • If cell is in the sentence, the function should update the sentence so that cell is no longer in the sentence, but still represents a logically correct sentence given that cell is known to be safe.
    如果 cell 在句子中，该函数应该更新句子，以便 cell 不再在句子中，但仍然表示一个逻辑上正确的句子，因为 cell 已知是安全的。
  • If cell is not in the sentence, then no action is necessary.
    如果句子中没有 cell ，则无需执行任何操作。

In the MinesweeperAI class, complete the implementations of add_knowledge, make_safe_move, and make_random_move.
在 MinesweeperAI 类中，完成 add_knowledge 、 make_safe_move 和 make_random_move 的实现。

• add_knowledge should accept a cell (represented as a tuple (i, j)) and its corresponding count, and update self.mines, self.safes, self.moves_made, and self.knowledge with any new information that the AI can infer, given that cell is known to be a safe cell with count mines neighboring it.
  add_knowledge 应该接受 cell （表示为元组 (i, j) ）及其相应的 count ，并更新 self.mines 、 self.safes 、 self.moves_made 和 self.knowledge 以及 AI 可以推断出的任何新信息，前提是 cell 已知是安全的其附近有 count 地雷的单元格。
  • The function should mark the cell as one of the moves made in the game.
    该函数应将 cell 标记为游戏中的动作之一。
  • The function should mark the cell as a safe cell, updating any sentences that contain the cell as well.
    该函数应将 cell 标记为安全单元，同时更新包含 cell 的任何句子。
  • The function should add a new sentence to the AI’s knowledge base, based on the value of cell and count, to indicate that count of the cell’s neighbors are mines. Be sure to only include cells whose state is still undetermined in the sentence.
    该函数应根据 cell 和 count 的值向 AI 知识库添加一个新句子，以指示 cell /b3> 的邻居是地雷。确保句子中仅包含状态尚未确定的单元格。
  • If, based on any of the sentences in self.knowledge, new cells can be marked as safe or as mines, then the function should do so.
    如果基于 self.knowledge 中的任何句子，新单元格可以标记为安全或地雷，则该函数应该这样做。
  • If, based on any of the sentences in self.knowledge, new sentences can be inferred (using the subset method described in the Background), then those sentences should be added to the knowledge base as well.
    如果基于 self.knowledge 中的任何句子，可以推断出新的句子（使用背景技术中描述的子集方法），那么这些句子也应该添加到知识库中。
  • Note that any time that you make any change to your AI’s knowledge, it may be possible to draw new inferences that weren’t possible before. Be sure that those new inferences are added to the knowledge base if it is possible to do so.
    请注意，每当你对人工智能的知识进行任何更改时，都有可能得出以前不可能的新推论。如果可能的话，请确保将这些新的推论添加到知识库中。
• make_safe_move should return a move (i, j) that is known to be safe.
  make_safe_move 应返回已知安全的移动 (i, j) 。
  • The move returned must be known to be safe, and not a move already made.
    返回的移动必须是安全的，而不是已经进行的移动。
  • If no safe move can be guaranteed, the function should return None.
    如果不能保证安全移动，该函数应返回 None 。
  • The function should not modify self.moves_made, self.mines, self.safes, or self.knowledge.
    该函数不应修改 self.moves_made 、 self.mines 、 self.safes 或 self.knowledge 。
• make_random_move should return a random move (i, j).
  make_random_move 应该返回随机移动 (i, j) 。
  • This function will be called if a safe move is not possible: if the AI doesn’t know where to move, it will choose to move randomly instead.
    如果无法安全移动，则会调用此函数：如果 AI 不知道要移动到哪里，它将选择随机移动。
  • The move must not be a move that has already been made.
    该举措不得是已经采取的举措。
  • The move must not be a move that is known to be a mine.
    该举动不得是已知有地雷的举动。
  • If no such moves are possible, the function should return None.
    如果不可能进行此类移动，则该函数应返回 None 。

Hints 提示

• Be sure you’ve thoroughly read the Background section to understand how knowledge is represented in this AI and how the AI can make inferences.
  请确保您已彻底阅读背景部分，以了解该人工智能中知识的表示方式以及人工智能如何进行推理。
• If feeling less comfortable with object-oriented programming, you may find Python’s documentation on classes helpful.
  如果对面向对象编程感觉不太舒服，您可能会发现 Python 的类文档很有帮助。
• You can find some common set operations in Python’s documentation on sets.
  您可以在 Python 的集合文档中找到一些常见的 set 运算。
• When implementing known_mines and known_safes in the Sentence class, consider: under what circumstances do you know for sure that a sentence’s cells are safe? Under what circumstances do you know for sure that a sentence’s cells are mines?
  在 Sentence 类中实现 known_mines 和 known_safes 时，请考虑：在什么情况下您确定句子的单元格是安全的？在什么情况下你能确定一个句子的单元格是地雷的？
• add_knowledge does quite a lot of work, and will likely be the longest function you write for this project by far. It will likely be helpful to implement this function’s behavior one step at a time.
  add_knowledge 做了相当多的工作，并且可能是迄今为止您为此项目编写的最长的函数。一次一步地实现该函数的行为可能会有所帮助。
• You’re welcome to add new methods to any of the classes if you would like, but you should not modify any of the existing functions’ definitions or arguments.
  如果您愿意，欢迎您向任何类添加新方法，但您不应修改任何现有函数的定义或参数。
• When you run your AI (as by clicking “AI Move”), note that it will not always win! There will be some cases where the AI must guess, because it lacks sufficient information to make a safe move. This is to be expected. runner.py will print whether the AI is making a move it believes to be safe or whether it is making a random move.
  当您运行 AI 时（例如单击“AI Move”），请注意，它并不总是获胜！在某些情况下，人工智能必须猜测，因为它缺乏足够的信息来采取安全行动。这是可以预料的。 runner.py 将打印 AI 是否正在做出它认为安全的举动，或者是否正在做出随机举动。
• Be careful not to modify a set while iterating over it. Doing so may result in errors!
  请注意，在迭代集合时不要修改集合。这样做可能会导致错误！

Testing 测试

If you’d like, you can execute the below (after setting up check50 on your system) to evaluate the correctness of your code. This isn’t obligatory; you can simply submit following the steps at the end of this specification, and these same tests will run on our server. Either way, be sure to compile and test it yourself as well!
如果您愿意，可以执行以下命令（在系统上设置 check50 后）来评估代码的正确性。这不是强制性的；您只需按照本规范末尾的步骤进行提交，这些相同的测试将在我们的服务器上运行。不管怎样，一定要自己编译和测试！

check50 ai50/projects/2024/x/minesweeper

Execute the below to evaluate the style of your code using style50.
执行以下命令以使用 style50 评估代码的风格。

style50 minesweeper.py

How to Submit

1. Visit this link, log in with your GitHub account, and click Authorize cs50. Then, check the box indicating that you’d like to grant course staff access to your submissions, and click Join course.
2. Install Git and, optionally, install submit50.
3. If you’ve installed submit50, execute

   submit50 ai50/projects/2024/x/minesweeper
   

   Otherwise, using Git, push your work to https://github.com/me50/USERNAME.git, where USERNAME is your GitHub username, on a branch called ai50/projects/2024/x/minesweeper.

Work should be graded within five minutes. You can then go to https://cs50.me/cs50ai to view your current progress!