CMSC 421 Programming Assignment 1 Fall 2006Due Date: Thursday, September 28, 10PMFor this programming, you will write a program to play the game Rushhour. We’ve provided somecode infrastructure in Lisp and test files. Please start early. While not a large amount of code isrequired for the final solution, you will need time for running and debugging, so plan accordingly!Note: Code available from http://www.cs.umd.edu/class/fall2006/cmsc421/projects/pa1.tar.RushHourIn this game, your goal is to drive a designated vehicle (represented by the letter R) out of the trafficjam and escape to freedom. To do so, you must maneuver all the blocking cars and trucks out ofyour way.You can gain some intuition on how to solve this problem by playing web-based version of the gameat:http://www.puzzles.com/products/RushHour/RHfromMarkRiedel/Jam.htmlhttp://gamerival.grab.com/index.cfm?game=6389B19FNote that the first url works properly using Internet Explorer, but not Firefox.A 6x6 grid describes the traffic world. All vehicles occupy either 2 or 3 grid squares. A vehicle canonly move along its axis of orientation (i.e. horizontal vehicles can only move left and right, ve rticlevehicles can only move up and down). The idea is to have the R car reach the state where it canexit the grid.Example: Take a look at the test file test2. In this puzzle, there is one other vehicle in addition toyour vehicle R. (Spaces marked NIL are empty.) In order to solve the puzzle, v1 needs to be moveddown one step, and then R needs to be moved to the right one step. When R reaches the end of therow, the goal has been achieved.Note: The red vehicle always starts somewhere in the 3rd row (i.e. x=2 in a 0-based array), andmust move off the board to the right. Also, assume the car can only move one space at a time toany direction.Vehicles (other than your red car) must stay on the board.AlgorithmYou will use depth-first (dfs), breadth-first search (bfs) and A* to solve the RushHour game. Yourfunction should find a solution if one exist.Code InfrastructureCopy the code, rush-hour-basics.lisp, to your directory. R ead the documentation in the file thor-oughly. A couple of notes on the code:1. Class - game: This class is used to define the game. It has four members: name, board,parent (i.e., parent game) and depth (depth in search tree). Each of these members can beaccessed through their accessor member. For example, we can access the board for a game gby (game-board g).2. Macros: The x-coord and y-coord functions are implemented using Lisp’s macro capability.This is an efficient way to do in-place expansion, giving a shorthand representation for fre-quently used code fragments without the overhead of a function c all. If you decide to usemacros in your own code, be sure you read up on them first.3. Logging messages: If you use the format function with a second argument of *DEBUG*,the message will be written to the global variable *DEBUG*. By default, this global variableProgramming Assignment 1: CMSC 421, Introduction to Artificial Intelligence: Fall 2006 2is bound to T, w hich sends messages to standard output (i.e., the screen). You can sendthis output to a file by using open-debug with the name of the file. When you close thelogging/debugging file with close-debug, it will revert to sending messages to standard output.4. Arrays: We’ve used an array to represent the game board. The main functions you need toknow for manipulating arrays are make-array, array-dimensions, and aref, which derefer-ences an array location.5. I/O: We’ve written the load-game function, so for this assignment, you won’t need to do muchof your own I/O.6. TIP: Because Lisp is an interpreted language, it’s very easy to test code fragments. Westrongly recommend tes ting every function independently before moving on to the next one.The file test0 is the simplest possible case, so you may want to use this for your initial debug-ging.7. Debugging: Use trace, format and step functions.The test cases are test1, test2, test3 and test4. Extra credit would be given if it works for test4.test0 is in the goal state.Implementation1. [50 points] BFS and DFSImplement a generic uninformed search function, along the lines of Russell & Norvig, Figure3.9 (page 72). Write wrapper functions that invoke this generic search function to p erformbreadth-first and depth-first search in the Rush Hour search space. Make sure the code is welldocumented.2. [50 points] A*Implement a heuristic function. Your heuristic is not required to be admissable. ImplementA*, which uses the heuristic function to guide the search.3. [25 points] Results and DiscussionRun your code on the tes t cases test1, test2, and test3 and generate the path to the goal stateusing the function, print-path-recursive. Find the number of nodes created and expanded, andalso the length of solution. Submit one output file for each test case, containing the aboveinformation, for each of the three algorithms.Include a short writeup (2 pages max), describing the heuristic you used, whether it is admiss-able or not and your results with the three different s earch algorithms.4. [45 points] Bonus(a) [15 points] Extra credit if you try more than one heuristic and compare results in yourwriteup.(b) [15 points] Extra credit if you also try greedy best-first se arch.(c) [15 points] Extra credit if you include results for test4.DeliverablesThe deliverables of this project is a single tar file, your-glue-id.tar, must contain the following files.1. The source code in rush-hour-basics.lisp. The code must run using ’alisp’ in the Grace serversand the following functions must be defined:Programming Assignment 1: CMSC 421, Introduction to Artificial Intelligence: Fall 2006 3(a) (BFS ”filename”) - Takes as input a filename, i.e.: (BFS ”test1”), and prints out thesolution using print-search-info.(b) (DFS ”filename”) - Takes as input a filename, i.e.: (DFS ”test1”), and prints out thesolution using print-search-info.(c) (A* ”filename”) - Takes as input a filename, i.e.: (A* ”test1”), and prints out the solutionusing print-search-info.2. Output files (test1.bfs, ..., test3.bfs, test1.dfs, ..., test3.dfs, test1.a*, ..., test3.a*, ) after applyingbfs, dfs and A* for each of the three test cases (test4 is b onus).3. A RE ADME file containing the names of the people in your group and their glue ids, as wellas any additional notes you want us to know. If you have any part of the project incompleteor