I WANT EXCELLENT Homework help

CSE2AIF - Artificial Intelligence Fundamentals

2015 Individual Assignment 2

Due Friday 9 October 2015, 10:00am

General Information

This assignment is to be done individually, and contributes 20% of your final mark for this subject. The

submission date for the assignment is Friday 9th October 10:00am. Submission is both hardcopy AND

electronic. Details of what to submit are provided below. Make sure that you follow the directions carefully

and that the files are named exactly as specified in the instructions.

The assignment is to be done individually. This means that any code that you write must be your own. You

must not collude with other students in any way, and you must not outsource your work to any third party.

For information on plagiarism, see the La Trobe University policy on academic misconduct at

http://www.latrobe.edu.au/students/learning/academic-integrity. Plagiarism is treated very seriously.

Penalties will be applied and are strictly imposed.

Late Submission Policy

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.

Extension Policy

In order to apply for an extension of time to submit your assessment task, you must:

1. Complete the light brown sections of the ‘Request for an Extension of Time to Submit an Assessment Task” form, which will be available from the subject’s LMS website

2. Submit the completed form to the Subject Coordinator with relevant supporting information (e.g. medical certificate) either by email or in hard copy

3. The submission must be made three days or more before the original due date for the assessment task. If it is less than three days before the due date, or after the due date, you should use the Special

Consideration process. You have up to three days after the due date to apply for special consideration. You

are not automatically granted an extension of time if you submit the form. The Subject Coordinator will

return this form to you (as a scan via email) with approval or rejection of your request clearly indicated. If

you are granted an extension of time, you should submit a copy of the approved form (showing the approval

and the new submission date) with your completed assessment task. The University’s Late Submission

penalties apply from the original submission date if your request for an extension is rejected, and from the

new submission date (provided on the approved form) if your request is accepted. Applications for extension

made because of poor time management are generally not accepted. You may wish to refer to the Late

Submission of Assessment Tasks Policy and Procedures for more information.

Note: The ‘Request for an Extension of Time to Submit an Assessment Task” form should only be used to

request extensions of time for assessment tasks that will form 15% or more of your total assessment for the

subject. Smaller assessment tasks are not covered by the University’s Late Submission of Assessment Tasks

Policy and Procedures.

Question 1 – Game Playing (10 marks)

The game Connect-4 is played on a board that has seven columns. There are six spaces on each column. The

