## Assignment 5: Minesweeper

This assignment is worth 25 points and has two parts.

## 1. CSP Solver (15 pts)

First clone (or update your existing copy of) the ai_1 repository. Look in the `csp``/src` subdirectory, which has source files for the classes described in this section.

Consider constraint satisfaction problems of the following nature:

• There is a set of variables X = {X0, ..., Xn-1}.

• All variables are boolean: their domain is { true, false }.

• There is a set of constraints Ci. Each constraint consists of

• a subset of variables that participate in the constraint

• an integer k indicating that exactly k of these variables are true

For example, here is one such problem:

• There are 4 variables X0 ... X3.

• There are 4 constraints:

• { X0, X1 } : 1

• { X1, X2 } : 1

• { X2, X3 } : 1

• { X0, X2, X3 } : 2

It's not difficult to see that this problem has a unique solution:

• X0 = true, X1 = false, X2 = true, X3 = false

In this part of the assignment you will write a solver for constraint satisfaction problems such as this.

The class `Constraint` (in csp/Constraint.java) represents a single constraint:

```public class Constraint {
public int count;
public List<Integer> vars;
}```

The class `BooleanCSP` (in csp/BooleanCSP.java) represents a constraint satisfaction problem (CSP):

```public class BooleanCSP {
public int numVars;
public Boolean[] value;
public Set<Constraint> constraints;

public ArrayList<Set<Constraint>> varConstraints;
public Queue<Constraint> unchecked;
…
}```

The first three fields define a CSP:

• `numVars` is the number of variables in the problem, which are numbered from 0 to (numVars – 1).

• `value[v]` is initially null for all variables v, meaning that their values are unknown. As your solver runs and deduces values for variables, it will store them here. When it backtracks in its search, values will become null again. (Recall that in Java the type ```Boolean ```can hold either true, false, or null.)

• `constraints` is the current set of constraints. Constraints may be added over time (which will be useful in solving Minesweeper, where new information is discovered as the game progresses).

The remaining two fields will be useful in your solver:

• `varConstraints` is an array that maps each variable number to a set of all constraints that affect it.

• `unchecked` is a Queue that contains all constraints that have not yet been forward checked, i.e. constraints from which you may be able to immediately infer variable values.

The BooleanCSP class contains several useful methods including these:

• `void```` addConstraint(Constraint c)``` – add a new constraint to the system (and to the unchecked queue)

• `void```` set(````int```` var, ````boolean```` val)``` set a variable's value (and add the variable's constraints to the unchecked queue)

Write a class `Solver` with the following API:

```public class Solver {
public Solver();

public List<Integer> forwardCheck(BooleanCSP csp) { … }

public List<Integer> solve(BooleanCSP csp) { … }

public int inferVar(BooleanCSP csp) { … }
}```

The methods above should behave as follows:

• forwardCheck() should infer as many variable values as possible by performing constraint propagation as described in section 6.2 of the Russell & Norvig textbook ("Constraint Propagation: Inference in CSPs"). Its implementation will be loosely similar to the AC-3 algorithm described in the text. However, AC-3 handles binary constraints, and so forwardCheck() will infer variable values differently because the constraints in a BooleanCSP are of a different nature.

Specifically, this method should check the queue of constraints in `csp.unchecked` to see if it can infer any variable values from any single constraint. As new variable values are discovered, those variables' constraints will join the queue to be checked in turn. The constraint propagation process will complete when the queue is empty. This method should return a list of variables whose values were inferred. If it realizes that some constraint can not be satisfied, that means that a contradiction has been reached and the entire system is unsolvable. In this case, forwardCheck() should reset any variables that it has set and return null.

As an example of how constraint propagation might work, suppose that the queue initially contains three constraints: 1 of {0 1 2}, 1 of {2 3}, and 0 of {3}. And suppose that at the beginning no values are known, i.e. every variable's domain is {true, false}. You will first remove '1 of {0 1 2}' from the queue and examine it. You can't infer any values from this constraint alone, so you will ignore it and move on. You'll next look at '1 of {2 3}'. Again, you can't infer anything from this constraint in isolation, so it simply falls out of the queue.

