cs50ai1

阅读原文时间：2023年08月25日阅读：1

cs50ai1-------Knowledge

cs50ai1-------Knowledge

基础知识

对我们来说，一些基本的logic是自然而然的，我们可以根据已知的事实，来作出判断或者进行推理，但是ai是如何模拟这一点呢

从最简单的命题逻辑开始，这节课介绍了命题逻辑的一些基本知识，比如命题符合、逻辑连接词，引入了sentence、model、knowledge base、entailment与inference的概念：

sentence：

an assertion about the world

in a knowledge representation language

model：

assignment of a truth value to every

propositional symbol (a "possible world")

knowledge base：

a set of sentences known by a

knowledge-based agent

Entailment

α ⊨ β

In every model in which sentence α is true,

sentence β is also true.

inference：

the process of deriving new sentences

from old ones

接着介绍了三种推理的算法，也就是解决KB ⊨ α？的问题，即是否可以从知识库中推理中α

第一种是model checking算法

也就是离散数学中最直接的一种方法，列真值表然后查真值表，但是这种方法显然在命题符号增加的时候，会十分复杂

第二种方法是Theorem Proving的方法

引入了一些常见的公理，比如合取、析取、分配律，德摩根定律等等

具体过程如下图：

第三者方法是Inference by Resolution算法：

这里是通过合取范式，合取范式可以通过以下的方式来生成：

而由于合取范式每个子句都是一个析取（OR）的组合，这使得我们可以更容易地应用resolution规则。resolution规则需要在两个子句中找到互补的文字（一个是正文字，另一个是它的否定），而CNF的形式正好契合这一点

具体算法如下：

简要来说就是对(KB ∧ ¬α)的合取范式进行不断的resolution，最后如果得到（）空，就说明KB ⊨ α是成立的

下面就是一个一步步resolution的例子

然后其实现实世界中逻辑问题要更为复杂，命题逻辑很可能很难或者说无法去表示这样的问题，这就又引出了一阶逻辑，存在量词与universal 量词等等，这里也没有更详细的展开

最后上面这些内容介绍的都是ai如何通过确定的来判断新的事物是true or false ，但是实际问题往往是uncertainty的，不是简单的能用0或1去表述，是0-1之间的，也就是下节课要学的关于ai是如何处理概率不确定的事物

课后题目

(1)Knights

understanding:

看一下logic.py，无需理解该文件中的所有内容，但请注意该文件为不同类型的逻辑连接词定义了多个类。这些类可以彼此组合，因此像 And(Not(A), Or(B, C)) 这样的表达式表示逻辑句子，表明符号 A 不为真，而符号 B 或符号 C 为真（其中这里的“或”是指包含，而不是排他）。

logic.py 还包含一个函数 model_check。 model_check 采用知识库和query。知识库是单个逻辑句子：如果已知多个逻辑句子，则可以将它们用 And 表达式连接在一起。 model_check 递归地考虑所有可能的模型，如果知识库蕴涵该query则返回 True，否则返回 False。

现在，看一下 puzzle.py。在顶部，我们定义了六个命题符号。例如，AKnight 代表“A 是骑士”这句话，而 AKnave 则代表“A 是无赖”这句话。我们也为字符 B 和 C 定义了命题符号。

接下来是四个不同的知识库，knowledge0、knowledge1、knowledge2和knowledge3，它们将分别包含推导即将出现的谜题0、1、2和3的解决方案所需的知识。请注意，目前这些知识库都是空的，这就是你要完成的地方。

这个 puzzle.py 的主要功能是循环遍历所有谜题，并使用model check来计算，根据该谜题的知识，无论每个角色是骑士还是无赖，打印model check算法能够得出的任何结论。

specification：

将knowldge添加到知识库knowledge0、knowledge1、knowledge2、knowledge3中，解决以下谜题。

谜题 0 是背景中的谜题。它包含一个字符，A。

A说：“我既是骑士，又是无赖。”

谜题 1 有两个角色：A 和 B。

A说：“我们都是无赖。”

B什么也没说。

谜题 2 有两个角色：A 和 B。

A说：“我们是同类。”

B 说：“我们是不同类型的。”

