课程
命题逻辑
参考离散数学。讲了基本的命题、联结词，真值表法。
利用它实现的 logic 库，可以在代码中表示命题，并且使用联结词连接起来。利用遍历每一个命题，赋值真假，在 knowledge 为真的时候，看 query 是否为真。这样就可以根据 knowledge 来推断 query。
Knowledge Engineering
寻找如何使用命题逻辑来表示问题。举了几个例子。
Inference Rules
代表推理规则。
利用搜索的思想，可以将开始的规则视为初始状态，动作看为推理规则，转移模型代表经过推理后得到的新知识，最后结果检测是是否证明了结论，路径消耗是经过的步数。
介绍了消解法。为了判断 $\alpha$ 是否正确，将 $\lnot \alpha$ 加入 knowledge，经过消解，看会不会得到矛盾式。如果是，那么 $\alpha$ 正确；否则，不正确。
First-Order Logic
最后简单提到了一点一阶逻辑。
Project
Knights
一个很简单的练习题，只需要实现相应的逻辑即可。
为了方便，可以定义一个函数
1
2
3
4
5
6
7
8
|
def person(Knight, Knave, sentence):
return And(Or(
And(Knight, sentence),
And(Knave, Not(sentence)),
), Or(
And(Knight, Not(Knave)),
And(Not(Knight), Knave))
)
|
这个函数保证这个人要么为骑士，要么为骗子，并且在两种情况下，分别满足相应的 sentence。
Minesweeper
介绍
实现扫雷的逻辑，这个项目有点意思。
如果像之前一样，使用每个格子是否有雷来表示，那么会导致判断起来十分复杂。对于一个 8 乘以 8 的地图，总共有 64 个格子，如果这样做，需要耗费 $2^{64}$ 的时间，显然无法接受。于是，考虑更好的表示方法。
一种更好地表示方法，就是用一个集合与相应的数字，来表示这些集合中一共有多少雷。
- 如果集合数量和雷数量一致，就说明都是雷。
- 如果雷的数量为 0，就说明这些都是安全的。
- 如果
set1 包含在 set2 当中，那么 set2 - set1 的雷的数量，就是 set2 雷的数量减去 set1 雷的数量
通过这三条规则，进行不断地推理，就可以推理出所有情况。
实现
一个 sentence 通过一个坐标的集合，以及一个 count 实现，代表这些格子拥有 count 个地雷。需要定义一个知识库 knowledge，其中储存了所有的 sentence 。
这个实现起来还是有点麻烦，尤其是 add_knowledge 函数。这个函数接受一个 cell 输入，也就是一个格子的坐标；接受一个 count 输入，也就是该格子翻开的数字大小。
首先遍历所有附近的节点，然后看如果这个节点没有看过，那就加入；如果之前确定是雷，那就不加入，并且把 count 减去一。然后，将所有附近有效节点，以及 count，作为一个新的规则。
然后，不断进行推理。从当前的知识库中，查看是否存在两个 sentence，其中拥有包含关系。然后，对于这些有关系的式子，进行减法，加入知识库。不断重复这个过程，直到没有新的 sentence 出现。
核心代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
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
new_cells = set()
for dx in range(-1, 2):
for dy in range(-1, 2):
x, y = cell
new_cell = (x + dx, y + dy)
if new_cell == cell:
continue
if self.validate_cell(new_cell):
if self.is_undetermined(new_cell):
new_cells.add(new_cell)
elif new_cell in self.mines:
count -= 1
new_sentence = Sentence(new_cells, count)
self.knowledge.append(new_sentence)
# 4 5
while True:
old_know = deepcopy(self.knowledge)
old_mines = self.mines.copy()
old_safes = self.safes.copy()
self.reason_most()
for sa, sb in self.find_subsets():
if self.construct(sa, sb):
self.knowledge.append(self.construct(sa, sb))
self.reason_most()
if self.mines == old_mines and self.safes == old_safes \
and self.knowledge == old_know:
break
|