6.871作业1：扫雷 2005年2月28日 截止期2005年3月10日，上午9：35 1问题 这是一个知识工程任务，即包含对一些喜爱的事情写下所需要的知识的任务，这里的事情是 Windows中的扫雷游戏。 你的工作是建立最好的规则集以使玩你可以玩的扫需等戏，我们将执行全部规则集以应 对富有挑战的一组例子并看一看我们是香可以为一个玩家加冕为责冠军。 在敏这个作业当中，你应该对定义喜欢着戏所需要的知识的意思很敏感。即， ·知道如何编写不同于编写传统的程序的规则。讲演中我们提到的“告诉它要知道什么， 不是要做什么”被称为是什么。 ·知道在你找出规则开始时什么经过了你的大脑。即，在找出你必领知道的并显式尊述 出来之中的思想过程是什么。（简单放入，试图在知识工程的过程中进行调节。） 我们已经建立了智俺扫雷程序(SmartSweeper),，一种MSPDE-扫需玩家开发环境. 通过使用我们所谓的S4语法，它佳够使编写，测试和调试本游戏的一组规则，你可以看 到保做的老样，可以改进保的规则直到保锈意为止。 2开始 玩儿种扫雷游戏.即使你以前玩过。请再玩一遍。但要试图知道你在响应的式样和做的推理。 如果你以前从米没有玩过。你实际上可能具有一种优势，因为当还不熟悉时你太容易意识 到保对游戏的思考了， 3S4:SmartSweeper规范语法 一个S4文件包甚一系列规则。一个烧则有一个名字（为了你的使利），一个左边（或条件） 和一个右边（如果左边满足所采取的行动》。 值Be LHS
6.871 作业 1: 扫雷 2005 年 2 月 28 日 截止期: 2005 年 3 月 10 日，上午 9:35 1 问题 这是一个知识工程任务，即包含对一些喜爱的事情写下所需要的知识的任务。这里的事情是 Windows 中的扫雷游戏。 你的工作是建立最好的规则集以便玩你可以玩的扫雷游戏。我们将执行全部规则集以应 对富有挑战的一组例子并看一看我们是否可以为一个玩家加冕为班冠军。 在做这个作业当中，你应该对定义喜欢游戏所需要的知识的意思很敏感。即， •知道如何编写不同于编写传统的程序的规则，讲演中我们提到的“告诉它要知道什么， 不是要做什么”被称为是什么。 •知道在你找出规则开始时什么经过了你的大脑，即，在找出你必须知道的并显式陈述 出来之中的思想过程是什么。(简单放入，试图在知识工程的过程中进行调节。) 我们已经建立了智能扫雷程序（SmartSweeper），一种 MSPDE – 扫雷玩家开发环境。 通过使用我们所谓的 S4 语法，它能够使你编写，测试和调试本游戏的一组规则。你可以看 到你做的怎样，可以改进你的规则直到你满意为止。 2 开始 玩几种扫雷游戏。即使你以前玩过，请再玩一遍，但要试图知道你在响应的式样和做的推理。 如果你以前从来没有玩过，你实际上可能具有一种优势，因为当还不熟悉时你太容易意识 到你对游戏的思考了。 3 S4: SmartSweeper 规范语法 一个 S4 文件包括一系列规则。一个规则有一个名字（为了你的便利），一个左边（或条件） 和一个右边（如果左边满足所采取的行动）。 {name LHS 1
-0 RHS 关于行分割的大括号的放置和管头的使用（两个字符序列心）是重要的一读该文针的 编译器是不稳定的 一个规侧文件简单讲藏是按题以上的格式组成的一个接一个的规则， 3.1左边 左边依次由一个式样组成，后限零个暖多个条作， HS廿-pattern condition* 一个式样是垂n的字符数组、拉述班的一部分合法的字符在： M 一个标记的地雷 小9 任何数字 Any 已知不是地雷的方块 内容未知的方块 通配符，匹配任何内客 -2 一个变量，匹配任何数学 世边的标记（看下例和进一步的解释）。 例如，在下图中，左上方块未知，与其相忽的三个方块包合数字，而其余的五个方块 已知为空.注意，除了左上的一个之外的所有方块都会匹配一个连字号，因为已知如它们不是 地雷。 现在考虑式样1： - -1a 只要我们找到一组3乘3的砖块的时候，这个式样都匹配。其中中问的砖块为一个， 并仅有一个未知砖块位于左上。例如。这将会匹配先前显示的盘部分： 这也将在盘的任何位置匹配这种式样： 2 21 可以使用任意数量的变量，它门可以在条件下使用。一个条件是保持山HS匹配的任何 (布尔)柄式表达式
=> RHS } 关于行分割的大括号的放置和箭头的使用（两个字符序列=>）是重要的－读该文件的 编译器是不稳定的。 一个规则文件简单讲就是按照以上的格式组成的一个接一个的规则。 3.1 左边 左边依次由一个式样组成，后跟零个或多个条件。 LHS ::= pattern condition* 一个式样是 n 乘 n 的字符数组，描述盘的一部分。合法的字符有： M 一个标记的地雷 0-9 任何数字 Any 已知不是地雷的方块 ? 内容未知的方块 * 通配符，匹配任何内容 a-z 一个变量，匹配任何数字。 | 盘边的标记（看下例和进一步的解释）。 例如，在下图中，左上方块未知，与其相邻的三个方块包含数字，而其余的五个方块 已知为空。注意，除了左上的一个之外的所有方块都会匹配一个连字号，因为已知它们不是 地雷。 现在考虑式样 1： ?-- -1- --- 只要我们找到一组 3 乘 3 的砖块的时候，这个式样都匹配，其中中间的砖块为一个 1， 并仅有一个未知砖块位于左上。例如，这将会匹配先前显示的盘部分： 这也将在盘的任何位置匹配这种式样： 可以使用任意数量的变量，它们可以在条件下使用。一个条件是保持 LHS 匹配的任何 （布尔）模式表达式。 2
除了堡在HS式样中用到的变量之外，还在一些变量，其值由系笙为你性控 matched-unkns 由式样中的全事通配符匹配的末知砖块的总 natche小-mines 由式样中的全部通配符匹配的标记为地雷的 总量 total-mines-remaining 盒上任何位置剩会的表标记为地雷的数量 otal-non-m●-代m鲤盆上剩会的未标记为非地雷的方块的数量 只要清楚设行：任何时候，盘上位置方块的总量一total-mines-remaining叶totain-on mines-remaining。 这里是一个更复杂的HS的例子，它包括一个式样和两个条件： 。山由 *n' 香内 (=matched-unkns n) (■matched-mines 0) 这种式样在任何时候都匹配，只要存在一个标记为数字的砖块，边与一组不与任何地 需匹配的通配符（因为我们定文过matched-mines-0)相邻，并按与中心砖块中数量一致 的一组未知方块所包围。这适合我们前面看到的例子，并且还有许多其它的： 1 11 符号匹配盘边界上的砖块。例如，考虑LS3。 1n* 1** (matched-ankns n) (=matched-mines 0) 这种式样在任何时候都将匹配，只要在盘的左上角的近处有一个数字与相忽的未知的 数字相匹配即可。注意，通配符也可以用于匹配盘边界上的砖块。 3.2右边 在右边RHS),如果HS匹配，你可以定义采取什么行动。可以按瓢另一种式样的形式， 和域一种预定义的动作来表达： RHS PATTERN I'no-action-pattern' DEFAULTACTION |'no-default-action' DEFAULTACTION:'mark-anknowns' |'clickun-kn0ws 例如，考虑我们以前看到的HS, -1-
除了你在 LHS 式样中用到的变量之外，还有一些变量，其值由系统为你维护： matched-unkns 由式样中的全部通配符匹配的未知砖块的总 量 matched-mines 由式样中的全部通配符匹配的标记为地雷的 总量 total-mines-remaining 盘上任何位置剩余的未标记为地雷的数量 total-non-mines-remaining 盘上剩余的未标记为非地雷的方块的数量 只要清楚就行：任何时候，盘上位置方块的总量= total-mines-remaining+ totaln-onmines-remaining。 这里是一个更复杂的 LHS 的例子，它包括一个式样和两个条件： *** *n* *** (= matched-unkns n) (= matched-mines 0) 这种式样在任何时候都匹配，只要存在一个标记为数字的砖块，边与一组不与任何地 雷匹配的通配符（因为我们定义过 matched-mines=0）相邻，并被与中心砖块中数量一致 的一组未知方块所包围。这适合我们前面看到的例子，并且还有许多其它的： |符号匹配盘边界上的砖块。例如，考虑 LHS 3。 | | | | n * | * * (= matched-unkns n) (= matched-mines 0) 这种式样在任何时候都将匹配，只要在盘的左上角的远处有一个数字与相邻的未知的 数字相匹配即可。注意，通配符也可以用于匹配盘边界上的砖块。 3.2 右边 在右边 (RHS)，如果 LHS 匹配，你可以定义采取什么行动。可以按照另一种式样的形式， 和/或一种预定义的动作来表达： RHS ::= PATTERN | ’no-action-pattern’ DEFAULTACTION | ’no-default-action’ DEFAULTACTION ::= ’mark-unknowns’ | ’clickun-knowns’ 例如，考虑我们以前看到的 LHS： ?-- -1- --- 3
一种合理的读策可以是标记末知的砖块为一个陆雷，像这种式样中表达的一样。 M- 小 这标记方块为一个地雷。结果如下所示： 1 将山HS和RHS放在一起。我们得到规则1 [Rulel t- - M- -l- No-default-action 终结线定义将会开展非缺省的行动，缺省的行动指的是由一个通配符◆所匹配的全部砖 块，并提供一种简单方法去陈述你想要标记所有这些砖块为地雷，或在它们上点击的事情 为了演示具有缺省行动的一个规，考虑提则2： (Rule2 专由由 *n* 者名西 (仁matched-unkns (mmatched-mines月 =2 no-action-patter mark-unknowns 这个规则指出，如果一个数字口由口个未知方块所包围而并不是地雷的话，那么所有 未知的都是地需。 这个规则没有动作式样。但是执行缺省动作去标记未知的东西，即标记所有未知的方 块都为陆雷。相信你明白了这种规则为什么可以工作（记住一个“未知”方块的定义。） 如果你有不同的情况，那时你认为所有未知的都是空的话，你可以使用k unknowns去点击它们的所有未知的东西。 有时，由于你认为它们是空的，你将需要点击一个或多个特殊的方块：放X在你想点 的RHS式样中
一种合理的决策可以是标记未知的砖块为一个地雷，像这种式样中表达的一样。 M-- -1- --- 这标记方块为一个地雷。结果如下所示： 将 LHS 和 RHS 放在一起，我们得到规则 1： {Rule1 ?— -1- => M-- -1- --- No-default-action } 终结线定义将会开展非缺省的行动，缺省的行动指的是由一个通配符*所匹配的全部砖 块，并提供一种简单方法去陈述你想要标记所有这些砖块为地雷，或在它们上点击的事情。 为了演示具有缺省行动的一个规则，考虑规则 2： {Rule2 *** *n* *** (= matched-unkns n) (= matched-mines 0) => no-action-pattern mark-unknowns } 这个规则指出，如果一个数字 n 由 n 个未知方块所包围而并不是地雷的话，那么所有 未知的都是地雷。 这个规则没有动作式样，但是执行缺省动作去标记未知的东西，即标记所有未知的方 块都为地雷。相信你明白了这种规则为什么可以工作（记住一个“未知”方块的定义。） 如果你有不同的情况，那时你认为所有未知的都是空的话，你可以使用 clickunknowns 去点击它们的所有未知的东西。 有时，由于你认为它们是空的，你将需要点击一个或多个特殊的方块；放 X 在你想点 击的 RHS 式样中。 4
3.3具有无效RHS的规则 如果你的规则动作按属某种方法不改变盘的话，这个程序将进入无限循环：它将会知道左 边是匹配的，然后应用这个动作，当它再一次扫描盘时，它将再一次知道左边匹配，因为没 有改变什么。你可以使用以下描述的调试标志去区分和纠正无限循环。 4 SmartSweeper规则翻译器 SmartSweeper通过你的规侧表进行遍历并试图匹配盘上任何位置的何一个线则（从左上开 始，但郑不是根重要)，如果LHS曾经匹配过。它藏应用RHS,然后返同到烧则表的溪部 和址的左上角，如果没有规则可匹配。SmartSw心cp心r将“猜出”我门确保的方格不是地雷， 当所有非地需的方格点击以后，游戏结束.SSwp总是从上到下，然后从左到右对盘 进行退历， 我们给你一个直达的猜测路径，以便你的系统可以仅仅是为了试，注意，最后即使保全 然没有写烧则，SmartSweepe最终也会猜出所有非地需砖块然后你将会赢。只要你不写点 击一个地需的任柯规则，通过触及一个地需也无法输掉骑戏。可是，会根据你的系统使用的 猜测次数多少给你打分（毕竟。一个基于知识的系统的整体思想是去知道。不是去猜测，） 4.1评分 对于给定的量，你的系统的分数依据以下儿项来计算： ·如果你在分配的时间内成功地完成了盘： C一点击过的事地雷方格的数量 1) G=猜测数量 (2) T=在你完成后剩余的分配给的时何的分数 (3) 分数=C-G+T 4) ·如果点击了一个地雷，或者没有在分配的时间内成功地完成盘： R■剩余的非地雷方格的数量 5) G=猜测数量 (6) 分数=-R-G (7 因为T是确保小于1的一个分数，两个规则集的时问复杂性只有当这些规则集准确地 使用同样的精测数量时才能开始生效。可是，你还会去思考如何使保的规则集更换速。每一 个盘的分配时闻将是0秒钟，对于盘上你将在使用的任柯合理的规则集来说。这应该是如 绰有余的。 这里是Pcn正程序输出的一个例子： 639,96123-0-0:Avg Guesse12.666666 Avg Time:3588.0 这说明获得了6399%的总分；300指的是所有三个盘都成功完成，具有零次失收和零 次超时。每个盘的猜测平均数也指示出来了。平均的用时也一样
3.3 具有无效 RHS 的规则 如果你的规则动作按照某种方法不改变盘的话，这个程序将进入无限循环：它将会知道左 边是匹配的，然后应用这个动作。当它再一次扫描盘时，它将再一次知道左边匹配，因为没 有改变什么。你可以使用以下描述的调试标志去区分和纠正无限循环。 4 SmartSweeper 规则翻译器 SmartSweeper 通过你的规则表进行遍历并试图匹配盘上任何位置的每一个规则（从左上开 始，但那不是很重要）。如果 LHS 曾经匹配过，它就应用 RHS，然后返回到规则表的顶部 和盘的左上角。如果没有规则可匹配，SmartSweeper 将“猜出”我们确保的方格不是地雷。 当所有非地雷的方格点击以后，游戏结束。SmartSweeper 总是从上到下，然后从左到右对盘 进行遍历。 我们给你一个直达的猜测路径，以便你的系统可以仅仅是为了试。注意，最后即使你全 然没有写规则，SmartSweeper 最终也会猜出所有非地雷砖块然后你将会赢。只要你不写点 击一个地雷的任何规则，通过触及一个地雷也无法输掉游戏。可是，会根据你的系统使用的 猜测次数多少给你打分（毕竟，一个基于知识的系统的整体思想是去知道，不是去猜测。） 4.1 评分 对于给定的盘，你的系统的分数依据以下几项来计算： • 如果你在分配的时间内成功地完成了盘： C =点击过的非地雷方格的数量 (1) G = 猜测数量 (2) T = 在你完成后剩余的分配给的时间的分数 (3) 分数 = C − G + T (4) • 如果点击了一个地雷，或者没有在分配的时间内成功地完成盘： R = 剩余的非地雷方格的数量 (5) G =猜测数量 (6) 分数 = −R − G (7) 因为 T 是确保小于 1 的一个分数，两个规则集的时间复杂性只有当这些规则集准确地 使用同样的猜测数量时才能开始生效。可是，你还会去思考如何使你的规则集更快速。每一 个盘的分配时间将是 30 秒钟，对于盘上你将在使用的任何合理的规则集来说，这应该是绰 绰有余的。 这里是 PatternEval 程序输出的一个例子： 639.9612 pts, 3-0-0; Avg Guesses: 12.666666 Avg Time: 388.0 这说明获得了 639.96 的总分；300 指的是所有三个盘都成功完成，具有零次失败和零 次超时。每个盘的猜测平均数也指示出来了，平均的用时也一样。 5
5运行SmartSweeper 你将蓄要具有一台工作着的Java虚拟机的机器米运行SmantSweeper,.可以从a.sun.com上 秋得VM。然后你应该铁得martsweeperjar和j除jm(从作业网站)并将它们做置在 你的类路经中 ·如果你在用Windows机器： 打开D0S窗口并到你故置以上两个文件的目录中去，按以下命令设置类路经： set classpath-%classpath%;smartsweeper.jar:jscheme.jar 这个角令将会增加这两个文件到你已经存在的类路经中，注意你必须准确输入以上给出 的命令。保可以使用以下命令检查并确认类路经是否已经设置好： cche %classpath% 结果度是色含以下文字的一厅 smartsweeper.jar:jxcheme.jar. ·如果你使用的是服务器： setemv CLASSPATH "smartsweeper.jar:jscheme.jar:SCLASSPATH" 在其它机器上，一种快速检验所有是否准答妥当的方法是运行这个命令，它应该输出 一个15乘15的盘，并含有10%的标记为地雷的砖块： java eda.mit.smartsweeper.Board 15 15.1 如果保得到一个像如下所示的加va错误信息 Exception in thread main java.lang.NeClassDefFoundError: edu/mitsmartsweeper/Board 这似平是你的类路经没有设置正确。随时与TA一道来校验。 5.1评估你的规则 使用这个命令来运行你的规则集： java edu.mit.smartsweeper.PatternEval [RULES][DEBUGLEVEL][BOARD] U儿E5定义包含你的悦则的文件：
5 运行 SmartSweeper 你将需要具有一台工作着的 Java 虚拟机的机器来运行 SmartSweeper。可以从 java.sun.com 上 获得 JVM。然后你应该获得 smartsweeper.jar 和 jscheme.jar（从作业网站）并将它们放置在 你的类路经中: • 如果你在用 Windows 机器： 打开 DOS 窗口并到你放置以上两个文件的目录中去，按以下命令设置类路经： set classpath=%classpath%;smartsweeper.jar;jscheme.jar 这个命令将会增加这两个文件到你已经存在的类路经中。注意你必须准确输入以上给出 的命令。你可以使用以下命令检查并确认类路经是否已经设置好： echo %classpath% 结果应该是包含以下文字的一行 smartsweeper.jar;jscheme.jar. • 如果你使用的是服务器： setenv CLASSPATH ‘‘smartsweeper.jar:jscheme.jar:$CLASSPATH’’ 在其它机器上，一种快速检验所有是否准备妥当的方法是运行这个命令，它应该输出 一个 15 乘 15 的盘，并含有 10%的标记为地雷的砖块： java edu.mit.smartsweeper.Board 15 15 .1 如果你得到一个像如下所示的 Java 错误信息 Exception in thread main java.lang.NoClassDefFoundError: edu/mit/smartsweeper/Board 这似乎是你的类路经没有设置正确。随时与 TA 一道来校验。 5.1 评估你的规则 使用这个命令来运行你的规则集： java edu.mit.smartsweeper.PatternEval [RULES] [DEBUGLEVEL] [BOARD] RULES 定义包含你的规则的文件。 6
D拒BUGLEVE.是一个0到6之间的整数，显示你需要帮局的调试级别。 0简单输出你的最终分数 ·输出每一个盆上的分数 2输出规则使用饶计结果。找到爆些规则在进行， ·3输出每一次没有应用你的线则的意。你可以使用这增加你的规则的履盖面。 4输出正在进行的每一条规则。这将标识出引起无限循环的规则来。 ·5显不每次一个规则在进行的盘。 6显示试的每一条规则。包括规则为什么不能匹配。 BOARD是可这的。它定义了一个但含单个盘的文件，或者包含一组盘的一个目录。如 果没有定义这个参数，它就应用线则到一个单个的，随机生成的维数为30乘0的盘，具 有每个砖块是地雷的25%的额率。 5.2输出盘 你可以输出你自己的盘去评估你的规则，Pa©m正d将使用一个随机产生的盘评估你的规则， 但是你可以通过使用一组标准盘比较不同线则集的值.事实上，这正是竞赛怎样将工作下去。 要输出盘，运行以下命令： java edu.mit.smartsweeper.Board [HEIGHT][WIDTH][MINE_PCT] 赋值应该是显而易见的。你可以发送输出到一个文作之中，接着使用那个文件作为 PattemEval的参数： java edu.mit.smartsweeper.Board 15 15.1>testboardl.txt java edumitsmartsweeper.PatternEval myrulesettxt 3 testboardl.txt 注意，大于6价乘6的的对于许多线则集会花费太长时间。为了避免无限循环，对于大 于30乘30的盘无法对你选行评估， 6.如何转变 )你的规则：当你认为你己经获得了你可以产生的最好的规则集时，将包含你的规则的文 件通过em过发给TA。我们将对最好的规则如冕为冠军，还有对作者的适当的表扬和奖励。 一页的分析。我们在早期演讲中所酸的观点之一是具有正确的语言是辅获知识的一个关 健.你对于我们提供给你编写Minesweeper规则的语言的计估是什么？即，这种语言中的什 么概念似乎是强大而有用的，如果有的话。你认为这种语言（和对应的规则翻译器》缺少什 么，它曾经使得编写规则变得比较容易写？
DEBUGLEVEL 是一个 0 到 6 之间的整数，显示你需要帮助的调试级别。 •0 简单输出你的最终分数 •1 输出每一个盘上的分数 •2 输出规则使用统计结果。找到哪些规则在进行。 •3 输出每一次没有应用你的规则的盘。你可以使用这增加你的规则的覆盖面。 •4 输出正在进行的每一条规则。这将标识出引起无限循环的规则来。 •5 显示每次一个规则在进行的盘。 •6 显示试的每一条规则，包括规则为什么不能匹配。 BOARD 是可选的。它定义了一个包含单个盘的文件，或者包含一组盘的一个目录。如 果没有定义这个参数，它就应用规则到一个单个的，随机生成的维数为 30 乘 30 的盘，具 有每个砖块是地雷的 25%的概率。 5.2 输出盘 你可以输出你自己的盘去评估你的规则。PatternEval 将使用一个随机产生的盘评估你的规则， 但是你可以通过使用一组标准盘比较不同规则集的值。事实上，这正是竞赛怎样将工作下去。 要输出盘，运行以下命令： java edu.mit.smartsweeper.Board [HEIGHT] [WIDTH] [MINE_PCT] 赋值应该是显而易见的。你可以发送输出到一个文件之中，接着使用那个文件作为 PatternEval 的参数： java edu.mit.smartsweeper.Board 15 15 .1 > testboard1.txt java edu.mit.smartsweeper.PatternEval myruleset.txt 3 testboard1.txt 注意，大于 60 乘 60 的盘对于许多规则集会花费太长时间。为了避免无限循环，对于大 于 30 乘 30 的盘无法对你进行评估。 6.如何转变 A) 你的规则：当你认为你已经获得了你可以产生的最好的规则集时，将包含你的规则的文 件通过 emial 发给 TA。我们将对最好的规则加冕为冠军，还有对作者的适当的表扬和奖励。 B) 一页的分析。我们在早期演讲中所做的观点之一是具有正确的语言是捕获知识的一个关 键。你对于我们提供给你编写 Minesweeper 规则的语言的评估是什么？即，这种语言中的什 么概念似乎是强大而有用的。如果有的话，你认为这种语言（和对应的规则翻译器）缺少什 么，它曾经使得编写规则变得比较容易写？ 7