board is initially empty. Two players take turns dropping one piece (black or grey 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 move

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 (horizontally, vertically, or diagonally) is the winner.

You have been provided with two files for this problem: minimax.lisp, which contains lisp code for the

minimax algorithm, and fourinarow.lisp, which contains a working LISP implementation of the Connect-4

game.

As the Connect-4 implementation currently stands, you should have absolutely no problem beating the

program. Try it:

[1]> (load 'minimax)

;; Loading file C:\CSE2AIF\minimax.lisp ...

;; Loaded file C:\CSE2AIF\minimax.lisp

T

[3]> (load fourinarow)

;; Loading file C:\CSE2AIF\fourinarow.lisp ...

;; Loaded file C:\CSE2AIF\fourinarow.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; i.e., 0.

Your task for this question is to develop and implement a good heuristic for the Connect-4 game.

The only LISP code that you are required to write is a LISP function static, which accepts a board and

player as input arguments, and returns an evaluation of the board state from the point of view of player.

You can, of course, write as many helper functions as you like.

To assist you, the code you have been supplied with contains a parameter *all-c4-lines* which is a list

of all of the 69 possible ways to win in Connect-4. Each element of this list is a list of length four, such as

((1 0) (2 1) (3 2) (4 3))

Each element of this list is a sublist in which the first number represents column position and the second

number represents row position. For example, the list above indicates that there is a line of length four that

includes a piece at the 1st row of the 2nd column, the 2nd row of the 3rd column, the 3rd row of the 4th column,

and the 4th row of the 5th column. (Row and Column indexing starts at 0).

Marking Criteria

Your solution will be marked according to the following criteria:

 English-language description of the heuristic, with code that correctly implements the heuristic as described

 Programming style - Code displays good functional programming style with appropriate use of local variable

definitions, higher-order functions if appropriate, etc.

- Appropriate documentation and indentation. Documentation should be brief, but clear. Indentation should reflect the logical structure of the code.

 Quality of the heuristic

Evaluating the following function should result in all necessary files loading, and the game play

commencing:

(defun test()

(load 'minimax)

(load 'fourinarow)

(load 'static)

(play)

)

It is your responsibility to ensure that your code loads correctly, and that all required functions are present.

Submit the following

 Hard copy and soft copy of the file Q1.lisp, which contains only the function static and any

helper functions required by static. The file must also contain a commented section at the top of

the file that explains in clear English how the heuristic operates.

 Hard copy of a run of your program playing against you, captured using dribble. The purpose of

this is to demonstrate how well your heuristic operates. Make sure that you play your best. Set the

value of *max-depth* to 4.

Question 2 – Resolution Refutation (10 marks)

Consider the following knowledge:

Fred, Barney and Ralph belong to the La Trobe Mountain Club. Every member of the Club is either

a skier or a hiker. Anyone that doesn’t like snow does not like skiing. No hikers like rain. Ralph

dislikes whatever Fred likes, and likes whatever Fred dislikes. Fred likes rain and snow.

(a) Choose a suitable set of predicates, functions and constant symbols for representing the above knowledge in Predicate Calculus, and provide a glossary where you indicate their intended meaning.

(b) Using only the predicates, functions and constant symbols you have described above, write sentences in first-order logic that represent this knowledge.

(c) Convert the sentences into clausal form and give the resulting set of clauses.

(d) Use resolution refutation to find the member of the Mountain Club who is a hiker but not a skier. Show the complete resolution derivation (in sequence or tree form), clearly indicating which clauses are

resolved, and under which substitutions.

Marking Criteria

Your solution will be marked according to the following criteria:

 Appropriateness of predicates, functions and constants.

 Correctness of predicate calculus expressions and their conversion to clausal form.

 Correctness of solution.

Submit the following

 Hard copy and soft copy of the file Q2.doc, which contains your solution to the problem.

Question 3 – A Prolog Program to Solve the Water Jugs Problem (10 marks)

Write a Prolog program to solve the water jugs problem:

There are two jugs, one holding 3 and the other 5 litres of water. A number of things can be

done with the jugs: they can be filled, emptied, and dumped one into the other either until

the poured-into jug is full or until the poured-out-of jug is empty. Devise a sequence of

actions that will produce 4 litres of water in the larger jug. (Hint: use only integers.)

You are advised to base your code on the Prolog code for the farmer, wolf, goat and cabbage

problem that you used in Week 8 labs. The program should output the sequence of states on the

path to the goal. (i.e., it does not need to output the operators – but you are welcome to also include

this in the program output if you so desire.)

Marking Criteria

Your solution will be marked according to the following criteria:

 Prolog code that leads to a correct solution being found.

 Programming style

Submit the following

 Electronic copy your Prolog file named Q3.pl.

 Hard copy that contains - a printout of your Prolog code. - a printout of a run of your program captured to a text file (see instructions at end of this

document for capturing a session using SWI-Prolog).

Question 4 – An expert system in CLIPS (20 marks)

Your task for this question is to develop a small rule base that can be used in the CLIPS expert system shell.

Choosing a domain

You may choose any appropriate domain for your system; however, it should be in an area that you have

some expertise. Remember that the success of Expert Systems comes from focussing on very restricted

narrow domains and problems, and not trying to deal with “common sense” issues. Suitable domains may

include:

 selecting a video from a video rental store (you might want to focus on a particular genre);

 selecting a suitable pet (you might want to focus on a specific breed of dog);

 choosing a restaurant to dine at ;

 selecting a suitable subject to take next semester;

 real estate advisor;

 share market advisor;

but there are thousands of others. Hopefully you will develop something that is both useful and fun! If you

are uncertain about the suitability of a particular domain, please check with your lab demonstrator.

Designing and Developing the system

The system that you develop should be engineered to return a single result (e.g., which restaurant to dine at,

which pet to purchase). As a rough guide, there should be approximately 5 to 10 outcomes (e.g., restaurants

or pets to choose from, etc.), but this will depend on the particular domain that you are creating the expert

system for.

Remember, the expert system approach is usually most appropriate when using ‘deep’ knowledge, and

inferencing involves several layers of intermediate-level hypotheses. While many real expert systems can

contain hundreds or even thousands of rules, as a rough guide your system should have about 20 to 30 rules.

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 some particular cases. That is, it should ask questions in a

sensible order (like a human expert), and should give correct advice (like a human expert).

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. In particular, select scenarios to demonstrate when your system works well, as

well as scenarios 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).

Report

You must write a brief report (approximately 300-500 words) that describes the application domain of your

expert system, and why you believe that an expert system approach is suitable for this domain (Refer to the

levels of intermediate hypotheses that are required). The report should also contain a critical evaluation of

the system that you have developed. It should describe in which situations your system works well, and in

which situations it works poorly. You should refer to the test scenarios in your report (you may wish to

annotate the printouts showing captures of your consultations sessions for the three scenarios). Make any

other comments/observations which you feel are pertinent.

Marking Criteria

Your solution will be marked according to the following 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. There should be a genuine

attempt to create a system that behaves like an expert.

 Rule Base. Development a of rule base containing approx. 20 to 30 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 and report. Scenarios are well selected to demonstrate both good performance, as well as

poor performance. Report covers all points described above.

Submit the following

 Electronic copy your CLIPS file named named Q4.clp.

 Hard copy that contains - a printout of your CLIPS code. - a printout of a capture of the consultations for each of the three test scenarios (see instructions at

end of this document for capturing a session using CLIPS).

- your report

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)