;;;; Assignment 3 ;;;; ;;;; File: asst3.txt ;;;; Author: CS 51 (Bob Walton) ;;;; Version: 1 In this assignment you are to write a game search engine, which will be applied to play TICTACTOE, and a goal search CHILDREN function, which will be applied to logic programming. Although both these functions are not long, they are somewhat complex, so this assignment counts 50% more than most other assignments. In part I of the assignment you write the game search engine as the function FIND-VALUE-AND-MOVES in the file game-search.lsp. This function is tested by making tictactoe.out. In part II of the assignment you implement logic programming using SLD-resolution by writing the CHILDREN function of logic-programming.in. This function is tested by making logic-programming.out. You are also asked to add substitution printing to the GOAL function in logic-programming.in. The two parts of the assignment are in fact independent, and can be done separately, in either order, or in parallel. Of course each part has a theory subpart. Part I: A game search engine is to be programmed in game- search.lsp in somewhat the same manner as search engines were programmed in search.lsp. The function that needs to be implemented is FIND-VALUE-AND-MOVES, which performs game search given an implementation of the STATE abstraction defined in game-search.lsp. The first design step has already been done for you: it has been decided to loop through moves by using a helper function, FIND-VALUE-AND-MOVES-RECURSE, with arguments as given in game-search.lsp. The specific things you must do are: (0) Read Section 3.2 of Introduction to Symbolic Computing. (1) For the theory subpart of Part I, do the following exercises from Section 3.2 of the above reading: 3.2.9.1 (Aa, Ba, Ca, Da) Remember to staple the theory subparts of both Part I and Part II of this assignment together but keep separate from any code as the theory is to be graded separately from the code. (2) Study the files game-search.lsp and tictactoe.in carefully. Study the game search algorithm WITHOUT alpha beta pruning, and figure out what FIND-VALUE- AND-MOVES and FIND-VALUE-AND-MOVES-RECURSE are supposed to do if they were to ignore their WORST and BEST arguments and not do ANY alpha-beta pruning. (3) Write the rewrite rules for FIND-VALUE-AND-MOVES and FIND-VALUE-AND-MOVES-RECURSE without alpha-beta pruning. Some things to remember are: (a) FIND-VALUE-AND-MOVES should call STATE-VALUE to get a direct value, and return that value if it is not NIL. (b) FIND-VALUE-AND-MOVES should call FIND-VALUE- AND-MOVES-RECURSE if there is no direct value. STATE-LEGAL-MOVES should be used to get the list of legal moves, which cannot be empty since there is no direct value. (c) If FIND-VALUE-AND-MOVES-RECURSE is given an empty MOVES list, it is done and merely needs to return the RESULT. (d) Otherwise the move (CAR MOVES) must be tried. After making this move to get to a new state, call FIND-VALUE-AND-MOVES for this new state with the WORSE and BETTER arguments reversed, and the WORST and BEST arguments also reversed (for use later when we add alpha-beta pruning). (e) After finding a value for a new state, FIND- VALUE-AND-MOVES-RECURSE calls itself recursive- ly and passes (CDR MOVES) and the best result from between the new result and the old RESULT. (f) The calls to INCREMENT-VISITS and RETURN-VALUE- AND-MOVES need NOT be included in the rewrite rules, as these are `program instrumentation', and not part of the algorithm. (4) Write the code for FIND-VALUE-AND-MOVES and FIND- VALUE-AND-MOVES-RECURSE. You are NOT permitted to use SETF or DO in this code. You MUST use PURE LISP and recursion. If you do this you will find this function is not long. You MUST indent your code in a proper readable fashion. Learn to use == and =% in vi. INCREMENT-VISITS should be called at the beginning of FIND-VALUE-AND-MOVES, and RETURN-VALUE-AND-MOVES should be called to return a value form FIND-VALUE- AND-MOVES. (5) Test the code by running: make tictactoe.out and looking at the results. You may add tests but are not required to. If you add tests, use only tests in which 4 initial moves have already been made until after alpha-beta pruning works (see below). (6) Now add alpha beta pruning by making use of the WORST and BEST arguments. Save you code with `make ci' before starting alpha- beta pruning, in case you mess up. (a) If a new result obtained by making a move is not worse than BEST, then FIND-VALUE-AND-MOVES- RECURSE is done and can return the new result as its final result. (b) If a new result is better than WORST, then the value of the new result can replace WORST when FIND-VALUE-AND-MOVES-RECURSE calls itself to process the next move. Add the alpha beta pruning to the rewrite rules and code, and then retest. You should now be able to uncomment the last test in tictactoe.in: see that file. The theory of Part I is worth 5 points, the rewrite rules of Part I are worth 5 points and the code is worth 35 points. Well written versions of FIND- VALUE-AND-MOVES and FIND-VALUE-AND-MOVES-RECURSE have 5 and 18 SLOCS respectively. Hints: (1) Read your functions and rewrite rules over frequent- ly and try to satisfy yourself that they do the cor- rect thing in each of the situations they can be in. (2) Remember that conditions in rewrite rules can evaluate expressions. For example: (find-value-and-moves 'state #'worse #'better worst best) ===> (state-value 'state) if (state-value 'state) is not nil (3) The rewrite rules for FIND-VALUE-AND-MOVES-RECURSE are rather messy, and therefore we have given you some help, including rewrite rules for two ficti- tious functions, BEST-VALUE-OF and BEST-RESULT-OF. These last are not intended to be real functions: they each are called once in the rewrite rules; so in the code their calls can be replaced by COND statements. We have also introduced two new meta- variables in the rules, NEW-VALUE and NEW-MOVES, which can be computed by a LET* statement in the code. (4) The alpha-beta pruning is very little code but is conceptually hard. You may want to do part II in parallel with doing alpha-beta pruning. Part II: SLD-resolution logic programming search is to be programmed in logic-programming.in in a manner analogous to the way picnic search was programmed in picnic.in. The major missing code is for the CHILDREN function, which requires finding all definite clauses in the database that match the first predicate of the query in the current state. The specific things you must do are: (0) Read Sections 3.1 and 3.4 of Introduction to Symbolic Computing. (1) For the theory subpart of Part II, do the following exercises from Sections 3.1 and 3.4 of the above reading: 3.1.7.2(a) 3.4.1(f) 3.4.2.1(f) 3.4.3.1(d) 3.4.3.2(b) Remember to staple the theory subparts of both Part I and Part II of this assignment together but keep separate from any code as the theory is to be graded separately from the code. (2) Write the rewrite rules for the CHILDREN function. Much of this has been done for you, as these rules are difficult to write. Rules are given for deriving a number of intermediate values that are needed for the results. These can be computed by a LET* statement in the code. (3) Write the code for CHILDREN. You are NOT permitted to use SETF or DO in this code. You MUST use PURE LISP and recursion. If you do this you will find CHILDREN is not a long function. You MUST indent your code in a proper readable fashion. Learn to use == and =% in vi. (4) Test the code by running: make logic-programming.out (5) Next you are to add code to print the substitutions for goal states to the GOAL function. For each symbol variable name V in the substitution list of the goal state, apply SUBIN to 'V and the substitution to get what the variable is replaced by, and print 'V +--> result-of-SUBIN You are NOT permitted to use DO in this code. You MUST use PURE LISP and recursion. You may write a helper function or use MAPCAR. (6) Retest the code by running: make logic-programming.out and looking at the results. (7) The natural language parsing example at the end of logic-programming.in is great fun, and you will probably want to add tests at the end of logic-programming.in. The theory of Part II is worth 15 points, the rewrite rules of Part II are worth 5 points and the code is worth 25 points. Well written versions of CHILDREN and the substitution printing in GOALS have 9 and 13 SLOCS respectively. Hints: (1) Master the use of LET*. (2) Be careful of the size of your output file. The unix command `wc logic-programming.out' will give a number of counts, the smallest of which is the number of lines. Assume around 50 lines per page. Up to 1000 lines is acceptable for this assignment. Good Luck!