# LISP Assignment Help, Homework Help (Artificial Inteligence)

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 ea
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.
T
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.

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.

(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 a 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

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.

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 the 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()
(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.
9
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.
You could test your code as follows:
(defun q2test()
(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
Marking criteria
Your code will be tested using a script similar to the one above. It is your responsibility to ensure that
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.

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?

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);
• 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