This assignment is worth 30 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.
Write a class that can solve 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
Your solver should live in a class Solver
with the following API:
public class Constraint {
int count;
List<Integer> vars;
public Constraint(int count, List<Integer> vars) {
this.count = count; this.vars = vars;
}
}
public class Assignment {
public int var;
public boolean val;
public Assignment(int var, boolean val) {
this.var = var; this.val = val;
}
}
public class Solver {
// Create a Solver for a problem with _n_ variables.
public Solver(int n) { ... }
// Add a constraint to the problem.
public void add(Constraint c) { ... }
// Assign a fixed value to a variable.
public void setVar(int i, boolean v) { ... }
// Deduce that some variable must have a certain value, and assign that value
// to the variable. Return the assignment that was made, or null if
// no deduction was possible.
public Assignment solve() { ... }
}For example, we could use your Solver to solve the constraint satisfaction problem defined above:
Solver s = new Solver(4);
s.add(new Constraint(1, List.of(0, 1)));
s.add(new Constraint(1, List.of(1, 2)));
s.add(new Constraint(1, List.of(2, 3)));
s.add(new Constraint(2, List.of(0, 2, 3)));
while (true) {
Assignment a = s.solve();
if (a == null)
break;
System.out.format("%d = %b\n", a.var, a.val);
}The output might be
2 = true 0 = true 1 = false 3 = false
Suppose that we omit the last constraint from this problem:
Solver s = new Solver(4);
s.add(new Constraint(1, List.of(0, 1)));
s.add(new Constraint(1, List.of(1, 2)));
s.add(new Constraint(1, List.of(2, 3)));
Now it is not possible to deduce the value of any variable, and
s.solve() will return null.
Let us fix the value of one variable:
s.setVar(0, false);
Now the values of the other variables can be deduced. The while
loop above will print output such as
1 = true 2 = false 3 = true
Note that the caller may add new constraints at any time, even after calling solve().
The
repository contains a test program SolverTest.java
that checks all of the cases described above, plus several test cases
corresponding to various situations on small Minesweeper boards. It
would be wise to ensure that your solver passes all these tests
before you apply it to Minesweeper in general.
Use a backtracking search as described in section 6.3 of the Russell & Norvig text (Artificial Intelligence: A Modern Approach).
The backtracking algorithm described there can determine whether a constrant satisfaction problem has any solution. Our problem here is a bit different: we want to determine whether some variable has the same value in every solution. In theory, we could use backtracking to find all solutions, and record which variables have the same value in all of them. But that would be impractically slow, because there could be exponentially many solutions.
So you will need to use a different approach. To try to determine the value of some variable, first choose a variable V using the degree heuristic, described in section 6.3.1. Assume that V is true. Now use a backtracking search to see if you can find any solution for all the other variables. If not, V must be false - and so you have solved one variable. Otherwise, now assume that V is false, and see if you can find any solution for all the other variables. If not, V must be true.
If you can find possible solutions both when V is true and when it is false, then you cannot determine the value of V. In this case you must move to another variable W (again, chosen using the degree heuristic). Assume that W is true or false, and see if you can determine its value by looking for a solution for the other variables. And so on.
If you go through all variables in this manner and cannot prove that any are true or false, you'll need to return null.
As you execute the algorithm above, you'll want to perform forward checking at every step, i.e. infer as many variable values as you can from individual constraints. This is called "maintaining arc consistency" in section 6.3.2 of the text, and will make your solver far more efficient than if you use backtracking alone.
The arcs in this solver are actually hyperarcs since constraints can be non-binary, i.e. on more than two variables. The text describes an arc consistency algorithm AC-3 for binary constraints; you will need to use a similar algorithm that works with the kind of constraints that this solver supports. Keep a queue of constraints that still need to be checked. In a loop, pull a constraint from the queue and check whether it determines the values of one of more variables. If so, set those values, and add all constraints involving those variables to the queue, since you now need to check those constraints as well.
This class may be a bit tricky to write even after you understand the algorithms that you want to use as described in the preceding section. There are many possible ways to structure the code. Here is one possible approach. Feel free to use some, all, or none of these ideas, as you see fit:
As
your solver runs, you will deduce the values of some variables,
while other values will still be unknown. You could have fields
boolean[] hasVal and
boolean[] val,
where hasVal[v]
is true if v currently has
a value, in which case val[v] is
the value.
For each variable, store a list of all constraints that affect it.
Keep a queue of all constraints that currently need to be checked.
You
will sometimes infer the values of many variables at once, but you
can only return one at a time from solve.
So you should keep a
list inferred of
all variables whose values have been assigned but not yet reported
to the caller.
Write
a method infer that
performs forward
checking to infer as many variable values as possible, using an
algorithm similar to AC-3. infer should
loop over the constraint queue, checking each constraint in turn. It
should store inferred values in the val array,
and return a list of variables that were assigned. The caller can
use the returned list to undo the variable assignments if necessary.
If inference reaches a contradiction, infer
should undo all variable
assignments and return null.
The
public method add adds
a constraint to the system. To implement this, add the constraint to
all of its variables, and also add the constraint to the constraint
queue.
The
public method setVar sets
a variable's value. To implement this, first check that the variable
does not already have the opposite value (in which case the
assignment is invalid, and you should throw an exception). Then set
the variable's value in the val array,
and add all the variable's constraints to the constraint queue.
(Also, if the variable is in the inferred list
you should remove it from there, so that it will not be returned
from solve later).
Write
a method backtrack that
is similar to the Backtrack function described in section 6.3 of the
Russell & Norvig text. Unlike the function described there,
however, your method does not need to return an actual assignment;
it can just return true if
any assignment was found, otherwise false.
This method should undo all changes it makes to the vals
array (so the particular
assignment it finds will not actually be available to the caller).
Furthermore,
I recommend breaking this method into two mutually recursive methods
called backtrack and
assign.
assign will
take a variable index v and a boolean value b, and will return true
if it can find any assignment in which v is set to b. To accomplish
this, call setVar to
set v to b, perform forward inference by calling infer,
then call backtrack to
look for more assignments. Like backtrack,
this method should undo any changes it makes.
Write
a method deduce that
attempts to deduce the value of a single variable. If it can make a
deduction, it will call setVal to
store the variable's value in the vals array
and will return an Assignment;
otherwise it will return null. To implement deduce,
first sort all variables in decreasing order by the number of
constraints that affect them (to follow the degree heuristic). Now
loop over the resulting list, and attempt to set each variable to
true or false by
calling assign.
As described in the previous section, if you cannot find a solution
when you set a variable to true, then its value must be false
(and
vice versa).
Finally,
write a method solve that
returns variable assignments. If the inferred
list is non-empty, return
the next assignment in that list. Otherwise, if the constraint queue
is non-empty, call infer to
infer variable values if possible and store them in the inferred
list. If that doesn't yield
any values, call deduce.
As
a possible optimization, you could make backtrack
know
about the sorted array of variables generated by the deduce
method.
That could give you a more efficient way to implement the degree
heuristic in backtrack.
Write an agent that plays Minesweeper using your CSP solver.
Download the Minesweeper code from the
Minesweeper4J
repository. Use the Minesweeper API.
Write your agent by
modifying the dummy implementation MyAgent in
the Minesweeper4J-Playground subdirectory.
To evaluate your agent, run the test() method in Evaluate.java. Your agent should be able to solve randomly generated Minesweeper boards of size 50 x 50 with a mine density of 20% in under 500 ms on average on a typical desktop or laptop computer, asking for an average of fewer than 8 hints while still solving the board safely. For boards of this size and mine density, typically 1-10 hints will be necessary, but occasionally as many as 20.
When a new tile becomes visible, use setVar
to fix its value.
When a number becomes visible, add a constraint.
When solve returns null, ask for
a hint.