This assignment is worth 25 points and has two parts.
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
{
X0,
X2,
X3
} : 2
BooleanCSP csp = new BooleanCSP(4); csp.addConstraint(new Constraint(1, List.of(0, 1))); csp.addConstraint(new Constraint(1, List.of(1, 2))); csp.addConstraint(new Constraint(1, List.of(2, 3))); csp.addConstraint(new Constraint(2, List.of(0, 2, 3)));
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.
Whenever you set a variable's value, call csp.set() so that the variable's constraints will be added to the unchecked queue.
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).
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.
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