IT470: Artificial and Computational Intelligence
1
CSE2AIF – Artificial Intelligence Fundamentals
2021 Individual Assignment 2
Due Friday 15 October 2021, 10:00am
This assignment is to be done individually, and contributes 20% of your final mark for this subject.
The submission date is Friday 15th October 10:00am. There are five questions, each worth 15 marks.
You should attempt all questions.
Submission is electronic and via the LMS. Details of what to submit are provided below each question.
Make sure that you follow the directions carefully and that the files are named exactly as specified in
the instructions. Do NOT zip your files or use any other archiving process — submit each of the files
individually.
The assignment is to be done individually. You must not collude with other students in any way, and
you must not outsource your work to any other party. For information on plagiarism, see the La Trobe
University policy on academic misconduct at http://www.latrobe.edu.au/students/academic-integrity.
Penalties are applied to late assignments (5% of total possible marks for that task is deducted per day,
accepted up to 5 days after the due date only). An assignment submitted more than five working days
after the due date will not be accepted. Delays caused by computer downtime cannot be accepted as a
valid reason for a late submission without penalty. You must plan your work to allow for both
scheduled and unscheduled downtime.
http://www.latrobe.edu.au/students/academic-integrity
2
Question 1 – A heuristic for Connect-4 (15 marks)
Background
Connect-4 is a two-person game played on a board that has seven columns, with six spaces in each
column. The board is initially empty. Two players take turns dropping one piece (red or yellow in the
diagram below, but X or O in our game) in a column. The piece falls into the lowest unoccupied row.
A player cannot place a piece in a column if the top-most row of that column already has a piece in it.
The first player to get four of their counters in a line (either horizontally, vertically, or diagonally) is
the winner.
Your task for this question is to write a heuristic for the two-player game Connect-4.
You have been provided with the following two files for this problem:
• minimax.lisp, which contains lisp code for the minimax algorithm, and
• connect-4.lisp, which contains a working LISP implementation of the Connect-4 game.
The following LISP interaction show you how to play a game. Try it.
[1]> (load ‘minimax)
;; Loading file C:\CSE2AIF\minimax.lisp …
;; Loaded file C:\CSE2AIF\minimax.lisp
T
[2]> (load connect-4)
;; Loading file C:\CSE2AIF\connect-4.lisp …
;; Loaded file C:\CSE2AIF\connect-4.lisp
T
[3]> (play)
The program plays poorly because it has a poor-quality heuristic. The function static, which
evaluates a position from the point of view of a particular player, is currently defined as follows:
(defun static (board player) 0)
This means that each board configuration receives exactly the same evaluation of 0.
Your task for this question is to develop and implement a better heuristic for the Connect-4 game.
3
The heuristic
You will be required to write various LISP functions which will be used to define the heuristic. The
heuristic is described here, and a suggested approach for the coding process is given to you below. The
code that you write should be in a file named q1.lisp. Do not include any other code in this file other
than any helper functions required by the heuristic.
The heuristic is described in terms of a segment score. A segment is a list of four adjacent positions on
the board which are on the same line (horizontal, vertical or diagonal). For a given segment and player,
the segment score is defined as follows:
• if the player has 4 pieces in the segment, then the segment score is 500 (as this is a victory);
• if the opposing player has a piece in the segment, then the segment score is zero;
• otherwise, the segment score is equal to 2𝑛, where 𝑛 is the number of pieces the turn player
has in that segment.
A board score is then defined by adding up the segment score for every possible segment on the board.
The connect-4.lisp file includes a parameter *all-c4-segments* which you can use to evaluate
this score.
The LISP code in connect-4.lisp defines a board as a list of columns. The correspondence between
LISP representation and board state is depicted below.
(defparameter *test-board*
‘((nil nil nil nil nil nil)
(O nil nil nil nil nil)
(X nil nil nil nil nil)
(X X O nil nil nil)
(O O X nil nil nil)
(nil nil nil nil nil nil)
(nil nil nil nil nil nil)))
O X
X O
O X X O
You are advised to define the segment-score function by following the steps below, but you are
permitted to define it in a different way if you prefer. Your submission must at least include a definition
of the segment-score, board-score and static functions.
The task
(a) Write code for the heuristic described above. Below, you are given a suggested approach to take.
This is just a suggestion, so you are permitted to take a different approach in your code, but the
heuristic must be the one described above. At minimum, your submission must include a definition
of these three functions:
segment-score board-score static
Your code must make appropriate use of higher order LISP functions and must not include any
looping constructs.
(b) Play some games against the algorithm, experimenting with how the parameter *max-depth* affects
the quality of the game play. Make sure that you include a *max-depth* value of 1 as one of your
cases. What is the smallest value of *max-depth* for which it is difficult to beat the algorithm?
Write a short paragraph summarising your findings, and include it as a commented section at the
top of your source code.
4
Suggested approach
The steps described here can be used to define the heuristic.
• Write a function get-element (board coords) that takes a board and a pair of
coordinates representing a board position as input. The first element of the pair represents the
column number and the second represents the row number (indexing starts from 0). Columns
are indexed from left-to-right and rows are indexed from bottom-to-top. The function returns
the contents of that board position, which can be either X, O or NIL. Using *test-board*
as defined above, the function should behave as follows:
[1]> (get-element *test-board* ‘(0 0))
NIL (column 0, row 0 contains NIL)
[2]> (get-element *test-board* ‘(1 0))
O (column 1, row 0 contains O)
[3]> (get-element *test-board* ‘(2 0))
X (column 2, row 0 contains X)
[4]> (get-element *test-board* ‘(4 2))
O (column 4, row 3 contains O)
• Write a function count-segment (board player segment) that takes a board, a
player, and a segment as input. The function returns a list of length 3, where the first element
of the list is the number of empty places in the segment, the second element is the number of
pieces that player has in the segment, and the third element is the number of pieces that the
player’s opponent has in the segment. You should find it useful to use get-element as a
helper function. Using the same test board state as defined above, the function should behave
as follows:
[5]> (count-segment *test-board* ‘X ‘((3 0) (3 1) (3 2) (3 3)))
(1 2 1) (segment contains 1 NIL, player has 2 pieces in segment, and opponent has 1)
[6]> (count-segment *test-board* ‘O ‘((3 0) (3 1) (3 2) (3 3)))
(1 1 2) (segment contains 1 NIL, player has 1 piece in segment, and opponent has 2)
You may wish to use the built in function count that takes and element and a list as arguments,
and returns the number of occurrences of the element in the list.
• Write a function segment-score (board player segment) that takes a board and
player as input, and returns the segment score for player, as defined above. You should use
count-segment as a helper function. Using the same test board state as defined above, the
function should behave as follows:
[9]> (segment-score *test-board* ‘X ‘((3 0) (3 1) (3 2) (3 3)))
0 (the opponent of X has a piece in this segment)
[10]> (segment-score *test-board* ‘O ‘((3 0) (3 1) (3 2) (3 3)))
0 (the opponent of O has a piece in this segment)
[11]> (segment-score *test-board* ‘X ‘((2 0) (3 1) (4 2) (5 3)))
8 (player has three pieces in the segment and opponent has none)
Note: the LISP function expt computes powers. For example, (expt 5 2) computes 52.
5
• Write a function board-score (board player), which takes a board and player as
input, and returns the board score for that player. To assist you, the code you have been supplied
with contains a parameter *all-c4- segments* which is a list of all the 69 possible segments
in Connect-4. You should use segment-score as a helper function.
• Finally, write the function static (board player), which accepts a board and player as input
arguments, and returns the board score of player, minus the board score for the opponent. This
is the function that will be used as the heuristic. You should use board-score as a helper
function.
Submit the following
• Electronic copy of a file q1.lisp. This file should contain definitions of the functions described
above, as well as any helper function required by these. Do not include any of the code from
minimax.lisp or connect-4.lisp in this file. Make sure that your name and student number appear
in the header documentation. Don’t forget to include a short summary of your findings as a
commented section at the top of your source code.
Marking criteria
Your code will be tested using the following test function
(defun q1test()
(load ‘minimax)
(load ‘connect-4)
(load ‘q1)
(play)
)
It is your responsibility to ensure that your code loads correctly, and that all required functions are
present.
Your solution will be marked according to the following criteria:
• Functioning code that operates as specified above
• Programming style
– Code displays good functional programming style with appropriate use of local variable
definitions, higher-order functions, etc.
6
– Appropriate documentation and indentation. Documentation should be concise, but clear.
Indentation should reflect the logical structure of the code.
7
Question 2 – LISP implementation of L-systems (15 marks)
Background – L-systems
Your task for this question will be to write LISP code to implement a string rewriting system called an
L-system. An L-system is a formal grammar consisting of an alphabet, an initial word, and a collection
of production rules. In more detail:
• The alphabet is a set of characters used to make the words.
• The initial word is the word the system starts with.
• The production rules define how characters are replaced. It is assumed that, if no rule for
replacing a character appears, then it is replaced with itself.
An example of an L-system is given below.
Alphabet: {A, B}
Initial word: A
Production rules: A → AB
B → A
New words are generated by iteratively applying all production rules simultaneously to the previous
word, starting from the initial word. Using the system above, for example:
Word 0 A (initial word)
Word 1 AB (using A → AB)
Word 2 ABA (using A → AB and B → A simultaneously)
Word 3 ABAAB (using A → AB and B → A simultaneously)
Word 4 ABAABABA (using A → AB and B → A simultaneously)
To illustrate the idea, this can also be represented in tree form.
8
Implementation details.
The LISP implementation for the L-system will use the following schematic:
• The alphabet will be represented by a list of characters.
o For example, the alphabet of the previous example will be written as ‘(A B)
• A word will be represented by a list of characters.
o The word A would be represented by the list ‘(A).
o The word ABAB would be represented by the list ‘(A B A B)
• Since the initial word is a word, it will be represented as a list of characters.
• A single rule will be represented by a list containing two elements.
o The first element is a single character, representing the character to be replaced.
o The second element is a list of characters, representing the word to replace it with.
o For example, the rule A → AB is represented as ‘(A (A B)).
o And the rule B → A is represented as ‘(B (A)).
• The set of rules will be represented by a list of rules
o The set of rules is thus a list of individual rules as described above. The set of rules for
the example on the previous page is represented by ‘((A (A B)) (B (A)).
You have been provided with the file l-system.lisp, which defines an l-system struct with 3 fields:
(defstruct l-system
(alphabet ‘(A B))
(initial-word ‘(A))
(rules ‘((A (A B)) (B (A))))
The default construction will result in the example on the previous page. It can be stored in a parameter
like so:
(defparameter *test-system* (make-l-system))
Other L-systems are defined by using the make-l-system function with the fields specified. For
example, an L-system used to generate a fractal curve called the dragon curve can be defined like so:
(defparameter *dragoncurve*
(make-l-system
:alphabet ‘(F G + -)
:initial-word ‘(F)
:rules ‘((F (F + G)) (G (G – F)))))
The accessor functions are defined automatically by LISP. For example, after defining the parameter
above, you can access the fields like so:
[1]> (l-system-alphabet *dragoncurve*)
(F G + -)
[2]> (l-system-initial-word *dragoncurve*)
(F)
[3]> (l-system-rules *dragoncurve*)
((F (F + G)) (G (G – F)))
If you are interested in seeing how L-systems can be used to generate images, you can explore this website:
http://paulbourke.net/fractals/lsys/. But you are not required to do that for this assignment.
http://paulbourke.net/fractals/lsys/
9
The task
Make sure you carefully read the details above before proceeding. The final goal of this section will
be to write a function named generate, which takes two arguments, l-system and n, and returns
the word generated by the l-system after n iterations. After completing the tasks below, an example
output would be
[1]> (generate *test-system* 6)
(A B A A B A B A A B A A B A B A A B A B A)
You are required to write the following functions, according to the specifications given, along with
any helper functions that are required. Load the file l-systems.lisp first to use the l-system struct.
• apply-rule-to-character (c rule)
The function apply-rule-to-character takes as input a single character and a single production
rule. If the rule does not apply to that character, it returns NIL. Otherwise, it returns the result of
applying that production rule to the character. Some example output is shown below.
[1]> (apply-rule-to-character ‘A ‘(A (A B)))
(A B)
[2]> (apply-rule-to-character ‘B ‘(A (A B)))
NIL
[3]> (apply-rule-to-character ‘B ‘(B (A)))
(A)
[4]> (apply-rule-to-character ‘C ‘(B (A)))
NIL
Specifications: there are no specific requirements for the apply-rule-to-character function.
You will be awarded full marks if your function completes the task successfully. Helper functions may
be used.
• apply-rules-to-character (c rules)
The function apply-rules-to-character takes as input a single character and a list of
production rules. It is assumed that at most one rule will apply to the input character. If an
applicable rule is in the list of rules, then the result of applying that rule is returned. Otherwise,
a list containing only c is returned. Some example output is shown below.
[5]> (defparameter *test-rules* ‘((A (A B)) (B (A))))
*TEST-RULES*
[6]> (apply-rules-to-character ‘A *test-rules*)
(A B)
[7]> (apply-rules-to-character ‘B *test-rules*)
(A)
[8]> (apply-rules-to-character ‘C *test-rules*)
(C)
Specifications: the function apply-rules-to-character must be defined recursively
and make use of the previous apply-rule-to-character function. If the function is not
defined recursively, then zero marks will be awarded for this part. Helper functions are ok.
• apply-rules-to-word (word rules)
The function apply-rules-to-word takes as input a word (represented by a list) and a
list of production rules. It returns the result of applying all production rules simultaneously to
each character in the word. Some example output is shown below.
10
[9]> (apply-rules-to-word ‘(A B A) *test-rules*)
(A B A A B)
[10]> (apply-rules-to-word ‘(A B C) *test-rules*)
(A B A C)
[11]> (apply-rules-to-word ‘(A C B C) *test-rules*)
(A B C A C)
Specifications: the function apply-rules-to-word must be defined recursively and
make use of the previous apply-rules-to-character function. If the function is not
defined recursively, then zero marks will be awarded for this part. Helper functions are ok.
• generate (l-system n)
The function generate takes as input an L-system structure and a non-negative integer n. It
returns the result of successively applying the rules of the L-system n times. Some example
output is shown below, using the L-systems defined in the file l-system.lisp.
[12]> (generate *test-system* 5)
(A B A A B A B A A B A A B)
[13]> (generate *dragoncurve* 2)
(F + G + G – F)
[14]> (generate *dragoncurve* 3)
(F + G + G – F + G – F – F + G)
Specifications: the function generate must be defined recursively. If the function is not
defined recursively, then zero marks will be awarded for this part. Helper functions are ok.
Testing your code
You could test your code as follows:
(defun q2test()
(load ‘l-system) ;supplied file
(load ‘q2) ;source code containing th functions you write
(generate *test-system* 5))
Your code will be marked based on other L-systems as well, so you should test your code thoroughly.
Submit the following
• Electronic copy of a file q2.lisp. This file should contain definitions of the functions described
above, as well as any helper functions you used. Make sure that your name and student number
appear in the header documentation.
Marking criteria
Your code will be tested using a script similar to the one above. It is your responsibility to ensure that
your code loads correctly, and that all required functions are present.
Your solution will be marked according to the following criteria:
• Functioning code that operates as specified above
• Programming style
– Code displays good functional programming style with appropriate use of local variable
definitions, higher-order functions, etc.
– Appropriate documentation and indentation. Documentation should be concise, but clear.
Indentation should reflect the logical structure of the code.
11
Question 3 – Resolution Refutation (15 marks)
Consider the following information:
Dolly is a lamb and Mary is Dolly’s master. A lamb is a baby sheep. On weekdays,
Mary will go to school if the temperature is warm. On cold days, Mary goes to the
library. Baby animals are obedient, and all obedient animals will be with their
master. On Friday it is cold.
(a) Represent the above information, as well as any relevant background information, in full
predicate form (i.e., you must show any existential or universal quantifiers). You must use only
the following predicates and constants:
sheep(X) X is a sheep
lamb(X) X is a lamb
baby(X) X is a baby
animal(X) X is an animal
obedient(X) X is obedient
weekday(X) X is a weekday
master(X,Y) X is the master of Y
weather(X,Y) The weather on day X is Y
e.g., weather(mon, cold)
location(X,Y,Z) The location of X on day Y is Z
mary Mary
dolly Dolly
cold cold (assumed to be a weather condition)
warm warm (assumed to be a weather condition)
mon Monday (a day)
tue Tuesday (a day)
wed Wednesday (a day)
thur Thursday (a day)
fri Friday (a day)
school school (a location)
library library (a location)
(b) Convert the predicate calculus expression you wrote in part (a) to clause form. This means
that each individual clause in the database must be a disjunction of literals, where a literal is
an atomic expression or the negation of an atomic expression.
(c) Using your database of clauses from part (b), manually use resolution refutation to extract the
answer to the question “Where is Dolly on Friday?”. Make sure that you show all steps, and
show clearly the substitutions required in order to answer the question.
Submit the following
• Electronic copy of a file q3.doc that contains your answers to parts (a), (b) and (c).
(Handwritten and scanned is OK, but make sure that it is easy to read). Make sure that your
name and student number appear in the header documentation.
Marking criteria
• Correctness and completeness of the expressions in part (a) and part (b).
• Correctness and completeness of the proof.
12
Question 4 – River crossing in Prolog (15 marks)
Consider the following river crossing problem, adopted from the video game Professor Layton and
the Last Specter for Nintendo DS:
A farmer is on the east side of a river with one wolf, two cats and three ducks. The wolf will
start a fight with any cats it shares a side with, unless the cats outnumber the wolf. Similarly,
any cats on the same side as a duck will start a fight, unless there are more ducks than cats.
But if the farmer is on the same side, he will prevent any fight before it starts.
The farmer’s boat can carry up to two animals at a time, in any combination. He is permitted
to cross the river with one or zero animals in his boat (unless doing so would cause a fight to
break out!) How can the farmer get all his animals to the other side without a fight?
For example, a fight will break out if there are two ducks and two cats on the east side of the river
whilst the farmer is on the west side, because the number of ducks must outnumber the number of cats
when the farmer is not there. Similarly, on each side of the river, the number of cats must outnumber
the number of wolves if the farmer is not there.
Your task is to write a Prolog program to solve this problem. You should model your code based on
the solution to the Farmer, Wolf, Goat and Cabbage problem from the Week 8 labs.
Represent the state of the program as a relationship state, so that state(W, C, D, F) represents
the state with W wolves, C cats and D ducks on the east, and the farmer is on side S. For example,
state(1,2,3,east) is the initial state. If the farmer moves both cats across the lake, then the
state is now represented as state(1,0,3,west).
You will need to create predicates for unsafe states and valid movements. To help you, here is an
English description for moving one wolf and one cat from the east to the west:
move(state(W1,C1,D1, east), state(W2,C2,D2,west)) is valid IF
W2 equals W1-1 AND W2 >= 0 AND
C2 equals C1-1 AND C2 >= 0 AND
D2 equals D1, AND
the animals remaining on the east do not start a fight.
Of course, this is not the only way that new states can be obtained. You will have to think of the
remaining ones yourself. You will also have to think carefully about how to describe the safe/unsafe
procedure.
Submit the following
• Electronic copy of a file q4.pl. This file should contain your Prolog code. Make sure that your
name and student number appear in the header documentation.
• Electronic copy of a file q4_run.txt, which contains a run of your program captured to a text
file (see instructions at end of this document for capturing a session using SWI-Prolog).
Marking criteria
Your submission will be marked according to the following criteria:
• Program design. Have you chosen suitable predicates? Are your procedures well-designed?
Have you included appropriate documentation?
• Program correctness. Does your solution load and run correctly? Does it find a valid solution?
13
Question 5 – An expert system rule base (15 marks)
Your task for this question is to develop a small rulebase that can be used in the CLIPS expert system
shell.
You may choose any appropriate domain for your system; however, it should be in an area in which
you have some expertise. Suitable domains may include:
• recommending a movie to watch (you might want to focus on a particular genre);
• recommending a suitable pet (e.g., you might want to focus on a specific breed of dog);
• real estate advisor;
• etc.
but there are hundreds of others. Hopefully you will develop something that is both useful and fun!
The system that you develop should be engineered to return a single result (e.g., which restaurant to
dine at, which movie to watch, etc). As a rough guide, there should be approximately 3 or 4 outcomes
(e.g., restaurants or movies to recommend) but this will depend on your particular domain.
Remember that the expert system approach is most appropriate when using ‘deep’ knowledge, and
inferencing involves several layers of intermediate-level hypotheses. While many real expert systems
can contain hundreds of rules, for the purpose of this exercise, approximately 15 to 20 rules (not
counting helper rules, whose purpose, for example, might be solely to obtain input) should be
sufficient. It is usually a good idea to use some rules which are more general (i.e., only one or two
conditions in the antecedent), and some which are more specific (e.g., three or more conditions in the
antecedent. Obviously, with such a small number of rules, the expert system will not work well in all
consultations. Try to engineer your system so that it performs well in a couple of particular cases (i.e.,
one or two particular restaurants; one or two particular movies).
Testing the system
Create at least three test scenarios, each corresponding to a different set of facts to be presented to the
system when prompted. The scenarios should be carefully selected to test your system and to
demonstrate the quality of its inferencing. Select two scenarios to demonstrate when your system
works well, and at least one scenario to show when your system works poorly (i.e., gives bad advice).
You will need to submit runs of these test scenarios, so you must capture the sessions to a text file.
Instructions on how to capture input into a text file in CLIPS, see the Appendix).
Submit the following
• Electronic copy of the file q5.clp that contains your CLIPS code. The documentation in the
header section should describe the problem domain that you have selected (e.g., pet
recommendation), with a justification for why you believe that an expert system approach is
appropriate for this problem (it should rely on intermediate hypotheses – see above). Make sure
that your name and student number appear in the header documentation.
• Electronic copy of the file q5_run.txt that contains a run of your CLIPS code, demonstrating
performance on three different scenarios. (See instructions at end of this document for
capturing a session using CLIPS). Make sure that your name and student number appear in the
header documentation.
14
Marking Criteria
• Appropriateness of problem to an expert system solution. Chosen domain should be sufficiently
complex to warrant an expert system approach – the problem should not be one that could be
solved trivially using a lookup table, or some other ‘conventional’ approach. Your mark for this
will be based on the justification you give in the documentation.
• Rule Base. Development of a rule base containing approx. 15 to 20 rules, as appropriate.
• Depth of complexity as measured by levels of intermediate hypotheses. Depending on the
nature of the problem, rules should use at least two or three levels of intermediate hypotheses.
• Test scenarios. Your test scenarios are well selected to demonstrate both good performance as
well as poor performance.
15
Appendix 1
Directions for capturing a session using CLISP
The function dribble can be used to capture a session with the CLISP interpreter to a text file. To
begin capture, call the function dribble with the double-quoted filename as an argument (if a file
with that filename does not exist, it will be created, otherwise the session will be appended to the end
of it). For example, the following command
[1]> (dribble “sample.txt”)
will cause the session to be captured to the file sample.txt. When you want to stop dribbling, call the
function dribble without any arguments.
[10]> (dribble)
Directions for capturing a session using SWI-Prolog
To capture a session using SWI-Prolog, use the commands protocol and noprotocol. For example,
to start capturing a session, give the command:
1 ?- protocol(‘sample.txt’).
where sample.txt is the name of the file to which you want to capture the interaction. To stop
capturing, give the command:
10 ?- noprotocol.
Directions for capturing a session using CLIPS
To capture a session using CLIPS, use the commands dribble-on and dribble-off. For
example, to start capturing a session, give the command:
CLIPS> (dribble-on “sample.txt”)
where dump.txt is the name of the file to which you want to dribble. To stop dribbling, give the
command:
CLIPS> (dribble-off)
CSE2AIF – Artificial Intelligence Fundamentals
2021 Individual Assignment 2
Due Friday 15 October 2021, 10:00am
Question 1 – A heuristic for Connect-4 (15 marks)
Question 2 – LISP implementation of L-systems (15 marks)
Background – L-systems
Implementation details.
If you are interested in seeing how L-systems can be used to generate images, you can explore this website: http://paulbourke.net/fractals/lsys/. But you are not required to do that for this assignment.
The task
Testing your code
Question 3 – Resolution Refutation (15 marks)
Question 4 – River crossing in Prolog (15 marks)
Question 5 – An expert system rule base (15 marks)
Appendix 1
Directions for capturing a session using CLISP
Directions for capturing a session using SWI-Prolog
Directions for capturing a session using CLIPS