CS计算机代考程序代写 prolog database algorithm interpreter IT470: Artificial and Computational Intelligence

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