COMP3411/9814 Artificial Intelligence
Term 1, 2020
DRAFT
Assignment 1– Prolog and Search
Due: End of week 5
Marks: 20% of final assessment for COMP3411/9814 Artificial Intelligence
Part 1 - Prolog
In this part, you are to write Prolog programs to perform some list and tree operations.
The aim of the assignment is to give you experience with typical Prolog programming
techniques.
At the top of your file, place a comment containing your full name, student number
and assignment name. You may add additional information like the date the program
was completed, etc. if you wish.
At the start of each Prolog predicate, write a comment describing the operation of the
predicate.
Testing Your Code
A significant part of completing this assignment will be testing the code you write to
make sure that it works correctly. To do this, you will need to design test cases that
exercise every part of the code.
You should pay particular attention to "boundary cases", that is, what happens when the
data you are testing with is very small, or in some way special. For example:
• What happens when the list you input has no members, or only one member?
• Does you code work for lists with both even and odd numbers of members?
• Does your code work for negative numbers?
Note: not all of these matter in all cases, so for example with sqrt_table, negative
numbers don't have square roots, so it doesn't make sense to ask whether your code
works with negative numbers.
With each question, some example test data are provided to clarify what the code is
intended to do. You need to design further test data. Testing, and designing test cases, is
part of the total programming task.
It is important to use exactly the names given below for your predicates, otherwise
the automated testing procedure will not be able to find your predicates and you
will lose marks. Even the capitalisation of your predicate names must be as given
below.
Question 1.1: List Processing
Write a predicate sumsq_even(Numbers, Sum) that sums the squares of only the
even numbers in a list of integers.
Example:
?- sumsq_even([1,3,5,2,-4,6,8,-7], Sum).
Sum = 120
Note that it is the element of the list, not its position, that should be tested for oddness.
(The example computes 2*2 + (-4)*(-4) + 6*6 + 8*8). Think carefully about how the
predicate should behave on the empty list — should it fail or is there a reasonable value
that Sum can be bound to?
To decide whether a number is even or odd, you can use the built-in Prolog operator N
mod M, which computes the remainder after dividing the whole number N by the whole
number M. Thus a number N is even if the goal 0 is N mod 2 succeeds. Remember that
arithmetic expressions like X + 1 and N mod M are only evaluated, in Prolog, if they
appear after the is operator. So 0 is N mod 2 works, but N mod 2 is 0 doesn't work.
Question 1.2: List Processing
Write a predicate log_table(NumberList,ResultList) that binds
ResultList to the list of pairs consisting of a number and its log, for each number in
NumberList. For example:
?- log_table([1, 3.7, 5], Result).
Result = [[1, 0.0], [3.7, 1.308332819650179], [5,
1.6094379124341003]].
Note that the Prolog built-in function log computes the natural logarithm, and that it
needs to be evaluated using is to actually compute the log:
?- X is log(3.7).
X = 1.308332819650179.
?- X = log(3.7).
X = log(3.7).
Question 1.3: List Processing
Any list of integers can (uniquely) be broken into "parity runs" where each run is a
(maximal) sequence of consecutive even or odd numbers within the original list. For
example, the list List=[8,0,4,3,7,2,-1,9,9] can be broken into [8,0,4],
[3,7], [2] and [-1,9,9] Write a predicate paruns(List,RunList) that
converts a list of numbers into the corresponding list of parity runs. For example:
?- paruns([8,0,4,3,7,2,-1,9,9], RunList).
RunList = [[8, 0, 4], [3, 7], [2], [-1, 9, 9]]
Note: you can find out how to test if a number is even or odd from the Prolog
Dictionary
Question 1.4: Prolog Terms
Arithmetic expressions can be written in prefix format, e.g 1+2*3 can be written as
add(1, mul(2, 3)). If the operators available are add, sub, mul, div, write a
Prolog program, eval(Expr, Val), that will evaluate an expression, e.g.
?- eval(add(1, mul(2, 3)), V).
V = 7
?- eval(div(add(1, mul(2, 3)), 2), V).
V = 3.5
Testing
This assignment will be marked on functionality in the first instance. However, you
should always adhere to good programming practices in regard to structure, style and
comments, as described in the Prolog Dictionary. Submissions which score very low in
the automarking will be examined by a human marker, and may be awarded a few
marks, provided the code is readable.
Your code must work under the version of SWI Prolog used on the Linux machines in
the UNSW School of Computer Science and Engineering. If you develop your code on
any other platform, it is your responsibility to re-test and, if necessary, correct your code
when you transfer it to a CSE Linux machine prior to submission.
Your code will be run on a few simple tests when you submit. So, it is a good idea to
submit early and often so that potential problems with your code can be detected early.
You will be notified at submission time if your code produces any compiler warnings.
Please ensure that your final submission does not produce any such warnings
(otherwise, marks will be deducted).
Part 2 - Search
Question 1: Search Algorithms for the 15-Puzzle
In this question you will construct a table showing the number of states expanded when
the 15-puzzle is solved, from various starting positions, using four different searches:
(i) Uniform Cost Search (with Dijkstra’s Algorithm)
(ii) Iterative Deepening Search
(iii) A*Search (using the Manhattan Distance heuristic)
(iv) Iterative Deepening A* Search
Go to theWebCMS. Under “Assignments” you will find Prolog Search Code
“prolog_search.zip”. Unzip the file and change directory to prolog search, e.g.
unzip prolog_search.zip
cd prolog_search
Start prolog and load puzzle15.pl and ucsdijkstra.pl by typing
[puzzle15].
[ucsdijkstra]. 

