prolog代写 CSE2AIF – Artificial Intelligence Fundamentals 2018 Individual Assignment 2

CSE2AIF – Artificial Intelligence Fundamentals 2018 Individual Assignment 2

Due Monday 15 October 2018, 10:00am

This assignment is to be done individually, and contributes 20% of your final mark for this subject. The submission date is Monday 15th October 10:00am. There are four questions, each worth 15 marks. You should attempt all questions.

Submission is both hard copy 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. 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.

Question 1 – A heuristic for the Connect-4 game (15 marks)

Connect-4 is a two-player game 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 connect-4.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.lisp”)
       ;; Loading file C:\CSE2AIF\minimax.lisp ...
       ;; Loaded file C:\CSE2AIF\minimax.lisp
       T
       [3]> (load “connect-4.lisp”)
       ;; 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; 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).

HINT: Before starting this question, study the code in the file tic-tac-toe.lisp, which we used in Week 5 labs. The static function and its helpers are a good example of the use of higher-order functions, and you will probably be able to structure your heuristic for the connect-4 game in a similar style.

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

       (defun test()
          (load “minimax.lisp”)
          (load “connect-4.lisp”)
          (load “Q1.lisp”)
          (play)

)

Experiments:

; Q1.lisp contains the function static

Evaluate your heuristic by playing against it several times, but note that the performance of the heuristic is also going to depend heavily on the depth of the search tree. As you would have seen in Week 5 labs, the depth of the search tree is determined by the value of the parameter *max-depth*. While a particular heuristic may work well using a depth of, say, 4, the same heuristic may not work so well when using a depth of only 3. Test your heuristic using depths of 2, 3 and 4. You should play a number of games for each case. Make sure that you play at your best! What is the smallest depth which results in the computer playing competitively against you? i.e., being able to bring the game to a draw, or even to win. Write a short report summarising your findings.

What to submit:

•   Hard copy and electronic copy of the file Q1.lisp that contains the code for your heuristic (as well as any helper functions) for the Connect-4 game. The file must be commented with a clear, English language description of how your 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, so make sure that you play at your (human) best. Have the value of *max-depth* set to the smallest value which results in competitive gameplay, and make sure that you state the depth on the printout.

  Marking criteria:

•   Clear English-language description of the heuristic
•   LISP 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, etc.
  – Appropriate documentation and indentation. Documentation should be brief, but clear.

  Indentation should reflect the logical structure of the code.

•   Quality of the heuristic

  Question 2 – Logic and Theorem-proving (15 marks) Consider the following problem:

  Children do not go to school when they are unwell. Whenever children are not at school they are with their mother. Dennis is a 10-year-old child, and Julie is Dennis’s mother. On sunny weekdays Julie goes to the park; otherwise she stays at home. It is Monday, Dennis is unwell, and it is rainy.

(a) Represent the above information, as well as any relevant background information (e.g., that if it is rainy, then it is not sunny), in full predicate calculus form (i.e., you must show any existential and universal quantifiers) using ONLY the following predicates and constants. Make sure that you follow the rules carefully (e.g., variables must begin with an uppercase character, constants must begin with a lowercase character).

Predicates:

      child(X)
      location(X,Y,Z)
      mother(X,Y)
      rainy(X)
      sunny(X)
      weekday(X)
      well(X,Y)

Constants:

      dennis
      home
      julie
      monday
      park
      school

X is a child
The location of X on day Y is Z The mother of X is Y
X is a rainy day
X is a sunny day
X is a weekday
X is well on day Y

Dennis home Julie Monday park school

2. (b)  Convert the predicate calculus expressions 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. For example, the following sentence (although unrelated to this question) is in clause form:

   pass(X, history)  win(X, lottery)  happy(X)

3. (c)  Using your database of clauses from part (b), manually use resolution refutation to extract the answer to the question “Where is Dennis on Monday?”. You may show the derivation in either sequence or tree form. Make sure that you show all steps, and show clearly the substitutions required at each step.

What to submit:

 Hard copy of your answers to (a), (b) and (c). (hand-written is acceptable, but make sure that it is legible).

Marking criteria:

•   Completeness and correctness of the expressions in (a) and (b). Make sure that you follow all of the rules; e.g., predicates and constants must begin with lowercase, variables must begin with uppercase, variables bound by different quantifiers must have unique names, etc.
•   Correctness and completeness of the proof in (c).
  Question 3 – Using Prolog to Solve a River-Crossing Problem (15 marks)

  Like the Farmer, Goat, Wolf and Cabbage problem, the Missionaries and Cannibals problem is another classic river-crossing problem. One version of the problem goes as follows:

  Three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (since the cannibals would eat the missionaries). The boat cannot cross the river by itself with no people on board. The three missionaries, three cannibals and the boat are initially all on the north bank of the river. How can all missionaries and cannibals get to the south bank alive?

  Write a Prolog Program to solve the solve the Missionaries and Cannibals problem. You are strongly advised to model your code based on the solution to the Farmer, Wolf, Goat and Cabbage problem that you studied in Week 8 Labs.

  What to submit:

  •   Hard copy and electronic copy of a file Q3.pl, that contains your Prolog code.
  •   Hard copy of a run of your program. (See instructions at end of this document for capturing a

    session using SWI-Prolog).

    Marking Criteria

•   Prolog code that leads to a correct solution being found.
•   Programming style including choice and design of predicates, documentation, and code layout.

  Question 4 – 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. 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:

  •   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! If you are uncertain about the suitability of a particular domain, please check with me.

    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 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 pets).

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).

What to submit:

•   Hard copy and electronic copy of the file Q4.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).
•   Hard copy of your report, which contains a capture of the consultation for three test scenarios, annotated to show in which cases your system works well, and in which case it works poorly. (See instructions at end of this document for capturing a session using CLIPS).

  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.
•   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. Scenarios are well selected to demonstrate both good performance, as well as poor

  performance.

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)