CSE2AIF - Artificial Intelligence Fundamentals Assignment 2 Due Friday 7 October 2016, 10:00am This assignment is to be done individually, and contributes 20% of your final mark for this subject. The submission date is Friday 7th October 10:00am. 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. Question 1 – Heuristic for the Towers of Hanoi Problem (10 marks) In Assignment 1 you wrote Lisp code for the Towers of Hanoi Problem, and used breadth first search to solve the problem. You probably found that the largest problem size that you could solve using breadth first search (in a reasonable amount of time, such as a minute or so) was 7 (i.e., seven disks). For this question, you are to use A-star search to solve the same problem. In order to use the a-star search code which has been supplied in the file a-star.lisp, you will need to include the following two additional functions:  cost-of-applying-operator (state operator) This function should take a state and an operator as input parameters, and return the cost of applying the operator to that state. We will usually assume that all costs are equal, and hence this function should always return 1, irrespective of the state or the operator. Thus, (defun cost-of-applying-operator (state operator) 1)  estimated-distance-from-goal (state) This function takes a state as a parameter, and returns an estimate of the number of steps required to get from this state to the goal. Your task is to find a good heuristic and to code it in Lisp. Create a heuristic which will allow a-star search to solve the Towers of Hanoi problem on problem sizes larger than 7. Try to come up with most informed heuristic that you can think of. What is the largest problem size that it can solve in a reasonable amount of time (e.g., 60 seconds)? (Hint: the code for your heuristic will probably need to reference the global variable that stores the problem size; i.e., the number of disks). Evaluating the following function should result in all necessary files loading, and a solution being found: (defun test() (load 'towers.lisp) (load 'a-star.lisp) (reset-stats) (a-star *start-state* *operators*) *stats* )What to submit:  A printout of the file towers.lisp that contains code implementing the Towers of Hanoi problem, together with the functions cost-of-applying-operator and estimated-distance-fromgoal.  A printout of a table showing the performance of your program for different problem sizes up to the maximum size that it can solve in a reasonable amount of time. For each case, record the number of nodes visited, the maximum length of node list, the length of solution, and the maximum depth of search tree.  An electronic copy of your file towers.lisp. Marking criteria:  English-language description of the heuristic (commented above the Lisp implementation of the heuristic), with Lisp code that correctly implements the heuristic as described.  Quality of the heuristic Question 2 – Heuristic for the Connect-4 game (10 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) ;; Loading file C:\CSE2AIF\minimax.lisp ... ;; Loaded file C:\CSE2AIF\minimax.lisp T [3]> (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, whichevaluates 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) (load 'connect-4) (load 'static) (play) ) Experiments: Evaluate your heuristic by playing against it several times. Play at your best! But note that the performance of the computer will depend not only on the heuristic, but also on the depth (or 'ply'), of the tree that is created by the mimimax algorithm. This depth is controlled by the parameter *maxdepth*, which is defined in the file Connect-4.lisp. A depth of 1 will probably result in poor gameplay, irrespective of the quality of the heuristic. 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:  A printout of the file static.lisp that contains code implementing your heuristic for the Connect-4 game.  A printout 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. 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.  A printout of a short report (one or two hundred words or so) which summarises the findings from your experiments.  An electronic copy of your file static.lisp.Marking 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, 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 3 – Resolution Refutation (10 marks) Consider the following information: "Flip is a trained poodle and James is Flip's master. Dogs that are trained are obedient, and obedient dogs are always with their master. On warm days, James always goes to the park. On cold weekdays James always goes to the Club. It is Tuesday and 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 universal quantifiers). You must use ONLY the following predicates and constants: poodle(X) X is a poodle trained(X) X is trained master(X,Y) The master of X is Y location(X,Y,Z) The location of X on day Y is Z conditions(X,Y) The weather conditions on day X is Y e.g., conditions(mon, cold) dog(X) X is a dog obedient(X) X is obedient weekday(X) X is a weekday james James flip Flip cold cold warm warm monday Monday tuesday Tuesday wednesday Wednesday thursday Thursday friday Friday park park club club (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 Flip?". Make sure that you show all steps, and show clearly the substitutions required in order to answer the questionWhat to submit: A printout containing your answers to parts (a), (b) and (c). (Hand-written submission is acceptable, but make sure that it is legible). Marking criteria:  Completeness and correctness of the expressions in part (a) and part (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.  Completeness and completeness of the proof in part (c). Question 4 – Solving the Beakers problem using Prolog (10 marks) You are to write a Prolog program to solve the following problem: A merchant has a beaker containing 24 ounces of a precious fluid. He also has empty 5- ounce, 11-ounce, and 13-ounce beakers. How can he divide the fluid into three equal portions? 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. (It does not need to output the actual operators – but you are welcome to also include this in the program output if you so desire.) What to submit:  A printout of the file beakers.pl that contains Prolog code implementing your solution to the Beakers problem.  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).  An electronic copy of your file beakers.pl. Marking criteria:  Prolog code that leads to a correct solution being found.  Programming style including documentation and layout of code.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.