谜题 3 有 3 个角色：A、B 和 C。

A 要么说“我是骑士”。或者“我是个无赖”，但你不知道是哪一个。

B 说“A 说‘我是个无赖。’”

B 然后说：“C 是个无赖。”

C说“A是骑士。”

在上述每个谜题中，每个角色要么是骑士，要么是无赖。骑士所说的每一句话都是真的，无赖所说的每一句话都是假的。

完成问题的知识库后，您应该能够运行 python puzzle.py 来查看难题的解决方案。

hints：

对于每个知识库，您可能需要编码两种不同类型的信息：(1) 有关问题本身结构的信息（即骑士与无赖谜题的定义），以及关于角色所说的话的信息

考虑一下如果一个角色说出一个句子意味着什么。在什么条件下这句话是正确的？在什么情况下这句话是错误的？你如何将其表达为一个逻辑句子？

每个谜题都有多个可能的知识库来计算正确的结果。您应该尝试选择一个能够对谜题中的信息提供最直接翻译的知识库，而不是自己进行逻辑推理。您还应该考虑谜题中信息的最简洁表示是什么。

例如，对于 Puzzle 0，设置knowledge0 = AKnave 将得到正确的输出，因为通过我们自己的推理，我们知道 A 一定是一个无赖。但这样做会违背这个问题的精神：目标是让你的人工智能为你进行推理。

您根本不需要（也不应该）修改logic.py 来完成这个问题。

(2)Minesweeper

background：

在这个扫雷游戏中，sentence的形式是以{E, F, H} = 3的样子构成的，其中{E,F,H}为sentence中的cells，3为count即地雷的计数，而排除地雷或其它操作都是通过对集合信息的更改或者集合之间的运算

understanding：

该项目中有两个主要文件：runner.py 和minesweeper.py。 minesweeper.py 包含游戏本身以及 AI 玩游戏的所有逻辑。 runner.py 已为您实现，并且包含运行游戏图形界面的所有代码。一旦你完成了minesweeper.py中所有必需的功能，你应该能够运行python runner.py来玩扫雷（或者让你的AI为你玩

让我们打开minesweeper.py来了解所提供的内容。该文件中定义了三个类，Minesweeper，处理游戏玩法； Sentence，表示一个逻辑句子，包含一组单元格和一个计数；MinesweeperAI，它根据knowledge推断要采取的行动。

扫雷类已经为您完全实现了。请注意，每个单元格都是一对 (i, j)，其中 i 是行号（范围从 0 到 height - 1），j 是列号（范围从 0 到 width - 1）。

Sentence 类将用于表示背景技术中描述的形式的逻辑句子。每个句子都有一组单元格，以及这些单元格中有多少是地雷的计数。该类还包含函数known_mines和known_safes，用于确定句子中的任何单元是否已知是地雷或已知是安全的。它还包含函数 mark_mine 和 mark_safe 来更新句子以响应有关单元格的新信息。

最后，MinesweeperAI 类将实现一个可以玩扫雷的 AI。 AI 类跟踪许多值。 self.moves_made 包含一组已单击的所有单元格，因此 AI 知道不要再次选择这些单元格。 self.mines 包含一组已知为地雷的所有单元格。 self.safes 包含一组已知安全的所有单元格。 self.knowledge 包含人工智能知道正确的所有句子的列表。

mark_mine 函数将一个单元格添加到 self.mines 中，因此 AI 知道它是一个地雷。它还循环遍历ai knowledge中的所有sentence，并告知每个sentence该单元是一个地雷，以便该sentence可以在包含有关该地雷的信息时进行相应更新。 mark_safe 函数执行相同的操作，但针对的是安全单元。

剩下的函数 add_knowledge、make_safe_move 和 make_random_move 就留给您完成了

specification：

完成minesweeper.py中Sentence类和MinesweeperAI类的实现。

在Sentence类中，完成known_mines、known_safes、mark_mine和mark_safe的实现。

known_mines 函数应返回 self.cells 中已知为地雷的所有单元格的集合。

known_safes 函数应返回 self.cells 中已知安全的所有单元格的集合。

mark_mine 函数应首先检查单元格是否是sentence中包含的单元格之一。