Now the queue contains only '0 of {3}'. From looking at this constraint, you immediately know that 3 = false. You now re‑add '1 of {2 3}' to the queue, since it is a constraint that involves variable 3. Now the queue contains only '1 of {2 3}'. From looking at this constraint, you now know that 2 = true since exactly 1 of {2 3} is true but 3 is false. So you will now re‑add '1 of {0 1 2}' to the queue, since it is a constraint that involves variable 2 which you just inferred.

Now you'll examine '1 of {0 1 2}'. Since 2 is known to be true, this constraint now tells you that 0 = false and 1 = false. Now the queue is empty. You were able to infer the values of all variables through constraint propagation alone - you didn't need to perform any backtracking.

• solve() should attempt to find any solution to the CSP by performing a backtracking search as described in section 6.3 "Backtracking Search for CSPs". If it finds a solution, it should set values for all variables in the solution and return a list of those variables. If it determines that the system is unsolvable, it should reset any variables that it has set and return null.

For selecting the next variable to try in the backtracking search (i.e. the Select-Unasssigned-Variable() step in the pseudocode in the text), I recommend using the degree heuristic described in section 6.3.1 "Variable and value ordering".

During the backtracking search, for efficiency you should perform forward checking as described in section 6.3.2 "Interleaving search and inference" in the text. (This is the Inference() step in the backtracking pseudocode). Specifically, you will want to use the technique that the textbook calls maintaining arc consistency, i.e. performing full constraint propagation after you select a variable value to try. You can do this by calling the forwardCheck() method that you wrote before.

For efficiency, solve() should ignore any variables that do not belong to any constraint (these variables may have any value, of course).

• inferVar() should attempt to infer the value of any single variable in the CSP using a proof by contradiction, which works as follows. For each variable in turn, the method should set the variable's value to true and then call solve() to test whether the resulting system has any solution. If the system is unsolvable, the method can infer that the variable must be false in any solution. Otherwise, it can try setting the variable to false; if that yields an unsolvable system, the method will infer that the variable must be true. As soon as a value is inferred for any variable, the method should stop the search process and return the index of that variable. If no value can be inferred for any variable, return -1. This method should not set values for any variables other than the variable that is returned (if any).

In this method, I recommend trying all variables in descending order of the number of constraints they belong to (this is the degree heuristic again). Do not bother to try to infer values for values with no constraints; that will never succeed.

To illustrate the use of these methods, let's create a `BooleanCSP` that represents the four-variable constraint satisfaction problem that we saw above:

• { X0, X1 } : 1

• { X1, X2 } : 1

• { X2, X3 } : 1

• ```{ X````0````, X````2````, X````3```` ````} : 2`

```BooleanCSP csp = new BooleanCSP(4);

Let's attempt to infer values by constraint propagation alone:

```Solver solver = new Solver();
List<Integer> vars = solver.forwardCheck(csp);

