Before we get started, allow me to set some guidelines for turning in
homework assignments. You've had ample time to get your computing
accounts sorted out and figure out how the handin program works, so
beginning with this assignment we won't be accepting submissions that
are emailed to us unless handin crashes.
Next, if you're working with someone else, the two of you should submit
only one set of solutions. Make sure the names, student numbers, and
email addresses of both contributors are at the top of the file. It
doesn't matter which account you submit from as long as the information
for both contributors is included. But don't submit duplicate solution
sets from two different accounts...it just makes more work for your TAs.
Thanks.
When your TAs are marking their homework, they're using Linux boxes to
look at what you've submitted. So if you write the assignment in an
environment other than Linux, please try to format what you write in
such a way that it is easily readable in Linux. If you need additional
guidance on this issue, be sure to talk to one of your TAs about it.
There may be more guidelines forthcoming from your TAs, so stay tuned.
Now let the fun begin.
Below you'll find the CILOG knowledge base and predicates for the
8-tile puzzle that we've been using as an example in class.
This CILOG code will be the basis for the learning and discovery
opportunities which follow.
neighbors([2,8,3,1,0,4,7,6,5],[[2,8,3,0,1,4,7,6,5],[2,0,3,1,8,4,7,6,5],[2,8,3,1,4,0,7,6,5]]).
neighbors([2,8,3,0,1,4,7,6,5],[[0,8,3,2,1,4,7,6,5],[2,8,3,7,1,4,0,6,5]]).
neighbors([2,0,3,1,8,4,7,6,5],[[0,2,3,1,8,4,7,6,5],[2,3,0,1,8,4,7,6,5]]).
neighbors([2,8,3,1,4,0,7,6,5],[[2,8,0,1,4,3,7,6,5],[2,8,3,1,4,5,7,6,0]]).
neighbors([0,8,3,2,1,4,7,6,5],[[8,0,3,2,1,4,7,6,5]]).
neighbors([2,8,3,7,1,4,0,6,5],[[2,8,3,7,1,4,6,0,5]]).
neighbors([0,2,3,1,8,4,7,6,5],[[1,2,3,0,8,4,7,6,5]]).
neighbors([2,3,0,1,8,4,7,6,5],[[2,3,4,1,8,0,7,6,5]]).
neighbors([2,8,0,1,4,3,7,6,5],[[2,0,8,1,4,3,7,6,5]]).
neighbors([2,8,3,1,4,5,7,6,0],[[2,8,3,1,4,5,7,0,6]]).
neighbors([8,0,3,2,1,4,7,6,5],[[8,3,0,2,1,4,7,6,5],[8,1,3,2,0,4,7,6,5]]).
neighbors([2,8,3,7,1,4,6,0,5],[[2,8,3,7,0,4,6,1,5],[2,8,3,7,1,4,6,5,0]]).
neighbors([1,2,3,0,8,4,7,6,5],[[1,2,3,8,0,4,7,6,5],[1,2,3,7,8,4,0,6,5]]).
neighbors([2,3,4,1,8,0,7,6,5],[[2,3,4,1,0,8,7,6,5],[2,3,4,1,8,5,7,6,0]]).
neighbors([2,0,8,1,4,3,7,6,5],[[0,2,8,1,4,3,7,6,5],[2,4,8,1,0,3,7,6,5]]).
neighbors([2,8,3,1,4,5,7,0,6],[[2,8,3,1,4,5,0,7,6],[2,8,3,1,0,5,7,4,6]]).
neighbors([8,3,0,2,1,4,7,6,5],[]).
neighbors([8,1,3,2,0,4,7,6,5],[]).
neighbors([2,8,3,7,0,4,6,1,5],[]).
neighbors([2,8,3,7,1,4,6,5,0],[]).
neighbors([1,2,3,8,0,4,7,6,5],[]).
neighbors([1,2,3,7,8,4,0,6,5],[]).
neighbors([2,3,4,1,0,8,7,6,5],[]).
neighbors([2,3,4,1,8,5,7,6,0],[]).
neighbors([0,2,8,1,4,3,7,6,5],[]).
neighbors([2,4,8,1,0,3,7,6,5],[]).
neighbors([2,8,3,1,4,5,0,7,6],[]).
neighbors([2,8,3,1,0,5,7,4,6],[]).
append([],Z,Z).
append([A|X],Y,[A|Z]) <- append(X,Y,Z).
is_goal([1,2,3,8,0,4,7,6,5]).
search(F0) <- choose(Node,F0,F1) &
neighbors(Node,NN) &
add_to_frontier(NN,F1,F2) &
search(F2).
search(F0) <- choose(Node,F0,F1) & is_goal(Node).
choose(N,[N|Flist],Flist).
add_to_frontier(Nodelist,Flist1,Flist2) <- append(Flist1,Nodelist,Flist2).
-------------------------------------------------------------------
Problem 1 (10 points): Load the code above into CILOG and run it
with the query
cilog: ask search([[2,8,3,1,0,4,7,6,5]]).
(Remember that the argument to the search predicate is a list of
nodes on the frontier and each node on the list is itself a list,
hence the double square brackets.)
Turn in the results of this query (there won't be much) so your
TA knows that you got this to work. Then, using all those new words
you've learned recently to talk about search, describe what kind of
search is going on here. How can you tell? (Hint: It won't be
obvious from the results of your query.)
-------------------------------------------------------------------
Problem 2 (10 points): This problem will be a little bit more
challenging than the previous one. Below are the arc costs for
our sample 8-tile puzzle. For example, the very first relation
indicates that the cost of going from [2,8,3,1,0,4,7,6,5] to
[2,8,3,0,1,4,7,6,5] is 2 (because Bubba had to move a tile
sideways, remember?).
cost([2,8,3,1,0,4,7,6,5],[2,8,3,0,1,4,7,6,5],2).
cost([2,8,3,1,0,4,7,6,5],[2,0,3,1,8,4,7,6,5],1).
cost([2,8,3,1,0,4,7,6,5],[2,8,3,1,4,0,7,6,5],2).
cost([2,8,3,0,1,4,7,6,5],[0,8,3,2,1,4,7,6,5],1).
cost([2,8,3,0,1,4,7,6,5],[2,8,3,7,1,4,0,6,5],3).
cost([2,0,3,1,8,4,7,6,5],[0,2,3,1,8,4,7,6,5],2).
cost([2,0,3,1,8,4,7,6,5],[2,3,0,1,8,4,7,6,5],2).
cost([2,8,3,1,4,0,7,6,5],[2,8,0,1,4,3,7,6,5],1).
cost([2,8,3,1,4,0,7,6,5],[2,8,3,1,4,5,7,6,0],3).
cost([0,8,3,2,1,4,7,6,5],[8,0,3,2,1,4,7,6,5],2).
cost([2,8,3,7,1,4,0,6,5],[2,8,3,7,1,4,6,0,5],2).
cost([0,2,3,1,8,4,7,6,5],[1,2,3,0,8,4,7,6,5],3).
cost([2,3,0,1,8,4,7,6,5],[2,3,4,1,8,0,7,6,5],3).
cost([2,8,0,1,4,3,7,6,5],[2,0,8,1,4,3,7,6,5],2).
cost([2,8,3,1,4,5,7,6,0],[2,8,3,1,4,5,7,0,6],2).
cost([8,0,3,2,1,4,7,6,5],[8,3,0,2,1,4,7,6,5],2).
cost([8,0,3,2,1,4,7,6,5],[8,1,3,2,0,4,7,6,5],3).
cost([2,8,3,7,1,4,6,0,5],[2,8,3,7,0,4,6,1,5],1).
cost([2,8,3,7,1,4,6,0,5],[2,8,3,7,1,4,6,5,0],2).
cost([1,2,3,0,8,4,7,6,5],[1,2,3,8,0,4,7,6,5],2).
cost([1,2,3,0,8,4,7,6,5],[1,2,3,7,8,4,0,6,5],3).
cost([2,3,4,1,8,0,7,6,5],[2,3,4,1,0,8,7,6,5],2).
cost([2,3,4,1,8,0,7,6,5],[2,3,4,1,8,5,7,6,0],3).
cost([2,0,8,1,4,3,7,6,5],[0,2,8,1,4,3,7,6,5],2).
cost([2,0,8,1,4,3,7,6,5],[2,4,8,1,0,3,7,6,5],3).
cost([2,8,3,1,4,5,7,0,6],[2,8,3,1,4,5,0,7,6],2).
cost([2,8,3,1,4,5,7,0,6],[2,8,3,1,0,5,7,4,6],1).
Add this cost information to the knowledge base, and then
make the necessary modifications to the CILOG search code
so that it performs a lowest-cost-first search in solving
the 8-tile puzzle. Call your search predicate "costsearch"
so we can distinguish it from the the generic search
predicate. Turn in a little transcript of your
interaction with CILOG to show your grader that it all
works. Also, turn in a copy of your revised program
so that your grader can test it with a different knowledge
base.
-------------------------------------------------------------------
Problem 3 (20 points): Now ignore all that cost information...
heck, you can just delete it all from your knowledge base.
You're now going to implement a simple heuristic search.
Use CILOG to implement a heuristic function that counts the
number of tiles out of place (including the "blank tile"), as
discussed in class, and then modify the CILOG search code to
use this heuristic knowledge to perform a best-first search
in solving the 8-tile puzzle. Just as a reminder, we assumed in
class that a board with fewer tiles out of place is closer to the
goal than one with more tiles out of place. That may not be
correct, but it's sufficient for the purposes of this exercise.
Call your search predicate "bestsearch" this time to avoid confusion.
Again, turn in a little transcript of your interaction with CILOG to
show your grader that it all works. And just like before, turn in a
copy of your revised program so that your grader can test it with a
different knowledge base and maybe even a different evaluation function.
Oh, by the way, call your evaluation function (or more accurately,
your evaluation predicate) "h", as in h(n). But your predicate should
take two arguments and work like this:
h(Board,N) is true if N is the number of tiles in Board (including
the blank tile) that are out of place.
-------------------------------------------------------------------
Problem 4 (10 points): That was fun, wasn't it? Now take the modified
CILOG code from problem 3 that performs a best-first search and modify
it even more so that it returns a path from the start node to the goal
(but in reverse order) instead of just a yes/no answer.
Your search predicate, which you'll name "pathsearch", should work just
like we specified in class. That is,
pathsearch(F,Path) is true if Path is a list of nodes from the start
node to the goal node (but in reverse order) that passes through one
of the nodes on the frontier F. And keep in mind that a node on
the frontier is represented by a list of nodes that represent a path
from the start node to that node on the frontier (yes, in reverse order).
Go back to the powerpoint slides or the textbook (pages 123-124)
to refresh your memory about what path search does.
Finally, one last time, turn in a little
transcript of your interaction with CILOG as well as a copy of your
revised program (the whole program, not just the modified parts).
Last revised: October 22, 2004