如果单元格在sentence中，则该函数应该更新sentence，以便单元格不再在sentence中，但仍然表示逻辑上正确的sentence，因为已知单元格是一个地雷。

如果单元格不在sentence中，则无需执行任何操作。

mark_safe 函数应首先检查单元格是否是sentence中包含的单元格之一。

如果单元格在sentence中，则该函数应更新sentence，以便单元格不再在sentence中，但在已知单元格是安全的情况下仍然表示逻辑上正确的sentence。

如果单元格不在sentence中，则无需执行任何操作。

在MinesweeperAI类中，完成add_knowledge、make_safe_move和make_random_move的实现。

add_knowledge 应该接受一个单元格（表示为元组 (i, j)）及其相应的计数，并使用 AI 可以推断的任何新信息更新 self.mines、self.safes、self.moves_made 和 self.knowledge，前提是该cell被认为是一个安全cell，其附近有数个地雷。

该函数应将单元格标记为游戏中的move之一。

该函数应将单元格标记为安全单元格，同时更新包含该单元格的任何sentence。

该函数应该根据单元格和计数的值向人工智能的知识库添加一个 new sentence，以指示该单元格的邻居的计数是地雷。确保sentence中仅包含状态尚未确定的单元格。

如果基于 self.knowledge 中的任何sentence，新单元格可以被标记为安全或地雷，那么该函数应该这样做。

如果基于 self.knowledge 中的任何sentence，可以推断出新的sentence（使用背景中描述的子集方法），那么这些sentence也应该添加到知识库中。

请注意，每当你对人工智能的知识进行任何更改时，都有可能得出以前不可能的新推论。如果可能的话，请确保将这些新的推论添加到知识库中。

make_safe_move 应该返回已知安全的移动 (i, j)。

返回的移动必须是安全的，而不是已经进行的移动。

如果不能保证安全移动，该函数应返回 None。

该函数不应修改 self.moves_made、self.mines、self.safes 或 self.knowledge。

make_random_move 应该返回随机移动 (i, j)。

如果无法安全移动，则会调用此函数：如果 AI 不知道要移动到哪里，它将选择随机移动。

该举措不得是已经采取的举措。

该举动不得是已知有地雷的举动。

如果不可能进行此类移动，则该函数应返回 None。

hints：

如果对面向对象编程感觉不太舒服，您可能会发现 Python 的类文档很有帮助。

您可以在 Python 的集合文档中找到一些常见的集合运算。

在 Sentence 类中实现known_mines和known_safes时，请考虑：在什么情况下您确定句子的单元格是安全的？在什么情况下你能确定一个句子的单元格是地雷的？

add_knowledge 做了相当多的工作，并且可能是迄今为止您为此项目编写的最长的函数。一次一步地实现该函数的行为可能会有所帮助。

如果您愿意，欢迎您向任何类添加新方法，但您不应修改任何现有函数的定义或参数。

当您运行 AI 时（例如单击“AI Move”），请注意，它并不总是获胜！在某些情况下，人工智能必须猜测，因为它缺乏足够的信息来采取安全行动。这是可以预料的。 runner.py 将打印 AI 是否正在做出它认为安全的举动，或者是否正在做出随机举动。

请注意，在迭代集合时不要修改集合。这样做可能会导致错误！

代码实践

(1) Knights

这个就是基本的命题逻辑之间的逻辑的表示，比较简单，puzzle 3稍微复杂一点，这里我写的就是最直接简单的，根据语句，对A可能说的两句话分别描述，然后用or连接起来，代码具体如下

# Puzzle 0
# A says "I am both a knight and a knave."
knowledge0 = And(
    # TODO
    # 不是同时为骑士或者无赖
    Not(And(AKnight, AKnave)),
    # 要么是骑士或者无赖
    Or(AKnight, AKnave),
    # 假如是骑士话是真的
    Implication(AKnight, And(AKnight, AKnave)),
    # 假如是无赖话是假的
    Implication(AKnave, Not(And(AKnight, AKnave)))

)