out.printf("inferred %d variables\n", vars.size());```

This will print

`inferred 0 variables`

That's because no values can be inferred from any individual constraint. In other words, the system is locally consistent with respect to individual constraints.

So if we'd like to infer a variable value, we need to use a more powerful tool:

```int var = solver.inferVar(csp);
out.printf("var = %d, value = %b\n", var, csp.value[var]);```

This might print

`var = 2, value = true`

Now that we have inferred one value, constraint propagation can easily find the rest:

```        List<Integer> vars2 = solver.forwardCheck(csp);
out.printf("inferred %d variables\n", vars2.size());
for (int v = 0 ; v < csp.numVars ; ++v)
out.printf("var = %d, value = %b\n", v, csp.value[v]);        ```

This will print

```inferred 3 variables
var = 0, value = true
var = 1, value = false
var = 2, value = true
var = 3, value = false```

As an alternative to calling forwardCheck() and inferVar(), we could have called solve(), which would find this same solution. However, note an important difference between these approaches. solve() searches for any solution to a CSP and returns it. By contrast, forwardCheck() and inferVar() infer variable values that must be true in every solution of a CSP. And so our calls to forwardCheck() and inferVar() have proven that the above solution is unique.

### hints

• Whenever you set a variable's value, call csp.set() so that the variable's constraints will be added to the unchecked queue.

### testing

It would be wise to test your CSP solver before you attempt to apply it to Minesweeper. The script `csp_test` will run the tests in SolverTest.java, which will test your solver methods forwardCheck(), solve(), and inferVar() on a number of constraint satisfaction problems (including some that were derived from Minesweeper game boards).

## 2. Minesweeper (10 pts)

Write an agent that plays Minesweeper. As always in this tutorial you may use any technique you like, but probably it will be easiest to use the CSP solver you just wrote. :)

Download the Minesweeper code from the Minesweeper4J repository. Use the Minesweeper API. Write your agent by modifying the dummy implementation `src/MyAgent.java`.

To evaluate your agent, run Minesweeper with the -sim option, e.g.

`\$ ./minesweeper MyAgent -sim 20`

Your agent should be able to solve randomly generated Minesweeper boards of size 50 x 50 with the default mine density of 20% in under 300 ms on average on a typical desktop or laptop computer, asking for an average of fewer than 7 hints while still solving the board safely. (The option `-size 50` will select a board of this size.) For boards of this size and mine density, typically 1-10 hints will be necessary, but occasionally as many as 20.

### hints

• Create a `BooleanCSP` with one variable for each square on the board.

• The first time you see any free tile, call csp.set() to set its value to false, since you know there is no mine there. Also, if the tile has a non-zero number, create a `Constraint` representing the mines around it and call addConstraint() to add it to your CSP.

• To infer variable values, first try forward checking. If that returns a set of variable assignments, remember them so that you can return one on each subsequent call to thinkImpl(). If forward checking fails, try calling inferVar() which is more powerful but slower. Remember that after inferVar() succeeds, forward checking can often find more variable values quickly, using the newly inferred value as a starting point. If inferVar() fails, you will have to ask for a hint.

• First test your solver on tiny boards (e.g. 3 x 3 or 4 x 4). Once you are confident it works there, proceed gradually to larger boards in your testing.

• Here are the minimum numbers of hints required for the first 10 random seeds on several small board sizes. If your solver asks for more hints than these, it is not inferring as much as it could.

```\$ ./minesweeper MyAgent -size 3 -sim 10
board size is 3 x 3, 2 mines
seed 0: solved in 2 ms, hints = 1
seed 1: solved in 2 ms, hints = 1
seed 2: solved in 2 ms, hints = 4
seed 3: solved in 1 ms, hints = 3
seed 4: solved in 0 ms, hints = 1
seed 5: solved in 0 ms, hints = 2
seed 6: solved in 0 ms, hints = 2
seed 7: solved in 0 ms, hints = 1
seed 8: solved in 0 ms, hints = 2
seed 9: solved in 0 ms, hints = 1
average over 10 runs: time = 0 ms, hints = 1.8

\$ ./minesweeper MyAgent -size 5 -sim 10
board size is 5 x 5, 5 mines
seed 0: solved in 4 ms, hints = 1
seed 1: solved in 1 ms, hints = 1
seed 2: solved in 3 ms, hints = 2
seed 3: solved in 1 ms, hints = 1
seed 4: solved in 1 ms, hints = 3
seed 5: solved in 0 ms, hints = 1
seed 6: solved in 1 ms, hints = 1
seed 7: solved in 0 ms, hints = 1
seed 8: solved in 2 ms, hints = 3
seed 9: solved in 2 ms, hints = 3
average over 10 runs: time = 1 ms, hints = 1.7

\$ ./minesweeper MyAgent -size 8 -sim 10
board size is 8 x 8, 13 mines
seed 0: solved in 7 ms, hints = 2
seed 1: solved in 11 ms, hints = 5
seed 2: solved in 3 ms, hints = 3
seed 3: solved in 0 ms, hints = 2
seed 4: solved in 1 ms, hints = 2
seed 5: solved in 6 ms, hints = 2
seed 6: solved in 1 ms, hints = 4
seed 7: solved in 5 ms, hints = 4
seed 8: solved in 0 ms, hints = 2
seed 9: solved in 2 ms, hints = 3
average over 10 runs: time = 3 ms, hints = 2.9```