6.871 Assignment 1: Minesweeper February 28, 2005 DUE: March 10, 2005, 9:35AM 1 The Problem This is a knowledge engineering task, i.e., a task involving writing down the knowledge needed to be good at something. In this case the something is the Minesweeper game from Windows. Your job is to create the best set of rules to play minesweeper that you can. We will run all the rule sets against a challenging set of examples and see if we can crown one player the class champion. In doing this assignment you should be sensitive to what it means to specify the knowledge needed to be good at the game. That is, • be aware of how writing rules differs from writing a traditional program, what we referred to in the lectures as ”telling it what to know, not what to do.” • be aware of what goes through your mind as you figure out the rules to begin with, i.e., what the thought processes are in figuring out what you need to know and in stating it explicitly. (Simply put, try to tune in to the process of knowledge engineering.) We have created SmartSweeper, an MSPDE – MineSweeper Player Devel-oper Environment. It will enable you to write, test, and debug a set of rules for the game, using a syntax we call S4. You can see how well you do, and can improve your rules until you’re happy with them. 2 To Begin Play several games of minesweeper. Even if you’re played it before, play it again, but try to be very aware of the patterns you are reacting to and the reasoning you are doing. If you’ve never played it before, you may actually have an advantage, as it’s easier to be conscious of how you’re thinking about the game when it’s still unfamiliar. 13 S4: The SmartSweeper Specification Syntax An S4 file contains a series of rules. A rule has a name (for your convenience), a left hand side (or condition), and a right hand side (the action to take if the left hand side is satisfied). {name LHS => RHS } The placement of the curly brackets with respect to line breaks and the use of the “arrow” (the two character sequence =>) are both crucial – the parser reading this file is not robust. A file of rules is simply one rule after another in the format shown above. 3.1 The Left-Hand Side A left hand side in turn consists of a pattern followed by zero or more conditions. LHS ::= pattern condition* A pattern is an n-by-n array of characters describing a subsection of the board. Legal characters are: M A labe led mine 0-9 Any number - Any square known not to be a mine ? A square whose contents are unknown * Wildcard, matches anything a-z A variable, matches any number. | A spot over the edge of the board (see below for example and further explanation). For example, in the figure below, the top left square is unknown, the three squares adjacent to it contain numbers, while the remaining five s quares are known to be clear. Note that all squares except the one at top left would match a hyphen, as they are known not to be mines. Now consider pattern1: 2---?---1-This pattern matches whenever we find a 3x3 group of tiles in which the middle tile is a 1, and there’s only 1 unknown tile, to the upper left. It will for example match the segment of the board shown previously: It will also match this pattern anywhere on the board: Any number of variables can be used, and they can be referred to in the conditions. A condition is any (Boolean) scheme expression that must hold for the LHS to match. In addition to the variables you used in the LHS pattern, there are several variables whose values are maintained for you by the system: matched-unkns The total number of unknown tiles matched by all wildcards in the pattern matched-mines The total number of marked mines matched by all wildcards in the pattern total-mines-remaining The number of unmarked mines remain-ing anywhere on the board total-non-mines-remaining The number of unmarked non-mine squares remaining on the board Just so it’s clear: at any moment, the total number of unknown squares on the board = total-mines-remaining + total-non-mines-remaining. Here is an example of a more complex LHS, an example that includes a pattern and two conditions: *** *n* *** (= matched-unkns n) (= matched-mines 0) This pattern matches any time there is a numbered tile, bordering a set of wildcards that do not match any mines (because we specified matched-mines=0), 3------and surrounded by a set of unknown squares e qual to the number in the central tile. This applies to the example we saw before, and many others: The | symbol matches tiles that are over the edge of the board. For example, consider LHS 3. ||| |n* |** (= matched-unkns n) (= matched-mines 0) This pattern will match any time there is a number in the far upper-left corner of the board that matches the number of adjacent unknowns. Note that wildcards can also be used to match tiles over the edge of the board. 3.2 The Right-Hand Side On the right-hand-side (RHS), you specify what action to take if the LHS matches. This can be expressed in the form of another pattern, and/or a pre-defined action: RHS ::= PATTERN | ’no-action-pattern’ DEFAULT-ACTION | ’no-default-action’ DEFAULT-ACTION ::= ’mark-unknowns’ | ’click-unknowns’ For example, consider the LHS that we saw b efore: ?---1-A reasonable decision would be to mark the unknown tile as a mine, as expressed in this pattern. M---1-This marks the square as a mine. The outcome is shown here: 4------Putting together the LHS and the RHS, we have Rule 1: {Rule1 ?---1-=> M---1-no-default-action } The final line specifies that no default ac tion will be undertaken. The default