# Puzzle 1
# A says "We are both knaves."
# B says nothing.
knowledge1 = And(
    # 不是同时为骑士或者无赖
    Not(And(AKnight, AKnave)),
    # 要么是骑士或者无赖
    Or(AKnight, AKnave),
    # 不是同时为骑士或者无赖
    Not(And(BKnight, BKnave)),
    # 要么是骑士或者无赖
    Or(BKnight, BKnave),
    # 假如是骑士话是真的
    Implication(AKnight, And(BKnave, AKnave)),
    # 假如是无赖话是假的
    Implication(AKnave, Not(And(BKnave, AKnave)))
)

# Puzzle 2
# A says "We are the same kind."
# B says "We are of different kinds."
knowledge2 = And(
    # TODO
    # 不是同时为骑士或者无赖
    Not(And(AKnight, AKnave)),
    # 要么是骑士或者无赖
    Or(AKnight, AKnave),
    # 不是同时为骑士或者无赖
    Not(And(BKnight, BKnave)),
    # 要么是骑士或者无赖
    Or(BKnight, BKnave),
    # 假如是骑士话是真的
    Implication(AKnight, And(AKnight, BKnight)),
    # 假如是无赖话是假的
    Implication(AKnave, Not(And(BKnave, AKnave))),
    # 假如是骑士话是真的
    Implication(BKnight, And(BKnight, AKnave)),
    # 假如是无赖话是假的
    Implication(BKnave, Not(And(BKnave, AKnight)))
)

# Puzzle 3
# A says either "I am a knight." or "I am a knave.", but you don't know which.
# B says "A said 'I am a knave'."
# B says "C is a knave."
# C says "A is a knight."
knowledge3 = And(
    # TODO
    # 不是同时为骑士或者无赖
    Not(And(AKnight, AKnave)),
    # 要么是骑士或者无赖
    Or(AKnight, AKnave),
    # 不是同时为骑士或者无赖
    Not(And(BKnight, BKnave)),
    # 要么是骑士或者无赖
    Or(BKnight, BKnave),
    # 不是同时为骑士或者无赖
    Not(And(CKnight, CKnave)),
    # 要么是骑士或者无赖
    Or(CKnight, CKnave),

    Or(
        And(
            Implication(AKnight, AKnight),
            Implication(AKnave, Not(AKnight)),
            # b
            Implication(BKnight, And(
                Implication(AKnight, AKnave),
                Implication(AKnave, Not(AKnave))
            )),
            Implication(BKnave, Not(And(
                Implication(AKnight, AKnave),
                Implication(AKnave, Not(AKnave))
            ))),
            Implication(BKnight, CKnave),
            Implication(BKnave, Not(CKnave)),
            # c
            Implication(CKnight, AKnight),
            Implication(CKnave, Not(AKnight))
        ),
        And(
            Implication(AKnight, AKnave),
            Implication(AKnave, Not(AKnave)),
            # b
            Implication(BKnight, And(
                Implication(AKnight, AKnave),
                Implication(AKnave, Not(AKnave))
            )),
            Implication(BKnave, Not(And(
                Implication(AKnight, AKnave),
                Implication(AKnave, Not(AKnave))
            ))),
            Implication(BKnight, CKnave),
            Implication(BKnave, Not(CKnave)),
            # c
            Implication(CKnight, AKnight),
            Implication(CKnave, Not(AKnight))
        ),
    )
)

(2) Minesweeper

sentence类的完善：

首先是knownsafe与knownmines两个函数的完善，对应的是下面这两种情况：

{D, E, G} = 0,假如sentence的count等于0,就说明周围的这些cells都是safe的

{E, F, H} = 3，假如sentence的count与周围的cells的数量相等，这就说明周围的cells全是mine

其次是marksafe与markmines，这里传入的参数就是已知为safe或者mine的cells，因为我们sentence里面cells存储的只是unknown state的cells，所以传入的这些cells都要从cells这个set中删去，如果删去的是mine，还要将sentence的count减1

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
        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)

minessweeperai类的完善：

首先是markmine与marksafe函数，就是把已经被标记为mine与safe的cell，加入knowledge，将knowledge中的每个sentence，都调用sentence中的markmine与marksafe函数，将对应的cell删去

其次是make safe move 与make random move函数，

make safe move就是取已知为safe的cells集合和已经走过的move made的cells集合的差集，从剩下的没走过的safe cells中选择一个（这里是第一个