Then invoke the search for the specified start10 position by typing
start10(Pos),solve(Pos,Sol,G,N),showsol(Sol).
When the answer comes back, just hit Enter/Return. This version of Uniform Cost
Search (UCS) uses Dijkstra’s algorithm which is memory efficient, but is designed to
return only one answer. Note that the length of the path is returned as G, and the total
number of states expanded during the search is returned as N.
a) Draw up a table with four rows and five columns. Label the rows as UCS, IDS, A*
and IDA*, and the columns as start10, start12, start20, start30
and start40. Run each of the following algorithms on each of the 5 start states:

(i)[ucsdijkstra]
(ii)[ideepsearch]
(iii)[astar]
(iv)[idastar]
In each case, record in your table the number of nodes generated during the search.
If the algorithm runs out of memory, just write “Mem” in your table. If the code
runs for five minutes without producing out- put, terminate the process by typing
Control-C and then “a”, and write “Time” in your table. Note that you will need to
re-start prolog each time you switch to a different search.
b) Briefly discuss the efficiency of these four algorithms (including both time and
memory usage).
Question 2: Heuristic Path Search for 15-Puzzle
In this question you will be exploring an Iterative Deepening version of the Heuristic
Path Search algorithm discussed in the Week 3 Tutorial. Draw up a table in the
following format:


The top row of the table has been filled in for you (to save you from running some
rather long computations).
In each case, record in your table the number of nodes generated dur-
ing the search. If the algorithm runs out of memory, just write “Mem”
in your table. If the code runs for five minutes without producing out-
put, terminate the process by typing Control-C and then “a”, and write
“Time” in your table. Note that you will need to re-start prolog each
time you switch to a different search.
(b) Briefly discuss the efficiency of these four algorithms (including both time
and memory usage).
Question 2: Heuristic Path Search for 15-Puzzle (2 marks)
In this question you will be exploring an Iterative Deepening version of the
Heuristic Path Search algorithm discussed in the Week 4 Tutorial. Draw up
a table in the following format:
start50 start60 start64
IDA∗ 50 14642512 60 321252368 64 1209086782
1.2
1.4
1.6
Greedy
The top row of the table has been filled in for you (to save you from running
some rather long computations).
(a) Run [greedy] for start50, start60 and start64, and record the values
returned for G and N in the last row of your table (using the Manhattan
Distance heuristic defined in puzzle15.pl).
(b) Now copy idastar.pl to a new file heuristic.pl and modify the code of
this new file so that it uses an Iterative Deepening version of the Heuristic
Path Search algorithm discussed in the Week 4 Tutorial Exercise, with
w = 1.2 .
In your submitted document, briefly show the section of code that was
changed, and the replacement code.
(c) Run [heuristic] on start50, start60 and start64 and record the
values of G and N in your table. Now modify your code so that the value
of w is 1.4, 1.6 ; in each case, run the algorithm on the same three start
states and record the values of G and N in your table.
(d) Briefly discuss the tradeoff between speed and quality of solution for
these five algorithms.
2
(a) Run [greedy] forstart50, start60 and start64, and record the values returned for G
and N in the last row of your table (using the Manhattan Distance heuristic defined
in puzzle15.pl).
(b) Now copy idastar.pl to a new file heuristic.pl and modify the code of this new file so
that it uses an Iterative Deepening version of the Heuristic Path Search algorithm
discussed in the Weak 2 Tutorial Exercise, with w = 1.2 .
In your submitted document, briefly show the section of code that was changed, and
the replacement code.
(c) Run [heuristic] on start50, start60 and start64 and record the values of G and N in
your table. Now modify your code so that the value of w is 1.4, 1.6 ; in each case,
run the algorithm on the same three start states and record the values of G and N in
your table.
(d) Briefly discuss the tradeoff between speed and quality of solution for these five
algorithms.
Submitting your assignment
Your submission will consist of two files: the one file should contain all of your Prolog
programs; the second file should contain the results of your search experiments in part
2.
*** INSTRUCTIONS ON HOW TO DO THIS TO FOLLOW ***
Please make sure your code works on CSE's Linux machines and generates no
warnings. Remove all test code from your submission. Make sure you have named
your predicates correctly.
You can submit as many times as you like - later submissions will overwrite earlier
ones. Once give has been enabled, you can check that your submission has been
received by using one of these commands:
The submission deadline is Friday 20 March, 10:00 pm.
10% penalty will be applied to the (maximum) mark for every 24 hours late after the
deadline.
Questions relating to the project can be posted to the forums on the course Web site.
If you have a question that has not already been answered on the forum, you can email
it to [email protected]
Plagiarism Policy
Group submissions are not allowed. Your program must be entirely your own work.
Plagiarism detection software will be used to compare all submissions pairwise
(including submissions for any similar projects from previous years) and serious
penalties will be applied, particularly in the case of repeat offences.
DO NOT COPY FROM OTHERS. DO NOT ALLOW ANYONE TO SEE YOUR
CODE
Please refer to the UNSW Policy on Academic Honesty and Plagiarism if you require
further clarification on this matter.