make random move 就是从所有cells的集合，选取一个不在mine集合或者move made集合中的cell作为下一步move

最后也是最复杂的add knowledge函数，根据提示

第一步与第二步将已知为safe的cell加入safes与moves made的集合，比较简单

第三步，向knowledge加入新的sentence，一个sentence是由cells(注意是所有状态未知的cells)与count(周围的地雷数)，所以我们要把作为参数的这个cell，周围的邻居都加入进来，然后从中筛选出去已经被标识为safe或者mine的邻居，剩下的就是unknown的cells，同时count也要减去已知为mine的邻居数量

第四步与第五步：

因为我们向knowledge中加入一个新的sentence之后，又获得了新的关于safe与mine的信息，需要更新，所以要遍历每个sentence，获取新的safe与mine的信息，然后再把它们传播到每个sentence中，而我们加入新的sentence之后(这里根据提示),遍历每个sentence，看它们取差集之后能不能产生新的sentence，如果产生了就添加到knowledge中。

并且由于上述操作之间也是相互关联的，所以要把它们放在一个大循环里，不断的进行conclude与infer，直到没有新的“知识”得出。

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 conclude(self):
        new_clue = 0
        mine_cells = []
        safe_cells = []
        for sentence in self.knowledge:
            if sentence.known_mines():
                new_clue += 1
                mine_cells += list(sentence.known_mines())
            if sentence.known_safes():
                new_clue += 1
                safe_cells += list(sentence.known_safes())
        if len(mine_cells) > 0:
            for cell in mine_cells:
                self.mark_mine(cell)
        if len(safe_cells) > 0:
            for cell in safe_cells:
                self.mark_safe(cell)
        return new_clue

    def infer(self):
        new_clue = 0
        new_knowledge = []
        for i in range(len(self.knowledge)):
            for j in range(i + 1, len(self.knowledge)):
                if self.knowledge[i].cells < self.knowledge[j].cells:
                    tmp = Sentence(self.knowledge[j].cells - self.knowledge[i].cells,
                                   self.knowledge[j].count - self.knowledge[i].count)
                    flag = True
                    for s in self.knowledge:
                        if tmp == s:
                            flag = False
                            break
                    if not flag:
                        continue
                    new_clue += 1
                    new_knowledge.append(tmp)
                elif self.knowledge[j].cells < self.knowledge[i].cells:
                    tmp = Sentence(self.knowledge[i].cells - self.knowledge[j].cells,
                                   self.knowledge[i].count - self.knowledge[j].count)
                    flag = True
                    for s in self.knowledge:
                        if tmp == s:
                            flag = False
                            break
                    if not flag:
                        continue
                    new_clue += 1
                    new_knowledge.append(tmp)
        self.knowledge += new_knowledge
        return new_clue

    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
        self.moves_made.add(cell)
        # 2
        self.mark_safe(cell)
        # 3
        x,y = cell
        neighbors = set()
        for i in [-1, 0, 1]:
            for j in [-1, 0, 1]:
                new_x, new_y = x + i, y + j  # 计算新的坐标
                if 0 <= new_x < self.height and 0 <= new_y < self.width and not (i == 0 and j == 0):
                    neighbors.add((new_x, new_y))  # 添加合适的相邻单元格坐标
        unknown_number = count - len(neighbors & self.mines)
        neighbors = neighbors - self.safes - self.mines
        self.knowledge.append(Sentence(neighbors, unknown_number))
        # 4 # 5
        while 1:
            new_conclude = self.conclude()
            new_infer = self.infer()
            if new_conclude == new_infer == 0:
                break

    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.
        """
        safe_move = self.safes - self.moves_made
        if len(safe_move) == 0:
            return None
        else:
            for element in safe_move:
                return element

    def make_random_move(self):
        """
        Returns a move to make on the Minesweeper board.
        Should choose randomly among cells that:
            6) have not already been chosen, and
            7) are not known to be mines
        """
        all_move = set()
        for i in range(self.width):
            for j in range(self.height):
                all_move.add((i, j))
        for move in all_move:
            if move not in self.moves_made and move not in self.mines:
                return move
        return None